랭턴의 개미( Langton's Ants)
1. 1986년 크리스 랭턴은 학위논문 속에서 한 흥미있는 세포자동자를 제출했다. 뒤에 "랭턴의 개미"(Langton's Ant)라고 명명된 이 세포자동자는 아주 간단한 결정론적 계가 얼마나 예측불가능한 복잡성을 산출할 수 있는지를 보여주는 한 패러다임적 사례이다. 이것의 규칙은 아주 간단하다. 개미는 격자상의 평면위에서 한번에 한칸씩 움직인다. 개미가 현재 흰색의 셀상에 있다면 개미의 진행방향에서 좌측으로 한칸 이동한다. 그리고 현재의 흰색셀은 검은색으로 바뀐다. 개미가 현재 검은색의 셀상에 있다면 개미의 진행방향에서 우측으로 한칸 이동한다. 그리고 검은색 셀은 흰색 셀로 바뀐다. 아래 그림은 이 규칙에 따른 개미의 이동을 보여주고 있다.(노란 화살표는 개미를 나타낸다.)
그림 1 랭턴의 규칙에 따른 개미의 이동
이 규칙에 따라 개미의 거동을 추적해가면 개미는 그야말로 어지러울 정도로 두서 없이 이리저리를 왔다갔다한다. 그러다가 10000세대를 넘어가면서 어느 지점에서 갑자기 어지러운 행보를 중단하고 화면을 45도의 대각선 방향으로 횡단한다. 정확히 102세대 마다 대각선 방향으로 한칸 위로 또는 아래로 이동한다. 이것을 반복하면서 하이웨이(highway)가 만들어진다.
대부분의 세포자동자는 주변 문맥에 아주 민감하다. 약간만 교란시켜도 원래의 패턴과는 완전히 다른 양상으로 발전한다. 그런 면에서 이 랭턴의 개미에는 흥미로운 점이 있다. 교란에도 불구하고 하이웨이가 항상 만들어진다는 것이다. 지금까지의 관찰의 결과 아직 이것의 반례를 찾지 못했다. 그렇다면 이 랭턴의 규칙속에는 배열방식에 독립적인 (즉 초기조건에 무관한) 하이웨이의 존재가 함의되어 있는 것인가?
2. 이 "랭턴의 개미"를 실행하고 몇가지 의문들을 실험해볼 수 있는 소프트웨어를 소개한다. Ed Richard가 작성한 Ant95라는 소프트웨어이다. 이것은 흑백 두 상태로 되어있는 오리지날 랭턴의 개미를 16상태로 까지 확장하고 있다. 그리고 개미의 경로를 교란시켜 볼 수 있는 장치들도 제공하고 있다. 아래 그림은 Ant95의 실행시킨 것이다. 우측 메인화면은 개미가 하이웨이를 만들고 있는 장면이다.
그림 2 메인화면
프로그램을 실행시키면 메인 화면의 바탕색이 위의 그림과는 달리 검정색으로 되어 있을 것이다. 규칙을 랭턴의 표준에 맞추기 위해서 이 바탕색을 흰색으로 바꾸는 것이 좋겠다. 메뉴의 BackGround를 White에 맞춰주기 바란다.
준비되었다면 랭턴의 규칙에 대한 연습부터 해보자. 우선 우측 툴바의 중간쯤의 Manually Position Ants를 선택해 두자. 다음 Help→Step by Step을 선택한 다음 OK를 누르고 화면의 중간쯤에 점하나를 찍어보자. 꽁무늬에 검은 셀을 단 개미 아이콘이 나올 것이다. 이 개미가 다음 세대에서는 어디로 이동할까? 초기배열이 그림1의 세대1처럼 되었다고 해보자.(배열이 랜덤하게 주어지므로 실제 여러분의 컴퓨터에 나타난 배열이 이것과 다를 수가 있다.) 현재의 상태가 백이므로 진행방향에서 좌측으로 한칸 움직일 것이다. 그리고 머물렀던 셀은 흑색으로 바뀔 것이다. 이 결과가 그림1의 세대2이다. 개미의 행로를 머릿속에 계산해 본 다음 좌측 툴바 상단의 Single Step을 클릭하라. 세대2의 결과를 보여줄 것이다. 이런식으로 그림1의 세대 12까지를 따라가면서 랭턴의 규칙을 익혀두자.
랭턴의 오리지날 버전은 흑, 백 두 상태만을 사용한다. 리차드의 Ant95는 16가지의 상태를 허용한다. 이 16가지의 상태에는 16가지의 색이 배당되어 있다. Ant_States→Multiple States를 클릭하면 아래와 같은 대화상자가 뜬다.
그림 3 상태에 관한 정보
랭턴의 규칙은 STATE 0과 1만을 사용하는 것이다. 이것을 랭턴규칙으로 바꾸려면 DIRECTION에 RL만을 입력시키면 된다.(주의! 디폴드는 LR로 되어있다.) 위의 사례는 12상태를 사용하고 있다. COLOR 흰 색에서 연록색 까지, STATE 0에서 B까지, DIRECTION은 LRRLRLRRRRRL이다. 지금 개미가 청색격자(2번)상에 있다고 하자.(그림4-1) DIRECTION의 3번째를 보면 R이다. 개미는 진행방향에서 오른쪽으로 회전한다. 그리고 격자는 2의 후속번호인 3번의 녹색으로 변한다.(그림4-2) 그러면 녹색의 경우 색은 무엇으로 변할까? 4번 연청색으로 변한다.(그림4-3) B번 초록의 경우 어떤 색으로 변할까? 그것은 색채순환의 방식으로 0번 흰색으로 연결된다. (그림4-4)
그림 4 다중상태 규칙표에 의한 개미의 이동
3. 메인화면의 메뉴의 3번째에 Ant Food가 있다. 앞서 랭턴의 개미는 어떻게 패턴을 교란시키더라도 결국은 하이웨이를 다시 복원해낸다는 점을 지적했다. 그러면 실제 이것을 교란시켜 볼 수 있도록 여러 가지 옵션을 제공하고 있는 것이 Ant Food이다. 화면안에 사각형을 그려넣거나 점을 무작위적으로 찍는 방법... 등 여러 가지 옵션들이 있다. 교란이 행해지면 처음에는 상당한 기간동안 개미의 걸음은 아주 혼돈적이다. 그러나 어떤 단계에 이르면 걸음이 정리되면서 신기하게도 하이웨이가 만들어진다.
이제 좌측의 툴바를 보자. Go는 연속적으로 Play시키는 것이고, Single Step은 클릭할 때 마다 한 세대 진행시키는 것이다. Clear는 메인화면의 화면을 지울 때 사용한다. Population막대는 개미의 수를 셋업하는 것인데 최대 95마리 까지 심을 수 있다.(이 소프트웨어의 제목 Ants95는 여기서 따온 것이라고 한다. Windows95와는 아무 상관이 없다.) 바로 그 아래에 개미의 사이즈 조절 막대가 있다. 최소1에서 최대 100까지 조절이 가능하다.
그 바로 아래에 초기에 개미들을 배열하는 방식에 대한 옵션들이 나와있다. 개미들을 랜덤하게 배열할 수도 있고 랜덤하더라도 국소적으로 편차를 두어 어떤 지역에 개미들의 밀도를 크게 할 수 있다. Partially Random Ants를 선택하면 아래에 분산의 정도나 분포 지역을 조절할 수 있는 조절단추가 활성화된다. 다음의 Manually Position Ants는 이용자가 개미의 위치를 직접 조절하고자 할 때 사용한다.