Is the Universe Computable? Can Reality Be Simulated by Code?

Chapter 1 — What does computability mean?

A function is computable if some finite description (an algorithm) transforms every input into the correct output in finite steps. A simulation computes a model's state transitions: given equations or rules, it predicts the model's next state. Physical identity is a far stronger claim: that reality itself is, at bottom, such a transition system. Discrete models (grids, steps) and continuous models (real-numbered fields) differ mathematically; deterministic and stochastic systems differ in what “prediction” even promises. Keeping model, simulation and reality in separate boxes is the intellectual hygiene of this whole article.

Chapter 2 — Cellular automata

A cellular automaton is a grid of cells, each in a state (here: alive/dead), updated synchronously: every cell counts its eight neighbours and applies Conway's rules — survive on 2–3, born on exactly 3. Initial conditions and boundary conditions (this lab wraps edges into a torus) are part of the model, not afterthoughts. Local rules, global behaviour: nothing in the rule mentions gliders, yet gliders exist.

def step(grid):
    h, w = len(grid), len(grid[0])
    nxt = [[0] * w for _ in range(h)]
    for y in range(h):
        for x in range(w):
            n = sum(grid[(y+dy) % h][(x+dx) % w]
                    for dy in (-1, 0, 1) for dx in (-1, 0, 1) if (dy, dx) != (0, 0))
            nxt[y][x] = 1 if (n == 3 or (grid[y][x] == 1 and n == 2)) else 0
    return nxt
# Executed: a horizontal blinker becomes vertical, then returns (period 2).

Chapter 3 — Emergence from simple rules

ESTABLISHED: the Game of Life contains still lifes, oscillators, spaceships (gliders), glider guns, and — assembled from them — logic gates and a universal Turing machine construction. Universality means: suitably prepared Life patterns can compute anything computable. Sensitivity matters too: flip one initial cell and distant futures diverge. What universality does not do: say anything about whether physics is Life-like. It is a theorem inside a toy universe, and its honesty depends on keeping that scope visible.

Chapter 4 — Computability and the halting problem

Encode any program as data. Ask for an algorithm H that always decides “does program P halt on input I?” ESTABLISHED THEOREM (Turing, 1936): no such H exists. Proof idea (contradiction): build D that runs H on D's own code and does the opposite; D halts exactly when it doesn't. Consequence for simulation: some questions about even simple systems are undecidable — not slow, not hard-for-now, but beyond every algorithm in the classical model. Prediction of arbitrary computations is therefore limited in principle, before physics enters the room.

Chapter 5 — Numerical simulation of physical systems

Real physics arrives as differential equations; computers answer with discretization: replace smooth change with steps of size h. Smaller h usually means smaller truncation error and larger cost; floating-point rounding adds its own floor; unstable methods amplify both into fiction. A trustworthy simulation reports method, step size, precision and a refinement test (halve h — does the answer move?). The Accuracy idea is built into this article's lab philosophy: an answer without an error story is marketing.

# Euler integration of dy/dt = -y, y(0)=1. Exact answer at t=1: e^-1 = 0.367879...
import math
def euler(h):
    y, t = 1.0, 0.0
    while t < 1.0 - 1e-12:
        y += h * (-y); t += h
    return y
for h in (0.1, 0.01, 0.001):
    print(h, euler(h), 'error:', abs(euler(h) - math.exp(-1)))  # error shrinks ~10x per 10x step (executed pattern)

Chapter 6 — Physical limits of computation

Computation costs physics: ESTABLISHED (Landauer's principle) erasing one bit in an environment at temperature T dissipates at least kT·ln2 of heat — a statement about erasure thermodynamics, quoted carefully and never as “the universe is a computer.” Reversible computation dodges that specific cost in principle; finite memory, finite energy, quantum measurement limits and plain engineering bound every real simulator. Fidelity is a budget, not a vibe.

Chapter 7 — What would count as evidence?

Chapter 8 — Open research questions

OPEN: which physical observables are computable in precise formal models of physics; how quantum simulation changes the cost of chemistry; where emergent computation appears in natural systems; and the complexity of physical prediction itself. Conclusion: computation models astonishingly much, computability theory limits prediction in principle, and nothing about a successful simulation alone licenses the claim that reality is code. Run the automaton below, break a pattern, and watch a theorem-grade toy refuse to become a cosmology.