Wolfram's Rule 110

Wolfram's Rule 110 is a remarkable one-dimensional cellular automaton from Stephen Wolfram's classification of "elementary" rules. Each cell in this linear grid can be in one of two states: 0 (off) or 1 (on). With every step, the next row of cells is determined by looking at triples in the current row—each cell plus its two neighbors. The pattern of which triplets produce a 1 in the next generation is encoded by the binary number 110.

Despite its minimal definition—just a handful of bits describing which local arrangements become "on"—Rule 110 demonstrates incredibly rich and complex behavior. It's even been proven to be Turing-complete under certain initial conditions, placing it on par with systems that can, in theory, perform universal computation.

How it works →

The Rule

In elementary cellular automaton terminology, the decimal rule number 110 corresponds to the bit pattern 01101110 when read from the '111' triplet down to '000.' That means certain triplets (like 110, 101, 011, 001) yield a live cell in the next generation, while others result in a dead cell.

Despite the straightforward naming convention, the behaviors that emerge can be surprisingly complex. You'll see chaotic regions, repetitive patterns, and all manner of interactions driven by these simple triplet rules.

Emergence & Complexity

One of the most intriguing aspects of Rule 110 is how a single row of bits can evolve into structures that look like moving particles, collisions, or wavefronts. Tiny changes in the initial row can drastically alter the unfolding tapestry, highlighting the system's sensitivity to initial conditions. This emergent complexity arises purely from local interactions—no central coordination is required.

In certain configurations, you'll witness stable regions, "gliders," and repeating or chaotic expansions that underscore the system's depth. Researchers have studied this automaton extensively to understand how simple deterministic systems might exhibit patterns that appear random or are at least computationally irreducible.

Turing Completeness

Rule 110 can be configured to compute anything a universal Turing machine can, making it Turing-complete. That means if you set up the initial row in just the right way, you can theoretically emulate logical operations, memory, and any fundamental computing element within this small automaton. It's a striking demonstration that complexity can arise from even the simplest set of rules—it's the repeated local interactions over time that yield powerful behavior.

Algorithmic Overview

Below is a straightforward approach to computing each new row. We optionally wrap edges so cells on one side can see neighbors on the opposite side. If this is disabled, edges are considered "dead" beyond the grid:

// 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
};

And here's how we apply it during each update (although our final implementation uses the bitshift approach, this table is an alternate expression of which triplets yield a live cell):

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;
}