Langton's Ant

Cellular Automaton의 한 종류로, 개미가 보드 위에서 움직이는 모습을 구현 한 듯 한 모양새.

무한한 2차원 그리드 보드에서 개미가 이동한다.

기본적인 룰.

• 검은색 셀에서 90° 시계 방향으로 회전하고, 현재 셀의 색을 반전시키고, 한 칸 앞으로 이동한다.
• 흰색 셀에서 90° 시계 반대 방향으로 회전하고, 현재 셀의 색을 반전시키고, 한 칸 앞으로 이동한다.

Turmites #¹

’termites’ 흰개미

튜링(Turing) 개미 라는 의미에서 ’turing’ + ’termites’ = ’turmites’가 되었다.

기존의 langton’s ant에서 개미에게 상태와 추가적 색을 부여하므로써 더욱 다양한 형태를 그릴 수 있다.

Turing Complete #¹

Langton’s Ant는 튜링 완전 머신이다.

(간략화를 위해 state n을 Sn, color n을 Cn으로 부르자.)

더욱 복잡하게 만들 수 도 있지만, 간단하게 if문을 만들어보자면 다음과 같다.

• S0 상태에서 C0에 가면 판별 전용 상태엔 S1로 변화.
• S1 상태에서 다음 셀이 C1이면 오른쪽으로 회전, C2이면 왼쪽으로 회전