셀룰러 오토마타

편집 역사 토론
계산물리 시뮬레이션 수치해석 마지막 수정: 2026-07-26 04:12:05

1. 개요[편집]

셀룰러 오토마타(cellular automaton, CA, 세포 자동자)는 이산적인 격자 위의 각 셀이 유한개의 상태를 갖고, 오직 자기 근방의 상태만 보는 동일한 국소 규칙에 따라 모든 셀이 동시에 갱신되는 이산 동역학계다. 미분방정식도, 전역 정보도, 중앙 관리자도 없다. 있는 것은 격자 · 상태집합 · 근방 · 전이규칙 네 가지뿐인데, 이 최소 세팅에서 자기복제와 튜링 완전성과 난류 비슷한 것까지 튀어나온다는 게 이 분야의 전부이자 미친 점이다.1

형식적으로 CA는 사중쌍 (L,S,N,f)(\mathcal{L}, S, N, f) 로 정의된다. L\mathcal{L} 은 격자(보통 Zd\mathbb{Z}^d), SS 는 유한 상태집합, NN 은 근방 벡터, f ⁣:S∣N∣→Sf\colon S^{|N|} \to S 는 국소 전이함수이며, 전체 상태는

σt+1(x)=f(σt(x+n1), …, σt(x+n∣N∣))\sigma^{t+1}(\mathbf{x}) = f\big(\sigma^{t}(\mathbf{x}+\mathbf{n}_1),\,\dots,\,\sigma^{t}(\mathbf{x}+\mathbf{n}_{|N|})\big)

로 동기(synchronous) 갱신된다. 이 “국소 규칙 + 동기 갱신”이라는 골격은 유한차분법의 명시적 시간전진 도식과 구조가 완전히 같다. 차이는 상태가 실수냐 유한집합이냐 하나뿐이다.

2. 폰 노이만과 울람 — 자기복제 기계[편집]

CA는 애초에 물리 시뮬레이션 도구로 태어나지 않았다. 1940년대 말 폰 노이만은 “기계가 자기 자신을 만들 수 있는가”라는 물음에 답하려 했고, 로스앨러모스 동료였던 스타니스와프 울람이 “연속체 말고 격자로 하라”고 조언했다. 그 결과가 29상태 폰 노이만 근방(상하좌우 4개 + 자기 자신) CA 위에 구성된 보편 구성자(universal constructor)다. 자기 자신의 설계도를 테이프처럼 들고 다니며 복사·해석하는 이 구조는 왓슨-크릭의 DNA 이중나선(1953)보다 먼저 나왔다. 폰 노이만이 1957년 사망한 뒤 아서 벅스가 정리해 1966년 Theory of Self-Reproducing Automata 로 출간됐다.

여기서 확인된 것은 결정적이다. 국소 규칙만으로 보편 계산과 보편 구성이 가능하다. 즉 CA는 장난감이 아니라 계산 모형이다.

3. 1차원 기본 규칙과 울프람 분류[편집]

가장 단순한 CA는 1차원, 2상태({0,1}\{0,1\}), 반경 1이다. 근방이 3칸이므로 입력 패턴은 23=82^3 = 8 가지, 각 패턴에 0/1을 배정하는 규칙은 28=2562^8 = 256 개다. 이 256개를 8비트 정수로 번호 매긴 것이 스티븐 울프람의 기본 셀룰러 오토마타(elementary CA)이고, 그 유명한 rule 30 · rule 90 · rule 110이 여기서 나온다.

울프람은 1983년 이 256개(그리고 더 큰 규칙공간)를 시뮬레이션한 뒤 점근 거동을 네 부류로 나눴다.

부류거동대략의 유비
I균일한 고정 상태로 죽음안정 고정점
II주기적·국소적 구조로 정착극한주기궤도
III통계적으로 무작위한 패턴카오스
IV국소 구조가 생겨 오래 상호작용카오스의 가장자리

rule 90은 셀 두 개의 XOR라 시어핀스키 삼각형을 그리는 II~III 경계의 사례이고, rule 30은 완전히 결정론적인데도 중심 열의 수열이 통계적 난수 검정을 통과한다. 실제로 Mathematica의 난수 생성기가 한동안 rule 30을 썼다. rule 110은 IV 부류의 대표로, 매튜 쿡이 1990년대에 튜링 완전임을 증명하고 2004년 논문으로 발표했다.2 이웃 3칸짜리 규칙 하나가 임의의 튜링 기계를 흉내 낼 수 있다는 뜻이다.

주의할 점: 울프람 분류는 경험적 분류지 정리가 아니다. 어떤 규칙이 몇 부류인지 판정하는 문제는 일반적으로 결정 불가능이며, IV와 III의 경계는 지금도 애매하다.

4. 생명 게임 — 창발의 표준 예제[편집]

1970년 존 호턴 콘웨이가 만들고 마틴 가드너가 Scientific American 칼럼으로 퍼뜨린 생명 게임(Game of Life)은 2차원, 2상태, 무어 근방(8이웃) CA다. 규칙은 B3/S23 딱 두 줄이다.

  • 죽은 셀은 살아 있는 이웃이 정확히 3개면 태어난다(Birth).
  • 산 셀은 이웃이 2개나 3개면 살아남고, 아니면 죽는다(Survival — 과소·과밀).
콘웨이 생명 게임 B3/S23을 120×68 토러스 격자에서 매 프레임 실제로 갱신한다. 각 셀은 무어 근방 8개의 살아 있는 이웃 수만 세어 다음 상태를 정하며, 전역 규칙이나 미리 만든 애니메이션은 일절 없다. 슬라이더는 초기 무작위 생존 밀도이고 0.28 근처에서 시작하면 과도기 뒤에 블록·연못 같은 정지물과 깜빡이, 이따금 격자를 가로지르는 글라이더가 남는다. 경계는 주기적으로 감싸므로 무한 평면에서의 점근 거동과는 다르며, 세대 진행은 가독성을 위해 몇 프레임에 한 번씩 이뤄진다.

이 두 줄에서 정지물(block, beehive), 진동자(blinker, pulsar), 이동체(glider), 그리고 글라이더를 무한히 뿜어내는 글라이더 건(빌 고스퍼, 1970)이 나온다. 고스퍼의 발견은 생명 게임에서 셀 개수가 무한히 증가할 수 있음을 보였고, 이는 곧 글라이더를 신호로 삼는 논리 게이트 구성으로 이어져 생명 게임 역시 튜링 완전임이 증명됐다. 실제로 생명 게임 격자 안에 생명 게임을 돌리는 메타픽셀 구현까지 존재한다.3

여기서 얻는 교훈이 창발과 자기조직화 논의의 출발점이다. 복잡한 거시 구조를 만드는 데 복잡한 규칙은 필요 없다. 단순한 국소 규칙 + 많은 셀 + 많은 시간이면 된다.

5. CA로 물리를 푼다는 것[편집]

CA를 편미분방정식 솔버로 쓰는 흐름은 두 갈래다.

첫째, 미시 CA에서 거시 방정식을 유도하는 길. 격자 위에서 입자를 충돌·병진시키는 격자 기체 오토마타(HPP/FHP)는 셀 상태가 불리언인데도 거시 극한에서 나비에-스토크스 방정식을 재현한다. 다만 불리언 표현 탓에 통계 잡음이 심해, 분포함수를 실수로 바꾼 격자 볼츠만 방법에 자리를 내줬다. 이 계보의 자세한 서술은 해당 문서들로 넘긴다.

둘째, 명시적 차분 도식을 CA로 읽는 길. 1차원 확산방정식의 FTCS 도식

uin+1=uin+ν (ui+1n−2uin+ui−1n),ν=αΔtΔx2u_i^{n+1} = u_i^{n} + \nu\,(u_{i+1}^{n} - 2u_i^{n} + u_{i-1}^{n}), \qquad \nu = \frac{\alpha \Delta t}{\Delta x^{2}}

는 근방 3칸을 보는 국소 규칙 그 자체다. 안정 조건 ν≤1/2\nu \le 1/2 역시 “정보가 한 스텝에 한 칸 이상 못 간다”는 CFL 조건의 CA 판이다. 반응-확산으로 무늬가 생기는 튜링 패턴, 지진 모형, 군중 시뮬레이션의 바닥장 모형, 나겔-슈레켄베르크 교통 CA가 모두 이 관점의 응용이다.

한 가지 정직하게 짚을 것: CA로 유체를 풀면 격자 대칭성이 물리에 새어 들어온다. HPP가 정사각격자 때문에 등방성을 잃어 실패하고 FHP가 육각격자로 살아난 사건이 그 증거다. 이산 규칙은 공짜가 아니다.

6. 병렬성 — CA의 진짜 무기[편집]

CA의 갱신은 (1) 완전히 국소적이고 (2) 완전히 동일한 규칙이며 (3) 모든 셀이 서로 독립이다. 이는 SIMD/SIMT 하드웨어가 원하는 조건 그 자체다. GPU 컴퓨팅에서 CA는 셀 하나당 스레드 하나를 배정하고 이전 세대 버퍼를 읽어 다음 세대 버퍼에 쓰는 핑퐁 구조로 거의 선형 확장된다. 통신은 도메인 분할 시 경계 한 겹(halo)만 교환하면 끝이라 병렬 컴퓨팅 관점에서 통신/계산 비가 매우 유리하다. 1980년대 MIT의 토폴리·마골러스가 CA 전용 하드웨어 CAM-8을 만든 것도 이 성질 때문이었다.

주의할 함정은 딱 하나, 동기성이다. 갱신 중인 버퍼를 그대로 읽으면 그것은 더 이상 같은 CA가 아니다(비동기 CA는 아예 다른 동역학을 갖는다). 버퍼 두 개를 쓰거나 주기경계조건 halo를 정확히 맞추는 것이 구현의 90%다.

한편 CA 규칙을 되돌릴 수 있게 만든 가역 CA(2차 CA, 프레드킨)는 정보 손실이 없어 이산적 해밀토니안 역학 유비로 연구된다. 랭턴이 1986년 만든 랭턴의 개미는 규칙 두 줄짜리 튜링 기계인데도 약 1만 스텝의 무질서 뒤에 폭 104칸의 주기적 “고속도로”를 짓는다. 왜 그런지는 여전히 증명되지 않았다.4

7. 관련 문서[편집]

8. Footnotes[편집]

  1. 울프람은 2002년 1200쪽짜리 A New Kind of Science 에서 “우주 자체가 단순한 규칙의 CA일지 모른다”고 주장했다. 학계 반응은 “관찰은 훌륭하고 주장은 과하다”로 요약된다. 심위키 입장도 대체로 같다 — 규칙은 신에게 맡기고 우리는 격자나 잘 짜자. ↩

  2. 쿡은 당시 울프람 리서치 소속이었고, 증명 공개를 둘러싸고 비밀유지계약 분쟁이 있었다. 튜링 완전성 증명이 법무팀을 거쳐 나온 흔치 않은 사례. ↩

  3. OTCA 메타픽셀. 생명 게임 셀 하나를 생명 게임 패턴 2048×2048로 구현한 물건이다. 즉 생명 게임 안에서 생명 게임이 돌아간다. 프레임 하나 보려면 현생을 포기해야 한다. ↩

  4. “랭턴 개미의 궤적은 항상 무한하다”는 정리는 증명됐지만, “항상 고속도로를 짓는다”는 미해결이다. 규칙 두 줄을 못 푸는 인류가 나비에-스토크스 방정식은 어떻게 풀려고 하는 걸까. ↩