세포자동자

 

복잡성의 과학 : 장은성 지음, 전파과학사, 1999, Page 247~326
 

     (1) 복잡성 과학에 대한 수학

     (2) 우주는 세포자동자이다

     (3) 양자우주와 세포자동자

1. 세포자동자란 무엇인가?

     (1) 세포자동자는 생물학 용어가 아니다

     (2) 세포의 기하학

     (3) 경계조건

     (4) 세포의 이웃

     (5) 세포의 상태

     (6) 세포자동자의 상태변환 규칙

     (7) 세포자동자의 종류

2. 세포자동자의 역사 

     (1) 어떤 문제라도 푸는 기계

     (2) 유한상태 기계의 수학적 정의

     (3) 상태 천이도

     (4) 오토마타

     (5) 생물의 환경적응과 오토마타

     (6) 짚신벌레의 의식

      (7) 노이만형 컴퓨터

     (8) 생명게임 (Life Game)

     (9) 생명게임의 여러 가지 패턴

     (10) 랭턴의 자기증식 루프

3. 1차원 세포자동자 

     (1) 스테펜 울프램

     (2) 세포자동자와 복잡성

     (3) 1차원 2상태 3이웃 세포자동자

     (4) 시공패턴

     (5) 세포자동자의 상태천이 규칙

     (6) 규칙의 분류

4. 세포자동자의 거시적 역할 

     (1) 세포자동자의 역학

     (2) 세포자동자의 세계

     (3) 상보적인 규칙

     (4) 거울상(경상)의 시공패턴

     (5) 반사규칙 Rr

     (6) 시공패턴의 주기

 

바닷가의 수면에서 미역 따위가 자라는 모습이나 호수의 수면에서 물풀이 자라는 모습과 매우 흡사한 패턴을 만드는 세포자동자

(1) 복잡성 과학에 대한 수학

현재 복잡성의 과학은 매우 산만하고 애매한 상황이다.  혁명기의 사회 분위기가 그렇듯이 신생과학인 복잡성의 과학은 기존의 보수적인 과학관을 모두 거부하고 새로운 우주관을 발판으로 하기 때문에 더욱 큰 혼란을 초래하고 있다.

과학사를 뒤돌아보면 새로운 과학이론이 등장하기 위해서는 먼저 수학적인 개념이 선행되어 정착되어야 했다. 그러나 과학이 진보하는 속도가 점차 빨라지면서 과학이 수학보다 앞서 나가는 지경에 이르렀다. 마치 철길이 수학이고, 그 위를 달리는 기차가 과학이라면 철길 공사를 하고 있는 곳까지 기차가 다다랐기 때문에 기차도 더 이상 나아가지 못하는 형국이 되었다.

복잡성의 과학이 정비되기 어려운 이유는 이런 점에도 있지 않은가 하는 생각이 든다.

지금 수학에서는 복잡성에대한 연구가 거의 이루어지지 않고 있다. 단지 프랙탈 기하학만이 복잡성에 대한 기하학적 접근을 시도하고 있을 뿐이다.

과거 미적분학이 탄생하던 시절, 무한과 연속 개념에 대한 오랜 논쟁 속에서 이들 개념에 대한 수학적 정의가 이루어지고 그 위에 미적분학이 정립된 다음에서야 뉴턴의 고전역학이 완성될 수 있었음을 상기한다면, 지금 수학계에서는 복잡성에 대한 어떤 검토도 이루어지지 않고 있기 때문에 복잡성의 과학이 과학으로서 자리잡기가 어려운 것이 아닌가 생각된다.

이에 필자는 세포자동자가 그런 역학을 할 수 있을 것으로 제안한다. 어떤 시스템이 복잡하다는 것을 수학적으로 정의를 내려야 하는 것이다. 

(2) 우주는 세포자동자이다

세상을 이해하는 데는 여러 가지 방법이 있다. 그 중에서도 세포자동자를 통한 세상바라보기는 가장 폭넓은 방법이 될 것이다. 실제로 우리 인체만 살펴보더라도 약 60 조라는 세포로 구성된 거대한 세계이다. 지금의 인류가 50 억 (1987 년 통계) 인 것에 비교하면 엄청나게 큰 서계라는 것을 알 수 있다.

한 인간을 이루는 이 60 조 개의 세포는 그 사람과 평생을 함께 하는 것이 아니고 계속 새로운 세포가 생겨나고 성장하고 죽어 가는 세대교체를 계속하고 있다. 세포의 삶과 죽음은 주위의 세포들과 밀접하게 관련되어 있다. 예를 들어 뇌세포는 간 조직에서는 제 기능을 발휘할 수 없는 데다 살아갈 수도 없고, 간세포도 허파 조직에 들어가서는 살아갈 수 없다.

유유상종이라는 말이 있는 것처럼 세포들도 같은 성질을 갖는 세포끼리 모여서 조직을 형성하고 그 속에서 삶과 죽음의 세대교체를 하고 있다. 이러한 세포들의 생명활동의 모임이 바로 한 사람의 활동상으로 드러나는 것이다. 각각의 세포들이 건강하고 잘 조직되어 있으며 잘 협동하면 그 사람은 원기왕성하고 건강한 삶을 유지할 것이고, 세포들이 무력하거나 조화가 깨져 있으면 그 사람은 어딘가에 질병이 있거나 매우 피곤을 느끼게 될 것이다.

따라서 세포들의 활동상을 간단하게 연구하는 방법이 있으면 좋을 것이다. 세포들은 주위의 세포들이 건강한지 허약한지, 새로 태어난 것인지, 노쇠하여 죽어 가는지에 따라 자신의 역할이 결정된다. 이러한 주위의 관계를 무시하고 제멋대로 살아가는 세포가 바로 암세포이다. 이런 의미에서 세포들간의 관계를 좀더 보편적으로 연구하는 방법이 필요해질 것이다.

이 책에서 소개하는 세포자동자는 이러한 목표를 갖고서 연구된 것은 아니지만 나름대로 전혀 무관하지만은 않은 것 같다. 세포자동자를 살펴보면 인체세포들의 생활을 수학적으로 간단히 추상화해 놓았다는 느낌을 받을 것이다.

인간만이 아니라 우주의 삼라만상이 알고 보면 모두가 세포자동자의 일종이라는 생각이 들기도 한다. 주변 사람 중에 하나라도 성공하면 모두가 성공하기도 하고 반대로 주변의 한 사람이 잘못되면 그 영향을 받아서 모두 심각한 어려움에 빠지기도 하는 것을 볼 때 인간사회도 세포자동자의 일종이고, 물질의 변화나 공허한 우주공간의 진화도 세포자동자의 다양한 변화의 모습으로 생각되기도 한다. 이런 것 때문에 세포자동자야말로 우주의 신비를 밝히는 궁극의 이론이 될 것이라고 강력하게 주장하는 사람도 나오고 있다.

이탈리아의 토마소 토폴리 (Tommaso Toffoli) 교슈는 그의 저서 세포자동자 기계 (CAM 1987) 에서 CAM 은 우주를 합성하는 장치라고 주장하고 있다. 에드워드 프레드킨 (Edward Fredkin,1934~) 은 세포자동자를 모델로 우주의 모든 것을 설명할 수 있다.고 주장한다. 프레드킨은 우주가 물질과 에너지로 이루어진 것이 아니라 정보가 그 본질이라고 생각한다. 전자나 광자 등의 소립자도 정보의 공간적인 한 패턴으로 보는 것이다. 원자핵의 궤도를 도는 전자의 운동도 이 패턴이 마치 파동이 옮겨가듯이 움직이는 것으로 설명한다. 입자 자신이 움직이는 것이 아니다. 앞으로 달려드는 파도의 움직임이 바닷물의 움직임이 아닌 것처럼 말이다.

아인쉬타인의 방정식에 의해 물질은 에너지의 다른 모습니다. 그리고 에너지는 정보의 다른 모습이라는 것이 프레드킨의 생각이다. 즉 진공에 에너지가 있고 없고 하는 정보로 볼 수 있다는 것이다. 전 우주에 에너지가 충만해 있다면 그것은 이미 에너지로서의 의미를 상실한다. 물은 높은 곳에서 낮은 곳으로 흐르듯이 에너지는 에너지가 있는 곳에서 없는 곳으로 흐른다.

한마디로 우주는 거대한 컴퓨터라는 것이다. 우주는 정보의 바다이고, 이 우주에 존재하는 모든 것들은 그 정보들 중에서 자기와 관련 있는 정보를 이용해서 자기를 변화시킨다.

필자는 세포자동자이론이 차세대 컴퓨터 구조의 중추적인 이론이 되리라 믿고 있다. 세포자동자의 특성은 병렬적이고 발견적, 창발적, 자기조직적이라는 면에서 인간의 직관적인 사고특성을 보여준다는 것이다. 더구나 카오스이론의 핵심이 되어 있다. 이런 점에서 인공지능을 구현하는 가장 좋은 수학적 모델이라고  생각한다. 

(3) 양자우주와 세포자동자

시간은 연속적으로 흐르고, 공간도 연속적으로 뻗쳐 있다. 에너지도 연속량이다. 근대과학을 확립시킨 뉴턴 (Isaac Newton,1642~1727) 은 이렇게 믿어 의심치 않았다. 그러나 뉴턴의 이런 믿음은 19 세기에 들어와 무참히 깨지고 말았다. 독일의 물리학자 막스 플랑크는 에너지의 변화가 아주 작기는 하지만 불연속적으로 변한다는 것을 알아냈다. 이러한 에너지의 덩어리를 그는 양자라고 불렀다.

우주는 이산 (불연속) 적이다. 우주는 연속적인 아날로그가 아니라 디지털적이다. 우주의 기본적인 구성요소는 바로 양자라는 것을 양자역학은 이야기하고 있다. 세포자동자도 디지털의 세계이다. 즉 세포자동자는 그야말로 모든 것을 설명할 것이다. 세포자동자야말로 아담이 품었던 의구심을 깨끗이 해소시켜 주고 그를 원죄에서 해방시켜 줄 것이다. 이제부터 그 놀라운 세포자동자의 이론을 본격적으로 알아보자. 

1. 세포자동자란 무엇인가?

(1) 세포자동자는 생물학 용어가 아니다

세포라는  말에서 생물학적인 것이라고 생각하겠지만 세포자동자는 물리학과 더 깊은 관계가 있으며 세포자동자는 물리학, 생물학을 비롯하여 인문사회과학 등을 통합하는 종합학문의 성격을 갖고 있다.

필자가 세포자동자에 주목하게 된 동기는 카오스이론을 공부하면서 이다. 카오스이론의 심연에 세포자동자가 숨어있다는 것을 직감하였다. 더구나 세포자동자는 컴퓨터와 아주 관련이 많다. 세포자동자를 연구하는 데는 컴퓨터가 자주 사용되며, 컴퓨터 동작의 기본원리와도 관계가 깊다.

컴퓨터의 이론적 토대를 마련한 수학자는 영국의 튜링이라는 괴짜 수학자이다. 그가 고안한 튜링머신이 오늘날 컴퓨터의 기본원리가 되었으며, 오늘날 컴퓨터의 아버지라고 불리는 노이만은 이 튜링머신을 구체적으로 고안한 것에 불과하다. 그는 튜링머신의 상태를 내부기억장치로 구현해 내어 오늘날의 기본적인 컴퓨터의 구조, 즉 직렬처리 방식의 컴퓨터를 탄생시켰다.

튜링머신을 보다 일반적으로 오토마타(Automata)라고 불는데 이 오토마타를 하나의 세포단위로 생각하고 다음과 같이 병렬로 연결해 놓은 것이 세포자동자이다. 작은 세포들이 결합해서 생물체가 이루어진 것과 마찬가지이다. 따라서 세포자동자는 개개 오토마타의 동작에 의해 결정되는 것이다.

오토마타가 여러 개 연결되어 있기 때문에 전체 세포자동자의 변화는 매우 다양하게 되고 다음에 어떻게 변해 예측하기 어려운 것이다. 

A

A

A

A

A

A

A

A

A

 

 

 

 

 

 

 

 

A

A

A

A

A

A

A

A

A

 

 

 

 

 

 

 

 

A

A

A

A

A

A

A

A

A

 

 

 

 

 

 

 

 

A

A

A

A

A

A

A

A

A

(2) 세포의 기하학

세포자동자에서 사용하는 세포의 기하학적 모양은 임의로 만들 수 있다. 가장 흔하게 사용하는 것은 다음과 같이 규칙적인 기하학적 모양인 정사각형, 정삼각형, 정육각형 등의 모양이 주로 사용되지만 이 책에서는 주로 정사각형 모양을 사용한다.

세포자동자의 모양은 세포자동자의 특성, 즉 세포의 이웃의 개수나 배열방법에 따라 그에 맞는 것을 적절하게 선택하면 된다.

이러한 같은 모양, 같은 크기의 세포들로 빈틈없이 평면을 메우도록 배열한다. 세포자동자의 배열을 한 줄로만 배열할 경우 1 차원 세포자동자라 하고, 평면에 배열하면 2 차원 세포자동자라 한다. 3 차원 세포자동자, 일반적으로 n 차원 세포자동자라도 생각할 수 있지만 그림으로 나타내기 어렵기 때문에 주로 2 차원 이하의 세포자동자를 생각하게 된다.

 

      

(3) 경계조건

세포자동자의 배열을 무한히 펼칠 수 있지만 대개는 유한하게 한정된다. 유한하게 한정된 경우에는 가장 변두리에 있는 세포를 어떻게 처리하느냐의 문제가 있다. 이 문제가 경계조건이다.

1 차원 세포자동자의 경우 맨 앞과 뒤의 세포의 이웃이 하나씩 부족하다. 이 부족한 이웃에 대한 처리를 어떻게 하느냐가 바로 경계조건이다.

경계조건에는 주기 경계조건과 0 경계조건이 있다. 주기 경계조건은 1 차원 세포자동자의 맨 앞 세포와 맨 끝 세포를 이어주는 것이다. 즉 세포들이 원통에 배열된 것처럼 생각하는 것이다.

0 경계조건은 세포 배열의 가장자리 세포의 바깥쪽에 이웃세포가 있다고 생각하고 그 세포의 상태를 무조건 0 의 상태로 보는 것이다.

(4) 세포의 이웃

세포자동자에서 가까이 이웃한 세포끼리는 서로의 상태에 따라서 영향을 주고 받는다. 마치 인간세계와도 같다. 이웃사촌이라는 말처럼 가까운 세포끼리 서로 영향을 준다. 영향을 주고 받는 이웃들을 다음과 같이 임의로 정해 줄 수도 있다.

다음은 보통 자주 사용되는 이웃이다.

 

2 차원 세포자동자에서 생각할 수 있는 여러 가지 이웃들

세포의 이웃은 한 세포의 환경으로서 입력 데이터가 된다.

세포자동자는 불교에서 말하는 연기의 세계이다. 우주만물은 서로의 인연으로 말미암아 생성되고 성장 소멸한다. 인연의 세계는 공간적으로나 시간적으로 가까운 것들끼리 보다 강하게 맺어진다.

세포는 혼자서는 아무 것도 하지 못한다. 마치 절해고도에 갇힌 고독한 인간과 같다. 세포는 세포끼리 모여서 서로 부대끼고 하는 중에 무엇인가 창조되어 나온다. 가장 가까운 이웃세포의 상태에 따라 새로운 세포가 생겨나기도 하고 죽어가기도 한다. 이러한 생사 인연의 파장은 마치 잔잔한 호수에 돌을 던질 때 파문이 퍼져 나가듯이 멀리 있는 세포에게까지도 그 영향이 서서히 미쳐서 그 세포의 생사를 결정하게 된다.

이러한 인연의 세계는 인간사에도 그대로 적용된다. 인간 한 사람 한 사람을 세포로 간주하면 한 인간의 성공과 실패는 파문이 되어 가장 가까운 가족에서부터 점점 그의 친구들과 친척들에게 그 영향이 퍼져 나간다.

산불이 번져 나가는 것도 세포자동자의 현상과 같은 것이다. 한 나무에 불이 붙으면 그에 이웃하고 있는 나무에게도 불이 옮겨간다. 나무 한 그루 한 그루를 세포로 간주하면 불이 붙은 상태, 안 붙은 상태의 변화가 유기적으로 변해 간다. 그래서 소방관들에게는 산불은 마치 살아 있는 괴물같이 생각되는 경우가 있다. 헬리콥터를 타고 공중에서 산불이 번져 가는 모습을 관찰하면 아마도 아메바 같은 생물이 그 위족을 사방으로 뻗치면서 서서히 기어가는 모습으로 보일 것이다. 세포자동자의 아이디어를 이용하는 것의 하나는 매스게임 (단체경기) 에서 보여주는 글자 만들기 등이다.

(5) 세포의 상태

세포자동자에서 한 세포의 상태란 생물학에서의 세포가 세포막으로 구획된 조그만 생명체인 것처럼 세포자동자의 세포는 조그만 네모격자로 구획된 것으로 그 안에 여러 가지 상태. 즉 살아 있음,  새로 태어남, 죽어감, 죽음 등의 상태를 갖는 어떤 알 수는 없지만 동적인 구조가 들어 있다는 것을 뜻한다.

세초자동자에서 '세포' 는 생물학에서 말하는 세포를 포함하여 원자나 분자, 동물개체나 식물개체 등의 존재를 추상화한 개념이다. 따라서 이들 존재가 가진 상태가 가진 상태도 추상된 것이다. 이 상태는 여러 가지로 표현된다. 즉 세포의 상태는 1 (삶), 0 (죽음) 등의 숫자로 나타내기도 한다.

다음은 가장 간단한 두 가지 상태만을 갖는 경우이다.

세포의 다양한 상태를 아라비아숫자로 표현하기도 한다.

정보이론의 창시자 샤논이 증명한 바와 같이 모든 정보를 0 과 1 이라는 단 두 가지 기호로 나타낼 수 있는 것처럼 아무리 다양한 상태를 가진 세포자동자라도 결국에는 0 과 1 이라는 두 가지 상태만을 가진 세포자동자로 환원될 수 있다.

일반적으로 세포자동자는 세포배열의 차원과 세포가 취할 수 있는 상태수에 따라 n 차원 p 상태 세포자동자를 생각할 수 있다.

(6) 세포자동자의 상태변환 규칙

세포 자동자의 상태는 이웃세포의 수와 그 상태에 따라 영향을 받아 상태가 변화한다. 그 변화를 어떤 규칙에 따라 하게 할 것인가를 정한다. 우선 모든 가능한 변화의 경우를 생각하고 거기에서 적당한 것을 택하여 실행하면 된다.

1차원 세포자동자라도 다음과 같이 여러 가지 규칙을 생각할 수 있다.

 

또 세포자동자의 상태변화가 오로지 한 가지만 정해진 결정적 상태변화인가 아니면 2 가지 이상이 되어 어느 것을 확률적으로 선택해야 하는 상태변화가 있다. 이것을 비결정적 세포자동자라고 한다.

(7) 세포자동자의 종류

이제까지 보아온 여러 가지 세포자동자의 조건에 따라 다양한 세포자동자의 종류를 생각할 수 있다. 모든 세포가 같은 양식으로 이웃을 갖는 균일한 상호결합과 그렇지 않은 불균일 상호결합에 따른 균일 세포자동자, 불균일 세포자동자가 있다.

또 상태변화가 결정적인 결정적 세포자동자, 비결정적인 세포자동자, 입력과 그에 관계되는 출력 사이에 시간경과를 인정하는 밀리 (Mealy) 형 세포자동자, 이웃의 상호결합이 시간에 따라 변하지 않는 정적 세포자동자, 시간에 따라 변하는 동적 세포자동자가 있다.

이들 세포자동자는 각각 그 활용목적에 따라 적당히 변형되어 사용된다. 결정적 세포자동자에 대한 유명한 문제로 일제사격 (firingsquard), 즉 각 세포를 사병이라 하고 그 중에 장군이 하나 있어서 모든 세포는 처음에 0(off)의 상태가 있다. 이때 장군세포 하나의 변화로 모든 사병이 동시에 사격을 개시할 수 있는지 어떤지 하는 문제를 상정할 수 있다.

불균일 이웃 세포자동자 (graphical CA), 동적 세포자동자 (Lindenmayer system) 는 생물의 성장. 발육의 모델로 사용되기도 한다.

이제까지 설명한 내용은 세포자동자 이론에서 사용하는 용어의 뜻과 세포자동자의 활용방법을 대략적으로 설명한 것으로서 세포자동자 이론의 입문에 해당한다고 볼 수 있다.

따라서 세포자동자를 깊이 다룬 것이 아니다. 세포자동자의 효용성은 이 이론의 깊은 내용을 읽고 그 구체적인 전개방법을 보면 스스로 파악할 수 있게 된다. 이제부터 본격적으로 세포자동자 이론으로 들어간다. 

2. 세포자동자의 역사 

(1) 사고의 기계화

우리 주변에는 생각하기 싫어하는 사람들이 있다. 이들은 다행인지 불행인지 아담의 정신병을 거의 유전 받지 않은 것이 분명하다. 그들은 흔히 어렵고 복잡하다는 문제들, 예를 들면 수학 문제를 내면 "어휴 수학은 정말 골치 아파!" 하면서 고개를 흔든다.

그렇게 '복잡한 생각' 하기를 싫어하는 사람들을 위해 사람 대신 생각해 주는 기계를 만든다면 어떨까? 사실 이 생각하는 기계는 그런 게으른 사람들을 위해서가 아니고 보다 생각하는 일을 효율적으로 하기 위해 고안되었다. 인간의 생각은 시시각각 다르고 종잡을 수 없는 것처럼 생각되지만 잘 생각해 보면 인간의 생각도 몇가지 종류로 구분할 수 있고 또 어떤 규칙성을 찾을 수도 있다. 즉 같은 생각을 되풀이하면서 아까운 시간을 허비할 수도 있다는 이야기다.

예를 들면 1 + 1 = 2, 1 + 2 = 3 같은 덧셈 문제는 덧셈이라는 한 가지 법칙을 되풀이 생각하는 것이다. 인간은 단순 반복적인 지루한 일을 싫어한다. 생각하는 일도 다른 내용을 계속 반복하는 것은 비능률적이고 지루한 일이다. 지루한 일을 반복하면 짜증이 나고 실수가 일어나기도 한다.

그래서 한 가지 법칙을 단순 반복하여 생각하는 일을 기계에게 시키면 어떨까 하는 생각에서 계산기라는 생각하는 기계를 만들기 시작한 것이다. 사실 프랑스의 수학자 파스칼은 세금 계산으로 온종일 똑같은 덧셈만을 반복해야 하는 아버지를 위해서 손잡이만 돌리면 자동으로 덧셈을 해주는 톱니바퀴 식 계산기를 고안해 냈다.

이 계산기는 계속 개선되어 덧셈만이 아니고 곱셈, 나눗셈 등을 하는 계산기, 더욱이 미적분까지 하는 계산기를 만들게 되었다. 그리고 마침내 아예 모든 수학문제를 기계적으로 처리할 수 있는 만능계산기가 있다면 어떨까? 하는 생각으로 발전한다. 대부분의 수학문제는 어떤 법칙에 따라 풀기 때문에 모든 법칙을 기억하여 어떤 수학문제라도 풀어 주는 계산기를 상상하는 것도 결코 공상만은 아니다. 그리고 인간은 보다 고상하고 창조적인 생각을 하면서 여유 있는 시간을 보낼 수 있을 것이다. 이러한 상상이 가능한 것은 세상일에는 모두 어떤 법칙성이 있다는 오랜 신념에서 비롯된 것이기도 하다. 즉 흔히 속담에 "엿장수 맘대로" 라는 말처럼 자기 멋대로 종잡을 수 없는 인간이 사고에도 어떤 법칙성이 있지 않을까? 하는 믿음에서 인간의 사고를 기계적으로 구현하겠다는 발상이 나왔던 것이다.

더구나 변덕이 심한 여자의 심리를 수학적으로 분석해서 연애를 성공시킬 수 있다는 새로운 수학 '카타스트로피 (파국) 이론' 까지 등장했다. 사람의 생각이 죽 끓듯 변한다고 치부해 버리는 사람에게서는 인간의 사고를 기계화한 '계산기' 라는 발상은 나올 수 없었다. 이 사고의 기계화의 정점이 오늘날 '인공지능', '인지과학' 이라는 신과학으로 나타나고 있다. 그러나 과학자들의 장담과는 달리 인공지능의 구현이 그렇게 쉬운 일이 아니다. 이미 현재의 기술로는 불가능에 가깝다는 결론이 나왔고, 그래서 새로운 모색이 시작되고 있다. 그 새로운 모색에서 가장 주목받는 것이 바로 세포자동자이다.

인간의 두뇌구조는 세포자동자와 같다. 뇌 신경세포 하나 하나의 움직임은 세포자동자의 세포와 다를 바 없다. 인간의 뇌세포는 세포자동자의 세포들이 그렇듯이 병렬적으로 동작하며 비선형적으로 전개되는 도안 전광석화 같은 아이디어를 번쩍 떠올린다. 이것은 세포자동자가 보여주는 거시적인 창발성 바로 그것이다. 사고의 기계화라는 사업은 아마도 세포자동자로 매듭지어질 것이다. 사고의 기계화라는 그 역사를 살펴보자.

(1) 어떤 문제라도 푸는 기계

세포자동자를 이해하는데 필수적이기 때문에 여기서 오토마타 이론을 간단히 소개한다. 오토마타 이론은 문제를 기계적으로 푸는 방법을 연구하는 이론이다.

어떤 문제, 예를 들어 수학문제를 기계에게 맡겨 풀게 하려고 기계를 만든다고 하자. 그렇다면 어떻게 설계해야 할까?

보통 어떤 문제를 해결할 때는 단계마다 절차를 밟아가면서 하나하나 해결해 준다. 즉 복잡한 문제를 단순한 문제로 분해해서 하나씩 해결해 가는 것이다.  이렇게 문제를 분해해서 기계적으로 문제를 하나씩 단계를 밟아 기계적으로 문제를 쪼개야 한다. 그리고 이들 문제를 하나씩 단계를 밟아 기계적으로 해결하면 되는 것이다.

이때 각 단계는 서로 그 내용이 다를 것이기 때문에 이에 대응하는 기계의 상태도 무언가 달라야 한다.

예를 들어 목수가 집을 짓거나 할 때에 각 단계마다 목수가 쓰는 연장이 달라지듯이 기계의 구조가 달라져야 할 것이다. 이 기계의 구조변화를 기계의 상태변화라고 말하는 것이다. 여러 가지 연장을 다룰 줄 아는 목수일수록 그가 만들 수 있는 물건의 가짓수가 많아지는 것처럼 기계의 상태수가 많아질수록 기계가 해결할 수 있는 문제도 많아질 것이다. 그런데 문제가 없는 것이 아니다.

여러 가지 연장을 사용하는 것은 좋지만 그렇게 되면 연장의 종류가 늘어나고 그것을 관리하고 운반하는 것이 번거롭게 된다. 되도록 한 연장이 여러 가지 역학을 할 수 있다면 좋을 것이다. 기계도 상태수가 많아지면 기계를 설계하고 만들기가 어려워진다. 그래서 어떤 문제라도 해결할 수 있는 보편적인 상태를 갖추는 문제가 있는 것이다. 이런 문제를 연구하는 것이 오토마타 이론으로서 기계가 가지는 상태수는 유한한 것이 바람직하기 때문에 유한상태 기계를 생각한다.

(2) 유한상태 기계의 수학적 정의

유한 상태 기계는 보고 듣는 것은 할 수 있지만 자신의 생각을 말할 수 없는 사람과 같다. 즉 입력은 가능하지만 그리고 그 입력으로 자신의 상태가 변하기도 하지만 어떠한 출력도 내놓지 않는 답답한 친구이다. 유한상태 기계를 설명하는 책자들을 보면 내부의 '상태' 를 유지하고 변화시키는 제어장치 (control box) 와 테이프를 판독하는 헤드 (reading head) 로 이루어졌으며 기다란 테이프는 네모 칸으로 구획되어 거기에는 유한 개의 기호가 나열되어 있다고 설명하고 있다.

 

유한상태 기계의 구성

즉 우리의 두뇌는 제어장치이고, 두 눈은 테이프를 판독하는 헤드이며, 우리가 보고 있는 책은 유한 개의 기호가 나열되어 있는 테이프라고 하는 것이다.

이러한 기계를 수학자들은 수학적인 기호로 정의하였다.

유한상태 기계는 유한 개의 내부상태 즉 기계적 구성 s0, s1, s2, …sn, 을 갖고 무한히 긴 테이프에 쓰여진 잘 정의된 유한 개의 기호 p0, p1, p2, …pm, 를 읽을 수 있다. 그리고 자신의 상태와 읽은 기호의 조합에 의해 다음 상태가 결정된다. 따라서 유한상태 기계는 다음 5 가지로 정의된다.

       FSM = (S, P, f, s0, T)

      상태집합 : S = {s0, s1, s2, …sn} (≠ Ø)

      입력기호집합 : P = {p0, p1, p2, …pm}

     ※ S ∩ P = Ø 일 것

      상태전이 함수 : f : S × P → 2S (= S)

      초기상태 : s0

      마지막 상태 : F ( ⊆ S)

이러한 정의에 따르면 길에 굴러다니는 돌멩이도 유한상태 기계이다. 돌멩이도 분명히 어떤 유한 개의 상태를 갖고 있으며, 그 상태는 외부의 압력 (입력) 에 의해 변하기 때문이다. 예를 들면, 입력으로서 햇빛을 많이 받으면 뜨거운 상태가 되고, 차가운 물이 닿으면 온도가 내려가는 상태가 되기도 하고 누군가의 발길에 채어 장소를 옮기는 상태가 되기도 하고 깨어져 두 조각이 되기도 한다. 

(3) 상태 천이도

유한 상태 기계의 전체적인 변화를 한눈에 알아볼 수는 없을까? 그래서 유한상태 기계의 상태변화를 그림으로 나타낸 것이 상태천이도 (transition diagram) 이다.

유한상태 기계를 작은 원 (○) 으로 나타내고 이 원 안에 현재의 상태를 써넣는다. 그리고 입력기호를 화살표 위에 써둔다.

상태 천이도를 그리기 위해서는 먼저 상태전이 도표를 작성해야 한다. 이것은 유한상태 기계의 동작을 전부 표로 작성한 것이기 때문에 동작 일람표라고도 부른다.

          테이프상의 기호

FSM 의 상태

p0

p1

s0

s3

s2

s1

s0

s2

s2

s3

s3

s1

FSM의 동작 일람표

(4) 오토마타

인간의 행동은 사고로부터 비롯된다. 따라서 사고의 기계화는 행동의 기계화ㆍ자동화의 산물이 바로 오토마타이다. 세포자동자의 역사를 제대로 살펴보려면 오토마타의 역사부터 살펴보아야 한다. 오토마타 즉 자동인형은 이미 고대 그리스 시대부터 제작되어 그 후로도 여러 나라에서 다양하게 제작되어 근대에는 아주 정교한 것까지 등장했으며, 어린이들에게 장난감으로 크게 애용되기도 했다.

오토마타의 자세한 소개는 나중에 『컴퓨터의 역사』라는 책자를 통해서 소개할 계획이고, 여기서는 단순하게 세포자동자를 중점적으로 살펴보기 위해 오토마타가 본격적으로 이론화되기 시작한 1936 년까지 거슬러 올라가 보기로 한다.

42 세의 젊은 나이에 동성연애 때문에 음독 자살한 비운의 수학자 튜링 (A. M. Turing. 1912 ~ 54) 과 폴란드에서 미국으로 이민한 논리학자 포스트 (Emil Leon Post, 1897 ~ 1954) 는 거의 동시에 어떤 수학 문제라도 푸는 상상 속의 계산기계를 생각했다. 이것을 튜링기계라고 한다.

괴텔(Kurt Gödel, 1906 ~ 78) 의 불완전성 정리를 증명하는 데 초수학의 산술화라는 방법이 사용된 클린 (S. C. Kleene), 처치 (A. Church) 등의 수학자들은 실제로 계산 가능한, 즉 답을 얻을 수 있는 수학 문제를 분명하게 정리할 필요를 느껴 수학적 정식화를 시도한 결과로서 나온 것이 튜링기계이다.

오래 전부터 수학자들은 모든 수학 문제를 기계적으로 풀이할 수 있는 절차, 이것을 알고리즘이라고도 하는데 이 절차가 반드시 존재하는지를 알고 싶어했다. 이 문제를 공식적으로 제기한 것은 독일 수학자 힐베르트 (D. Hibert, 1862 ~ 1943) 이다. 힐베르트는 1900 년 파리에서 열림 제1회 국제 수학자협회의에서 23 개의 미해결 수학문제를 내놓았다. 여기서 10 번째 문제인 부정방정식의 해가 있는지 없는지를 알아내는 방법이 있는가 하는 문제이다. 이 문제는 곧 모든 수학문제를 일반적으로 해결하는 알고리즘이 존재하느냐는 문제이다. 이 문제의 해결을 위해 수학자들이 덤벼들었다.

수학자들은 먼저 알고리즘의 개념을 분명히 하였다. 알고리즘은 다른 말로 계산 가능한, 재귀 (귀납) 적인, 효과적인 이라는 말로도 표현된다. 알고리즘은 유한 회수의 절차인데 이것을 하나의 자연수에 대응시킨다. 이 대응을 귀납적 함수 (일반적으로 수론적 함수) 라고 하는데 이 함수를 일반화시켜서 수학적으로 정식화하는 문제이다.

1924 년에 쇤핀켈 (M. Schönfinkel), 1929 년에 커리 (h. B. Curry), 1934 년 괴텔과 허브랑 (J. Herbrand) 이 이 문제에 뛰어 들었다. 그후 클린 (Kleene) 은 이들의 결과를 더욱 개량하고 발전 시켰으며, 처치 (A. Church) 와 클린은 λ 기법으로 λ 정의 가능한 함수개념을 도입했다. 여기에 튜링이 나타난다.

영국 런던에서 인도 공무원의 아들로 태어난 튜링은 셔본 학교와 케임브리지에 있는 킹스 칼리지에서 공부하고 미국의 수학자 처치의 지도로 박사학위를 받은 그는 튜링기계를 고안해 내고 계산기능한 함수를 정의한다.

어떤 집합 S = {x1, x2, …, xn}의 원소에 관한 명제 P (x1, x2, …, xn) 가 주어질 때, S 의 어떤 원소들의 집합 (x1, x2, …, xn) 에 대해서도  P (x1, x2, …, xn) 가 성립하는가 어떤가를 유한 회의 조작으로 판정할 수 있는 일반적인 수순이 존재하는가를 묻는 문제를 그 명제의 항진문제라고 한다.

예를 들어 집합 S 를 다음과 같이 조건제시법으로 나타낼 때

명제 p(x) 는 S 안에서는 항진명제이며, 이 명제가 S에 대하 항진인지 판정하는 수순을 찾는 것이다.

그리고 적당한 원소의 집합에 대해서 즉, S 의 어떤 진부분집합에 대해서 명제 P가 성립하는가 어떤가를 판정하는 일반적인 수순이 존재하는가를 묻는 문제를 그 명제의 충족문제라고 한다. 그리고 이 두 개의 문제를 합쳐서 그 명제의 결정문제라고 한다.

예를 들어 집합 S 를 자연수 전체집합이라고 하자. 그러면 짝수의 집합에 대한 명제 '짝수는 적당한 두 홀수의 합으로 나타낼 수 있다' 는 명제가 참인지 어떤지 증명하는 절차를 찾는 문제가 그것이다. 또 임의의  짝수를 구하는 공식 2n (n 은 자연수) 도 있다. 이렇게 공식으로 어떤 집합의 원소를 모두 구할 수 있고 그 집합이 가산집합이라면 그러면 집합을 귀납적 가산집합 (recursively enumerable set) 또는 재귀적 열거 가능한 집합이라고 한다. 그리고 나아가 어떤 집합이 그 자신과 그 여집합이 모두 귀납적 가산집합일 때 귀납집합 (recursive set) 이라고 한다.

귀납적 가산집합이라도 귀납집합이 아닌 것이 존재한다. 프랙탈 기하학에서 등장하는 만델브로트 집합은 비귀납 집합이라고 알려졌다. 비귀납 집합은 프랙탈 기하학에서 보는 것처럼 복잡한 모습을 하고 있다.

튜링기계는 비귀납적 집합에 대해서는 분석하지 못한다. 이 때문에 튜링기계의 연장선상의 인공지은은 불가능할 것이라고 로저 펜로즈 (Roger Penrose) 는 주장했다. 

(5) 생물의 환경적응과 오토마타

생물 진화의 역사를 보면 급변하는 환경에 대한 적응의 역사라고 해도 과언이 아니다. 환경은 생물체에게 입력기호로서 작용한다. 생물체가 그 입력신호를 인식하지 못하면 그 환경에서 살아남기 어렵다. 생물체는 환경의 압력을 해석하고 그에 대한 대처방안을 모색한다.

그러나 단정적으로 해석이 불가능한 경우도 있을 것이다. 이런 경우는 비결정적인 상태로 해 두고 점점 비결정적인 부분을 없애가는 것이다.

학습의 경우도 그렇다. 어린이는 비결정적인 부분이 많다. 비결정적인 부분은 한마디로 모르는 부분이다. 차츰 배워 나가면서 비결정적인 부분을 없애 가는 것이다.

백지상태는 다음과 같이 두 가지 경우가 있다. 즉 아무런 회로가 형성되어 있지 않은 경우와 모두가 회로로 연결된 경우이다. 아마도 유아의 뇌는 후자 쪽인지도 모른다. 

(6) 짚신벌레의 의식

현미경으로 짚신벌레를 살펴보면 그 활발한 운동에 감탄할 것이다. 섬모들을 움직여 재빨리 이동하면서 먹이를 잡아먹는가 하면, 다른 짚신벌레와 '성적 교섭' 을 하기도 한다.

신경계나 뇌의 한 조각도 없는 이와 같은 단세포생물이 '감정' 이나 '의식' 을 가지고 있을까? 겉으로 보기에는 마치 의식적으로 감정적으로 움직이고 있다는 착각이 든다.

이 의문은 해소하기 위해 미국의 마취학자 스튜어트 하멜로프는 단세포생물 속에 단백질 컴퓨터가 들어 있다는 가설을 세웠다.

70 년대 초에 고성능 전자현미경으로 세포 속에 단백질로 이루어진 미세한 파이프가 얼기설기 얽혀있는 것을 발견했다. 이 파이프를 미소관이라고 부르는데, 원핵세포보다 덩치가 커진 진핵세포의 몸통을 유지하기 위한 세포내 골격으로서 역할을 하고 있다고 생각된다.

그런데 이 미소관의 네트워크가 단세포생물의 정보처리 시스템이라는 것이 하멜로프의 가설이다. 더구나 흥미로운 사실은 미소관 네트워크가 뇌세포 속에서 유난히 뚜렷하게 나타난다는 점이다. 이 미소간은 외게의 정보를 홀로그램 (입체사진) 과 비슷한 형식으로 처리한다는 것이다. 뇌의 홀로그램 이론의 창시자인 스탠포드 대학의 신경학자 칼 프리그램은 하멜로프읭 이 가설을 전적으로 지지한다.

결국 어떻든 간에 이렇게 미세한 생명체도 나름대로 만능튜링기계를 능가하는 기구를 갖추고 있다.

(7) 노이만형 컴퓨터

수학적인 가상의 계산기계인 튜링기계는 계속 연구되어 실제 물리적인 기계로 구현되기 시작한다. 이때부터 물리적으로 동작하는 계산장치를 연구하는 학문인 컴퓨터공학과 계속 이론적으로 논리적으로 동작하는 계산장치를 연구하는 학문인 오토마타 이론으로 나누어지게 된다.

1946 년 모클리 (J. W. Mauchly), 엑커드 (J. Presper Eckert) 의 공동 설계로 에니악 (ENIAC) 이라는 컴퓨터가 18,800 개의 진공관을 사용하여 만들어졌다. 그러나 이 컴퓨터는 전선의 배선으로 프로그램을 바꾸기 때문에 다른 프로그램을 수행하기 위해서는 일일이 배선을 바꾸어야 했다. 이렇게 해서 튜링의 가상 기계를 실제 물리적인 부속품을 이용해서 구체화시켰다.

이에 대해 1947 년 노이만 (John von Neumann) 은 버크스 (Arthur Walter Burks, 1915 ~), 골드스타인 (Herman H. Goldsteine) 과 함께 2 진법을 사용한 프로그램 내장방식의 컴퓨터 설계를 마쳤다. 이로써 만능 튜링기계인 오늘날의 컴퓨터가 탄생하게 되자 이제 그의 최대 관심사인 자기복제하는 기계를 설계하는 일에 몰두했다. 노이만은 생명체를 일종의 기계로 보았기 때문에 무기물인 기계로도 생명체와 똑같이 기계 자신이 자신과 닮은 새끼 기계를 만들 수 있다고 생각했다. 새끼 기계를 만드는 기계를 설계하는 것이 노이만의 일생 일대의 꿈인 것이다. 이처럼 자기증식 기계는 생명현상을 깊이 있게 이해시켜 준다. 실제로 자기 증식 기계는 공학적으로도 의의가 크다. 우주공간에 떠 있는 우주선이나 화성 탐사선 같은 것은 고장이 나면 수리하는 것이 매우 어렵거나, 불가능할 수도 있다. 전에 지구궤도를 돌고 있는 인공위성 수리를 위해 많은 비용을 들여 우주왕복선을 타고 수리하는 장면을 본 적이 있다. 그러나 자기증식 기계는 자가 수리도 가능하기 때문에 우주선에 직접 수리공을 보내지 않아도 좋은 것이다. 더구나 자기증식 기계는 피보나치 수열에서 보는 것처럼 기하급수로 증식해 가기 때문에 짧은 시간에 많은 것을 만들어 낼 수 있다. 즉 생산성이 가장 높은 것이다. 이러한 공학적인 이유 때문이라도 많은 사람이 자기 증식 기계를 꿈꿀 것은 당연하다.

우선 노이만은 이 기계를 만들 수 있는 가능성부터 타진하기로 하였다. 그래서 이 작업을 논리적으로 해야겠다고 생각하고 자기복제하는 기계의 존재를 논리적으로 증명하는 데 몰두했다.

보통 선반이나 밀링 같은 공작기계는 그 기계가 만들어 내는 물건보다 복잡하다. 사진기나 복사기도 마찬가지다. 자기복제 기계가 되기 위해서는 자기와 거의 같은 정도로 복잡한 기계를 만들 수 있어야 한다. 노이만은 적어도 자신과 같은 정도의 복잡한 것을 만들어 내는 것이 가능하다는 것을 1948 년에 논리적으로 증명하였다. 여기에 그 간단한 증명을 소개한다.

먼저 임의의 어떤 기계라도 만들 수 있는 만능제조 기계 UM 을 설계한다. 사실 지금의 범용 퍼스널 컴퓨터는 이 UM 에 해당한다. 컴퓨터에 적당한 프로그램만 넣어 주면 워드프로세서로 문서작성기가 되고, 그래픽 에디터로 그림을 그릴 수 있고, 문자인식기로, 번역기로, 노래방 기계로, TV 로 변할 수 있는 다목적 만능기계이다.

요즘에는 CNC 라는 완전 자동화된 공작기계가 등장하여 제품에 대한 각 스펙을 입력한 데이터만 넣어 주면 자동으로 제품을 만든다. 더구나 자동화된 로봇 공장도 등장하였다.

이렇게 UM 에 어떤 기계 M 을 만드는 프로그램을 담은 테이프 T(M) 을 넣어 준다. 그럼 UM 은 테이프 내용대로 기계 M 을 만들어 낼 것이다.

그럼 테이프 내용이 UM 을 만들라는 것이라면 어떻게 될까? 물론 만능기계인 UM 은 테이프 내용 그대로 자신과 똑같은 또 하나의 UM 을 만들어 낼 것이다.

테이프 내용을 그대로 복사하여 넣어 주면 새로 만들어진 UM 도 복제능력을 갖게 된다. 그러나 이 증명에는 마음에 걸리는 것이 있는데 그것은 만능제조 기계 UM 을 전제로 한다는 것이다. 만능, 모든 등의 개념은 파라독스를 가져오기 때문이다.

아무튼 논리적으로 가능하다고 해도 실제로 자기증식하는 기계를 만들 수 있는 것은 쉬운 일이 아니다. 노이만은 실제로 자기증식하는 기계를 설계하려고 하였다.

이러한 노이만의 작업은 생각처럼 쉽지 않았다. 고심하는 노이만에게 폴란드 수학자 울람(Stanislaw Ulam)은 오토마타를 병렬로 연결한 것을 이용해 볼 것을 권한다.

오토마타를 병렬로 연결해서 어떤 물리적인 문제를 해석하는 데 이용하고 있었던 것은 독일의 컴퓨터 과학자 콘라드 주세 (Konrad Zuse, 1910 ~ 95) 이다. 그는 물리적 계의 이산모델로서 계산공간을 고안해 낸다. 이 계산공간은 바로 오토마타가 병렬로 연결된 것이다. 그런 내용이 공간의 계산 (Calculating Space)에 정리되어 있다.

노이만은 이 아이디어를 흉내내어 29 개의 상태를 갖는 오토마타를 2 차원의 평면에 배열한다. 배열된 오토마타의 수는 무려 20 만 개에 달한다.

이들 오토마타, 나중에는 세포라고 불리는 작은 네모상자는 0 의 상태로부터 28 의 상태까지 취할 수 있다.

20 만 개의 세포로 이루어진 이 세포들은 크게 두 부분으로 나누어져 있다. 만능제조 장치를 포함한 복제작업이 프로그램된 지령서로 구성된다.

17

16

28

9

23

6

27

5

 

 

 

 

 

 

 

 

 

0

2

12

18

17

20

26

7

 

 

 

 

 

 

 

 

 

3

4

14

8

21

24

11

15

 

 

 

 

 

 

 

 

 

19

22

13

25

1

10

16

16

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

즉 자기증식 능력을 갖춘 기계를 만드는데 사용되는 정보는 기계 자체를 직접 만드는 데 사용되고 그리고 정보 자체를 복제하는 데도 사용된다. 자기 자신을 복제하라는 정보의 자기 언급이 일어나고 있는 것이다.

애석하게도 폰 노이만은 자기 스스로 번식하는 오토마톤을 실행해 보지 못했다. 당시의 컴퓨터 용량으로는 20 만 개의 세포에 대한 처리를 할 수 없었기 때문이다. 그리고 자기 증식 오토마톤에 대한 책을 완성하기 전에 골수암으로 죽었다.

노이만의 자기복제에 관한 기록은 비밀문서로 취급되었으며 훗날 그의 공동연구자 아터 버크스가 완성하여 출판하였다. 울람은 오토마톤을 작은 정사각형으로 하여 평면에 배열한 것을 모자이크 구조라고 불렀다. 세포자동자라는 명칭은 노이만의 논문을 편집했던 버크스가 붙인 것이다.

그후로 노이만의 구상은 미국 IBM 의 코드 (E. F. Codd) 에 의해 단순화되었다. 노이만의 29 상태를 갖는 세포자동자를 8 가지 상태를 갖는 것으로 단순화시켰다. 코드는 1970 년대 초에 이것을 가지고 자기복제 패턴을 발견했다.

(8) 생명게임 (Life Game)

세포자동자가 일반인들에게 소개된 것은 '생명게임' 이라는 이름으로 알려졌다. 그것은 단순한 흥미거리의 퍼즐 같은 것이었다. 처음에 어떤 임의의 모양으로 세포를 배열시키면 이들이 종국에는 어떤 모양으로 남게 되는가를 재미로 알아보는 정도이다.

영국의 케임브리지 대학의 수학자로서 '콘웨어 집합' 이라는 수학적 업적을 남긴 존 콘웨어(John Horton Conway)가 1968 년에 튜링기계나 노이만의 자기증식 기계로부터 2 차원 세포자동자를 생각해 냈다.

세포자동자는 삶과 죽음, 그리고 번식이라는 3 개의 상태를 갖는 튜링머신으로 주위의 환경을 계속 읽으면서 삶과 죽음, 그리고 번식의 상태가 결정된다. 이렇게 간단한 규칙을 주었을 때 이들 세포들이 어떤 패턴을 보이는가 연구하였다.

이 게임은 미국의 수학 계몽가 가드너 (Martin Gardner) 에 의해 『사이언티픽 아메리칸』 Scientific American 이라는 과학잡지에 1970 년 10 월과 1971 년 1 월호에 걸쳐 소개되었다. 간단한 규칙인데도 불가사의하게 다양한 결과를 만들어 내는 것에 매료되어 크게 대중화되었다. 특히 컴퓨터의 대중화와 함께 더욱 많은 사람들이 이 게임을 즐겼다.

패턴은 주어진 규칙에 의해 일의적으로 결정되지만 그 규칙으로부터 어떤 패턴이 나올지는 전혀 예상할 수 없다. 마치 자신의 자식이 자라서 어떤 인물이 될지 전혀 예상할 수 없는 것과 같다.

세포들이 바둑판 모양의 칸에 2 차원으로 배열되어 있을 때의 세포들의 배열 패턴 변화를 연구하는 것이다. 처음에 주어진 세포 배열에서 배열 패턴 변화를 연구하는 것이다. 처음에 주어진 세포 배열에서 각 칸 안의 세포의 운명 (살아남느냐, 죽는냐, 번식하느냐) 은 이웃의 세포 수가 결정한다. 이웃은 상하좌우 그리고 대각선상의 세포가지 모두 이웃으로 간주하는 무어이웃을 사용한다.

다음은 그 예인데 세 개의 세포가 현재 살아 있지만 다음 순간 좌우의 세포는 이웃을 하나씩밖에 갖지 못했기 때문에 죽어 간다. 가운데 있는 세포도 그 다음 순간 이웃이 하나도 없어서 죽게 될 것이다. 반대로 너무 이웃이 많아도 환경이 공해로 멍들고 식량안이 생겨서 죽게 된다.

 

이 이외는 그대로 생존이 유지되며 빈칸 주위에 3개의 세포가 있으면 그 빈칸에 새로운 세포가 탄생한다. 즉 처음에 나란히 3 개가 배열된 세포는 모두 죽어서 없어지지 않고 다음과 같이 가로에서 세로로 세로에서 가로로 그 패턴이 반복적으로 계속 변하게 된다. 이처럼 생명게임에서는 죽어 없어지는 세포와 그 상태를 그대로 유지하는 세포, 그리고 새로 생겨나는 세로를 동시에 고려해야만 하는 복잡한 게임인 것이다.

 

이처럼 죽음과 탄생은 동시에 일어난다. 이 규칙에 따라 세포배열이 단계마다 변화하며 재미있는 모양을 만들기도 하고, 마치 살아 움직이는 듯한 착각이 들게도 한다. 

(9) 생명게임의 여러 가지 패턴

생명게임은 여러 사람에 의해 여러 가지 재미있는 패턴들이 발견되었다.

 

우선 가장 간단한 패턴으로 아무리 시간이 흘러도 아무런 변화를 보이지 않는 앞의 3 개의 패턴이 있다. 이제부터는 바둑판에 검은 바둑돌을 놓는 것으로 세포가 살아 있음을 표현한다.

두 번째 그룹은 생사를 서로 반복하는 패턴이다. 곧 주기 2로 진동하는 패턴이다.

주기가 3 이나 4 인 패턴도 존재한다. 예를 들면 다음의 8 자 패턴은 주기 8을 갖는 패턴이다.

생명게임이라고 불릴 만한 생명체와 같은 패턴이 존재하기도 한다. 그 대표적인 것이 글라이더라는 패턴이다. 이 패턴은 마치 벌레가 꾸물거리며 기어가듯이 바둑판 위를 기어간다. 글라이더도 주기를 갖는 패턴인데 다만 원래의 패턴으로 돌아올 때마다 위치가 조금씩 달라지는 것이다. 다음 그림과 같이 주기 4로 원래와 같은 모양으로 돌아오며 그 위치는 오른쪽 아래 방향으로 한 칸씩 이동한다.

글라이더는 물리학에서 발견된 솔리톤과도 비슷하다.

이동하는 패턴은 이 외에도 주기 4로 오른쪽으로 2칸씩 움직이는 경량급 우주선이라고 불리는 패턴, 중량급 우주선 등 여러 가지 종류가 있다. 특히, 재미있는 것은 글라이더를 계속 생성해 내는 글라이더 건(glider gun)이다.

이 외에도 생명게임에는 매우 흥미 있는 변화를 보여주는 패턴이 계속 발견되고 있다. 연기를 내면서 이동하는 기차 같은 패턴, 글라이더를 만들어 내는 패턴 등등 이러한 것을 찾기 위해 많은 사람들이 연구하고 있다.

(10) 랭턴의 자기증식 루프

생명게임은 이처럼 바둑판에 바둑돌을 두듯이 일일이 손으로 해야 했기 때문에 매우 어려웠다. 바둑게임의 경우는 한 수 한 수 두지만 생명게임은 동시에 모든 세포들이 변하기 때문에 다음 세포들의 배치를 만드는 것은 매우 어려운 일이다. 그러나 MIT의 윌리암 고스퍼(William Gosper)가 생명게임을 실행하는 프로그램을 개발해서 생명게임의 연구는 크게 활기를 띠었다. 컴퓨터에 초기의 세포 배열만 정해주면 자동으로 다음 세대의 세포자동자 운명을 화면에 보여주기 때문에 생명게임은 크게 유행하게 되었다. 세포자동자를 발전시킨 버크스가 있던 미시간대학의 토마소 토플리(T. Toffli)나 노만 마골라스(N. Margolus)는 세포자동자기계(CAM)를 제작했다.

그리고 인공생명이라는 새로운 학문을 창안한 랭턴(Chris Langton, 1948 ~)은 이 세포자동자를 이용해서 인공적으로 생명현상, 즉 자기복제 현상을 구현해 보기 위해 백방으로 노력한다. 랭턴은 코드의 자기복제 세포자동자를 보와하였다. 주기억 용량이 64킬로 바이트밖에 안되는 애플Ⅱ컴퓨터에서 실행해 볼 수 있는 자기복제 세포자동자를 만들기 위해서는 세포자동자를 되도록 단순화시켜야만 했다.

그리하여 드디어 노이만의 꿈이었던 다음 그림과 같이 15×10의 크기로 모두 94개의 세포로 이루어진 자기복제 시스템이 탄생하게 된다. 아마도 이것을 볼 수 있었다면 자신의 복잡한 시스템보다 간단한 것이 자기증식하는 것을 보고 감탄을 금하지 못했을 것이다.

자기증식하는 세포자동자인 랭턴의 Q자형 루프

이 세포자동자는 다음과 같이 노이만 이웃을 이용하여 변화한다.

즉 가운데 있는 세포의 다음 상태는 위, 아래, 좌우의 네 개의 세포의 상태에 의해 결정된다. 다음은 그 규칙의 일부이다.

 

이웃이 모두 0이고 자신도 ■이면, 다음에도 변함없이 그대로 0이다.

 

이웃이 각각 그림처럼 2, 7, 0이면 ■은 다음에 ■ 로 바뀐다는 등의 규칙이다.

각 세포는 8가지 상태를 취할 수 있는데다 5의 이웃을 갖기 때문에 이들 조합의 가짓수는 모두 32,768가지나 된다. 이 가짓수에 다시 8가지 상태 중에서 하나를 선택하는 변이 규칙을 생각한다. 가능한 규칙은 모두 832768가지의 규칙이 된다. 랭턴은 이 많은 규칙을 일일이 조사해 가면서 자기증식을 만드는 규칙을 찾아낸 것이다. 실로 엄청난 인내심을 요구하는 지루하고 번잡하기 짝이 없는 작업이었다. 하지만 그것으로부터 나무 것도 나오는 것은 없다. 속된 말로 밥이 나오는 것도, 떡이 나오는 것도 아니다. 이제 막 결혼한 그의 아내도 그 부질없는 작업에 대해서 불만이 대단했다. 그러나 밤늦게 작업하는 랭턴을 향해 그만하고 침대로 와서 잠을 청하라고 바가지를 긁는 정도였다. 소크라테스의 아내처럼 물벼락을 내리지 않은 것이 다행한 일이었다. 이 지루한 작업은 랭턴에게는 단지 검불 속에서 바늘을 찾아냈다는 희열감 이상이었다. 그는 처음으로 그것도 직접 자기 손으로 자연의 생명체에서 볼 수 있는 것과 똑같이 자기증식하는 인공의 생명체 같은 것을 창조한 것이다.

신만의 금단의 영역인 생명창조를 인간이 해낸 것이다. 비록 컴퓨터 상의 일이지만 더구나 생명의 일부 특정인 자기복제를 실현한 것에 지나지 않지만 이것은 인류역사의 가장 커다란 사건인 것이다.

이 세포자동자의 움직임은 마치 전자회로를 타고 신호가 전해지는 것과 같다. 먼저 상태 2의 세포들은 전선의 피복과 같은 역할을 한다. 그리고 상태 1의 세포는 구리선과 같은 도체로서 신호가 지나가는 길이다. 그리고 다른 번호는 신호이다. 신호는 1초에 한 칸씩 진행한다. 이제부터는 네모는 생략하고 숫자로만 세로를 나타낸다. 0번 세포는 진공을 뜻하며 특별한 경우가 아니면 나타내지 않는 경우가 많다.

 

신호의 흐름은 분기점에 도달하면 위쪽으로는 신호를 그대로 복사해서 보내고 오른쪽으로는 그 신호 내용을 실행시키도록 한다.

여기서 7 0은 핵심적인 유전코드로서 껍질 2를 자라게 하고 자신을 복제한다.

즉 다음 그림과 같이 상태 7과 0이 연속된 7 0 이 꼬리 부분에 가면 꼬리를 1만큼 늘리고, 연속신호 4 0이 2회 반복되면 꼬리를 왼쪽으로 90° 돌리도록 고안되어 결국에는 자신과 똑같은 모습과 기능을 갖춘 자식을 만들어 낸다.

두 개의 2로만 둘러싸여 있을 때는 전혀 변함이 없던 7은 3개의 2를 만나면 6 으로 바뀌고 6은 곧 1로 바뀌며, 6을 만난 2들은 5로 바뀐다. 2는 7과 5가 이웃에 오면 3으로 바뀌고, 3은 곧 2로 바뀐다. 2나 1에 접해 있는 5는 그 상태를 그대로 유지한다. 5를 두 개 만난 0은 2로 바뀌고, 3이 이웃에 있는 5는 2로 바뀌고, 그 외 5는 1로 바뀐다. 2로 둘러싸이지 않은 0이 1을 만나면 2가 된다. 이렇게 해서 한 칸이 늘어난다. 이때까지 시간은 10초가 걸린다.

2는 4와 5가 오면 3이 되고,

인 경우만 5가 1로 바뀌고, 그 외는 무조건 2로 바뀐다.

더구나 울프램의 1차원 세포자동자 연구는 카오스와 인공생명의 개념을 이어주는 가교 역할을 한다. 그리고 랭턴은 자신과 같은 생각을 갖는 사람들이 공동연구를 할 수 있으면 좋겠다는 생각에서 1987년 로스앨러모스에서 최초의 인공생명회의를 개최하였다. 이렇게 해서 세포자동자는 복잡성 과학의 중심 테마로서 인공생명 연구의 중요수단으로서 부상하기 시작한 것이다.

3. 1차원 세포자동자 

(1) 스테펜 울프램

여기 또 한 사람, 아담의 원조 때문에 십자가를 짊어진 사람이 있다. 그는 우주나 생명의 신비를 수학으로 완벽하게 설명할 수 있다고 믿었다. 지치치 않는 끈질긴 정열로 그 신념을 밀고 나갔다.

영국에서 태어난 울프램 (Stephen Wolfram, 1959~)은 16 세에 옥스퍼드 대학에 입학했던 수학과 물리학의 천재이다. 울프램은 우주나 생명의 비밀은 수학으로 완전히 기술할 수 있다고 믿었다.

그리고 물리학이야말로 우주의 비밀을 푸는 열쇠를 쥐고 있다고 생각하여 더 이상 얻을 것이 없는 옥스퍼드 대학을 그만두고 캘리포니아 공과대학으로, 프린스턴 고등연구소로 자리를 옮기면서 이론 물리학을 전공하였다.

그는 우주의 근원을 찾아서 소립자 물리학을 연구하는 아담의 후예인 것이다. 그러나 소립자를 연구하면 우주의 수수께끼가 풀리기는커녕 새로운 수수께끼를 양산할 뿐이었다. 그 기본적인 입자를 연구하면 할수록 더 많은 입자가 발견되고 계산이 복잡하게 될 뿐이었다. 자연은 단순하다는 서구인의 오랜 믿음은 뭔가 잘못되었다고 생각하게 만들었다. 소립자 이론은 우주의 본질을 추구하는 이론이라기보다 우주의 다양한 현상을 보여주는 겉 핥기에 지나지 않은 것 같았다. 그에게는 무언가 새로운 변혁이 필요했다. 토마스쿤이 말하는 패러다임이 전환과 같은 것이다.

울프램은 갑자기 소립자 이론의 연구를 멈추고 마우도 거들떠보지 않는 세포자동자를 연구하기 시작했다. 그에게는 복잡한 소립자의 세계를 단적으로 설명할 새로운 수학적 방법이 필요했던 것이다. 그 수학은 컴퓨터를 절대적인 도구로 하는 새로운 수학이었다.

물리학에서 보는 난류 현상이나, 경제학에서 보는 주가 폭락은 전혀 다른 현상이지만 공통적으로 동일한 구조의 복잡성을 나타낸다는 점에 주목하고 이러한 복잡성을 분석하는 데 세포자동자가 위력을 발휘하리라는 직감을 얻었다. 세포자동자는 간단한 규칙으로부터 스스로 복잡한 패턴을 만들어 내기 때문이다.

울프램은 노이만의 세포자동자를 보고 이것을 최대한 단순화해서 그 메커니즘을 자세히 조사하기로 했다. 어떤 수학적 시스템에 어떤 조건을 덧붙이면 복잡함이 생기는가 이 문제를 해결하는 것이 우주의 비밀을 밝히는 관건이라고 생각한 것이다.

그래서 프린스턴 연구소로 옮겨가 얼마 있지 않아 소립자 물리를 포기하고, 세포자동자를 연구하기로 했다. 그러나 세포자동자는 아직 학문적인 틀을 갖추지 못한 상태였다. 아무도 거기에서 좋은 연구성과를 올릴 수 있다고 생각지 않았다. 그것은 마치 궤도를 이탈한 열차와도 같은 것이었다.

그러나 울프램은 지금의 과학은 어떤 한계(이러한 한계를 복잡성의 과학에서는 자기조직 임계현상이라고 부르기도 한다)에 도달했으며 새로운 돌파구를 모색할 때라고 느끼고 1982년부터 세포자동자를 연구했다. 주위 사람들의 비웃음을 받으면서….

(2) 세포자동자와 복잡성

생명게임에서 보듯이 세포자동자는 2차원만 되어도 그 전체적인 거동이 매우 복잡해진다. 울프램은 세포자동자를 더욱 간단히 하여야만 수리적 관계를 간파하기 쉬워진다고 생각했다. 그래서 울프램은 세포들을 단순히 일렬로만 배열하여 두고 그 변화의 양상을 컴퓨터로 조사하기 시작했다.

이렇게 해서 1차원 세포자동자는 울프램에 의해 집중적으로 연구되었다. 그의 [세포자동자와 복잡성]이라는 저서에 그 연구결과가 집대성되어 있다.

복잡한 것에서 복잡함이 생기는 것은 당연하지만 단순한 것에서 복잡한 것이 탄생하는 일은 놀랄 만한 것이다. 그것은 마치 마술을 보고 있는 듯한 감을 주기도 한다. 그래서 울프램은 가장 단순한 시스템을 선택했다. 그것이 바로 1차원 세포자동자이다.

노이만의 세포자동자는 20만 개의 세포가 각각 29가지의 상태를 가지게 된다. 콘웨이는 이것을 단순화해서2차원 세포자동자로 해서 생명게임이라는 새로운 수학퍼즐을 만들었다. 그러나 이것도 아직은 복잡하다. 울프램은 더욱더 간단한 것을 찾았다. 그것은 고대 그리스 수학자들이 작도 문제에서 오로지 자와 컴퍼스라는 가장 간단한 도구로 어떤 복잡한 도형이라도 그리려고 했던 고집과 일맥상통한다. 그래서 가장 간단한 1차원 세포자동자를 택한 것이다. 수학의 정신은 모든 가능선을 항상 염두에 두는 것이다. 그러나 아담이 선악과 먹다가 말았기 때문인지 몰라도 신피질은 그다지 뛰어나지 못하다. 건망증이 아주 심하고 조금만 복잡해지면 그만 혼란에 빠진다. 따라서 모든 가능성을 염두에 두기 위해서는 처음 출발점은 되도록 간단해야 할 것이다.

너무 간단한 것에서는 아무 것도 얻을 수 없다고 생각할지도 모른다. 그러나 1차원 세포자동자는 우리에게 많은 것을 보여준다.

(3) 1차원 2상태 3이웃 세포자동자

1차원 세포자동자는 말 그대로 1차원, 즉 한 줄로 세포들을 배열한 것이다. 1차원 세계의 생물들에게 공간 감각은 앞뒤밖에 없다.

즉 이들 세포들은 앞뒤의 세포들밖에 생각할 수 없는 것이다.

                             …■■□■□■■□□□■■□■□□□■□…

                                          -1차원 세포자동자-

따라서 세포들이 영향을 미칠 수 있는 것은 오로지 앞뒤의 세포뿐이다. 그리고 검은 세포(■)는 살아있는 세포이고, 흰 세포(□)는 죽어있는 또는 빈자리라고 생각해도 좋다. 즉 각각의 세포는 2가지 상태를 취할 수 있는 것이다.

이 1차원 세포자동자는 어떤 장소의 세포의 상태가 양쪽 이웃에 있는 세포의 상태에 의해서 정해진다. 각각의 세포는 살아있거나 죽어있는 상태를 취한다. 좌우의 두 개의 세포를 포함해 모두 세 개의 세포 조합으로 다음 세대의 세포상태, 즉 삶과 죽음이 결정된다. 즉 3이웃 세포자동자이다. 이것을 간단히 정리해서 1차원 2상태 3이웃 세포자동자라고 부른다. 이것을 간단히 정리해서 1차원 2상태 3이웃 세포자동자라고 부른다. 앞에서 말한 것처럼 우리는 일반적으로 n 차원 p 상태 m 이웃 세포자동자를 생각할 수 있다. 그러나 가장 단순한 1차원 2상태 3이웃 세포자동자라도 얼마든지 복잡한 패턴을 만들어 내는 것을 보게 될 것이다. 그리고 덧붙여서 세포배열의 길이를 유한으로 한정하면 그 경계조건을 정해 주어야 하는데 여기서는 주기 경계조건을 사용하기로 한다.

이제 1차원 2상태 3이웃 세포자동자로 생명게임을 해보자. 즉 생명게임에서처럼 너무 갑갑해도 모두 죽고 너무 외로워도 죽고 적당한 조건이면 새로 생기는 그런 이웃의 조건을 찾아보면 다음과 같다.

이외의 경우는 살아 있는 것이 그대로 유지되거나 새로 생겨난다.

다음과 같이 세포분열의 세포배열의 길이가 10인 곳에 단 하나의 세포(■)만 살아 있다고 하자. 즉 사막과 같은 곳에 살아있는 단 하나의 세포는 다음 순간에 죽어서 온통 죽음의 바다만 남게 된다. 두 개가 살아 있는 경우는 서로 의지하여 주위에 새로운 세포를 만들어 낸다.

     t = 0 : □□□□■□□□□□   t = 0 : □□□□■■□□□□   t = 0 : □□□■□■□□□□

     t = 1 : □□□□□□□□□□   t = 1 : □□□■■■■□□□   t = 1 : □□■□■□■□□□

     t = 2 : □□□□□□□□□□   t = 2 : □□■■□□■■□□   t = 2 : □■□□□□□■□□

                  ¦                                       ¦                                       ¦

1차원 세포자동자로 2차원의 생명게임처럼 다양하고 재미있는 패턴을 찾아볼 수는 없다. 하지만 1차원 세포자동자의 경우에는 그 변화의 역사를 한눈에 볼 수 있는 장점이 있다. 그리고 그 역사의 패턴은 살아있는 세포의 개수나 그들의 배열방법 등에 따라서 다양한 패턴을 보여준다. 2차원 생명게임의 경우에도 패턴의  변화에 대한 기록을 할 수는 있지만 그것은 3차원의 패턴이 되기 때문에 안쪽에 있는 세포들의 변화는 가려서 잘 보이지 않게 되거나 산만하여 관찰하기 힘들다. 이러한 세포자동자의 변화의 역사를 시공패턴이라고 한다. 

(4) 시공패턴

1차원 세포자동자는 1차원의 공간으로 배열되어 있고 세포자동자의 세다간의 변화는 시간 축을 따라 전개된다. 따라서 이 시간적인 전개를 하나로 정리한 패턴을 시공패턴이라고 부르는 것이다.

처음의 공간적인 배열의 초기배열 또는 초기패턴이라고 부른다.

           ← 공간적인 배열 →
                       ↓
               시간적인 배열
                       ↓

이러한 시공패턴의 재미있는 예로 조개껍질의 문양을 들 수 있다.

 

이 하나의 씨앗은 다음 세대에 3개로 번식한다. 즉,

이라는 규칙으로 연이어 살아 있는 ■■■ 세포열이 1세대에 생긴다. 이 1세대의 세포들은 다음 2세대의 세포들을 만드는데 그 규칙은 여전히 같은 규칙이 그대로 적용된다. 이 과정을 22세대까지 반복해 보았다. 이것은 수 작업으로 만들었는데, 컴퓨터를 이용하면 50세대, 100세대까지도  쉽게 만들어 볼 수 있다.

2세대에서는 3개의 자손이 각자 삶의 터전을 찾아 흩어져 나가는 것처럼 보인다. 다시 3세대에서 자손이 더욱 불어나고 4세대에서 흩어져 나간다. 이때 잉여 자손들이 죽어서 사라진다. 즉 좁은 땅에서의 인구폭발 때문에 아사자들이 생기는 것처럼 보인다. 그리고 이러한 반복이 계속되어 가면서 삶의 터전을 계속 확대해 나가는 것처럼 보이기도 한다.

바닷가에서 주워 모은 조개껍질의 패턴을 보고 그것이 어떤 규칙을 이용해서 그러한 문양을 만들 게 되었는지 주사해 보는 것도 흥미 있는 일이다. 그러기 위해서는 먼저 1차원 2상태 3이웃 세포자동자에서 생각할 수 있는 모든 규칙을 정리해 보아야 한다.

 

(5) 세포자동자의 상태천이 규칙

세포자동자는 3이웃의 상태에 따라 다음 상태가 결정된다. 각 세포는 2의 상태를 가질 수 있으므로 3세포가 가지는 상태의 조합 가짓수는 2의 3제곱, 즉 8가지의 경우밖에 없다. 즉 다음과 같이 3개 모두 살아 있는 경우부터 3개 모두 죽어 있는 경우까지이다.

■(ON)을 1, □(OFF)를 0으로 나타내기로 하면, 세 개의 세포의 상태를 0과 1만을 사용하는 2진법의 3자릿수로도 표시할 수 있다.

이들은 000, 001…, 111까지의 여덟 개의 상태로, 이들이 다음 세대에서 한가운데 세포가 ON이 되는가 OFF가 되는가를 결정하는 방법은 또 다음과 같이 2의 8승, 즉 256 가지의 경우가 있다.

아무리 간단한 1차원 세포자동자라도 벌써 조사해야 할 규칙이 256 가지나 되는 엄청난 것이다. 이것을 손으로 일일이 한다는 것은 단순 반복적인 지루한 일을 가장 싫어하는 호모 사피엔스에게는 고역 중에 고역이다. 필자도 이 작업을 처음에는 수 작업으로 조사하다가 도저히 불가능한 작업이라는 것을 깨닫고 프로그래머에게 이 작업을 신속히 끝낼 수 있는 프로그램을 개발해 줄 것을 의뢰해야만 했다. 앞으로 수학 연구를 희망하는 사람은 간단한 것이라도 프로그램 언어를 하나쯤 익혀두어야 할 것이다. 실제로 울프램은 수학 연구에 큰 도움이 되는 '매쓰매티카'라는 이름으로 상품화되어 있는 강력한 소프트웨어를 직접 제작한 유능한 프로그래머이기도 하다.

울프램의 집념은 이 256 가지의 경우를 모두 조사했다는 것이다. 물론 컴퓨터를 이용했다.

이 256가지의 규칙을 다음과 같이 함수로도 나타낼 수 있다. 정의역은 SN으로 S는 한 세포가 가질 수 있는 상태의 집합이고, 지수 N은 이웃의 개수이다. 따라서 SN은 모든 이웃의 상태를 나타내는 것이다. 물론 공변역은 S 자신이 된다

 

(6) 규칙의 분류

256개의 규칙을 하나씩 적용해서 그 시공 패턴을 그려보자. 우선 규칙에 번호를 붙인다. 다음과 같이 3개의 이웃의 상태가 배열되어 있고 이것으로부터 결과가 나온다.

 

즉 무조건 0을 만드는 규칙을 0번으로 시작해서 255번까지 번호를 붙인다. 다음은 결과만을 모아서 정리한 것이다.

0번 규칙으로는 초기의 세포가 어떻게 배열되어 있어도 다음 그림처럼 1세대부터 완전히 하얀 색이 나와 버린다.

      ■□■□□□■□□■■□□■■■□□□□■□□■□□□■□■  392576442

      □□□□□□□□□□□□□□□□□□□□□□□□□□□□□□

      □□□□□□□□□□□□□□□□□□□□□□□□□□□□□□

      □□□□□□□□□□□□□□□□□□□□□□□□□□□□□□

      □□□□□□□□□□□□□□□□□□□□□□□□□□□□□□

0번 규칙은 잔인하게도 무조건 모든 세포를 죽여 버린다. 제일 마지막 규칙인 255번 규칙은 무조건 검은 색이 된다. 255번 규칙은 너무 마음이 좋아 무조건 세포를 살려주는 것이다. 그야말로 극과 극, 지옥과 천당을 보는 것 같다.

      ■□■□□□■□□■■□□■■■□□□□■□□■□□□■□■  392576442

      ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■

      ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■

      ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■

      ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■

그리고 그 사이에 있는 규칙은 간단한 패턴부터 복잡한 패턴으로 그리고 아주 불규칙하고 무질서한 패턴까지 만들어 낸다.

4. 세포자동자의 거시적 역할 

(1) 세포자동자의 역학

이미 본 것처럼 (결정적인)세포자동자는 마치 뉴턴 역학처럼 결정론적인 법칙에 따라 움직이다. 즉 세포자동자는 이제까지 보아왔던 아주 단순한 결정론적인 규칙을 반복하는 것만으로 전개되는 이산역학계이다. 따라서 우리는 세포자동자를 역학처럼 연구할 수가 있다. 특히 세포자동자는 통계역학과 매우 흡사하다. 세포 하나 하나의 상태는 기체분자 하나 하나의 상태(위치와 속도)에 해당한다. 그리고 기체분자가 서로 충돌하면서 에너지를 교환하여 상태가 변하는 것처럼 세포자동자의 각각의 세포들도 이웃하는 세포와 상호작용하여 서로의 상태를 변화시킨다. 결국 통계역학이 미시적인 기체 분자들의 상태변화를 통계적으로 처리하여 거시적인 상태를 설명하는 것처럼 세포자동자에서 각 세포들의 변화를 모아 전체 세포자동자의 변화양상을 설명하려고 한다. 

이상의 내용을 수학적으로 정리해 보자. 즉 세포자동자 CA를 수학적으로 정의하면 다음과 같다.

거시변환규칙(global [transition] function)  F : c → c를 생각할 수 있다.

그리고 거시상태의 변화상태를 그래프로 그릴 수 있는데 이 그래프는 역학에서 '궤도'와 같은 것이다.

이제부터 가장 단순하고 기본적인 1차원 기본 세포자동자의 상태공간을 조사하기로 한다.

위 그림은 세포배열의 길이가 L = 4 인 경우의 모든 세포배열의 상태를 나타낸 것이다. 모두 16가지가 된다는 것은 24 = 16이라는 것으로부터 알 수 있다. 동그라미 번호는 세포배열의 가짓수 즉 거시상태를 나타내며, 네모의 번호는 각 세포의 위치를 나타낸다. 이것이 바로 길리 4인 세포자동자의 '상태공간'이다.

세포배열 길이 L = 10 이면 상태공은 210 = 1024개의 거시상태로 구성된다. 이처럼 세포자동자의 길이가 길어지면 상태공간은 지수함수적으로 팽창한다. 마치 우주가 빅뱅으로 인플레이션을 일으킨 것과 같은 것이다.

세포자동자의 고정점 어트랙터

점(•)은 세포자동자의 하나의 거시상태를 나타낸다.

그리고  전 상태 즉 조상을 갖지 않는 거시상태도 있는데, 이런 것을 터키(John Tukey)가 '에덴동산(Eden garden)'이라고 이름붙였다. 성경의 에덴동산이 그렇듯이 그 자신이 시작패턴(starting pattern)이 된다. 에덴동산은 특별히 이중원(◎)으로 표시하겠다.

이 에덴동산과 관련하여 '무어(Moore)의 정리'라는 것이 있다. 세포자동자에는 반드시 에덴동산의 존재한다는 것이 그 내용이다. 에덴동산이 무조건 시작패턴이 되고 어트랙터는 귀착(sequel)패턴이 된다. 그리고 그 외의 패턴은 임시(transient)패턴이라고 한다.

초기 거시상태로 에덴동산을 정하여 세포자동자를 실행한다. 실행이 되면 각 세포들은 일시에 초기상태의 값을 바꾸면서 어트랙터를 향해 간다. 이때 끌려가는 모든 임시패턴을 어트랙터의 유역(basin)이라고 한다. 어트랙터의 유역은 상태공간에 역학적 흐름을 결정한다.

이제 세포자동자의 거시역학을 전개할 준비는 대충 되었다. 필요한 개념이 나오면 그때그때 다시 설명하기로 하고 본격적으로 세포자동자 역학의 세계로 나아가 본다.

(2) 세포자동자의 세계

 

시공패턴의 최대 길이는 '상태공간의 크기' + 1 = 3이고, 다음과 같이 □와 ■를 중복을 허용하여 세 개씩 늘어놓는 가지수는 23(8)가지에서 다음 두 패턴은 시공패턴으로서는 있을 수 없기 때문에

               ■□
               ■□
               □■

시공패턴은 모두 6(8 - 2)가지가 된다.

더구나 자기 자신이 다시 자신의 좌우의 이웃이 되기 때문에 이웃의 상태는 □□□와 ■■■의 경우밖에 없다. 따라서 규칙의 적용은 이 두 이웃의 상태만을 생각하면 된다. 8개의 미시규칙 중에서 맨 왼쪽 것과 오른쪽 것에만 네모 틀로 표시하였다.

두 개의 미시규칙만 허용하므로 256개의 규칙은 4( = 22)개의 그룹으로 축소된다.

첫 번째는 무조건 □이 되는 규칙으로 짝수 번인 0, 2, 4, 6, …, 126의 64개의 규칙이다. 이 경우에는 시공패턴이 A와 E의 패턴밖에 나오자 않았다.

따라서 어트랙터 포인터는 ⓞ□이고 상태천이도는 다음과 같다.

이 포인트 어트랙터가 되는 거시상태의 세포자동자로 어트랙터가 되는 것은 이제부터 검은 원으로 표시한다.

두 번째 부류는 홀 수 번인 규칙으로 1, 3, 5, 7 …, 127의 경우이다. 이 경우는 시공패턴이 B와 D가 나온다.

이 경우에는 두 개의 규칙, 이 서로 피드백을 일으킨다. 상태천이도는 다음과 같으며,

이 경우는  과 이 주기(순환) 어트랙터를 만든다.

세 번째는 128번부터 짝수번인 규칙들로 128, 130, 132, …, 254이다.

 

이 경우의 시공패턴은 A, F가 나온다. A와 F는 매우 배타적인 패턴이다. 검은 것은 검은 것만, 흰 것은 희 것만 만들어낸다. 따라서 상태천이도는 다음과 같이 두 개가 나오는 것이다.

네 번째 부류는 129 이상의 홀수 번인 129, 131, …, 255이다.

 

시공패턴은 C, F라고 상태천이도는 다음과 같으며, 첫 번째 그룹과 모양만 같고 어트랙터와 가지고 서로 뒤바꿔진다.

이상을 정리하면 상태천이도가 대칭성을 갖추고 있는 것을 볼 수 있다.

                  □□               □■
                  □□               ■■
                  □■               ■■
                    :                 □□
                                        :

 

이 경우에는 이웃의 상태는 □□□, □■□, ■□■, ■■■의 경우밖에 없다. 따라서 규칙의 적용은 이 4이웃의 상태만을 생각하면 된다. 8개의 미시규칙 중에서 맨 왼쪽 두 개와 오른쪽 것 두 개에만 네모 틀로 표시하였다.

4개의 미시규칙만 허용되므로 256개의 규칙은 16( = 42)개의 그룹으로 확대하기 시작한다.

우주가 빅뱅으로부터 태어나면서 우주를 구성하는 기본적인 4개의 힘, 중력, 핵력, 전자기력, 약력이 차례로 갈라져 나오는 것처럼 세포자동자의 길이가 커지면서 세포자동자의 규칙도 한 가닥씩 늘어나 확대되기 사작하는 것이다. 16개의 그룹을 정리해 보자.

첫 번째 부류는 무조건 □이 되는 규칙으로 짝수 번인 0, 2, 4, 6, …, 126 중에서 0, 2, 8, 10, 16, 18, 24, 64, 66, 72, 74, 80, 82, 88, 90의 16가지의 경우이다.

어트랙터 포인트는 ⓞ□이고 상태천이도는 다음과 같다.

시공패턴은 상태천이도를 보고 그릴 수도 있다.

두 번째 부류는 맨 왼쪽 이웃의 상태만이 ■이 되는 경우이다. 홀 수 번 규칙인 1, 3, 5, 7, …, 127에서 1, 3, 9, 11, 17, 19, 25, 27, 65, 67, 73, 75, 81, 83, 89, 91의 16가지이다.

 

이 경우 상태천이도는 다음과 같이 된다.

그림에서 보듯이 거시상태 ①과 ②는 어트랙터 의 유역(basin)이 된다.

세초자동자의 길이가 3, 즉 이웃의 크기와 같아지면 256개의 규칙이 모두 갈라져 나와 세포자동자의 우주가 완성된다. 따라서 세포자동자의 길이가 3 이상의 경우에는 다른 방법으로 접근하는 편이 낫다. 그 방법은 규칙을 고정시키고 세포자동자의 길이를 점점 늘려 가면서 상태천이도가 어떻게 달라지는지 조사하는 것이다.

다음은 규칙 0부터 차례대로 255번 규칙까지 세포자동자 배열의 길이 N이 1부터 시작되는 상태천이도(State Transition Diagram ; STD)를 그린 것이다. 상태천이도의 기하학적인 구조는 역학에서 어트랙터의 기하학적 구조가 그 역학계가 어떤 상태에 있는지를 알 게 해주는, 특히 스트레인지 어트랙터는 역학계가 카오스 상태에 있다는 것을 알려주듯이 중요한 지표인 것처럼 세포자동자의 규칙이 어떤 성격의 규칙인가를 말해 주는 매우 중요한 의미를 갖는다.

<0번의 규칙 : □□□□□□□□>

어트랙터는 고정점 어트랙터이고 N이 커질수록 유역이 더욱 조밀하게 되어 가는 것을 볼 수 있다.

255번 규칙은 다음 그림처럼 ⓞ번과 제일 마지막 번호가 서로 바뀌어 제일 마지막 번호가 어트랙터가 된다.

이와 같이 서로 어트랙터가 뒤바뀌는 규칙들을 서로 상보적(complementray)이고 역의 관계라고 부른다. 상보적인 규칙은 결과치가 서로 반대로 된다. 다음은 서로 상보적인 규칙들을 정리하였다.

규칙 R에 대해서 상보적인 규칙을 여규칙 Rc라고 부른다. 그림에서 보는 것처럼 1차원 세포자동다의 256개의 규칙은 다음과 같이 여규칙의 쌍으로  나누어진다.

(3) 상보적인 규칙

 

규칙의 결과가 서로 상보적이라고 해서 시공패턴까지 상보적인 것은 아니라는 것을 다음 그림을 보면 알 수 있다. 다음은 규칙 127과 128번의 시공패턴이다.

규칙을 이와 같은 입장에서 분류하면 다음과 같이 역변화규칙, 반사규칙, 대칭규칙도 있다. 역(negative)변환규칙은 다음 그림과 같이 어떤 규칙 R과 입력라인 I로 만들어지는 시공패턴 P에 대해서 역상의 입력라인 In과 역상의 시공패턴 Pn을 만드는 규칙을 말한다. 이 역변환 규칙을 Rn으로 나타낸다.

역변환규칙 Rn을 찾아내는 방법은 먼저 규칙 표에서 이웃의 모든 값을 1은 0으로, 0은 1로 바꾸고, 결과도 마찬가지로 바꾼다. 그리고 원래의 배열로 재배열하면 규칙 R에 대한 역변환 규칙이 얻어진다.

반사규칙은 마치 거울에 반사된 것과 같은 효과를 나타내는 규칙으로 임의의 규칙 R과 입력라니 I, 시공패턴 P에 대해서 반사규칙 Rr, 반사입력라인 Ir, 반사 시공패턴 Pr이 존재한다.

(4) 거울상(경상)의 시공패턴

어떤 규칙 R의 반사규칙을 얻기 위해서는 먼저 다음의 규칙표의 거울상을 만든 다음에 그것을 원래의 배열대로 재배열하면 된다. 즉 먼저 다음의 임의의 규칙 R의 규칙 표를 생각하고 이것의 거울상을 만든다.

 

(5) 반사규칙 Rr

반사규칙 Rr 은 R 에서 4 개의 비대칭적인 이웃배열인, ■■□, ■□□, □■■, □□■ 을 서로 거울상이 되는 것끼리 짝을 지어 뒤바꾼 것에 지나지; 않음을 알 수 있다.

따라서 T1 = T4, T3 = T6 인가 T1 ≠ T4, T3 ≠ T6 에 따라 대칭규칙인가 반대칭규칙인가로 구분되기도 한다. 즉 다음과 같이 정리된다.

0 번 규칙의 역변환 규칙은 255 번이며, 0 번이나 255 규칙은 자기 자신이 반사규칙이 된다. 따라서 이들은 대칭규칙이 되기도 한다. 그리고 임의의 규칙 R 에 대해서 역변환 규칙과 반사규칙을 두번 적용한 규칙 Rnr 도 있다.

이상으로 규칙 R 과 그 역변환, 반사 등의 규칙의 시공패턴을 정리하면 다음과 같다.

이렇게 규칙 R 에 대해서 Rn, Rr , Rnr, Rc, Rcn, Rnr , Rcr, Rcnr 등의 규칙을 서로 관련지어 그래프로 묶어서 한 묶음으로 생각할 때, 이 묶음을 규칙 R 의 클러스터라고 부른다. 이상의 내용을 그래프로 정리하면 다음과 같다.

1, 127, 128, 254 번 규칙들은 각각 서로 역변환규칙이고 상보규칙이면서, 모두 자기 자신이 반사규칙이 되기 때문에 Z 축이 없게 된다. 그것을 그림으로 나타내면 다음과 같다. Z 축이 없는 규칙들 즉 자신이 반사규칙이 되는 것을 몇 개 정리한 것이 다음 그림이다.

Rc = Rn 인 경우

R = Rn 인 경우

반 비대칭규칙 전 비대칭 규칙은 다음과 같이 온전한 육면체를 갖는다.

이상의 것들을 생각하면 256 개의 규칙에 대해서 일일이 조사할 것은 없다. 우선 0 번부터 127 번까지만 조사하면 나머지는 클러스터의 관계에서 상태천이도의 그 기하학적 구조를 유추할 수 있게 된다. 이제 규칙 1 번부터 다시 그 상태천이도의 변화를 살펴본다.

1 번 규칙과 역의 관계에 있는 127 번 규칙, 상보관계의 254 번 규칙, 역이고 상보적인 128 번 규칙의 상태천이도는 상보 관계의 것만 기하학적인 구조가 다르고 역의 관계는 같다. 왼쪽 그림은 254 번 규칙으로 세포자동자의 길이가 4 일 때의 상태천이도이다.

(6) 시공패턴의 주기

세포의 길이가 유한인 유한 세포자동자의 시공패턴에는 주기가 있다. 즉 같은 패턴이 반복되는 것이다. 재미있는 것은 규칙에 따라 이 시공패턴의 주기가 달라지며 또한 같은 규칙이라도 세포자동자의 길이에 따라서도 크게 달라지는 것이다.

울프램의 책을 보면, 규칙번호 90 (= 01011010) 에 대해서 주고 집중적으로 분석하였다. 이 규칙에 대한 시공패턴의 주기를 알아본다.

N = 1, N = 2 일 때의 시공패턴과 상태천이도

N = 3 일 때 시공패턴과 상태천이도

N = 3 일 때 시공패턴의 순환길이 C = 1 이다.

N = 4 일 때의 시공패턴

세포배열의 길이 N = 4 일 때는 상태천이도가 다음과 같은 것이 하나만 나온다.

N = 5 일 때, 시공패턴의 순환길이 C = 3 이다.

N = 6 일 때 상태천이도는 다음과 같다.

N = 7 일 때 순환주기 7 을 갖는 다음과 같은 모양의 상태천이도가 9 개 생긴다.

9 개의 같은 구조의 상태천이도가 생긴다.

다음 그림은 N = 11, 12 일 때의 상태천이도이다. 번호는 생략되어 있다.

울프램의 책 세포자동자와 복잡성의 정리 3.2. 에서 세포자동자 배열의 길이가 홀수이면 전임자를 정확히 2 개 가지며, 짝수이면 전임자를 정확히 4 개 가진다고 증명하고 있다. 규칙 90 번의 상태천이도를 이 정리의 내용을 그대로 보여준다.

특히 홀수일 때 시공패턴의 순환 주기는 매우 길어지는데 그 길이에도 법칙성을 가지고 있다. 홀수 중에서도 소수인 것, 그 중에서도 시공패턴 순환주기가 다음 법칙 을 따르는 소수는 다음과 같다.

세포배열길이 (N)

어트랙터 순환길이 (C)

3

5

7

11

13

19

23

29

71

1 (4 개)

3 (5 개)

7 (9 개)

31 (33 개)

 63 (130 개)

 511 (1026 개)

2047 (4096 개)

16383 (32770 개)

30000000000

N = 71 일 때 순환길이는 무려 으로 약 이라는 엄청난 수가 된다.

다음은 길이 15, 17, 19, 29 일 때의 시공패턴이다. 마치 뱀껍질처럼 주기가 반복되기 전에는 같은 패턴을 찾아볼 수 없다.