랭턴의 개미와 터마이트로 보는 창발과 튜링 머신: 규칙 두 줄이 만드는 혼돈과 질서

핵심 메시지

• 랭턴의 개미는 '흰 칸이면 검게 칠하고 좌회전, 검은 칸이면 희게 칠하고 우회전'이라는 규칙만 따르는데, 약 1만 스텝 뒤 갑자기 '하이웨이'라 불리는 규칙적 구조를 무한히 짓기 시작한다.
• 개미를 여러 마리 놓으면 짝수일 때만 경계를 쌓고 홀수면 그러지 않는 등, 이유를 알 수 없는 규칙성이 나타난다.
• 개미의 두뇌를 유한 상태 기계로 바꾸면 '터마이트'가 되고, 상태 기계가 프로그램, 격자가 메모리 역할을 하면서 사실상 2차원 튜링 머신이 된다.
• 터마이트는 상태와 메모리가 충분하면 계산 가능한 어떤 프로그램도 실행할 수 있는 범용 기계이며, 여러 마리를 돌리는 것은 메모리를 공유하는 멀티스레딩에 해당한다.
• 제작자는 AI 도움으로 이 시뮬레이터를 만들었지만, 직접 알고리즘을 파고드는 경험을 잃었고 이해도 얕아졌다며 양면성을 솔직히 인정한다.

쉽게 이해하기

인공생명 연구자 크리스 랭턴이 고안한 '랭턴의 개미'는 규칙이 두 줄뿐이다. 개미는 흑백 칸으로 이뤄진 격자 위를 돌아다니며, 흰 칸에 있으면 그 칸을 검게 칠하고 왼쪽으로, 검은 칸에 있으면 희게 칠하고 오른쪽으로 방향을 튼다. 색이나 회전 방향을 반대로 뒤집어도 결과는 같다.

완전히 결정론적인 프로그램인데도 개미의 움직임은 처음엔 무작위처럼 보인다. 중간에 거의 대칭에 가까운 모양을 만들다가 다시 어수선해지고, 약 1만 스텝이 지나면 갑자기 하나의 루프에 갇혀 '하이웨이'라 불리는 구조를 무한히 뻗어나간다. 단순한 규칙에서 혼돈과 질서가 뒤섞여 나오는, 창발의 교과서적 사례다.

개미를 여러 마리 놓으면 더 기묘해진다. 두 마리를 나란히 놓고 같은 방향을 보게 하면 곧바로 협업하듯 경계를 끝없이 쌓고, 격자 가장자리를 넘어 서로 부딪히면 지금까지 지은 것을 완벽하게 되짚어 허물기도 한다. 이 경계 쌓기는 한 줄로 늘어선 개미 수가 짝수일 때만 일어나고 홀수면 일어나지 않는데, 영상 제작자도 그 이유는 모른다고 말한다.

여기서 개미의 두뇌를 유한 상태 기계로 확장하면 이야기가 달라진다. 개미의 행동이 '현재 칸의 색'과 '현재 상태' 두 가지에 따라 결정되고, 그 결과로 이동 방향·칠할 색·다음 상태가 정해진다. 이렇게 확장된 개미를 튜링 머신과 이 방식을 처음 만든 그레그 터크에서 이름을 딴 '터마이트(turmite)'라 부른다. 상태 기계가 프로그램이고 격자가 읽고 쓰는 메모리이므로, 정의상 이것은 1차원 테이프 대신 2차원 격자를 쓰는 튜링 머신이다.

영상 후반부는 개미의 움직임을 좌우로만 제한해 1차원 테이프를 흉내 내고, 그 위에서 '비지 비버' 프로그램을 재현한다. 비지 비버는 정해진 상태 수로 만들 수 있으면서도 반드시 멈추는 프로그램 중 가장 오래 도는 것을 말한다. 상태 4개짜리는 107스텝을 돌고, 최근에야 확정된 상태 5개짜리는 47,176,870스텝을 돈 뒤 멈춘다. 6개짜리는 탐색 공간이 너무 커서 아마 영영 알 수 없을 것이라고 한다.

주요 인사이트

• 결정론적인 것과 예측 가능한 것은 다르다. 이 개미들의 규칙은 완전히 공개돼 있고 무작위성도 없지만, 실제로 돌려보기 전에는 무엇을 만들지 알 수 없다. 계산 이론에서 말하는 정지 문제가 눈앞에서 시각적으로 재현되는 셈이다.
• 제작자는 어떤 개미가 만드는 구조가 '작은 영역 안에 갇힌 것처럼 보이는데 정말 영원히 그런지'는 알 수 없다고 말한다. 수십억 스텝 뒤에 갑자기 하이웨이를 뻗기 시작할 수도 있고, 아무도 답을 모른다는 것이다.
• 터마이트가 범용 튜링 머신이라면 원하는 어떤 이미지도 한 칸씩 찍어 그리는 규칙을 만들 수 있어야 한다. 실제로 완벽한 대칭 눈송이를 만드는 규칙이 존재할 것이라고 보지만, 아직 그런 규칙은 발견되지 않았다.
• AI로 개발한 소감이 흥미롭다. AI가 없었다면 아예 만들지 못했을 것이라면서도, 알고리즘을 스스로 알아내고 규칙을 다듬는 경험을 빼앗긴 느낌이며 직접 만들었을 때만큼 잘 이해하지 못한다고 말한다. 특히 시각적 결함 같은 잔여 버그는 AI로 잡아내기 어려웠다고 한다.
• 역설적으로 이 시뮬레이터에서는 AI가 만든 코드가 맞는지 검증하기가 쉽다. 다른 사람이 공개한 규칙을 넣었을 때 알려진 패턴이 그대로 나오지 않는다면, 결과가 조금 어긋나는 정도가 아니라 아예 아무것도 만들어지지 않기 때문이다.

자주 묻는 질문

관련 AI 소식