튜르마이트

컴퓨터 과학에서 튜르마이트(turmite)는 현재 상태와 무한한 2차원 셀 격자로 구성된 "테이프"와 방향을 가진 튜링 기계를 뜻한다. 개미(ant) 및 반트(vant)라는 용어도 사용된다. 랭턴의 개미는 정사각형 격자의 셀에 정의된 잘 알려진 유형의 튜르마이트이다. 패터슨의 벌레는 등축 격자의 모서리로 정의된 튜르마이트의 한 유형이다.

2단계 2색 튜르마이트가 정사각형 격자 위에 있는 모습. 비어 있는 격자에서 시작하여 8,342단계를 거친 후 튜르마이트(빨간색 픽셀)는 혼돈 및 규칙적인 이동 단계를 모두 보였다.

일반적인 튜르마이트는 무한한 테이프를 가진 1차원 튜링 기계와 기능적으로 정확히 동등하며, 서로를 시뮬레이션할 수 있다는 것이 입증되었다.

역사

랭턴의 개미는 1986년에 발명되었으며 "튜링 기계와 동등하다"고 선언되었다.^[1] 독립적으로 1988년에 앨런 H. 브래디는 방향을 가진 2차원 튜링 기계에 대한 아이디어를 고찰하고 이를 "터닝 머신"(TurNing machines)이라고 불렀다.^[2][3]

이 둘과 독립적으로,^[4] 그레그 터크는 동일한 종류의 시스템을 연구하고 A. K. 듀드니에게 이에 대해 편지를 썼다. A. K. Dewdney는 1989년 사이언티픽 아메리칸의 "컴퓨터 레크리에이션" 칼럼에서 이들을 "튜르-마이트"(tur-mites)라고 명명했다.^[5] 루디 러커는 다음과 같이 그 이야기를 전한다.

듀드니는 터크의 창조물에 이름을 붙이기 위해 궁리하면서 이렇게 생각했다고 한다. "음, 그것들은 터크가 연구한 튜링 머신이니까 "tur-뭐시기"일 거야. 그리고 작은 곤충, 즉 진드기(mites) 같으니까 tur-mites라고 부르자! 그리고 그건 흰개미(termites)처럼 들리네!" 터크와 듀드니의 친절한 허락을 받아 하이픈을 빼고 turmites라고 부르겠다.

— 루디 러커, Artificial Life Lab^[4]

상대적 튜르마이트 대 절대적 튜르마이트

튜르마이트는 상대적 튜르마이트와 절대적 튜르마이트로 분류할 수 있다. "터닝 머신"이라고도 알려진 상대적 튜르마이트는 내부 방향을 가진다. 랭턴의 개미가 그러한 예이다. 상대적 튜르마이트는 정의상 등방성을 가진다. 튜르마이트를 회전시켜도 그 결과에 영향을 미치지 않는다. 상대적 튜르마이트는 현재 방향에 상대적인 방향으로 인코딩되기 때문에 "왼쪽" 또는 "뒤쪽"과 같은 단어를 사용하는 것과 같아 '상대적'이라는 이름으로 명명되었다. 이와 비교해 절대적 튜르마이트는 절대적인 용어로 방향을 인코딩한다. 특정 명령어를 통해 튜르마이트에게 "북쪽"으로 이동하라고 지시할 수 있다. 절대적 튜르마이트는 기존의 튜링 기계의 2차원 아날로그 형태이므로 때로는 단순히 "2차원 튜링 기계"라고도 불린다. 이 문서에서는 대부분 상대적 튜르마이트에 대해 다룬다.

사양

다음 사양은 가장 많이 연구된 유형의 튜르마이트인 2차원 정사각형 격자에 있는 튜르마이트에 특정하며 본다. 다른 격자에 있는 튜르마이트는 아래 예시와 유사한 방식으로 지정할 수 있다.

랭턴의 개미와 마찬가지로 튜르마이트는 각 단계마다 다음 작업을 수행한다.

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° 유턴) 중 하나이다.

예시

• 정사각형 격자 위의 2단계 2색 튜르마이트 예시, 모두 비어 있는 설정에서 시작:
• 
  나선형 성장을 보이는 모습
• 
  혼돈스러운 성장 기간을 거친 후 한 방향으로 고속도로처럼 나가는 모습
• 
  독특한 질감을 가진 혼돈 성장 모습
• 
  확장하는 사각형 안에서 독특한 질감을 가진 성장 모습
• 
  피보나치 나선형 구성 모습
• 
  성장하는 다이아몬드 모습

• 더 많은 상태와 색상을 가진 튜르마이트 및 비정사각형 격자 위의 예시:
• 
  3단계 2색 튜르마이트가 눈송이 모양의 프랙탈 패턴을 생성한다.
• 
  3색 3단계 튜르마이트가 정육각형 격자 위에서 혼돈스럽게 성장하다가 약 194,150 단계 후 특정 주기를 가진 루프에 갇힌다.

비어 있는 격자 또는 다른 설정에서 시작할 때 가장 일반적으로 관찰되는 행동은 혼돈 성장, 나선형 성장 및 '고속도로' 구성이다. 드문 예로 특정한 단계 후에 주기를 이루는 경우가 있다.

바쁜 비버 게임

앨런 H. 브래디는 종료되는 튜르마이트(바쁜 비버의 동등체)를 찾았으며, 멈추기 전까지 총 37개의 1을 인쇄하는 2단계 2색 기계와 멈추기 전에 121단계를 거친 다른 기계를 발견했다.^[3] 또한 정삼각형 격자에서 움직이는 튜르마이트도 고려해 여기서도 바쁜 비버를 발견했다.

에드 페그 주니어는 바쁜 비버 게임에 대한 또 다른 접근 방식을 고려했다. 예를 들어 왼쪽과 오른쪽으로 모두 회전하여 둘로 분할될 수 있는 튜르마이트를 제안했다. 나중에 만나는 튜르마이트는 서로를 소멸시킨다. 이 시스템에서 바쁜 비버는 하나의 튜르마이트의 시작 패턴에서 모든 튜르마이트가 서로를 소멸시키기 전에 가장 오래 지속되는 튜르마이트를 가리킨다.^[6]

기타 격자

앨런 H. 브래디의 정삼각형 격자 위 튜르마이트에 대한 초기 연구에 이어 정육각형 테셀레이션에서의 튜르마이트도 탐구되었다. 이 작업의 대부분은 팀 허튼이 진행했으며 그의 결과는 Rule Table Repository에 있다. 또한 3차원의 튜르마이트를 고려했으며 일부 예비 결과를 수집했다. 앨런 H. 브래디와 팀 허튼은 정수 격자 위의 1차원 상대 튜르마이트(브래디가 플리퍼(flippers)라고 명명)를 연구했다. (1차원 절대 튜르마이트는 물론 단순한 튜링 기계로 알려져 있다.)

같이 보기

• 세포 자동자
• 랭턴의 개미
• 패터슨의 벌레