랭턴의 개미

계산물리 시뮬레이션 마지막 수정: 2026-07-28 04:47:09

1. 개요[편집]

랭턴의 개미(Langton’s ant)는 정사각 격자 위를 돌아다니는 이동체(개미)에게 두 줄짜리 규칙만 주고 돌렸을 때 나타나는 결정론적 동역학계로, 크리스 랭턴이 1986년에 인공생명 연구 중에 제시했다. 규칙 전체가 이것뿐이다.

지금 서 있는 칸이 흰색이면 → 오른쪽으로 90° 회전, 그 칸을 검게 뒤집고, 한 칸 전진.
지금 서 있는 칸이 검은색이면 → 왼쪽으로 90° 회전, 그 칸을 희게 뒤집고, 한 칸 전진.

전부 흰 격자에서 출발시키면 처음 수백 스텝 동안은 얌전한 대칭 무늬가 나오고, 그 뒤 1만 스텝 가까이 아무 구조도 없는 지저분한 얼룩이 커진다. 그런데 대략 1만 스텝 언저리에서 개미가 갑자기 104스텝마다 같은 동작을 반복하며 대각선으로 두 칸씩 무한히 뻗어 나가는 주기 궤도에 진입한다. 이 구조를 고속도로(highway)라고 부른다. 규칙 두 줄에는 “고속도로”라는 개념이 어디에도 없다는 점에서, 셀룰러 오토마타 계열에서 창발을 설명할 때 거의 반드시 등장하는 표본이 됐다.¹

흰 칸이면 우회전, 검은 칸이면 좌회전 — 칸 색을 뒤집고 한 칸 전진하는 규칙을 매 스텝 그대로 실행한다. 수백 스텝의 대칭 국면, 1만 스텝 안팎의 무질서 국면, 그리고 104스텝 주기로 대각선을 향해 두 칸씩 뻗는 고속도로가 순서대로 나온다. 격자는 유한해서 바깥 경계는 토러스로 감긴다.

2. 튜르밋 — 2차원 튜링 기계[편집]

랭턴의 개미는 형식적으로 튜르밋(turmite, Turing + termite)이다. 튜링 기계의 1차원 테이프를 2차원 격자로 바꾸고, 헤드에 “현재 향한 방향”이라는 내부 상태를 붙인 것. 구성 요소를 대응시키면 이렇게 된다.

튜링 기계	랭턴의 개미
테이프 기호	칸의 색(흰/검)
헤드 내부 상태	개미가 향한 방향 4가지
전이 함수	회전 + 반전 + 전진 규칙
헤드 이동	격자 위 한 칸 이동

전이 함수가 색 2개 × 방향 4개 = 8줄이면 끝나고, 그마저도 “색에 따라 좌/우 회전”이라는 대칭 때문에 사실상 2줄로 압축된다. 이 최소성이 이 모형의 매력이자 함정이다. 규칙을 아무리 들여다봐도 104라는 숫자가 어디서 나오는지 읽어낼 방법이 없다.

규칙 자체는 가역이라는 점도 짚어둘 만하다. 현재 상태에서 직전 상태를 유일하게 복원할 수 있어서, 개미를 거꾸로 되감으면 원래 궤적을 그대로 되짚는다. 정보를 버리지 않는 결정론적 계인데도 예측이 안 된다는 뜻이라, 카오스 이론에서 말하는 “결정론적이지만 실질적으로 예측 불가”의 이산판 표본이기도 하다.

3. 고속도로는 항상 나타나는가[편집]

이 모형이 학술적으로 살아남은 진짜 이유는 여기에 있다. 처음에 검은 칸을 유한 개 아무렇게나 뿌려놓고 시작해도 개미는 결국 고속도로를 만드는가? 지금까지 시도된 모든 초기 배치에서 예외 없이 관측됐지만, 증명은 없다. 열려 있는 문제다.

증명된 것은 그보다 훨씬 약한 명제 하나다. 코헨과 쿵, 그리고 부니모비치-트루베츠코이가 각각 보인 결과에 따르면 개미의 궤적은 유계일 수 없다 — 즉 개미는 유한한 영역 안에 영원히 갇혀 있을 수 없고, 반드시 무한히 멀리 나간다. 증명의 뼈대는 “개미가 유한 영역 안에서만 움직인다면 그 영역의 가장 바깥 방문 칸에서 방향 전환이 모순을 일으킨다”는 식의 조합적 논증이라 놀랄 만큼 초등적이다. 그런데 무한히 멀리 나가는 방식이 반드시 그 104스텝 고속도로여야 한다는 것까지는 아무도 못 갔다. 유계가 아니라는 사실과 특정 주기 구조가 나온다는 사실 사이의 간극이 이 문제의 전부다.²

고속도로의 구조 자체는 한번 진입하면 지루할 만큼 단순하다. 104스텝을 돌 때마다 격자 무늬가 정확히 같은 모양으로 복제되고 개미는 대각선 방향으로 두 칸 이동한다. 즉 주기 104, 이동 벡터 (2, 2)짜리 병진 대칭 궤도이고, 이 뒤로는 아무리 오래 돌려도 새로운 일이 벌어지지 않는다. 검은 칸 수도 그 시점부터 스텝에 비례해 선형으로 늘어난다. 흥미로운 구간은 오직 고속도로 진입 전이고, 그 구간의 길이를 예측하는 방법이 없다는 게 이 모형의 성격을 요약한다.

4. 일반화 튜르밋[편집]

규칙을 색 $k$ 개로 늘리고, 각 색에서 좌회전(L)/우회전(R) 중 무엇을 할지를 문자열로 적으면 일반화된 튜르밋이 된다. 이 표기로 원조 랭턴의 개미는 RL이다. 문자열을 바꾸면 거동이 극적으로 갈린다.

LLRR — 성장하는 동안 시각적 대칭을 유지하는 패턴.
LRRRRRLLR — 공간을 사각형 모양으로 메워 나간다.
LLRRRLRLRLLR — 원조와 마찬가지로 고속도로를 만든다.
RL, RLR 계열 — 무질서한 얼룩을 길게 끄는 카오스형.

즉 “고속도로”는 규칙 공간 전체의 성질이 아니라 특정 규칙들이 가진 성질이며, 어떤 문자열이 어떤 부류에 속하는지 예측하는 일반 이론도 아직 없다. 울프람이 1차원 기본 규칙을 네 부류로 나눴던 것과 같은 분류를 2차원 튜르밋에 대해서는 아무도 완성하지 못했다는 뜻이다. 색을 늘리면 규칙 수가 $2^{k} \cdot k!$ 규모로 폭발하는데, 그 광대한 공간에서 우리가 아는 것은 “돌려본 것들”뿐이다.

5. 구현 노트[편집]

시뮬레이션 코드로서 랭턴의 개미는 격자 문제 중에서도 유별나게 값싸면서 유별나게 다루기 까다롭다.

영역이 미리 정해지지 않는다. 개미는 고속도로를 타고 무한히 뻗어 나가므로, 진짜 무한 격자를 원하면 고정 배열 대신 좌표를 키로 쓰는 해시(희소 표현)나 필요할 때 배열을 2배로 늘리는 동적 확장이 필요하다. 유한 배열로 갈 거라면 경계에서 토러스로 감거나, 개미가 경계에 닿는 순간 정지시키고 그 이후 결과는 신뢰하지 않아야 한다. 감아버리면 개미가 자기 옛 흔적과 다시 만나게 되므로, 그 시점 이후는 원래 문제와 다른 계다.
갱신 비용이 스텝당 $O(1)$ 이다. 한 칸의 색 하나만 바뀌므로, 매 프레임 전체 격자를 다시 그리는 대신 바뀐 칸만 칠하면 렌더링이 스텝 수에 선형으로 떨어진다. 수만 스텝을 프레임 안에 몰아넣기 좋은 구조.
병렬화가 사실상 불가능하다. 다음 스텝은 직전 스텝의 결과에 전적으로 의존하고 지름길도 없다. $10^{9}$ 스텝을 보고 싶으면 $10^{9}$ 번 순서대로 돌려야 하며, 이 “예측하려면 실행하는 수밖에 없다”는 성질을 울프람은 계산 비환원성(computational irreducibility)이라고 불렀다. 아래에서 볼 P-난해성 결과는 그 직관을 계산복잡도 언어로 다시 쓴 것이다.

6. 계산 보편성[편집]

가하르도, 모레이라, 골레스는 개미의 궤적으로 불 회로를 구성할 수 있음을 보였다. 격자에 검은 칸을 적절히 배치해 도선·교차·논리 게이트에 해당하는 국소 구조를 만들면, 개미가 그 위를 지나가면서 신호를 전달하고 게이트를 계산한다. 여기서 두 가지 결론이 나온다. 첫째, 유한한 초기 배치에서 “개미가 특정 칸을 언젠가 방문하는가”를 판정하는 문제는 P-난해다 — 즉 개미를 실제로 돌려보는 것보다 본질적으로 빠른 예측 알고리즘을 기대하기 어렵다. 둘째, 무한하지만 규칙적인 초기 배치를 허용하면 튜링 완전하다. 규칙 두 줄짜리 장난감이 범용 계산기라는 이야기고, 이는 생명 게임의 글라이더 총·논리 게이트 구성과 같은 결론이다.

7. 셀룰러 오토마타와 무엇이 다른가[편집]

랭턴의 개미도 넓은 의미에서는 CA로 표현할 수 있다. 각 칸의 상태에 “여기 개미가 있고 방향은 북쪽” 같은 정보를 얹으면 상태 수가 유한한 국소 규칙이 되기 때문이다. 하지만 실전에서 둘의 성격은 꽤 다르다.

갱신 방식: 셀룰러 오토마타는 매 스텝 모든 칸을 동시에 갱신한다. 개미는 스텝당 정확히 한 칸만 바뀐다. 그래서 CA는 격자 크기에 비례하는 병렬 작업량을 가지지만(병렬 컴퓨팅과 궁합이 좋다), 개미는 본질적으로 순차적이라 GPU로 가속할 여지가 거의 없다. 1억 스텝을 보고 싶으면 1억 번 순서대로 돌리는 수밖에 없다.
활성 영역: CA의 활동은 격자 전역에 퍼지고, 개미의 활동은 헤드 하나에 집중된다. 대신 개미가 뒤집어 놓은 색이 기억으로 남아 나중에 자기 자신에게 되먹임된다.
창발의 성격: 생명 게임의 창발이 “많은 셀의 국소 상호작용”에서 나온다면, 개미의 창발은 “하나의 이동체 + 자기가 남긴 흔적”에서 나온다. 자기조직화에서 말하는 되먹임 구조가 개체 수 1로도 성립한다는 점이 이 모형의 교훈이다.

이 차이 때문에 랭턴의 개미는 물리 계산 도구로는 거의 쓰이지 않는다. 격자 기체 오토마타처럼 보존량을 갖고 연속체 극한으로 가는 구조가 아니기 때문. 대신 “규칙의 단순함과 거동의 복잡함 사이에는 아무 관계도 없다”는 명제의 반례 제조기로, 그리고 창발을 30초 안에 눈으로 보여주는 교보재로 살아남았다.³⁴

8. 관련 문서[편집]

104라는 주기는 아무도 손으로 유도하지 못했고, 그냥 돌려서 센 숫자다. 이 바닥에서 “일단 돌려”가 정당한 방법론이 되는 몇 안 되는 사례. ↩
무질서 국면의 길이가 초기 배치에 따라 요동친다는 점도 고약하다. 검은 칸 몇 개를 더 뿌리면 고속도로가 2천 스텝 만에 나오기도 하고 5만 스텝을 넘기기도 한다. 수렴 판정 기준을 못 정하니 “충분히 오래 돌렸다”는 말에 근거를 댈 수가 없다. ↩
개미 여러 마리를 동시에 풀어놓는 변형도 있다. 한 마리가 만든 고속도로를 다른 마리가 지나가며 부수고, 서로의 흔적이 얽히면서 고속도로가 생겼다 사라졌다를 반복한다. 규칙은 여전히 두 줄이다. ↩
참고로 이 모형은 강의실에서 “결정론 = 예측 가능”이라는 오해를 깨는 용도로 대단히 효율적이다. 규칙을 칠판에 다 적어놓고도 다음에 뭐가 나올지 아무도 못 맞힌다는 상황이 그 자리에서 만들어지기 때문. ↩