cellular automaton

An elementary (1D) cellular automaton explorer — pick a rule, pick a seed, watch it unfold.

rule

seed

rule 110 — Turing-complete (proved by Matthew Cook, 1998/2004)

Click a tile's output square to flip that bit of the rule.

the rule

An elementary cellular automaton is the smallest interesting machine of its kind: a single row of cells, each either on or off, where every cell's next value depends only on itself and its two immediate neighbors,

s_i^{\,t+1} \;=\; f\bigl(s_{i-1}^{\,t},\; s_i^{\,t},\; s_{i+1}^{\,t}\bigr)

and the only thing that varies between rules is $f$ . Three cells with two states each gives $2^3 = 8$ possible neighborhoods, and $f$ is nothing more than a choice of output for each one — eight bits, so exactly $2^8 = 256$ rules exist, and the number in the picker is that byte read as a decimal. Each new row is drawn below the last, so the image is a complete history: time runs downward, space runs across.

wolfram's classes

Stephen Wolfram's classification is the useful lens for browsing them. Some rules die out to blank, some settle into stripes that repeat forever, some produce what looks indistinguishable from noise — rule 30 is the classic example, random-looking enough that Wolfram used its center column as Mathematica's pseudorandom integer generator — and a small handful land in a fourth category, where localized structures move across a patterned background and interact when they collide.

rule 110

Rule 110 is the famous member of that fourth group, and the reason this whole family gets taken seriously. Matthew Cook proved it Turing-complete — it can simulate any Turing machine, and therefore compute anything computable — with a proof whose publication was tangled up in a dispute with Wolfram Research over A New Kind of Science, and which eventually appeared in 2004. Among the 88 elementary rules that are genuinely distinct once you account for symmetry, rule 110 is the only one whose universality has been proven directly.

in two dimensions

Conway's Game of Life is also a cellular automaton — just a two-dimensional one, where each cell looks at all eight neighbors instead of the two an elementary rule considers. That extra dimension and neighborhood size is what lets Life support its rich zoo of gliders, guns, and oscillators. Rule 110 reaches the same destination from the opposite direction: one dimension, two states, a neighborhood of three. It is about as minimal as a system can be while still computing anything computable, which is exactly what made Cook's result a landmark. For the contrast with a machine that can't do this, the regex visualizer builds finite automata, which have no unbounded memory to spread structure across.

view source

import { useEffect, useRef, useState } from 'react';

const CELL = 4;

type SeedMode = 'center' | 'random' | 'paint';

const SEED_MODES: SeedMode[] = ['center', 'random', 'paint'];

const PRESETS: { rule: number; caption: string }[] = [
  { rule: 30, caption: "chaotic — was Mathematica's default RNG for years" },
  { rule: 90, caption: 'Sierpinski triangle via XOR' },
  { rule: 110, caption: 'Turing-complete (proved by Matthew Cook, 1998/2004)' },
  { rule: 184, caption: 'traffic flow model' },
];

function nextGen(row: number[], rule: number): number[] {
  const w = row.length;
  return row.map((_, i) => {
    const l = row[(i - 1 + w) % w];
    const c = row[i];
    const r = row[(i + 1) % w];
    const idx = (l << 2) | (c << 1) | r;
    return (rule >> idx) & 1;
  });
}

function randomRow(width: number): number[] {
  return Array.from({ length: width }, () => (Math.random() < 0.5 ? 1 : 0));
}

function centerRow(width: number): number[] {
  const row = Array<number>(width).fill(0);
  row[Math.floor(width / 2)] = 1;
  return row;
}

interface Props {
  initialRule?: number;
}

export default function CellularAutomaton({ initialRule = 110 }: Props) {
  const canvasRef = useRef<HTMLCanvasElement>(null);
  const [rule, setRule] = useState(initialRule);
  const [seedMode, setSeedMode] = useState<SeedMode>('center');
  const [paintedRow, setPaintedRow] = useState<number[] | null>(null);

  const ruleRef = useRef(rule);
  const seedModeRef = useRef(seedMode);
  const paintedRowRef = useRef(paintedRow);
  const colsRef = useRef(0);
  const redrawRef = useRef<() => void>(() => {});

  useEffect(() => {
    ruleRef.current = rule;
    redrawRef.current();
  }, [rule]);
  useEffect(() => {
    seedModeRef.current = seedMode;
    redrawRef.current();
  }, [seedMode]);
  useEffect(() => {
    paintedRowRef.current = paintedRow;
    redrawRef.current();
  }, [paintedRow]);

  useEffect(() => {
    const canvas = canvasRef.current;
    if (!canvas) return;
    const ctx = canvas.getContext('2d');
    if (!ctx) return;

    const seedRow = (width: number): number[] => {
      const mode = seedModeRef.current;
      if (mode === 'paint') {
        const painted = paintedRowRef.current;
        return painted && painted.length === width
          ? painted
          : Array<number>(width).fill(0);
      }
      if (mode === 'random') return randomRow(width);
      return centerRow(width);
    };

    const draw = () => {
      const rect = canvas.getBoundingClientRect();
      const dpr = window.devicePixelRatio || 1;
      canvas.width = rect.width * dpr;
      canvas.height = rect.height * dpr;
      ctx.setTransform(dpr, 0, 0, dpr, 0, 0);

      const cols = Math.floor(rect.width / CELL);
      const rows = Math.floor(rect.height / CELL);
      colsRef.current = cols;

      ctx.fillStyle = '#000';
      ctx.fillRect(0, 0, rect.width, rect.height);
      ctx.fillStyle = '#e6e6e6';

      let row = seedRow(cols);
      for (let y = 0; y < rows; y++) {
        for (let x = 0; x < cols; x++) {
          if (row[x]) ctx.fillRect(x * CELL, y * CELL, CELL, CELL);
        }
        row = nextGen(row, ruleRef.current);
      }
    };

    redrawRef.current = draw;
    draw();

    let painting = false;
    let paintValue = 1;

    const columnAt = (clientX: number) => {
      const rect = canvas.getBoundingClientRect();
      return Math.floor((clientX - rect.left) / CELL);
    };

    const paintAt = (clientX: number) => {
      const col = columnAt(clientX);
      const width = colsRef.current;
      if (col < 0 || col >= width) return;
      const current = paintedRowRef.current;
      const base =
        current && current.length === width
          ? [...current]
          : Array<number>(width).fill(0);
      base[col] = paintValue;
      paintedRowRef.current = base;
      setPaintedRow(base);
    };

    const onPointerDown = (e: PointerEvent) => {
      const col = columnAt(e.clientX);
      const width = colsRef.current;
      if (col < 0 || col >= width) return;
      if (seedModeRef.current !== 'paint') setSeedMode('paint');
      const current = paintedRowRef.current;
      const base =
        current && current.length === width
          ? current
          : Array<number>(width).fill(0);
      paintValue = base[col] ? 0 : 1;
      painting = true;
      paintAt(e.clientX);
    };
    const onPointerMove = (e: PointerEvent) => {
      if (!painting) return;
      paintAt(e.clientX);
    };
    const stopPainting = () => {
      painting = false;
    };

    canvas.addEventListener('pointerdown', onPointerDown);
    window.addEventListener('pointermove', onPointerMove);
    window.addEventListener('pointerup', stopPainting);

    const onResize = () => draw();
    window.addEventListener('resize', onResize);

    return () => {
      canvas.removeEventListener('pointerdown', onPointerDown);
      window.removeEventListener('pointermove', onPointerMove);
      window.removeEventListener('pointerup', stopPainting);
      window.removeEventListener('resize', onResize);
    };
  }, []);

  const toggleBit = (idx: number) => setRule((r) => r ^ (1 << idx));

  const regenerate = () => {
    if (seedMode === 'paint') {
      setPaintedRow(null);
    } else {
      redrawRef.current();
    }
  };

  const activeCaption = PRESETS.find((p) => p.rule === rule)?.caption;

  return (
    <div className="cellular-automaton">
      <div className="ca-canvas">
        <canvas
          ref={canvasRef}
          aria-label={`Elementary cellular automaton, rule ${rule}`}
          role="img"
        />
      </div>

      <div className="controls">
        <div className="group">
          <span className="group-label">rule</span>
          {PRESETS.map((p) => (
            <button
              key={p.rule}
              type="button"
              className={rule === p.rule ? 'active' : ''}
              title={p.caption}
              onClick={() => setRule(p.rule)}
            >
              {p.rule}
            </button>
          ))}
        </div>
        <div className="group">
          <span className="group-label">seed</span>
          {SEED_MODES.map((mode) => (
            <button
              key={mode}
              type="button"
              className={seedMode === mode ? 'active' : ''}
              onClick={() => setSeedMode(mode)}
            >
              {mode}
            </button>
          ))}
        </div>
        <button type="button" className="regenerate" onClick={regenerate}>
          regenerate
        </button>
      </div>

      <p className="rule-caption">
        rule {rule}
        {activeCaption ? ` — ${activeCaption}` : ''}
      </p>

      <div className="rule-table">
        <p className="hint">
          Click a tile's output square to flip that bit of the rule.
        </p>
        <div className="tiles">
          {[7, 6, 5, 4, 3, 2, 1, 0].map((idx) => (
            <div className="tile" key={idx}>
              <div className="pattern">
                <span className={(idx >> 2) & 1 ? 'on' : ''} />
                <span className={(idx >> 1) & 1 ? 'on' : ''} />
                <span className={idx & 1 ? 'on' : ''} />
              </div>
              <button
                type="button"
                className={`output ${(rule >> idx) & 1 ? 'on' : ''}`}
                aria-label={`toggle output for pattern ${idx.toString(2).padStart(3, '0')}`}
                onClick={() => toggleBit(idx)}
              />
            </div>
          ))}
        </div>
      </div>

      <style>{`
        .cellular-automaton {
          border: 1px solid #2a2d31;
          background: #0e1113;
        }
        .ca-canvas {
          aspect-ratio: 2 / 1;
          border-bottom: 1px solid #2a2d31;
        }
        .ca-canvas canvas {
          display: block;
          width: 100%;
          height: 100%;
          cursor: crosshair;
          touch-action: none;
        }
        .cellular-automaton .controls {
          display: flex;
          flex-wrap: wrap;
          gap: 1.25rem;
          padding: 0.75rem 1rem;
        }
        .cellular-automaton .group {
          display: flex;
          align-items: center;
          gap: 0.4rem;
          flex-wrap: wrap;
        }
        .cellular-automaton .group-label {
          color: var(--muted);
          font-size: 0.75rem;
          text-transform: uppercase;
          letter-spacing: 0.04em;
          margin-right: 0.15rem;
        }
        .cellular-automaton .controls button {
          font-family: inherit;
          font-size: 0.75rem;
          color: #8a8f98;
          background: rgba(0, 0, 0, 0.4);
          border: 1px solid #2a2d31;
          padding: 0.25rem 0.6rem;
          cursor: pointer;
        }
        .cellular-automaton .controls button:hover {
          color: #e6e6e6;
        }
        .cellular-automaton .controls button.active {
          color: #0b0d0f;
          background: var(--accent);
          border-color: var(--accent);
        }
        .cellular-automaton .rule-caption {
          color: var(--muted);
          font-size: 0.8rem;
          margin: 0;
          padding: 0 1rem 0.75rem;
        }
        .cellular-automaton .rule-table {
          border-top: 1px solid #2a2d31;
          padding: 0.75rem 1rem 1rem;
        }
        .cellular-automaton .hint {
          color: var(--muted);
          font-size: 0.75rem;
          margin: 0 0 0.6rem;
        }
        .cellular-automaton .tiles {
          display: grid;
          grid-template-columns: repeat(4, minmax(0, 1fr));
          gap: 0.5rem 0.25rem;
        }
        @media (min-width: 480px) {
          .cellular-automaton .tiles {
            grid-template-columns: repeat(8, minmax(0, 1fr));
          }
        }
        .cellular-automaton .tile {
          display: flex;
          flex-direction: column;
          align-items: center;
          gap: 0.3rem;
        }
        .cellular-automaton .pattern {
          display: flex;
          gap: 2px;
        }
        .cellular-automaton .pattern span {
          width: 12px;
          height: 12px;
          border: 1px solid #2a2d31;
        }
        .cellular-automaton .pattern span.on {
          background: #e6e6e6;
          border-color: #e6e6e6;
        }
        .cellular-automaton .output {
          width: 26px;
          height: 26px;
          padding: 0;
          border: 1px solid #2a2d31;
          background: transparent;
          cursor: pointer;
        }
        .cellular-automaton .output:hover {
          border-color: #4a4f56;
        }
        .cellular-automaton .output.on {
          background: var(--accent);
          border-color: var(--accent);
        }
      `}</style>
    </div>
  );
}