셀룰러 오토마타는 무엇을 이루어냈는가? — 70년간의 이론적 발전

CA의 발전은 단순히 연구자가 늘어나고 응용 분야가 넓어진 과정이 아니다. 연구의 중심 질문 자체가 시대에 따라 달라졌다.

처음에는 '자기복제하는 기계를 만들 수 있는가?'라는 질문에서 출발했다. 이후 '단순한 규칙으로 얼마나 복잡한 계산을 할 수 있는가?'로 발전했고, 다시 '물리현상 자체를 계산 규칙으로 표현할 수 있는가?'라는 질문으로 확장되었다.

오늘날에는 더 근본적인 질문에 도달해 있다.

우리가 살고 있는 우주 자체가 어떤 계산 규칙의 결과라면, 시간과 공간, 물질과 에너지도 그 규칙에서 만들어질 수 있을까?

이 질문에 접근하기 위해 CA의 발전을 시대순으로 살펴보자.

1. 1940~1950년대: 자기복제와 계산의 기초

CA의 초기 연구는 생명체의 자기복제 문제와 연결되어 있었다.

폰 노이만은 자기 자신을 복제하는 기계를 수학적으로 설계하고자 했다. 이 과정에서 복잡한 구조를 구성하는 기본 요소를 작은 셀로 나누고, 각 셀이 주변 셀과 상호작용하도록 만드는 방법을 고안했다.

이 연구가 남긴 중요한 성과는 다음과 같다.

• 공간을 연속적인 평면이 아닌 격자로 표현할 수 있다.

• 각 셀은 제한된 수의 상태를 가질 수 있다.

• 전체 시스템은 국소적인 규칙을 반복 적용해 진화한다.

• 복잡한 구조도 단순한 요소들의 상호작용으로 만들어질 수 있다.

• 자기복제와 범용 계산을 이산적 시스템으로 구현할 수 있다.

이 시기 CA는 생명체의 구조와 계산의 본질을 연구하는 모델이었다.

2. 1960년대: 도달 가능성과 수학적 구조의 정립

1960년대에는 CA의 수학적 성질이 본격적으로 연구되었다.

대표적인 성과는 에덴동산 정리다. 이 정리는 CA의 진화 과정에서 이전 상태로부터 만들어질 수 없는 패턴이 존재할 수 있다는 사실을 보여준다.

이 연구는 CA가 단순히 상태를 바꾸는 규칙의 집합이 아니라, 수학적으로 분석할 수 있는 독립적인 동역학계라는 사실을 분명히 했다.

이 시기에는 다음과 같은 질문들이 중요해졌다.

• 특정 상태가 도달 가능한가?

• 모든 상태에 대응하는 이전 상태가 존재하는가?

• 정보는 진화 과정에서 사라지는가?

• 시간 역방향으로 시스템을 복원할 수 있는가?

이러한 질문은 훗날 가역 CA와 정보 보존 이론의 발전으로 이어졌다.

3. 1970년대: 복잡성의 창발과 범용 계산

1970년 콘웨이의 라이프 게임은 CA의 가능성을 대중적으로 알린 결정적 계기였다.

두 가지 상태만을 갖는 셀들이 단순한 규칙에 따라 움직이는데, 그 결과는 놀라울 정도로 다양했다.

어떤 패턴은 정지하고, 어떤 패턴은 반복되며, 어떤 패턴은 공간을 이동한다. 더 복잡한 구조에서는 계산을 수행할 수 있는 논리적 장치도 구현할 수 있다.

이것은 중요한 철학적 질문을 제기했다.

단순한 구성요소와 단순한 규칙만으로 복잡한 세계가 만들어질 수 있다면, 복잡성은 처음부터 주어진 것이 아니라 규칙의 반복에서 출현하는 것일까?

1970년대 후반 토폴리는 가역 CA를 연구하며 정보의 보존과 물리법칙의 관계를 탐구했다.

이 시기의 주요 성과는 다음과 같다.

• 단순한 규칙으로 복잡한 구조가 만들어지는 창발 현상.

• CA의 범용 계산 능력.

• 역방향 계산이 가능한 가역 CA.

• 물리현상을 이산적인 계산 과정으로 모델링할 수 있다는 가능성.

4. 1980년대: CA의 체계화와 계산적 복잡성

1980년대는 울프럼의 연구를 통해 CA가 본격적인 복잡계 연구의 중심에 등장한 시기다.

울프럼은 1차원 CA의 동작을 분석하면서 네 가지 유형의 행동을 분류했다.

특히 세 번째 유형은 중요하다. 단순한 초기 조건과 규칙에서 출발했지만, 시간이 흐르면서 불규칙하고 복잡한 패턴이 나타난다.

이러한 시스템은 외형상 무작위처럼 보이지만, 실제로는 결정론적인 규칙에 따라 움직일 수 있다.

여기서 중요한 개념이 계산적 비환원성(Computational Irreducibility)이다.

어떤 시스템의 미래 상태를 알고 싶을 때, 그 결과를 간단한 공식으로 계산할 수 없다면 실제로 그 시스템의 진화 과정을 상당 부분 계산해야 할 수 있다는 개념이다.

즉, 시스템이 결정론적이라는 사실이 곧 미래를 쉽게 예측할 수 있다는 뜻은 아니다.

이 개념은 우주가 결정론적 계산 구조일 가능성을 생각할 때 매우 중요하다. 우주의 미래가 원리적으로 정해져 있더라도, 그 미래를 알아내려면 우주 자체가 진행하는 계산을 따라가야 할 수 있기 때문이다.

5. 1980~1990년대: 물리학으로의 확장 — 격자 기체 자동자

CA가 물리학과 연결된 중요한 분야 중 하나가 격자 기체 자동자(Lattice Gas Automata, LGA)다.

LGA에서는 입자들이 격자 위를 이동하고, 같은 위치에 도착한 입자들이 정해진 충돌 규칙에 따라 방향을 바꾼다.

각 입자는 이산적인 상태를 갖고, 이동과 충돌은 반복적인 계산 규칙으로 처리된다.

1986년 프리슈(Frisch), 하슬라허(Hasslacher), 포모(Yves Pomeau)는 결정론적 격자 기체 모델이 유체역학의 핵심 방정식인 나비에-스토크스 방정식을 재현할 수 있음을 보여주었다.

• U. Frisch, B. Hasslacher & Y. Pomeau (1986).

• Lattice-Gas Automata for the Navier-Stokes Equation.

• Physical Review Letters, 56, 1505–1508.

이 연구는 매우 중요한 의미를 갖는다.

유체의 흐름이라는 연속적인 거시 현상이, 이산적인 입자와 국소적인 충돌 규칙으로부터 재현될 수 있음을 보여주었기 때문이다.

1992년과 1993년에는 열적 요동과 밀도 상관관계에 관한 연구가 이어졌다. 격자 기체 모델에서 실제 유체와 유사한 통계적 특성이 나타나는지 분석한 것이다.

• Grosfils, Boon & Lallemand (1992). Spontaneous Fluctuation Correlations in Thermal Lattice-Gas Automata.

• Grosfils, Boon, Brito & Ernst (1993). Statistical Hydrodynamics of Lattice-Gas Automata.

따라서 압력과 온도, 밀도와 유체의 흐름 같은 거시적 물리량이 CA 계열 모델에서 연구된 것은 이미 오래전부터의 일이다.

다만 여기서 주의할 점이 있다. 이 연구들은 이미 격자와 입자, 운동량과 충돌 규칙을 정의한 모델에서 거시적인 물리량을 재현한 것이다. 공간과 입자 자체가 어떻게 발생하는지까지 설명한 것은 아니다.

6. 1990~2000년대: 양자 셀룰러 오토마타의 등장

고전적 CA는 각 셀의 상태가 명확하게 정해져 있고, 다음 상태도 규칙에 따라 결정된다.

그러나 양자역학에서는 중첩과 얽힘, 측정확률 같은 고전적 직관으로 이해하기 어려운 현상이 등장한다.

이를 CA의 구조와 연결하려는 연구가 양자 셀룰러 오토마타(QCA)다.

1996년 데이비드 마이어는 양자 CA와 양자 격자 기체 모델의 이론적 구조를 연구했다. 이 모델에서는 각 셀의 상태가 양자상태로 표현되며, 전체 진화는 유니터리 연산으로 이루어진다.

2004년 슈마허와 베르너는 양자 CA의 구조를 엄밀하게 정리했다. 국소적인 양자 연산이 전체 시스템의 가역적인 시간 진화를 어떻게 구성하는지 연구했다.

이 분야는 양자컴퓨팅과 양자정보, 이산적인 양자장론 모델을 연구하는 중요한 분야가 되었다.

그러나 양자 CA가 등장했다고 해서 고전적 결정론 CA가 양자역학의 확률성을 완전히 설명하게 된 것은 아니다. 양자 CA는 양자역학의 수학적 구조를 이산적인 국소 시스템으로 표현하는 모델이며, 양자확률의 근본 원인을 설명하는 문제는 별도로 남아 있다.

7. 2010년대 이후: 신경망 CA와 복잡한 구조의 자기조직화

최근에는 CA의 국소 규칙을 인공신경망으로 학습시키는 신경망 셀룰러 오토마타(Neural Cellular Automata, NCA)가 연구되고 있다.

전통적인 CA에서는 연구자가 규칙을 직접 설계한다. 반면 NCA에서는 학습 알고리즘을 통해 셀들이 어떤 방식으로 상호작용해야 하는지 스스로 학습하도록 한다.

이 방식은 다음과 같은 분야에서 활용 가능성을 보여준다.

• 손상된 구조의 복원.

• 이미지와 패턴의 자기조직화.

• 생물학적 형태의 생성.

• 분산형 인공지능.

• 자기조립 시스템.

특히 흥미로운 점은 전체를 통제하는 중앙 장치 없이 각 셀이 주변 정보만을 이용해 전체적인 형태를 유지하거나 복원할 수 있다는 사실이다.

이는 생명체의 발생과 조직 유지, 복잡계의 자기조직화를 이해하는 데 새로운 관점을 제공한다.

8. 2020년대: 우주 자체를 계산 구조로 설명하려는 시도

오늘날 CA 연구에서 가장 철학적이고 근본적인 질문은 우주론과 연결되어 있다.

대표적인 흐름이 울프럼의 Wolfram Physics Project다.

이 프로젝트는 전통적인 격자 CA보다 더 일반적인 하이퍼그래프를 사용한다. 하이퍼그래프는 여러 요소가 하나의 관계로 연결될 수 있는 구조다.

이 구조에서 국소적인 재작성 규칙이 반복되면 관계망 자체가 변화한다.

연구자들은 이 변화 과정에서 다음과 같은 개념이 나타날 가능성을 탐구하고 있다.

• 공간: 요소들 사이의 관계와 연결 구조.

• 시간: 관계망이 변화하는 사건들의 순서.

• 인과관계: 어떤 변화가 다른 변화에 영향을 주는 구조.

• 양자현상: 가능한 변화 경로가 여러 갈래로 분기하는 구조.

• 상대론적 성질: 관찰자에 따라 사건의 순서와 기술 방식이 달라지는 문제.

이 연구는 기존 CA의 발전을 한 단계 확장하려는 시도다. 고정된 공간 위에서 셀들이 움직이는 것이 아니라, 공간을 구성하는 관계망 자체가 계산에 따라 만들어지고 변화한다는 발상이기 때문이다.

다만 이러한 연구가 현재의 일반상대성이론이나 양자장론을 대체할 수준으로 완성된 것은 아니다. 아직은 수학적 구조와 물리적 예측을 검증해 나가야 하는 연구 프로그램이다.

제2편의 결론: CA가 실제로 이루어낸 것과 아직 남은 것

연구 분야현재까지의 성과남아 있는 과제

자기복제	자기복제 가능한 CA의 이론적 구성	실제 생명 발생과의 연결
계산이론	범용 계산 능력 증명	자연의 계산 규칙과의 관계
복잡계	단순 규칙에서 복잡성 창발 확인	복잡성의 일반 법칙 정립
가역성	정보 보존형 CA의 수학적 연구	실제 물리법칙과의 완전한 대응
유체역학	격자 기체에서 유체 방정식 재현	근본 공간·시간으로부터의 유도
양자 CA	국소적 유니터리 양자 진화 모델 정립	양자확률의 근본적 설명
우주론	관계망에서 시공간 창발을 탐색	검증 가능한 물리적 예측

CA의 가장 큰 성과는 단순한 국소 규칙만으로도 계산, 복잡성, 유체역학적 현상 등 다양한 구조가 만들어질 수 있음을 보여준 것이다.

그러나 우리가 궁극적으로 알고 싶은 것은 아직 남아 있다.

공간이 먼저 존재하고 그 위에서 계산이 일어나는 것일까? 아니면 계산과 관계의 변화가 반복되면서 공간이라는 개념 자체가 만들어지는 것일까?

이 질문이 다음 단계의 CA 연구를 이끌고 있다.