PROFILBARU.COM

세포 자동자(細胞自動子) 또는 셀룰러 오토마타(cellular automata, 단수 cellular automaton)는 계산 가능성 이론, 수학, 물리학, 복잡계, 수리생물학, 미세구조 모델링에서 다루는 이산 모형이다. 여러 개의 세포 자동자를 세포 공간, 테셀레이션 구조라고도 부른다.

세포 자동자는 규칙적인 격자 형태로 배열된 세포 또는 칸(cell)들에서 정의된다. 각 세포는 유한한 수의 "상태"를 가질 수 있는데 예를 들어 "살아 있음/죽음"이 있다. 격자는 유한한 수의 아무 차원이면 된다. 각 세포에 대하여, "이웃들"이라 부르는 세포들은 그 세포에 대한 관계로 정의하는데, 예를 들어 그 세포에 대해 모든 방향으로 한 칸씩 떨어져 있는 세포들이라는 식으로 하면 된다. 시간 t=0 일 때의 각각의 세포의 상태를 지정해놓고 이를 초기 상태라고 한다. 새로운 "세대"(시간 t가 그 다음 자연수)는 고정된 "규칙"에 의해 이전 세대로부터 만들어지는데, 규칙은 각 세포와 그 이웃들의 상태에 따라 그 세포의 새로운 상태가 지정하는 수학적인 함수이다. 일반적으로 그 규칙은 각 세포에 대해 동일하고 시간에 따라 변하지 않으며 각 세대의 모든 세포에 동시에 적용되는데, 물론 일반적이지 않은 규칙을 적용한 세포 자동자도 있다.(예: 확률론적 세포 자동자, 비동시적 세포 자동자)

1940년대에 스타니스와프 울람과 존 폰 노이만이 로스앨러모스 국립 연구소에서 함께 연구하면서 이 개념을 처음 발견했으나, 학계 밖에서 활발히 화자되기 시작한 것은 1970년대에 2차원 세포 자동자의 하나인 존 호턴 콘웨이의 라이프 게임이 소개된 이후였다.

역사

폰 노이만은 1948년 그의 논문 Theory of Self-reproducing Automata에서 스스로 자기 자신을 복제할 수 있는 로봇 모델을 구상했다. 이러한 로봇은 환경 인식 부분, 활동 부분, 에너지원 등 다양한 부분들로 이루어져 있었는데, 폰 노이만이 로봇을 구상하면서 직면한 과제는 바로 그러한 로봇이 적절한 환경에서 필요한 것들을 모아서 자기 자신의 복제품으로 만들도록 하는 것이었다. 이러한 모델 세계의 복잡성 때문에 과제를 손쉽게 해결하지 못 하고 있던 폰 노이만에게, 로스 알라모스 국립 연구소 동료였던 Stanislaw Ulam은 별개의 부분으로 이루어진 연속적인 공간 대신 간단한 유한 오토마타로 이루어진 균일하고 구별된 공간(uniform discrete space of simple finite automata)을 사용하라고 제안했다. 바로 이러한 공간 하나를 바로 셀룰러 오토마톤(Cellular Automaton)이라고 부른다. 아이디어를 얻은 폰 노이만은 처음엔 3차원의 셀룰러 공간을 구상했으나, 2차원 셀룰러 공간이 더 단순하고 편리함을 깨닫고 2차원 셀룰러 공간을 택했다. 그는 각각의 셀을 차지하는 29개의 상태를 가지는 유한 오토마타를 정의했고, 그가 '기관'(organ)이라고 부른 다양한 유한 연산 구조를 만들었다. 그의 목표는 이것들을 어떻게 조합하여 자가 복제 오토마타를 이론적으로 만들 것인가였지만, 그는 말년에 병에 걸렸기 때문에 이 연구를 완성시킬 순 없었다고 한다. Arthur W. Burks는 Creative Uses of Logic in the Invention of the Electronic Computer("전자 컴퓨터의 발명에서의 논리의 창의적 활용")에서 비록 폰 노이만이 EDVAC의 구조를 설계하는 데에는 성공하고 자가 복제 오토마타를 완성시키진 못 했지만, 폰 노이만의 구상은 실용적으로 응용될 수 있는 부분이 많으며, 자가 복제 가능한 시스템들의 집합의 중요한 특징에 대한 추상적 모델이라고 평가하면서 그 의의를 밝히고 있다.^[2]

이렇게 시작된 셀룰러 오토마타의 개념은 정의할 때부터 이미 유한 오토마타의 성질을 갖고 있었을 뿐만 아니라 유한 오토마타와 역사적, 기술적으로 관련이 있는 인공생명과도 밀접한 관계에 있다. 특히 폰 노이만의 셀룰러 오토마타(von Neumann's cellular automata)는 최초의 '부드러운' 인공 생명 중 하나로 꼽히고 있으며, 폰 노이만과 같은 해에 인공 생명과 연관이 있는 논문을 썼던 Norbert Wiener는 1946년에 Arturo Rosenblueth와 함께 쓴 논문 "The mathematical formulation of the problem of conduction of impulses in a network of connected excitable elements, specifically in cardiac muscle"에서 흥분될 수 있는 매질 내에서의 셀룰러 오토마타를 디자인했다고 한다.

셀룰러 오토마톤(cellular automaton)은 존 폰 노이만이 그의 1948년 논문 Theory of Self-reproducing Automata에서 사용한 개념으로, 공간에 규칙적으로 배열된 격자 '셀(cell)' 하나를 말한다. 각각의 셀은 유한 개의 가짓수의 상태를 가지며 각각의 셀은 불연속적인 시간(discrete time step)마다 동시에 업데이트된다. 각각의 셀은 입력값으로 현재 그 셀의 상태 및 이웃한 셀의 상태를 받고 출력값으로 다음 시간에서의 셀의 상태를 출력하는 유한 상태 기계이다. 이러한 셀룰러 오토마톤을 모아 놓은 공간을 셀룰러 오토마타(Cellular Automata, CA)이다. 셀룰러 오토마타는 다른 말로 "셀룰러 공간"(cellular space), "테셀레이션 오토마타"(tessellation automa), "균일 구조"(homogeneous structures), "세포적 구조"(cellular structures), "테셀레이션 구조"(tessellation structures), "반복적 배열"(iterative arrays)등으로 불린다고 한다.

존 폰 노이만으로부터 시작한 셀룰러 오토마타는 이후 다른 과학자들에 의해 활발히 연구되었다. 복잡계나 이론전산학 등에서 종종 연구되며, 인공생명의 맥락에서 생물학에서 연구하기도 한다. 그 중 영국의 수학자 존 호튼 콘웨이(John Horton Conway, 1937~)는 1970년에 셀룰러 오토마타의 가장 훌륭한 예로 평가받는 라이프 게임 또는 생명 게임(Game of Life)을 제창하였다.^[3]

생명 게임(Game of Life, 또는 Life Game)

생명 게임은 영국 수학자 존 콘웨이가 만든 게임인데, 게임 조종자는 없는 "zero-player game"이다. 대신 생명 게임은 초기 상태에 셀룰러 공간(cellular space)의 어떤 셀(cell)이 '살아있는' 것으로 선택되는가에 따라 그 계의 진화의 방향이 결정된다. 즉, 초기 상태에 의해서만 결정되는 오토마타인 것이다. 존 콘웨이가 정한 생명 게임의 룰은 아래와 같은 네 가지뿐이지만, 초기 상태를 어떻게 놓느냐에 따라서 매우 다양하고 "생명 같은"(life-like) 시뮬레이션이 나타난다.(참고로 여기서 '이웃'이란, 2차원 격자 평면에서의 생명 게임의 경우, 한 사각형 셀을 둘러싸고 있는 8개의 셀을 그 사각형 셀의 '이웃'이라고 정의한다.)

현재 살아있는 셀 중 2개 미만의 '이웃'이 살아있는 경우, "under-population"에 의해 외로워서 그 셀은 다음 상태에 죽는다.
현재 살아있는 셀 중 4개 이상의 '이웃'이 살아있는 경우, "overcrowding"에 의해 복잡해서 그 셀은 다음 상태에 죽는다.
현재 살아있는 셀 중 2,3개의 '이웃'이 살아있는 경우 다음 상태까지 그 셀은 살아남는다.
현재 죽은 셀 중 정확히 3개의 '이웃'이 살아있는 경우, "reproduction"에 의해 자손이 태어나 그 셀은 다음 상태에 부활한다.

이러한 규칙에 따라, 초기 패턴 이후 모든 격자 셀들이 동시에 삶과 죽음이 결정되고, 이러한 모습을 시뮬레이션으로 나타낸 것이 바로 생명 게임이라고 할 수 있다.

이렇게 비교적 간단한 룰로 이루어져 있지만, 생명 게임은 초기 상태에 따라 여러 아름다운 모습을 보여주는데, 아래의 유투브 영상에서 과학자들이 발견한 여러 재밌는 모습 몇 가지를 볼 수 있다.(wichstretcher/glider guns/puffer train/rahes/spaceship guns/cordonships/primer/saw-tooth/star gate 총 9가지가 나온다.)"Amazing Game of Life Demo"

한편 생명 게임은 규칙의 변형에 따라 단순 격자 형태가 아닌 육각 타일링 구조나 3D 구조에서도 구현될 수 있다.

이렇게 간단한 룰들은 아름다운 모양을 만들어 낼 수 도 있지만 자기 복제나 심지어 튜링 완전한 계산까지 할 수 있는 패턴들이 여럿 있다. 이는 라이프 게임이 무한한 메모리를 가진 어떤 컴퓨터와도 동등한 계산능력을 가짐을 의미한다. 또한, '만능 건축사'패턴은 튜링 머신과 동등한 컴퓨터를 만들 수 있으며, 이것은 더 복잡한 여러 가지 개체를 만들어내는 데 사용될 수 있다. "LifeWiki"에서 좀 더 자세한 내용을 확인할 수 있다.

한편 1969년에 Konrad Zuse(1910~1995)는 그의 저서 Calculating Space에서 우주 전체가 매우 거대한 셀룰러 오토마타의 결정 가능한 결과라는 생각을 내놓았다. 그의 책은 오늘날 디지털 물리학(digital physics)에 관한 최초의 책이라고 평가받는다고 한다.

1983년 스티븐 울프럼 (Stephen Wolfram)은 1차원 셀룰러 오토마타 들의 선택이 유한 개수이기 때문에 초기에 부류를 나누어 연구할 수 있다는 것을 깨달았다. 울프램은 규칙 집합을 다음과 같은 네 부류로 분류할 수 있다는 것을 알았다.

부류 1: 모든 죽은 셀 또는 살아있는 셀 같은 무의미한 보편자를 만드는 규칙들
부류 2: 안정되고 반복되는 배열을 만드는 규칙들
부류 3: 혼돈스러운 패턴을 만드는 규칙들
부류 4: 복잡하고 논리적으로 구성된 패턴을 만드는 규칙들

이 때, 부류 4의 셀룰러 오토마타가 가장 생명에 유사한 것이고 울프램의 분류 스키마는 본질적으로 생명체에 대하여 유사성을 늘려나가는 것이다. 울프램의 스키마는 규칙들을 분류하는 질적 스키마이다. 크리스토퍼 랭턴은 규칙 집합에 $\gamma$ 라고 하는 숫자적인 양을 할당해서 더 양적인 스키마를 개발했다. 셀룰러 오토마타를 계산하는 이 양은 값의 전영역에 걸쳐서 완만하게 분포되어 있다. $\gamma$ 의 값에 따라서 울프램의 부류를 배치해 보면, 1부류, 2부류, 4부류, 3부류 의 순서로 배치가 된다. 재미있는 점은 부류 4의 행동은 $\gamma$ 값이 좁은 폭으로만 변해도 일어나는데, 그 행동이 규칙적이고 주기적인 행동에서 혼돈스러운 행동으로 변한다는 것이다. 랭턴의 관점에서는 주기적인 행동과 혼돈스러운 행동 사이에는 위상 전이를 하고, 생명과 지능은 이 전이지대 안에서 가능하게 된다.

초등 셀룰러 오토마타(Elementary Cellular Automata)

초등 셀룰러 오토마타(Elementary Cellular Automata)는 1차원으로 배열된, 오로지 두 개의 상태(0과 1)만 가질 수 있는 공간으로 만들 수 있는 가장 간단한 셀룰러 오토마타들이다. 매 세대마다 각 공간은 주변에 위치한 두 공간 및 자기 자신의 값에 따라 지정된 값으로 변경되는데 이러한 규칙이 8개 필요하기 때문에 가능한 초등 셀룰러 오토마타는 총 256개이다.

초등 셀룰러 오토마타는 흔히 하나의 숫자로 표현하는데, 이 숫자는 이진법으로 나타냈을 때 8개의 규칙에 대응하는 결과값이 각 비트에 나타나도록 구성되어 있다. 예를 들어 Rule 110의 경우 다음과 같은 규칙으로부터 유래한다.

이전 상태	111	110	101	100	011	010	001	000
새 상태	0	1	1	0	1	1	1	0

새 상태에 해당하는 비트를 모두 모으면 01101110₂ = 110이 된다. 따라서 가능한 오토마타는 Rule 0부터 Rule 255까지인데, 규칙들에서 0과 1을 모두 뒤집을 경우와 규칙들을 세로로 반전할 경우 실질적으로는 같은 오토마타가 나오기 때문에 이를 제외한 88가지만을 고려하면 된다.

초등 셀룰러 오토마타는 매우 단순화된 계산 모델임에도 불구하고, 적절한 규칙과 적절한 초기 상태만 있으면 튜링 완전한 계산을 할 수 있다는 것이 알려져 있다. (앞에서 말한 Rule 110이 그러한 규칙으로 알려져 있다.) 이런 특성 때문에 이러한 초등 셀룰러 오토마타를 "범용적" (universal)이라고 하기도 한다.

중요한 초등 셀룰러 오토마타에는 매우 랜덤한 결과를 내 놓으며 난수 생성에 흔히 쓰이는 Rule 30과 적절한 초기상태를 주면 튜링 완전한 것으로 알려져 있는 Rule 110이 있다. ^[4]

응용

셀룰러 오토마타는 물리학에서 비선형화학반응의 모델, 나선 은하의 진화, 수지상 결정의 성장모델로 사용된다. 컴퓨터 공학에서는 병렬컴퓨터의 모델로 생각하고 패턴 인식과 이미지처리기로서 응용하려는 시도도 있다.

벨로소프-자보틴스키 반응

셀룰러 오토마타를 실용적으로 활용한 좋은 예로는 벨로소프-자보틴스키(Belousov-Zhabotinsky) 반응의 셀룰러 오토마타 모델이 있다. 벨로소프-자보틴스키 반응은 프리고진의 산일구조론, 자기조직화의 화학반응의 좋은 보기로 유명하다. 벨로소프-자보틴스키 반응은 생명현상에서도 찾아 볼 수 있는 두 가지 이상의 화학물질이 서로에 대해 촉매작용을 하는 복잡한 화학반응을 보인다. 이 벨로소프-자보틴스키반응의 화학반응식은 밝혀졌지만 보다 본질적인 측면을 찾아내기 위해 셀룰러 오토마톤 모델을 생각한 것이다. 그린버그(J. M. Greenberg)와 헤이스팅스(S. p. Hastings)는 벨로소프-자보틴스키 반응의 세포자동자 모델로 다음과 같은 그린버그-헤이스팅스(Greenberg-Hastings)모델을 고안했다.

셀이 취할 수 있는 상태는 정지기, 활동기, 불응기 3가지이다.