울프람의 규칙 110

Wolfram의 규칙 110은 Stephen Wolfram의 '기본' 규칙 분류에 속하는 주목할 만한 1차원 셀룰러 오토마톤입니다. 이 선형 그리드의 각 셀은 0(꺼짐) 또는 1(켜짐)의 두 상태 중 하나를 가질 수 있습니다. 매 단계마다 다음 행의 셀은 현재 행의 트리플(각 셀과 두 이웃)을 보고 결정됩니다. 어떤 트리플이 다음 세대에서 1을 생성하는지의 패턴은 이진수 110으로 인코딩됩니다.

최소한의 정의—어떤 로컬 배열이 '켜짐'이 되는지를 설명하는 몇 비트—에도 불구하고, 규칙 110은 놀랍도록 풍부하고 복잡한 행동을 보여줍니다. 특정 초기 조건에서 튜링 완전함이 증명되어, 이론적으로 범용 계산을 수행할 수 있는 시스템과 동등합니다.

작동 방식 →

규칙

기본 셀룰러 오토마톤 용어에서, 십진수 규칙 번호 110은 '111' 트리플부터 '000'까지 읽을 때 비트 패턴 01101110에 해당합니다. 이는 특정 트리플(110, 101, 011, 001 등)이 다음 세대에서 살아있는 셀을 생성하고, 나머지는 죽은 셀이 됨을 의미합니다.

간단한 명명 규칙에도 불구하고, 나타나는 행동은 놀랍도록 복잡할 수 있습니다. 이 간단한 트리플 규칙에 의해 구동되는 혼돈 영역, 반복 패턴, 그리고 모든 종류의 상호작용을 볼 수 있습니다.

창발과 복잡성

규칙 110의 가장 흥미로운 측면 중 하나는 단일 비트 행이 움직이는 입자, 충돌 또는 파면처럼 보이는 구조로 진화하는 방식입니다. 초기 행의 작은 변화가 펼쳐지는 태피스트리를 극적으로 바꿀 수 있어, 시스템의 초기 조건에 대한 민감성을 강조합니다. 이 창발적 복잡성은 순전히 로컬 상호작용에서 발생하며, 중앙 조정이 필요하지 않습니다.

특정 구성에서는 안정적인 영역, 'Glider', 그리고 반복되거나 혼돈스러운 확장을 목격하게 되며, 이는 시스템의 깊이를 강조합니다. 연구자들은 단순한 결정론적 시스템이 어떻게 무작위로 보이거나 최소한 계산적으로 환원 불가능한 패턴을 나타낼 수 있는지 이해하기 위해 이 오토마톤을 광범위하게 연구해왔습니다.

튜링 완전성

규칙 110은 범용 튜링 기계가 계산할 수 있는 모든 것을 계산하도록 구성할 수 있어, 튜링 완전합니다. 이는 초기 행을 올바른 방식으로 설정하면, 이 작은 오토마톤 내에서 논리 연산, 메모리, 그리고 모든 기본 계산 요소를 이론적으로 에뮬레이션할 수 있음을 의미합니다. 이것은 가장 단순한 규칙 세트에서도 복잡성이 발생할 수 있다는 인상적인 시연입니다. 시간에 걸친 반복적인 로컬 상호작용이 강력한 행동을 만들어냅니다.

알고리즘 개요

다음은 각 새로운 행을 계산하는 간단한 접근 방식입니다. 선택적으로 가장자리를 래핑하여 한쪽의 셀이 반대쪽의 이웃을 볼 수 있게 합니다. 이것이 비활성화되면 그리드 너머의 가장자리는 '죽음'으로 간주됩니다:

// Rule 110 transition table - maps each 3-bit pattern to its next state
const transitions = {
  // pattern => next state
  '111': 0,
  '110': 1,
  '101': 1,
  '100': 0,
  '011': 1,
  '010': 1,
  '001': 1,
  '000': 0
};

그리고 각 업데이트 중에 이를 적용하는 방법입니다 (최종 구현은 비트시프트 접근 방식을 사용하지만, 이 테이블은 어떤 트리플이 살아있는 셀을 생성하는지의 대안적 표현입니다):

function computeNextRow(currentRow, wrapEdges) {
  const length = currentRow.length;
  const newRow = new Array(length).fill(0);

  for (let i = 0; i < length; i++) {
    const leftIndex  = wrapEdges ? (i - 1 + length) % length : i - 1;
    const rightIndex = wrapEdges ? (i + 1) % length : i + 1;

    const left   = (leftIndex < 0 || leftIndex >= length) ? 0 : currentRow[leftIndex];
    const center = currentRow[i];
    const right  = (rightIndex < 0 || rightIndex >= length) ? 0 : currentRow[rightIndex];

    const pattern = (left << 2) | (center << 1) | right;
    newRow[i] = (110 >> pattern) & 1;
  }
  return newRow;
}