초등 셀룰러 오토마타

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

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

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

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

다음은 중요한 초등 셀룰러 오토마타의 목록이다.

• Rule 30 — 매우 랜덤한 결과를 내 놓으며, 난수생성에 흔히 쓰인다.
• Rule 110 — 적절한 초기 상태를 주면 튜링 완전한 것으로 알려져 있다.