Conway's Game of Life

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.

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">{{hint}}</p>
<div class="toolbar">
  <button id="play" type="button">{{play_btn}}</button>
  <button id="step" type="button">{{step_btn}}</button>
  <button id="clear" type="button" class="ghost">{{clear_btn}}</button>
  <span class="sep"></span>
  <button id="glider" type="button" class="preset">{{glider_btn}}</button>
  <button id="blinker" type="button" class="preset">{{blinker_btn}}</button>
  <button id="gun" type="button" class="preset">{{pulsar_btn}}</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; }

// Code not found

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.

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)$ 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.

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.

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.