랭턴의 개미

랭턴의 개미는 같은 계열의 개미들 중 가장 단순한 경우입니다. 빈칸을 0으로 하여 번호를 붙인 n가지 색이 있을 때, 규칙은 각 색에 R 또는 L 하나를 대응시킨 문자열 $r = r_0 r_1 \cdots r_{n-1}$입니다. 랭턴의 개미의 규칙은 RL입니다. 개미가 칸 p에 서서 방향 d를 보고 있다면 한 걸음은 다음과 같습니다.

개미는 기억이 없고 발밑의 색만 봅니다. 여기서는 질서 있는 무늬를 만들다가 복잡하게 얽히고, 마침내 길을 내는 모습을 볼 수 있습니다. 거꾸로 움직이거나, 앞길의 칸에 색을 칠하거나, 다른 문자열을 시험할 수도 있습니다.

색은 규칙의 상태입니다. 평면에는 끝이 없으며 반대편으로 이어지지도 않습니다. 패널 위쪽 곡선은 매 단계가 끝난 뒤 색칠한 칸의 수를 나타냅니다.

빈 평면에서 위를 향해 출발하면 개미는 처음에 작고 가지런한 무늬를 만듭니다. 473번째 걸음처럼 반 바퀴 회전에 대칭인 무늬도 있습니다. 이어 약 1만 걸음 동안 무작위처럼 보이는 얽힌 무늬가 나타납니다. 그러다 9 977번째 걸음부터 같은 104걸음을 반복하며, 주기마다 (−2, 2), 즉 왼쪽 두 칸, 아래 두 칸으로 이동합니다. 이 대각선 띠를 고속도로라고 부르며, 104걸음마다 색칠된 칸이 정확히 12개 늘어납니다. 반복되는 것은 개미의 움직임과 발밑의 띠뿐입니다. 뒤에 남은 얽힌 무늬는 제자리에 있습니다.

몇 주기 반복했다는 것만으로는 아무것도 증명되지 않습니다. 다음 주기에 색칠된 칸을 만나 길을 벗어날 수도 있기 때문입니다. 따라서 이 페이지는 확인을 마친 뒤에만 길이 계속된다고 보장합니다. 최근 주기가 끝난 뒤, 그동안 읽은 칸들을 개미의 변위만큼 옮겼을 때 원래 칸들이 주기 시작 전에 가졌던 색과 같아야 하며, 개미도 시작 때와 같은 방향을 보고 있어야 합니다. 또한 이후 모든 주기에서 이전 주기의 범위를 벗어나는 칸은 지금 비어 있어야 하고, 확인한 주기부터 어느 주기에서도 방문한 적이 없어야 합니다. 그러면 매 주기 앞선 주기와 똑같은 상황을 만나므로 같은 움직임이 영원히 이어집니다. 곡선의 점선은 반복이 시작되는 지점을 표시합니다. 앞에 색칠된 칸이 있으면 페이지는 그 칸을 동그라미로 표시하고 보장을 하지 않습니다.

따라서 빈 평면에서는 계산과 이 확인을 함께 사용해 길이 계속됨을 증명합니다. RL 규칙에서 유한 개의 칸에만 색을 칠한 판은 지금까지 시험한 경우 모두 결국 길을 만들었지만, 모든 경우가 그렇다는 것은 아직 누구도 증명하지 못했습니다.

모든 걸음은 되돌릴 수 있습니다. 개미는 방금 움직인 방향을 보고 있으므로 출발한 칸이 바로 뒤에 있고, 그 칸의 색은 순환에서 한 단계 앞으로 바뀌어 있습니다. 한 걸음 되돌리는 과정은 다음과 같습니다.

따라서 판과 개미만으로 한 걸음 전 상태가 정해집니다. 뒤로는 기록을 역재생하는 것이 아니라 규칙에 따라 개미를 거꾸로 움직입니다.

글자가 많아지면 방문할 때마다 칸이 다음 색으로 바뀝니다. 빈 평면에서 시작해도 규칙 버튼에 따라 전혀 다른 모양이 자랍니다. LLRR은 대칭처럼 보이는 무늬, LRRRRRLLR은 거의 속이 찬 정사각형, RRLLLRLLLRRR은 계속 커지는 삼각형을 만듭니다. 이 세 경우가 결국 어떻게 될지는 알려져 있지 않습니다. LLRRRLRLRLLR은 약 3만 걸음 뒤에 길을 만듭니다.

크리스 랭턴은 1986년 인공생명의 예로 이 개미를 설명했습니다.