랭턴루프는 복사의 아포리아를 어떻게 해결했는가?
랭턴 루프는 mcell의 userDLLs/DNA.mcl을 클릭하면 구동시킬 수 있습니다.
1. 폰 노이만과 복사의 아포리아
생명체가 생명체를 복사하는 것은 복사기가 서류를 복사하는 것과는 다르다. 그것은 자기자신을 복사하는 것이며 구태여 비교하자면 복사기가 복사기를 복사하는 것과 같다. 이것은 복사기가 자기 내부에 복사기 제조공장을 갖고 있어야 한다는 것을 의미한다. 그러나 이것은 아직 해결책이 아닌데 그렇게 해서 생산된 2세대 복사기는 다음세대의 복사기를 생산하지 못하는 불임의 복사기일 것이기 때문이다. 이것은 생명체의 복사와는 다르다. 생명체는 복사된 것이지만 자신도 복사를 수행할 수 있다. 그러므로 복사기가 생명체와 닮기 위해서는 복사기가 복사기와 함께 복사기 제조공장도 함께 복사해야 한다. 그러나 복사기를 복사하기 위해서는 복사기 제조공장이 필요하듯이 복사기 제조공장을 복사하기 위해서는 복사기 제조공장을 복사하는 복사기 제조공장의 공장이 필요할 것이다. 그러나 이것이 갖추어졌다 하더라도 다시 다음 3세대에서 불임이 될 것이다. 복사기의 복사의 연속성이 보장되기 위해서는 복사기 제조공장의 공장의 공장의....무한한 공장이 복사기 속에 내장되어 있지 않으면 안 된다.
이것은 생명체의 복사가 논리적으로 불가능하다는 것을 의미한다. 그러나 이 곤혹스러운 난관에도 불구하고 생명체는 그 복사를 아무런 어려움 없이 해치운다. 도대체 생명체는 어떤 방법으로 이 난관을 뛰어넘는 것일까? 40년대 말 폰노이만(von Neumann)은 이 파라독스를 해결하기 위해 골몰하고 있었다. 치밀한 분석의 결과 이 파라독스를 해결하기 위해서는 복사가 두 번 실행되어야 한다는 결론에 도달했다.
우선 생명체에 대한 자기 기술(discription)을 포함하고 있는 유전자를 복사하는 것이다. 이것은 유전자에 대한 단순한 기계적 복사이다. 그 다음 유전자의 지령에 따라 실제 생명체를 만드는 복사가 행해진다. 이렇게 만들어진 생명체 안에 앞서 복제해 놓은 자기기술을 넣어주면 된다. 그러면 이 자손도 그 기술에 따라 새 생명체를 복사할 수 있을 것이다. (이 생명의 자기복사적 특성이 종묘회사를 곤란하게 한다. 자동차를 팔면서 자동차에 대한 설계도를 함께 넘겨주지는 않는다. 그러나 종묘회사는 씨앗을 팔면서 그 설계도도 같이 넘겨주게 된다. 농부는 설계도를 넘겨받았기 때문에 원리적으로는 다시 그 씨앗을 살 필요가 없다. 종묘회사는 이것을 막기 위한 여러 가지 방법들을 강구하고 있다. 그 가운데 하나가 몬산토사에서 개발해서 말썽이 되었던 터미네이터이다. 그 씨앗의 후손을 심으면 싹이 나지 않고 썩어버리도록 유전자 조작되어 있다.) 말하자면 자동차를 복사할 때 자동차 자체만을 복사해서 넘겨주는 방식이 있고 그와 함께 설계도도 복사해서 넘겨주는 방식이 있다. 후자의 방식이 생명체의 복사의 방식이다.
그 후 왓슨과 크릭에 의해서 DNA의 구조가 해명되면서 DNA와 RNA의 정보의 복사(복제와 전사 replication, transcription)와 리보솜의 몸의 복사(번역 translation) 등 두 종류의 복사가 있다는 것이 밝혀졌다. 폰노이만의 통찰이 옳았음이 입증된 것이다. 물리학자 프리먼 다이슨은 "우리가 아는 한, 바이러스 보다 큰 모든 미생물의 기본적 설계는 폰 노이만이 예상했던 구조와 정확히 일치한다."고 폰노이만의 천재성에 감탄했다.
그림 1 폰 노이만의 자기재생산 기계. 상단의 construction control은 몸체를 복사하는 것이고 하단의 tape control은 몸체에 대한 기술을 복사하는 것이다.
이 폰노이만의 복사자는 5개의 이웃, 29개의 내부 상태를 갖는 20만개의 셀들로 구성되어 있다. 이것은 너무 복잡해서 폰노이만 외에는 아무도 그것을 이해했을 것 같지 않다. 물론 그 당시의 컴퓨터로는 그것을 실행해 보는 것은 어림없었다. 폰노이만의 설계가 이렇게 복잡하게 된 데에는 이것이 단순히 복사자로서 설계된 것이 아니고 그 외 연산기능, 운동기능 등을 포괄하는 보편적 기능을 갖는 것으로 설계되었기 때문이다. 그래서 이것은 엄밀하게 말해서 복사자라기 보다 버크스가 명명했듯이 "보편적 구성자"(universal constructor)이다. 생명을 그럴듯하게 모사하고자 하는 한 불가피한 복잡성이기도 하다.
코드은 보편적 구성자라는 엄격한 요구를 완화함으로써 폰노이만의 모델을 단순화시켰다.(Codd, 1968) 이제 이것은 5개의 이웃에 8개의 내부 상태를 갖도록 설계되었다. 그러나 그 과정에서 셀의 수는 오히려 늘어 무려 1억개로 되어 있다. 뒤에 셀의 수는 95,000개로 까지 줄일 수 있었다.(Devore, 1992)
랭턴(C.Langton)은 컴퓨터에 생명의 현상을 구현해 보기 위해서 폰노이만의 조건을 훨씬 더 완화시켰다. 이제 보편적 구성자로서의 기능을 포기하고 생명의 가장 핵심적인 기능, 즉 복사기능만을 구현해 보고자 했다. 이렇게 완화시킴으로써 대폭 단순화시킨 모델을 만들어 낼 수 있었는데 랭턴의 복사자는 코드의 모델과 같이 8개의 내부상태를 갖지만 그 셀들의 수는 고작 94개이다! 151 세대만에 자신과 똑같은 형태를 만들어 낸다. 물론 이것은 그 속에 자신에 대한 기술(discription)도 갖고 있기 때문에 이것 역시 자신을 복사할 수 있다! 랭턴은 최소한의 복잡성을 사용해서 생명체를 근사하게 본뜨는데 성공할 수 있었던 것이다. 어떻게 이것이 가능했을까?
2. 랭턴의 복사자
랭턴의 복사자는 세포자동자의 일종이다. 세포자동자를 규정하는 것은 다음 세가지이다.
1. 세포당 가지는 상태의 수. 세포 당 두 상태만을 가지는 2진수의 세포자동자는 가장 다루기 쉬우며 가장 널리 연구되어온 것이다. 그러나 어떤 상황에서는 더 많은 상태를 가지는 세포자동자를 연구하는 것이 유용할 경우도 있다. 예컨대 폰노이만은 29개의 상태를 가지는 자기재생산 세포자동자를 연구했다. 랭턴의 복사자는 8개의 상태를 갖는다.
2. 세포의 '이웃'(neighborhood)을 구성하는 방식. 여기서 이웃이란 어떤 세포의 다음 세대에 영향을 줄 수 있는 인접한 세포이다. 이웃은 그 세포자신도 포함한다. 1차원 세포자동자에서 이웃을 정의하는 가장 흔한 방식은 어떤 세포의 좌우에 있는 하나 또는 두 세포이다. 2차원 세포자동자의 경우 두 가지 정의방식이 널리 연구되어 왔다. '폰노이만 이웃'(von Neumann neighborhood)과 '무어 이웃'(Moore neighborhood)이 그것인데 전자는 어떤 세포의 동서남북의 넷 세포가 이웃이고, 후자는 거기에 동서, 서남, 남북, 북동의 넷 세포를 부가한 8개의 세포가 이웃이다. 랭턴의 복사자는 폰 노이만 이웃을 사용한다.
그림 2 폰 노이만이웃과 무어이웃
3. 다음 세대에서 그 세포의 상태를 규정하는 진화의 규칙. 규칙은 이웃세포의 가능한 상태의 배열 집합 가운데 어떤 것을 선택함으로 만들어진다. 초기 상태가 주어지면 그것의 이웃의 상태가 분석되고 여기에 주어진 규칙이 적용됨으로써 그 세포의 다음 상태가 결정된다.
랭턴의 복사자에서 규칙의 수는 얼마인가? 이웃이 둘(3셀)이고 1,0 의 두 상태를 갖는 1차원 세포자동자를 생각해 보자. 이 경우 배열의 수는 얼마일까? 행이 2이고(상태=2), 열이 셋(셀의 수=3)인 행렬이다.
0 0 0
1 1 1
1행부터 차례로 읽으면 000, 001, 010, 011, 100, 101, 110, 111 이다. 이것을 앞서 세포자동자에서 아래와 같이 표현했다.
그림 3 이웃이 2(3셀)인 1차원 세포자동자의 배열
배열의 수는 2×2×2=8개이다. 그렇다면 규칙의 수는 얼마인가? 8개의 배열이 1 또는 0이 될 수 있으므로 2×2×2×2×2×2×2×2=2^8=256 개다. 똑같은 요령으로 랭턴의 복사자의 배열의 수와 규칙의 수가 얼마인지를 알아보자.
우선 배열의 수. 행이 8(상태의 수=8)이고 열이 5(셀의 수=5)인 행렬이다.
0 0 0 0 0
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
4 4 4 4 4
5 5 5 5 5
6 6 6 6 6
7 7 7 7 7
1행부터 차례로 읽어 보자. 00000, 00001, 00002 ... 00007, 00010, 00011, 00012,... 00017, ...00020, 00021,.. 이런 식으로 읽어 가면 제일 마지막이 77777이 될 것이다. 그러므로 총수는 8×8×8×8×8 =32,768 이 된다. 이 32.768의 배열이 각각 0에서 7까지의 8개의 값 가운데 하나를 가질 수 있으므로 가능한 규칙들의 수는 8×8×8×8×8×.... 즉 8을 32,768번 곱한 수이다. 수가 엄청나게 커서 감이 오지 않는데 이럴 때는 아주 간단한 1차원 3셀의 위 도식에 넣어 유추해 보는 것이 좋다. 위 도식의 그 배열들이 32,768개(1차원 3셀의 경우 고작 8개)가 죽 늘어서 있고 각 배열마다 하단의 박스에 8색 가운데 하나를 입력할 수 있다(1차원 3셀의 경우 흑, 백 2색)고 상상해 보자. 그림이 떠오를 것이다.
이 엄청난 수의 규칙들의 집합 가운데 랭턴의 복사자를 만들어내는 직접적 규칙의 수는 고작 108개이다. 8^32,768 가운데 108개라니...모래사장에서 바늘찾기 보다 훨씬 더 어려운 작업이다. 이제 이 규칙들이 만들어내는 복사자를 감상해 보도록 하자. 아래는 mcell에서 구동시킨 랭턴의 복사자이다.
그림 4 랭턴의 복사자의 초기배열. 아래는 색채조견표.
mcell을 구동시킨 다음 userDLLs 항목의 DNA.mcl을 선택하면 랭턴의 복사자의 초기배열이 뜬다. 8개의 상태가 있으므로 검정에서 연청색 까지 8개의 색들을 각 상태에 할당했다. 각 색에 할당된 번호를 확인하려면 하단의 팔렛트처럼 생긴 부위를 클릭하면 된다. 그러면 위에서 보는 것 같은 Colors/states bar가 뜬다.
우선 ▶∞을 크릭해 보자. 아주 빠르게 자신을 복제하는 모습을 보여줄 것이다. 일단 복제를 감상하자. 다음 이것을 중단시키고 ▶1을 눌러 한 타임 한 타임의 변화를 따라 가보자. 여기에 어떤 규칙들이 적용되고 있는지 이 관찰만으로는 이해하기 어려울 것이다. 이제 여기에 어떤 규칙들이 적용되고 있는지 그리고 그것이 어떻게 셀의 배치와 상태에 변화를 일으키는지를 검토해 보자.
3. 랭턴의 복사자의 규칙표
아래는 랭턴의 복사자에 적용되는 규칙들을 모아놓은 것이다.( 완전히 매거되지는 않았고 복제에 연관되는 규칙들을 중심으로 정리했다)
0 0(0)0 0 → 0 0 0(0)0 1 → 2 0 0(0)0 2 → 0 0 0(0)1 0 → 2
0 0(0)1 1 → 2 0 0(0)1 2 → 2 0 0(0)2 0 → 0 0 0(0)2 1 → 2
0 0(0)2 1 → 2 0 0(0)2 2 → 0 0 0(0)3 2 → 0 0 0(1)0 0 → 0
0 0(1)0 1 → 1 0 0(1)1 0 → 1 0 0(2)0 1 → 2 0 0(2)0 2 → 2
0 0(2)0 7 → 1 0 0(2)1 0 → 2 0 0(2)1 2 → 2 0 0(2)2 2 → 2
0 0(2)4 2 → 3 0 0(2)5 2 → 2 0 0(2)6 2 → 0 0 0(2)7 2 → 2
0 0(3)2 1 → 0 0 1(0)0 0 → 2 0 1(0)0 2 → 2 0 1(1)0 0 → 1
0 1(0)0 2 → 2 0 1(2)0 0 → 2 0 1(3)0 2 → 0 0 2(0)0 0 → 0
0 2(0)0 1 → 2 0 2(0)0 2 → 0 0 2(0)0 3 → 0 0 2(0)1 0 → 2
0 2(0)2 0 → 0 0 2(0)2 1 → 5 0 2(1)1 7 → 0 0 2(1)2 0 → 6
0 2(1)2 1 → 1 0 2(1)2 4 → 4 0 2(1)2 7 → 7 0 2(2)0 0 → 2
0 2(2)0 2 → 2 0 2(2)0 4 → 3 0 2(2)0 5 → 2 0 2(2)0 6 → 0
0 2(2)2 0 → 2 0 2(2)2 1 → 2 0 2(2)2 2 → 2 0 2(0)2 3 → 2
0 2(2)2 5 → 0 0 2(2)2 6 → 2 0 2(2)2 7 → 2 0 2(2)7 0 → 3
0 2(3)0 1 → 3 0 2(3)1 0 → 1 0 2(4)2 1 → 0 0 2(4)3 2 → 1
0 2(5)2 7 → 2 0 2(7)2 1 → 0 0 2(7)2 5 → 5 0 3(0)0 2 → 0
0 4(2)0 2 → 2 0 5(2)0 2 → 0 0 6(2)0 2 → 2 0 7(2)0 0 → 1
1 0(0)0 0 → 2 1 0(0)0 2 → 2 1 0(0)1 0 → 2 1 0(0)2 0 → 2
1 0(1)0 0 → 1 1 0(1)7 2 → 0 1 0(2)0 0 → 2 1 0(3)0 2 → 1
1 1(0)0 0 → 2 1 1(1)1 1 → 0 1 2(0)0 0 → 2 1 2(0)2 0 → 5
1 2(0)2 4 → 1 1 2(0)2 7 → 1 1 2(1)2 0 → 1 1 2(1)2 1 → 1
1 2(1)2 3 → 1 1 2(1)3 2 → 1 1 2(2)0 0 → 2 1 2(2)2 3 → 1
1 2(2)2 7 → 0 1 2(4)2 0 → 0 1 2(5)2 2 → 0 1 2(7)2 0 → 0
1 2(7)2 7 → 7 1 4(0)2 2 → 0 1 7(1)0 2 → 0
2 0(0)0 0 → 0 2 0(0)0 2 → 0 2 0(0)1 0 → 2 2 0(0)1 2 → 5
2 0(0)3 2 → 2 2 0(1)1 2 → 1 2 0(1)4 2 → 4 2 0(1)7 2 → 7
2 0(2)0 2 → 2 2 0(2)2 2 → 2 2 0(2)3 2 → 1 2 0(2)5 2 → 0
2 0(2)6 2 → 2 2 0(4)1 2 → 0 2 0(5)7 2 → 2 2 0(7)1 2 → 0
2 0(7)5 2 → 5 2 1(0)0 0 → 2 2 1(0)0 2 → 5 2 1(0)4 2 → 1
2 1(0)7 2 → 1 2 1(1)0 2 → 1 2 1(1)1 2 → 1 2 1(1)3 2 → 1
2 1(2)0 0 → 2 2 1(2)0 2 → 2 2 1(2)1 2 → 2 2 1(2)3 2 → 0
2 1(2)7 2 → 0 2 1(3)0 0 → 3 2 1(4)0 2 → 0 2 1(5)2 2 → 0
2 1(7)0 2 → 0 2 1(7)7 2 → 7 2 2(0)0 0 → 0 2 2(0)1 4 → 1
2 2(1)3 1 → 0 2 2(2)0 0 → 2 2 2(2)0 2 → 2 2 2(2)2 0 → 2
2 2(2)2 2 → 0 2 2(4)3 0 → 0 2 2(5)1 2 → 0 2 2(5)2 1 → 0
2 3(0)0 2 → 2 2 3(1)1 2 → 1 2 3(2)1 2 → 0 2 4(0)1 2 → 1
2 4(0)2 1 → 1 2 4(1)0 2 → 4 2 5(2)0 2 → 0 2 5(7)0 2 → 5
2 6(2)0 2 → 2 2 7(0)1 2 → 1 2 7(1)0 2 → 7 2 7(1)1 2 → 7
2 7(2)0 2 → 2 2 7(2)1 2 → 0 2 7(5)0 2 → 2
3 0(4)2 2 → 1 3 1(1)2 2 → 1 3 2(0)0 0 → 0 3 2(0)2 0 → 2
3 2(1)1 2 → 0 3 2(1)2 1 → 1 3 2(2)2 0 → 1 3 2(2)2 1 → 0
3 2(4)0 2 → 0 3 3(3)3 3 → 0
4 0(2)2 0 → 3 4 2(0)2 1 → 1 4 2(1)2 0 → 4 4 2(2)0 0 → 2
4 4(4)4 4 → 0
5 2(2)0 0 → 0 5 2(2)2 0 → 0 5 2(7)2 0 → 5 5 5(5)5 5 → 0
6 2(2)0 0 → 2 6 2(2)2 0 → 2 6 6(6)6 6 → 0
7 0(2)0 2 → 3 7 2(0)2 1 → 1 7 2(1)1 0 → 0 7 2(1)2 0 → 7
7 2(2)0 0 → 2 7 2(2)2 1 → 0 7 2(5)2 0 → 2 7 2(7)2 1 → 7
7 7(7)7 7 → 0
# #(2)2 2 → 2 # 2(2)# 2 → 2 2 #(2)2 # → 2 2 2(2)# # → 2
(#에는 0,1,2,3,4,5,6,7 의 임의의 수가 들어갈 수 있으므로 각각 8×8=64가지의 규칙들을 갖는다.)
이 규칙이 무엇을 의미하는지 구체적 예를 가지고 살펴보자. 상단의 화면에서 color/states bar의 빨간색을 마우스로 클릭한 다음 화면을 클릭하면 빨간셀이 하나 생성된다. 다음 ▶1을 클릭하면 오른쪽과 같이 변화한다.
그림 5 하나의 빨강색 셀이 다음 세대에 4개의 청색 셀로 바뀐다.
규칙표에 따라 빨간색 셀에 어떤 변화가 일어났는지를 살펴보자. 빨간색 셀은 색채표를 보면 1이다. 나머지는 모두 검정색인데 이것은 0이다. 이 상태를 번호로 나타내면 아래와 같다.
그림 6 중앙셀(1)에 영향을 주는 것은 동, 서, 남, 북의 4 셀(노란색으로 표시한 것)이다.
폰노이만 이웃을 택하고 있으므로 중앙셀(1)에 영향을 주는 것은 동, 서, 남, 북의 4 셀(노란색으로 표시한 것)이다. 자신이 상태1이고 이웃 4셀이 상태0인 것을 0 0(1)0 0 으로 표기하기로 한다. 이 다섯자리 수열의 다섯째 자리는 북쪽셀, 네째 자리는 서쪽셀, 셋째 자리는 중앙셀(중앙셀임을 강조하기 위해 괄호안에 넣었다.), 둘째 자리는 동쪽셀, 첫째 자리는 남쪽 셀을 나타낸다. 규칙표에서 0 0(1)0 0을 찾아보자. 0 0(1)0 0 → 0 으로 되어 있을 것이다. 중앙셀은 다음 세대에서 0이 된다는 것을 의미한다. 0은 색채표에서 검정이므로 중앙셀이 빨간색(1)에서 검정색(0)으로 바뀔 것이다. 확인해 보면 그대로이다. 그러나 이것으로 끝난 것이 아니다. 다른 셀들의 변화도 보아야 한다. 북쪽셀의 경우 이것을 중앙셀로 보면 0 0(0)0 1 이다. 규칙표를 찾아보면 그 다음 값은 2이다. 따라서 청색으로 바뀔 것이다. 서쪽셀의 경우는 0 0(0)1 0 , 동쪽셀은 0 1(0)0 0, 남쪽셀은 1 0(0)0 0 으로 그 값이 모두 2이다. 따라서 동서남북의 셀들은 모두 검정에서 청색으로 바뀔 것이다. 그 외의 다른 셀들은 모두 0 0(0)0 0 이므로 규칙표에 따라 0 이기 때문에 아무런 변화가 없다.
이제 규칙표의 의미는 대략 파악되었으리라 생각한다. 랭턴의 복사자를 한 세대씩 진행시키면서 규칙이 어떻게 적용되고 있는지를 살펴보자.
4. 거시적으로 살펴보기
우리는 지금까지 한 셀 한 셀이 규칙에 따라 어떻게 바뀌는지를 미시적으로 추적해 왔다. 이제 그 원리를 알았으니 구체적 작동은 컴퓨터에 맡겨 두고 이 루프의 흐름을 거시적 측면에서 살펴보자. 거시적으로 보면 이 동작은 하나하나 규칙을 따질 때와는 달리 그렇게 복잡하지 않다.
청색 셀(2)은 복사자의 껍질처럼 보인다. 이것은 변하지 않고 그 안에 들어있는 일련의 셀들이 시계반대 방향으로 한번에 한칸씩 이동한다. 사각형의 하단 우측에 이르면 셀이 복사되어 하나는 사각형의 루프를 따라 상단으로 가고 다른 하나는 진행방향으로 계속 가면서 꼬리를 늘린다. 여기서 7 0 은 핵심적 코드로서 자신을 계속 자라게 하면서 자신의 정보를 복제하는 기능을 한다. 아래는 5세대(그림7 상단 좌)에서 10세대(그림7 하단 우)에 이르면서 꼬리가 한 칸 길어진 것(5칸에서 6칸)을 볼 수 있다.(이것은 패턴에 대한 기술이며 왜 그렇게 되는가에 대한 설명이 규칙의 적용이다. 이 기술에 대한 설명을 시도해 보기 바란다)
그림 7 정보의 해석..루프의 증식
청색 셀로 된 사각형의 루프가 몸체이고 그 안의 셀들이 그 루프를 만드는 정보라고 볼 수 있다. 사각형의 하단 좌측 모서리에서 셀이 복사되면서 원본은 루프 안으로 되돌아간다. 그러나 복사본은 루프 바깥으로 꼬리를 만들면서 자라는데 이것을 자라게 하는 것은 청색 셀 안에 들어있는 셀들 즉 정보들이다. 이것은 정보의 해석에 해당된다. 꼬리가 자라서 모체를 닮은 루프가 완성되면 이제 이 정보는 해석되지 않고 그 사각형 안에 내장된다. 이것은 정보의 복제에 해당된다. 아래 그림은 복사가 완성되어 딸 루프가 만들어지는 순간(124세대-127세대)을 보여주고 있다.
그림 8 해석되지 않은 정보..정보의 복제
랭턴의 루프는 자신을 복사했을 뿐 아니라 자신에 대한 기술(discription)도 복사했다. 그러므로 복사된 이 딸 루프도 자신을 복사할 수 있다. 이 랭턴의 루프는 복사의 파라독스를 완벽하게 해결하고 있다. 이것은 기계의 복사와는 다르며 생명의 복사를 근사하게 흉내내고 있다.
랭턴 루프외 몇가지 유형의 복사자를 모아놓은 소프트웨어 다운받기