셀룰러 오토마타

Cellular automaton (CA). 수학적 모델로, 유한한 갯수의 "상태" 중 하나를 가질 수 있는 독립적인 "셀"들로 이루어진 공간이 있고, 각 셀들의 상태가 이산적인 시간에 따라 주변(즉, 유한한 갯수의) 셀의 상태에만 지역적으로 영향을 받는다는 가정 하에 셀들의 반응과 그로부터 생겨나는 구조를 연구하는 목적으로 쓰인다. 복잡계나 이론전산학 등에서 종종 연구되며, 인공생명의 맥락에서 생물학에서 연구하기도 한다.

대표적인 셀룰러 오토마타의 예로 라이프 게임(1970)이 있는데, 이 모델에서 상태는 두 종류–삶·죽음–가 있고, 각 셀은 무한한 2차원 공간에 균일하고 규칙적으로 분포해 있으며, 매 순간마다 8개의 주변 셀들 중 살아 있는 것의 갯수를 세어서 거기에 따라 다음 순간에 해당 셀이 살아 있는지 죽어 있는지가 결정된다. 각 셀은 주변 셀들의 변화에 지역적으로만 반응하며 사실 규칙 또한 매우 단순하지만, 라이프 게임에서 셀들의 반응은 생각보다 훨씬 복잡하며 튜링 완전한 계산까지 할 수 있음이 밝혀졌다. 그 밖에도 셀룰러 오토마타로 분류되는 수학적 모델은 여러 종류가 있다.

• 폰노이만셀룰러오토마타 (최초의 셀룰러 오토마타로 간주된다)
• 라이프 게임
• 랭턴의개미
• 초등 셀룰러 오토마타: Rule 30, Rule 110
• 와이어월드