셀룰러 오토마타, 우주는 계산하고 있는가? — 단순한 규칙에서 물리적 세계의 창발까지

 

제1편. 셀룰러 오토마타의 탄생과 발전을 이끈 학자들

셀룰러 오토마타(Cellular Automata, 이하 CA)는 매우 단순한 규칙을 가진 작은 단위들이 모여 복잡한 전체 현상을 만들어 내는 수학적·계산적 모델이다. 하나의 셀은 몇 가지 상태 중 하나를 가지며, 주변 셀의 상태를 바탕으로 다음 상태를 결정한다. 이 과정이 반복되면 처음에는 상상하기 어려웠던 복잡한 패턴과 구조가 나타난다.

CA가 흥미로운 이유는 단순히 컴퓨터 화면에서 아름다운 무늬를 만들어 내기 때문이 아니다. 생명체의 자기복제, 물질의 성장, 유체의 흐름, 복잡계의 형성처럼 자연에서 관찰되는 현상들이 국소적인 상호작용의 반복으로 만들어질 수 있는지 탐구할 수 있기 때문이다. 더 나아가 일부 연구자들은 자연의 근본 법칙 자체가 이러한 계산 규칙으로 표현될 가능성까지 탐색하고 있다.

그렇다면 CA는 누가 처음 생각했고, 어떤 과정을 거쳐 지금의 이론으로 발전했을까?

1. 노버트 위너와 아르투로 로젠블루스: 생명현상을 이산적 요소로 바라본 선구적 발상

CA의 직접적인 창시자로 가장 널리 인정받는 인물은 존 폰 노이만(John von Neumann)이지만, 그보다 앞서 연결된 요소들의 국소적인 작용으로 생물학적 현상을 설명하려는 연구가 있었다.

1946년 노버트 위너(Norbert Wiener)와 아르투로 로젠블루스(Arturo Rosenblueth)는 심장근육과 같은 흥분성 조직에서 신호가 전달되는 과정을 수학적으로 모델링했다. 이 연구는 모든 세포가 동일한 방식으로 반응하는 것이 아니라, 이웃 요소와의 상호작용을 통해 전체적인 파동과 신호 전달이 형성될 수 있다는 관점을 보여주었다.

• 주요 논문: The Mathematical Formulation of the Problem of Conduction of Impulses in a Network of Connected Excitable Elements, 1946.

• 핵심 의미: 복잡한 생명현상을 개별 요소들의 연결과 국소적 반응으로 설명하려는 시도.

이 연구를 현대적인 CA와 완전히 동일한 이론이라고 부를 수는 없다. 다만 생명현상을 연속적인 물질의 흐름이 아니라 이산적인 요소들의 상호작용으로 이해하려는 초기 흐름이라는 점에서 의미가 있다.

2. 스타니스와프 울람과 존 폰 노이만: CA의 본격적인 탄생

CA의 역사에서 가장 중요한 출발점은 스타니스와프 울람(Stanislaw Ulam)과 존 폰 노이만이다.

울람은 로스앨러모스 연구소에서 수학적 격자 위에 단순한 성장 규칙을 적용하면 복잡한 형태가 만들어질 수 있다는 생각을 발전시켰다. 그는 공간을 연속적인 평면으로만 취급하지 않고, 작은 칸들이 모인 이산적인 구조로 표현하는 접근을 제안했다.

이 아이디어에 주목한 폰 노이만은 생명체의 자기복제를 수학적으로 설명하려 했다. 생명체가 자신과 동일한 구조를 만들어 낼 수 있다면, 그 과정은 어떤 논리적 규칙으로 구성될 수 있을까?

폰 노이만은 각 셀이 29개의 상태 중 하나를 갖는 복잡한 2차원 CA를 고안했다. 이 모델은 자기 자신을 복제하는 구조를 만들 수 있었으며, 단순한 국소 규칙을 이용해 범용 계산을 수행할 수 있다는 점도 이론적으로 보여주었다.

• 주요 저작: John von Neumann, The General and Logical Theory of Automata, 1951년 강연에 기초한 저작.

• 관련 정리·편집본: Arthur W. Burks 편, Theory of Self-Reproducing Automata, 1966.

• 핵심 주장: 자기복제와 복잡한 계산은 국소적인 규칙을 가진 이산적 시스템으로 구현될 수 있다.

여기서 중요한 변화가 생겼다. CA는 단순한 수학적 놀이가 아니라 생명체의 자기복제와 계산의 본질을 연구하는 이론적 도구가 되었다.

3. 에드워드 무어와 존 마이힐: CA의 수학적 구조를 정립하다

1960년대에는 CA의 동작 원리와 수학적 성질을 엄밀하게 연구하는 흐름이 나타났다.

에드워드 무어(Edward F. Moore)와 존 마이힐(John Myhill)은 이른바 ‘에덴동산 정리(Garden of Eden theorem)’와 관련된 연구를 발전시켰다.

에덴동산 패턴이란 이전 단계의 어떤 상태에서도 만들어질 수 없는 패턴을 뜻한다. 즉, CA의 진화 과정에서 자연스럽게 도달할 수 없는 상태가 존재할 수 있다는 것이다.

이 연구는 CA의 시간 역방향 구조, 상태의 도달 가능성, 정보의 소실과 보존 등을 이해하는 중요한 기반이 되었다.

• Edward F. Moore, Machine Models of Self-Reproduction, 1962.

• John Myhill, The Converse to Moore's Garden-of-Eden Theorem, 1963.

• 핵심 의미: CA의 상태 전이와 도달 가능성을 수학적으로 분석할 수 있는 기반을 마련했다.

이 시기의 연구는 훗날 가역 CA와 정보 보존 문제를 이해하는 데도 중요한 토대가 되었다.

4. 존 콘웨이: 게임을 통해 복잡성의 창발을 보여주다

1970년 수학자 존 호턴 콘웨이(John Horton Conway)는 유명한 ‘라이프 게임(Game of Life)’을 발표했다.

라이프 게임은 2차원 격자 위에서 각 셀이 살아 있거나 죽어 있는 두 가지 상태만 갖는다. 각 셀은 주변 8개 셀의 상태를 확인하고 다음 규칙에 따라 살아남거나 죽거나 새롭게 태어난다.

규칙은 놀라울 정도로 단순하다.

• 살아 있는 셀 주변에 살아 있는 셀이 2개 또는 3개 있으면 생존한다.

• 살아 있는 셀 주변에 살아 있는 셀이 1개 이하이면 고립되어 죽는다.

• 살아 있는 셀 주변에 살아 있는 셀이 4개 이상이면 과밀로 죽는다.

• 죽은 셀 주변에 살아 있는 셀이 정확히 3개 있으면 새로운 생명이 탄생한다.

그런데 이 단순한 규칙에서 움직이는 패턴, 진동하는 구조, 자기복제와 유사한 패턴, 심지어 범용 계산을 구현할 수 있는 구조까지 나타난다.

콘웨이의 연구는 단순한 규칙이 반드시 단순한 결과를 낳는 것은 아니라는 사실을 대중적으로 보여주었다.

• 주요 저작: Berlekamp, Conway, Guy, Winning Ways for Your Mathematical Plays, 1982.

• 핵심 의미: 국소적인 규칙의 반복만으로 복잡한 패턴과 계산 능력이 창발할 수 있음을 보여주었다.

5. 토마소 토폴리와 노먼 마골러스: 물리법칙을 계산 규칙으로 표현하다

1970년대 후반부터 CA는 물리학과 직접 연결되기 시작했다.

토마소 토폴리(Tommaso Toffoli)는 CA를 단순한 계산 모델이 아니라 물리적 현상을 표현하는 대안적 모델로 바라보았다. 특히 중요한 주제는 가역성(reversibility)이었다.

일반적인 계산 과정에서는 이전 상태의 정보가 사라질 수 있다. 하지만 물리학의 근본적인 법칙을 정보의 보존이라는 관점에서 이해하려면, 이전 상태를 역으로 복원할 수 있는 계산 규칙이 중요해진다.

토폴리와 노먼 마골러스(Norman Margolus)는 가역 CA의 수학적 구조를 발전시켰다.

• Tommaso Toffoli, Computation and Construction Universality of Reversible Cellular Automata, 1977.

• Tommaso Toffoli, Cellular Automata as an Alternative to (Rather Than an Approximation of) Differential Equations in Modeling Physics, 1984.

• Toffoli & Margolus, Invertible Cellular Automata: A Review, 1990.

핵심 주장은 물리적 현상을 반드시 연속적인 미분방정식으로만 표현해야 하는 것은 아니라는 것이다. 이산적인 공간과 시간, 국소적인 계산 규칙으로도 물리현상을 모델링할 수 있다는 가능성을 제시했다.

6. 스티븐 울프럼: 단순한 규칙에서 복잡성이 만들어지는 원리를 체계화하다

1980년대 CA 연구를 대중적·학문적으로 크게 확장한 인물은 스티븐 울프럼(Stephen Wolfram)이다.

그는 특히 1차원 CA를 체계적으로 연구했다. 한 줄로 배열된 셀들이 0 또는 1의 상태를 가지며, 각 셀의 다음 상태가 자신과 양옆 셀의 상태에 의해 결정되는 모델이다.

울프럼은 이러한 간단한 CA에서 나타나는 패턴을 관찰하고, 그 동작을 네 가지 유형으로 분류했다.

1. 단순하고 균일한 상태로 수렴하는 유형

2. 반복적이고 주기적인 패턴이 나타나는 유형

3. 복잡하고 불규칙한 패턴이 나타나는 유형

4. 질서와 복잡성이 혼재하는 구조가 나타나는 유형

이 분류는 단순한 규칙으로부터 복잡성이 만들어지는 과정을 이해하는 중요한 출발점이 되었다.

대표 논문은 다음과 같다.

• Stephen Wolfram, Statistical Mechanics of Cellular Automata, Reviews of Modern Physics, 1983.

• Stephen Wolfram, Universality and Complexity in Cellular Automata, Physica D, 1984.

울프럼은 훗날 저서 A New Kind of Science(2002)를 통해 자연의 복잡한 현상도 단순한 계산 규칙의 반복으로 설명할 수 있다는 관점을 더욱 발전시켰다.

7. 매튜 쿡: 단순한 CA도 범용 컴퓨터가 될 수 있음을 증명하다

울프럼이 주목했던 Rule 110은 매우 단순한 1차원 CA 규칙이다. 그런데 매튜 쿡(Matthew Cook)은 이 규칙이 범용 계산 능력을 갖는다는 사실을 증명했다.

이는 CA의 역사에서 매우 중요한 성과다.

범용 계산이 가능하다는 것은 적절한 초기 조건을 주면 이 시스템이 원리적으로 컴퓨터가 수행할 수 있는 모든 종류의 계산을 모방할 수 있다는 뜻이다.

• Matthew Cook, Universality in Elementary Cellular Automata, Complex Systems, 2004.

• 핵심 의미: 매우 단순한 국소 규칙도 충분히 복잡한 계산을 수행할 수 있다.

8. 오늘날의 연구자들: CA를 양자물리학과 우주론으로 확장하다

1990년대 이후 CA는 고전적 계산 모델을 넘어 양자물리학과 연결되기 시작했다.

데이비드 마이어(David A. Meyer)는 양자 셀룰러 오토마타(Quantum Cellular Automata, QCA)를 연구했다. 고전적 CA의 셀 상태가 0과 1 같은 고전적 값이라면, QCA에서는 양자상태와 유니터리 연산을 이용한다.

• David A. Meyer, From Quantum Cellular Automata to Quantum Lattice Gases, 1996.

• B. Schumacher & R. F. Werner, Reversible Quantum Cellular Automata, 2004.

이후 양자 CA는 양자정보, 양자컴퓨팅, 양자장론의 이산적 모델을 연구하는 분야로 발전했다.

한편 스티븐 울프럼은 2020년부터 Wolfram Physics Project를 통해 CA보다 일반화된 하이퍼그래프 재작성(hypergraph rewriting) 모델을 이용해 공간과 시간, 인과관계, 양자현상의 창발을 탐구하고 있다.

이 연구는 아직 확립된 물리학 이론은 아니지만, 우주를 고정된 공간 위에서 움직이는 물질의 집합이 아니라 관계망의 변화 과정으로 이해하려는 시도라는 점에서 주목할 만하다.

제1편의 결론

CA의 역사는 세 가지 큰 변화로 요약할 수 있다.

첫째, 생명체의 자기복제와 같은 현상을 이산적인 규칙으로 설명하려는 시도에서 출발했다.

둘째, 단순한 국소 규칙이 복잡한 패턴과 범용 계산 능력을 만들어 낼 수 있다는 사실이 수학적으로 입증되었다.

셋째, 이러한 계산 구조가 물리현상과 양자역학, 나아가 우주의 근본 구조를 설명할 수 있는지 탐색하는 단계로 확장되고 있다.

CA는 이제 단순한 컴퓨터 알고리즘이 아니다. 자연의 복잡성을 이해하기 위한 하나의 사고방식이자, 물리학의 근본 원리를 새롭게 바라보게 하는 연구 틀로 발전하고 있다.

주요 참고문헌

• von Neumann, J. (1951). The General and Logical Theory of Automata.

• Moore, E. F. (1962). Machine Models of Self-Reproduction.

• Myhill, J. (1963). The Converse to Moore's Garden-of-Eden Theorem.

• Toffoli, T. (1977). Computation and Construction Universality of Reversible Cellular Automata.

• Wolfram, S. (1983). Statistical Mechanics of Cellular Automata. Reviews of Modern Physics, 55, 601–644.

• Wolfram, S. (1984). Universality and Complexity in Cellular Automata. Physica D, 10, 1–35.

• Cook, M. (2004). Universality in Elementary Cellular Automata. Complex Systems.

• Meyer, D. A. (1996). From Quantum Cellular Automata to Quantum Lattice Gases.

• Schumacher, B. & Werner, R. F. (2004). Reversible Quantum Cellular Automata.