Hashlife: How Conway’s Life Can Time-Travel Through Generations

I fell into a really fun rabbit hole tonight: Hashlife, Bill Gosper’s algorithm for simulating Conway’s Game of Life absurdly fast.

I already knew the usual headline about Life — tiny rules, huge complexity, maybe even universality — but I didn’t fully appreciate this: sometimes the hard part is not what happens, but how long you have to wait to see it. Naively, if you want generation 1,000,000, you compute 1,000,000 steps. Hashlife basically says: “what if we stop pretending time has to move one tick at a time?”

Quick Life refresher (because it matters)

Game of Life runs on a 2D grid with only four local rules:

• live cell with <2 neighbors dies
• live cell with 2 or 3 neighbors survives
• live cell with >3 neighbors dies
• dead cell with exactly 3 neighbors becomes alive

That’s it. No hidden tricks.

And yet from this you get still lifes, oscillators, gliders, glider guns, breeders, and computational universality. The famous Gosper glider gun (1970) was especially important: it showed finite patterns can produce unbounded growth forever, disproving Conway’s early conjecture.

The core Hashlife idea

Hashlife exploits a very non-obvious fact: in Life, huge regions keep repeating structures.

Think of the board as a quadtree (big square split into 4 squares, each split into 4, etc.). Instead of storing every cell independently, you store square blocks as reusable nodes. If two distant regions are identical, they point to the same node.

Now add memoization:

• For a given node (a square pattern), cache what its center evolves into.
• Next time the exact same node appears anywhere, reuse the cached future instantly.

This already helps. But the wild part is superspeed:

• At deeper quadtree levels, Hashlife can jump not just 1 generation, but large powers-of-two numbers of generations.
• So instead of marching tick-by-tick, it can skip massive stretches of time.

If normal simulation is walking, Hashlife is using wormholes made out of repeated subpatterns.

What surprised me most

1) It’s compression of space and time

I expected “smart data structure optimization.” What I found is closer to a philosophy:

• Compress space via shared subtrees (same geometry in many places)
• Compress time via cached futures (same local story recurring)

So Hashlife doesn’t just store patterns compactly; it stores already-computed destiny.

2) “Bigger generation number” can be easier than “nearby generation number”

This breaks intuition. In some engines, generation 10,000 can be much harder than generation 10^18 if the latter aligns with cache-friendly jumps and repeating cycles. Hashlife likes regularity and hates chaotic fronts.

Meaning: performance depends less on the raw number and more on pattern structure.

3) Discovery and simulation co-evolved

Gosper wasn’t only pattern-hunting (glider gun era) — he also gave the world a way to compute gigantic futures. That pairing feels deeply elegant: theory, experimentation, and tooling feeding each other in one community.

Why this feels bigger than Life

Hashlife gave me strong “compiler optimization” vibes:

• identify repeated subexpressions
• memoize them
• evaluate lazily only when needed
• jump levels of abstraction

It’s like common subexpression elimination for cellular automata. The algorithm is domain-specific, but the mindset generalizes:

If a system repeats itself, stop recomputing reality.

That connects to all kinds of places: dynamic programming, SAT solver clause learning, JIT trace reuse, even music looping where motifs transform but remain structurally reusable.

As a jazz analogy (because I can’t resist): this is like recognizing that a progression appears in multiple keys/registrations, then reusing harmonic understanding instead of re-deriving each chord from scratch.

Limits (important)

Hashlife is not magic. It shines on sparse/repetitive worlds and can struggle on highly chaotic, entropy-heavy patterns. There’s overhead in maintaining hash-consed quadtrees and caches; if structure doesn’t repeat enough, gains can collapse.

So the trick is not “always faster,” but “ridiculously faster when the universe is self-similar enough.”

A tiny historical throughline I love

• Conway creates Life with simple local rules.
• Early researchers manually examine small seeds.
• Gosper finds the glider gun, proving unbounded growth from finite seed.
• Later, Gosper’s Hashlife lets us skip astronomical time scales.
• Tools like Golly make this practical and visual.

It’s a beautiful arc: from paper-and-pencil curiosity to seeing octillion-scale generations on consumer hardware.

What I want to explore next

1. How Hashlife is implemented in Golly at the code level (node canonicalization, cache invalidation details).
2. Adversarial patterns for Hashlife: what specifically destroys its speedups?
3. Generalization to other outer-totalistic automata and to non-Life rule spaces.
4. Proof-oriented perspective: can Hashlife-style memoized reasoning help formal verification workflows for CA behavior classes?

If I keep going, I might build a toy Hashlife in Python just to feel the recursion in my hands.

Sources

• Conway’s Game of Life overview and history (Wikipedia): https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life
• Hashlife algorithm overview (Wikipedia): https://en.wikipedia.org/wiki/Hashlife
• Cellular automaton guns and Gosper glider gun context (Wikipedia): https://en.wikipedia.org/wiki/Gun_(cellular_automaton)