투르마이트

Turmite
테르마이트와혼동해서는 안 된다.
사각 격자 위에 2주 2색 투르미이트.빈 격자에서 시작하여 8342계단 걸은 후에 터마이트(빨간색 픽셀)는 혼란스러운 움직임 단계와 규칙적인 움직임 단계를 모두 보여 주었다.

컴퓨터 과학에서 터마이트는 현재 상태 외에 방향성을 갖는 튜링 기계와 무한한 2차원 세포 격자로 구성된 '테이프'를 말한다.개미와 밴트라는 용어도 사용된다.랭턴의 개미는 사각 격자의 세포에 정의된 잘 알려진 유형의 터미티다.패터슨의 지렁이는 등축 격자 가장자리에 정의된 터미트의 일종이다.

일반적으로 터미테는 무한테이프가 있는 1차원 튜링 기계와 정확히 동등한 힘을 가진 것으로 나타났는데, 어느 한쪽이 다른 한쪽을 시뮬레이션할 수 있다.

역사

랭턴의 개미들은 1986년에 발명되었고 "튜링 기계와 동등하다"[1]고 선언했다.독자적으로, 1988년 앨런 H. 브래디는 방향성을 가진 2차원 튜링 기계에 대한 아이디어를 고려했고 그들을 "터닝 머신"[2][3]이라고 불렀다.

분명히 이 두 가지와는 별개로,[4] 그렉 터크는 같은 종류의 시스템을 조사하여 A. K. 듀드니에게 그들에 대해 편지를 썼다.A. K. 듀드니는 1989년 사이언티픽 아메리칸에 있는 그의 "컴퓨터 레크리에이션" 칼럼에서 그들을 "터미이트"라고 명명했다.[5]루디 러커는 그 이야기를 다음과 같이 이야기한다.

듀드니는 투르크의 생명체들의 이름을 부르며, "그것들은 투르크에 의해 연구된 튜링 기계들이기 때문에, 그들은 터어머신이 되어야 한다고 생각했다.그리고 그것들은 작은 곤충이나 진드기 같으니까, 나는 그들을 터어미이트라고 부를 거야!그리고 저건 흰개미 소리 같아!"투르크와 드웨드니의 친절한 허락을 받아 하이픈은 빼놓고 터미티라고 부르겠다.

— Rudy Rucker, Artificial Life Lab[4]

상대적 대 절대적 터미티

터미테는 상대적이거나 절대적이라고 분류할 수 있다."터닝 머신"으로 알려진 상대적 터미티는 내부 방향을 가지고 있다.랭튼의 개미가 그런 예다.상대 투르미트는 정의상 등방성이므로, 투르미트를 회전시키는 것은 결과에 영향을 미치지 않는다.상대 터미테는 "왼쪽" 또는 "뒤로"라는 단어를 사용하는 것과 동등한 방향의 현재 방향과 비교하여 방향이 인코딩되어 있기 때문에 그렇게 이름이 붙여진다.그에 비해 절대 터미테는 절대적 용어로 그들의 방향을 암호화한다: 특정한 지시가 터미테에게 "북"을 이동하도록 지시할 수도 있다.절대 투르미트는 기존의 튜링 기계의 2차원 유사점이라 하여 단순히 "2차원 튜링 기계"라고 부르기도 한다.이 글의 나머지 부분은 상대적 사례와 관련이 있다.

사양

다음의 사양은 가장 많이 연구된 형태의 터미트인 2차원 사각 격자 상의 터미트(turmite)에 특유한 것이다.다른 그리드의 투르미트는 유사한 방식으로 지정될 수 있다.

랭턴의 개미와 마찬가지로 터미테는 각 시간 단계별로 다음과 같은 작전을 수행한다.

  1. 그 자리에 켠다 (90°의 배수 일부)
  2. 정사각형의 색을 바꾸다
  3. 한 칸 앞으로 나아가다

튜링 기계와 마찬가지로, 그 작용은 터마이트의 현재 내부 상태와 그것이 현재 서 있는 세포의 색상을 나열한 상태 전환표에 의해 명시된다.예를 들어, 이 페이지 상단의 이미지에 표시된 터미티는 다음 표로 지정된다.

현재 색상
0 1
쓰기 색 돌다 다음 상태 쓰기 색 돌다 다음 상태
현재 상태 0 1 R 0 1 R 1
1 0 N 0 0 N 1

회전 방향은 L(왼쪽 90도), R(오른쪽 90도), N(회전 없음), U(180도 U턴) 중 하나이다.

예

  • 사각 격자 위의 2개 상태 2색 투르미트의 예, 모두 빈 구성에서 시작됨:

  • 나선 성장.

  • 무질서한 성장기 이후의 고속도로 생산.

  • 독특한 질감을 가진 무질서한 성장.

  • 팽창하는 프레임 안에서 독특한 질감을 가진 성장.

  • 성장하는 다이아몬드 구축

  • 상태와 색상이 더 많고 사각형이 아닌 그리드에 있는 투르미트의 예:

  • 눈송이 같은 프랙탈 패턴을 연출하는 3주 2색 터미이트.

  • 육각 격자 위에 3가지 색상의 3-스테이트 터미이트로, 약 194150 걸음 후에 주기적인 루프에 갇히기 전에 독특한 질감으로 차오티컬하게 성장한다.

빈 그리드나 다른 구성에서 시작하여, 가장 흔히 관찰되는 행동은 무질서한 성장, 나선형 성장, 그리고 '고속도로' 건설이다.드문 예는 일정 수의 단계를 거치면 주기적인 것이 된다.

바쁜 비버 게임

앨런 H. 브래디는 터미티 종료를 찾아다녔고(바쁜 비버에 해당) 정지 전 37 1을 인쇄한 2주 2색 기계와 정지 전 121단계를 찍은 다른 것을 발견했다.[3]그는 또한 삼각망 위에서 움직이는 터미티를 고려했고, 이곳에서도 분주한 비버들을 발견했다.

에드 페그 주니어는 바쁜 비버 게임에 대한 또 다른 접근을 고려했다.그는 좌우를 둘로 쪼개어 회전할 수 있는 터미테를 제안했다.나중에 만난 터키인들은 서로를 섬멸한다.이 시스템에서 Busy Beaver는 하나의 터미티 시작 패턴에서 모든 터미티들이 서로를 멸종시키기 전까지 가장 오래 지속되는 것이다.[6]

기타 그리드

알렌 H. 브래디가 삼각 격자 위에 터미테를 처음 작업한 데 이어 육각형 틸팅도 함께 탐구했다.이 작업의 대부분은 팀 허튼 덕분이며, 그의 결과는 규칙 테이블 저장소에 있다.그는 또한 터키인들을 3차원으로 고려했고, 약간의 예비 결과를 수집했다.앨런 H. 브래디와 팀 허튼도 브래디가 지느러미라고 부르는 정수 격자 위의 1차원 상대 터미트를 조사했다. (물론 1차원 절대 터미티는 단순히 튜링 기계로 알려져 있다.)

참고 항목

참조

  1. ^ Langton, Chris G. (1986). "Studying artificial life with cellular automata" (PDF). Physica D: Nonlinear Phenomena. 22 (1–3): 120–149. Bibcode:1986PhyD...22..120L. doi:10.1016/0167-2789(86)90237-X. hdl:2027.42/26022.
  2. ^ Brady, Allen H. (1988). "The Busy Beaver Game and the Meaning of Life". In Rolf Herken (ed.). The Universal Turing Machine: A Half-Century Survey. Springer-Verlag. ISBN 0-19-853741-7.
  3. ^ a b Brady, Allen H. (1995). "The Busy Beaver Game and the Meaning of Life". In Rolf Herken (ed.). The Universal Turing Machine: A Half-Century Survey (2nd ed.). Springer-Verlag. pp. 237–254. ISBN 3-211-82637-8.
  4. ^ a b Rucker, Rudy. "Artificial Life Lab". Retrieved October 16, 2009.
  5. ^ Dewdney, A. K. (September 1989). "Computer Recreations: Two-dimensional Turing machines and Turmites make tracks on a plane". Scientific American. 261: 180–183. doi:10.1038/scientificamerican0989-180. closed access
  6. ^ Pegg, Jr., Ed. "Math Puzzle". Retrieved 15 October 2009.

외부 링크