Introduction

In 1970, mathematician John Horton Conway published a set of rules so simple they fit on a napkin, yet so powerful they can simulate any computer ever built. He called it the Game of Life — though it is not a game you play in the usual sense, and whether it counts as life is a philosophical question.

The world is an infinite grid of cells, each either alive (on) or dead (off). Every tick of the clock, three rules decide the next generation:

  1. Birth: a dead cell with exactly 3 live neighbors comes alive.
  2. Survival: a live cell with 2 or 3 live neighbors stays alive.
  3. Death: every other live cell dies (underpopulation or overcrowding).

That is all. From those three sentences emerge gliders that slide across the grid, oscillators that pulse forever, spaceships, guns that shoot gliders, and eventually — proven rigorously in 1982 — a complete Turing machine built of nothing but on/off cells. Whatever a computer can compute, the Game of Life can compute too.

The catch? Turing completeness comes with Turing's own curse. Predicting whether a pattern will ever vanish, grow forever, or stabilize is undecidable — provably impossible in general, by a direct reduction from the halting problem.

Try It

Click cells to toggle them alive or dead, then press Play to watch the rules run. Use the preset buttons to place classic patterns — a glider that moves diagonally across the grid, or a Blinker that oscillates between two shapes forever.

<p class="hint">Click cells to toggle alive/dead. Press <b>Play</b> to run the rules, or step one generation at a time. Use presets to place classic patterns and watch three rules compute.</p>
<div class="toolbar">
  <button id="play" type="button">Play</button>
  <button id="step" type="button">Step</button>
  <button id="clear" type="button" class="ghost">Clear</button>
  <span class="sep"></span>
  <button id="glider" type="button" class="preset">Glider</button>
  <button id="blinker" type="button" class="preset">Blinker</button>
  <button id="gun" type="button" class="preset">Pulsar</button>
</div>
<canvas id="life" width="400" height="360"></canvas>
<div class="info" id="info">Generation: 0 &nbsp;|&nbsp; Population: 0</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.toolbar { display: flex; gap: .4rem; flex-wrap: wrap; margin-bottom: .5rem; align-items: center; }
.sep { flex: 1; }
button { font: 600 13px system-ui; padding: .38rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button.preset { background: #457b9d; border-color: #457b9d; }
canvas { display: block; border: 1.5px solid #cdd9e3; border-radius: 6px; cursor: crosshair;
         max-width: 100%; touch-action: none; }
.info { font-size: .85rem; color: #555; margin-top: .4rem; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Conway's Game of Life — three rules:
//   Birth:    dead cell with exactly 3 live neighbors → alive
//   Survival: live cell with 2 or 3 live neighbors   → stays alive
//   Death:    all other live cells                    → dead
// The system is Turing-complete; predicting the long-run fate is undecidable.

const COLS = 40, ROWS = 36, CELL = 10;
const canvas = document.getElementById('life');
const ctx = canvas.getContext('2d');
let grid = Array.from({length: ROWS}, () => new Uint8Array(COLS));
let gen = 0, pop = 0, rafId = null, running = false;

function idx(r, c) { return (r + ROWS) % ROWS * COLS + ((c + COLS) % COLS); }
function get(g, r, c) { return g[(r + ROWS) % ROWS][(c + COLS) % COLS]; }

function step() {
  const next = Array.from({length: ROWS}, () => new Uint8Array(COLS));
  pop = 0;
  for (let r = 0; r < ROWS; r++) {
    for (let c = 0; c < COLS; c++) {
      let n = 0;
      for (let dr = -1; dr <= 1; dr++)
        for (let dc = -1; dc <= 1; dc++)
          if (dr || dc) n += get(grid, r + dr, c + dc);
      const alive = grid[r][c];
      // Birth: dead + 3 neighbors; Survival: alive + 2 or 3
      next[r][c] = (!alive && n === 3) || (alive && (n === 2 || n === 3)) ? 1 : 0;
      if (next[r][c]) pop++;
    }
  }
  grid = next;
  gen++;
}

function draw() {
  ctx.clearRect(0, 0, canvas.width, canvas.height);
  ctx.fillStyle = '#e8f0f7';
  ctx.fillRect(0, 0, canvas.width, canvas.height);
  ctx.fillStyle = '#1d3557';
  for (let r = 0; r < ROWS; r++)
    for (let c = 0; c < COLS; c++)
      if (grid[r][c]) ctx.fillRect(c * CELL + 1, r * CELL + 1, CELL - 1, CELL - 1);
  // light grid lines
  ctx.strokeStyle = '#cdd9e3';
  ctx.lineWidth = 0.4;
  for (let r = 0; r <= ROWS; r++) { ctx.beginPath(); ctx.moveTo(0, r*CELL); ctx.lineTo(canvas.width, r*CELL); ctx.stroke(); }
  for (let c = 0; c <= COLS; c++) { ctx.beginPath(); ctx.moveTo(c*CELL, 0); ctx.lineTo(c*CELL, canvas.height); ctx.stroke(); }
}

function updateInfo() {
  pop = 0;
  for (let r = 0; r < ROWS; r++) for (let c = 0; c < COLS; c++) pop += grid[r][c];
  document.getElementById('info').innerHTML =
    fmt('Generation: %gen% &nbsp;|&nbsp; Population: %pop%', { gen: gen, pop: pop });
}

function loop() { step(); draw(); updateInfo(); if (running) rafId = requestAnimationFrame(loop); }

canvas.addEventListener('pointerdown', e => {
  const rect = canvas.getBoundingClientRect();
  const scaleX = canvas.width / rect.width;
  const scaleY = canvas.height / rect.height;
  const c = Math.floor((e.clientX - rect.left) * scaleX / CELL);
  const r = Math.floor((e.clientY - rect.top) * scaleY / CELL);
  if (r >= 0 && r < ROWS && c >= 0 && c < COLS) {
    grid[r][c] = grid[r][c] ? 0 : 1;
    draw(); updateInfo();
  }
});

document.getElementById('play').addEventListener('click', () => {
  running = !running;
  document.getElementById('play').textContent = running ? 'Pause' : 'Play';
  if (running) loop();
  else cancelAnimationFrame(rafId);
});
document.getElementById('step').addEventListener('click', () => {
  if (running) return;
  step(); draw(); updateInfo();
});
document.getElementById('clear').addEventListener('click', () => {
  running = false; cancelAnimationFrame(rafId);
  document.getElementById('play').textContent = 'Play';
  grid = Array.from({length: ROWS}, () => new Uint8Array(COLS));
  gen = 0; draw(); updateInfo();
});

// Glider: classic 5-cell shape that moves diagonally
// Pattern (top-left at r,c):  .X.  /  ..X  /  XXX
function placeGlider(r, c) {
  [[0,1],[1,2],[2,0],[2,1],[2,2]].forEach(([dr,dc]) => { grid[r+dr][c+dc] = 1; });
}
// Blinker: 3 cells in a row that oscillate between horizontal and vertical
function placeBlinker(r, c) {
  [[0,0],[0,1],[0,2]].forEach(([dr,dc]) => { grid[r+dr][c+dc] = 1; });
}
// Pulsar: period-3 oscillator, one of Life's most beautiful patterns
// Encoded as relative coords from top-left bounding box
function placePulsar(r, c) {
  const coords = [
    [0,2],[0,3],[0,4],[0,8],[0,9],[0,10],
    [2,0],[2,5],[2,7],[2,12],
    [3,0],[3,5],[3,7],[3,12],
    [4,0],[4,5],[4,7],[4,12],
    [5,2],[5,3],[5,4],[5,8],[5,9],[5,10],
    [7,2],[7,3],[7,4],[7,8],[7,9],[7,10],
    [8,0],[8,5],[8,7],[8,12],
    [9,0],[9,5],[9,7],[9,12],
    [10,0],[10,5],[10,7],[10,12],
    [12,2],[12,3],[12,4],[12,8],[12,9],[12,10]
  ];
  coords.forEach(([dr,dc]) => {
    if (r+dr < ROWS && c+dc < COLS) grid[r+dr][c+dc] = 1;
  });
}

document.getElementById('glider').addEventListener('click', () => {
  placeGlider(1, 1); draw(); updateInfo();
});
document.getElementById('blinker').addEventListener('click', () => {
  placeBlinker(10, 18); draw(); updateInfo();
});
document.getElementById('gun').addEventListener('click', () => {
  placePulsar(5, 12); draw(); updateInfo();
});

// Verify core rules at startup (logged to console):
(function verify() {
  // Test 1: Blinker period 2 — horizontal → vertical → horizontal
  const g0 = Array.from({length: ROWS}, () => new Uint8Array(COLS));
  g0[5][4] = g0[5][5] = g0[5][6] = 1; // horizontal blinker
  const saved = grid; grid = g0;
  step(); // gen 1: should be vertical
  const vertOk = grid[4][5] && grid[5][5] && grid[6][5] &&
                 !grid[5][4] && !grid[5][6];
  step(); // gen 2: back to horizontal
  const horzOk = grid[5][4] && grid[5][5] && grid[5][6] &&
                 !grid[4][5] && !grid[6][5];
  grid = saved; gen = 0;
  console.assert(vertOk,  'Blinker gen1 (vertical) failed');
  console.assert(horzOk,  'Blinker gen2 (horizontal) failed');

  // Test 2: Still life — 2×2 block never changes
  const g2 = Array.from({length: ROWS}, () => new Uint8Array(COLS));
  g2[10][10] = g2[10][11] = g2[11][10] = g2[11][11] = 1;
  grid = g2;
  step();
  const blockOk = grid[10][10] && grid[10][11] && grid[11][10] && grid[11][11];
  grid = saved; gen = 0;
  console.assert(blockOk, '2x2 block (still life) failed');

  // Test 3: Isolated cell dies (underpopulation)
  const g3 = Array.from({length: ROWS}, () => new Uint8Array(COLS));
  g3[15][15] = 1;
  grid = g3; step();
  const dieOk = !grid[15][15];
  grid = saved; gen = 0;
  console.assert(dieOk, 'Isolated cell should die');

  console.log('Game of Life rule verification:', vertOk && horzOk && blockOk && dieOk ? 'ALL PASSED' : 'SOME FAILED');
})();

draw(); updateInfo();
Result
Console

Notice how the same three rules produce wildly different fates: some patterns vanish in a few generations, others cycle endlessly, and the glider travels indefinitely. Deciding in advance which will happen for an arbitrary pattern is the undecidable part.

The Real Complexity

Three rules. Infinite power. Provable impossibility.

  • Turing completeness (1982): Paul Chapman and others showed that the Game of Life can simulate any Turing machine. The key pieces — logic gates (AND, OR, NOT built from glider collisions), memory (stable patterns called still lifes used as flags), and a universal signal carrier (the glider itself) — were all constructed explicitly from Life patterns.
  • The prediction problem is undecidable. Because Life can simulate any Turing machine, asking "will this pattern ever die out?" is equivalent to asking "will this program ever halt?" — and that is the halting problem, proved undecidable by Alan Turing in 1936. There is no algorithm that can answer the question for all possible starting patterns.
  • Even simple questions are hard. Is a given cell ever alive again after step k? Does the population grow without bound? Is the pattern periodic? All of these reduce to halting and are equally undecidable.
  • Turing completeness does not mean everything is hard. Running the rules forward for n steps costs O(n)O(n) time per cell. The difficulty is reasoning about the infinite future — any general predictor would have to solve the halting problem first.

The Game of Life sits in a sweet spot of mathematical interest: small enough to simulate, rich enough to represent all of computation, and wild enough in the long run that no finite shortcut can tame it. It is the P vs NP question's undecidable cousin — not just hard, but provably impossible.

Where It Matters

The Game of Life is not just a mathematical curiosity — its ideas ripple across science and engineering:

  • Complex-systems research: Life showed that global complexity can emerge from local rules. The same insight drives models of ant colonies, market dynamics, and brain activity.
  • Biology and ecology: cellular automata model crystal growth, tumor expansion, and animal coat patterns (the spots on a leopard can be reproduced by two-chemical diffusion rules that Life shares the spirit of).
  • Epidemiology: SIR and CA-based epidemic models are spiritual descendants of Life — each cell is a person, neighbors spread disease, rules determine recovery.
  • VLSI and parallel computing: Life-style local-update logic is the natural computation model for massively parallel chips, where every processor only talks to its immediate neighbors.
  • Theoretical computer science: Life is the canonical example of a universal cellular automaton — the simplest proof that enormous computational power needs no central controller, only local interactions.

Understanding why Life is undecidable teaches you why any sufficiently powerful system — a programming language, a physics simulation, a growing neural network — carries within it questions that no algorithm can answer in full generality.

Conclusion

Conway's Game of Life is a lesson in humility: three rules, a blank grid, and the entire power of computation springs into existence. Gliders carry signals, collisions compute logic, and the resulting machine is universal.

Universal means undecidable. The moment a system can simulate any Turing machine, it inherits Turing's own impossibility result — no algorithm can predict the fate of all patterns. The grid is alive with potential, but its future is beyond the reach of any finite proof.

Next time you watch a glider drift across the screen, remember: you are looking at the same computational power that runs every program ever written, wrapped in three sentences. And whether that glider's descendants will still be moving a billion generations from now is a question that mathematics says no one can ever fully answer — just like the halting problem.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/game-of-life/Content licensed under CC BY-NC 4.0.