랭턴의 개미베타

랭턴의 개미 소개

랭턴의 개미는 규칙이 두 줄뿐인 기계다. 흰 칸에 서 있으면 오른쪽으로 90도 돌고, 검은 칸이면 왼쪽으로 돈다. 그다음 서 있던 칸의 색을 뒤집고 한 칸 앞으로 간다. 크리스토퍼 랭턴이 1986년 인공 생명 연구에서 소개했다. 이 도구의 기본 규칙 「RL」이 바로 이것으로, 글자 하나가 색 하나에 대응한다(0번 색=흰색에서 R, 1번 색에서 L).

처음 누르면 256×256 격자 가운데에 개미 한 마리가 위를 보고 선다. 격자 가장자리는 반대편과 이어져 있어(토러스) 개미가 밖으로 떨어지지 않는다. 속도 슬라이더는 한 화면 프레임에 몇 스텝을 계산할지 정하며, 기본값 100이면 초당 약 6,000스텝이 진행된다.

관찰 포인트 1: 혼돈 뒤에 나타나는 고속도로

처음 수백 스텝 동안 개미는 대칭에 가까운 작은 무늬를 만들다가 곧 불규칙한 얼룩을 키운다. 이 상태가 약 1만 스텝 이어진 뒤, 개미는 갑자기 104스텝마다 똑같은 동작을 반복하며 한쪽 대각선으로 곧게 뻗는 띠를 짓기 시작한다. 이것을 「고속도로」라고 부른다. 기본 속도에서는 2초 남짓이면 볼 수 있다.

고속도로에서 개미는 104스텝마다 가로 2칸, 세로 2칸 움직인다. 대각선으로 한 칸(가로·세로 1칸씩) 나아가는 데 평균 52스텝이 드는 셈이다. 이 도구의 테스트 코드도 1만 1천 스텝 뒤 104스텝 동안의 이동량이 (±2, ±2)인지 확인한다.

고속도로가 왜 생기는지, 모든 초기 상태에서 결국 생기는지는 증명되지 않았다. 증명된 것은 더 약한 사실이다. 개미의 궤적은 어떤 유한한 초기 무늬에서 시작해도 유한한 영역에 갇히지 않는다(무한 평면 기준).

관찰 포인트 2: 도넛 격자에서 고속도로가 부서질 때

무한 평면이라면 고속도로는 영원히 이어진다. 이 도구의 격자는 유한한 도넛이라, 고속도로는 가장자리를 넘어 반대편으로 들어와 결국 처음의 혼돈 영역이나 자기 흔적과 만난다. 그 순간 규칙적인 움직임이 깨지고 다시 혼돈이 시작된다. 가끔은 새 고속도로가 다른 방향으로 생기기도 한다.

대략 계산해 보면, 256칸 격자에서 고속도로가 한 바퀴 돌아 얼룩에 닿기까지 가로·세로로 200칸 가까이 가야 하고, 칸당 52스텝이면 1만 스텝 정도가 더 든다. 그래서 2만 스텝 전후에 충돌이 일어나기 쉽다(얼룩 크기에 따라 달라진다). 격자를 1024²로 키우면 고속도로가 훨씬 오래 유지된다.

관찰 포인트 3: 색을 늘린 규칙들

규칙 문자열의 길이가 색의 수다. 개미는 i번 색 칸에서 i번째 글자대로 돈 뒤 칸을 i+1번 색으로 바꾼다(마지막 색 다음은 0번). L=왼쪽, R=오른쪽, N=직진, U=유턴이며 최대 32색까지 쓸 수 있다.

• RLR: 오래 돌려도 고속도로 없이 불규칙하게 커지는 경우가 많다.
• LLRR: 네 색 규칙. 모양이 어떻게 커지는지 RL과 비교해 보자.
• LRRRRRLLR, RRLLLRLLLRRR 같은 긴 규칙: 채워진 삼각형, 사각형 같은 기하 도형처럼 자라는 것이 있다.
• N이나 U가 들어간 규칙: 직진·유턴은 방향을 바꾸지 않거나 되돌아가게 해 전혀 다른 무늬가 된다.

개미를 여러 마리 풀면

캔버스를 누르면 그 자리에 무작위 방향의 개미가 추가된다(최대 256마리). 개미들은 한 세대에 번호 순서대로 한 스텝씩 움직이고 같은 격자를 칠하므로, 한 개미가 뒤집은 칸을 다른 개미가 바로 읽는다. 두 마리만 있어도 서로의 흔적을 지워 고속도로가 생기지 않거나 늦게 생기는 일이 흔하다.

화면 아래에는 「세대」와 「이동」이 따로 표시된다. 개미가 10마리면 한 세대에 10번 움직이므로 이동 수는 세대 수의 10배로 늘어난다(중간에 개미를 더하면 그 시점부터 늘어난 수만큼 더해진다). 속도 슬라이더는 개미 이동 총량을 기준으로 하므로 개미가 많을수록 세대는 느리게 늘어난다.

튜링 완전성

가하르도, 모레이라, 골레스는 2002년 논문에서 개미 한 마리의 궤적으로 임의의 불 회로를 계산하는 초기 배치를 만들 수 있음을 보였다. 즉 흰 격자에서 시작하면 단순해 보이는 이 규칙도, 초기 무늬를 잘 짜면 계산 장치가 된다. 이 도구는 빈 격자에서만 시작하므로 그런 구성을 직접 그려 볼 수는 없다.

예시

사용 방법

1. 규칙 프리셋을 고르거나 L·R·N·U로 된 규칙을 입력한다(2~32글자).
2. 속도 슬라이더로 프레임당 스텝 수를 정한다.
3. 캔버스를 눌러 개미를 추가하고, 처음부터 버튼으로 빈 격자에 개미 한 마리로 되돌린다.

자주 묻는 질문

관련 가이드

• 단순한 규칙이 복잡한 세계를 만드는 방식: 라이프 게임부터 유령 정체까지