Cellular Automaton의 한 종류로, 개미가 보드 위에서 움직이는 모습을 구현 한 듯 한 모양새.
무한한 2차원 그리드 보드에서 개미가 이동한다.
기본적인 룰.
- 검은색 셀에서 90° 시계 방향으로 회전하고, 현재 셀의 색을 반전시키고, 한 칸 앞으로 이동한다.
- 흰색 셀에서 90° 시계 반대 방향으로 회전하고, 현재 셀의 색을 반전시키고, 한 칸 앞으로 이동한다.
| Current Color | |||
|---|---|---|---|
| 0 | 1 | ||
| Write | Rotation | Write | Rotation |
| 1 | R | 0 | L |
Turmites
’termites’ 흰개미
튜링(Turing) 개미 라는 의미에서 ’turing’ + ’termites’ = ’turmites’가 되었다.
기존의 langton’s ant에서 개미에게 상태와 추가적 색을 부여하므로써 더욱 다양한 형태를 그릴 수 있다.
Turing Complete
Langton’s Ant는 튜링 완전 머신이다.
(간략화를 위해 state n을 Sn, color n을 Cn으로 부르자.)
더욱 복잡하게 만들 수 도 있지만, 간단하게 if문을 만들어보자면 다음과 같다.
| Current | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| C0 | C1 | C2 | ||||||||
| Write | Rot | Next | Write | Rot | Next | Write | Rot | Next | ||
| Current | S0 | X | 1 | |||||||
| S1 | R | L | ||||||||
S0상태에서C0에 가면 판별 전용 상태엔S1로 변화.S1상태에서 다음 셀이C1이면 오른쪽으로 회전,C2이면 왼쪽으로 회전