Universality of Computation

One idea ties together Ada Lovelace's notes, Turing's abstract tape, Deutsch's quantum computer, and the possibility of virtual reality.

There is an idea so strange that it took a century to stumble into, and so deep that once you see it you cannot unsee it: a single machine, built once, can compute anything that can be computed at all. It can be a calculator, a word processor, a chess engine, a weather model, a brain simulator — all without changing a wire. This is the universality of computation, and it is arguably the most consequential idea of the last two hundred years.

Its story runs through three people.

Ada Lovelace — the first glimpse

In 1843, Ada Lovelace was translating an Italian paper about Charles Babbage's unbuilt Analytical Engine. She appended her own notes. They ended up being more than twice as long as the original paper.

Hidden in Note G is an algorithm for computing the Bernoulli numbers — widely considered the first computer program. But the more radical move is elsewhere. Babbage saw his machine as a fast calculator. Lovelace saw further:

“The Analytical Engine... might act upon other things besides number. Supposing, for instance, that the fundamental relations of pitched sounds in the science of harmony... were susceptible of such expression, the engine might compose elaborate and scientific pieces of music of any degree of complexity or extent.”

She understood that a machine shuffling symbols isn't really about numbers at all. If you can encode something — music, logic, language — as symbols, a machine that manipulates symbols can manipulate it. This is the seed of universality, a century before the word.

Alan Turing — the proof

In 1936, Alan Turing wrote a paper called “On Computable Numbers.” He was 24. He was trying to answer a question in logic — is there a mechanical procedure that can decide whether any given mathematical statement is true? — and to answer it, he had to first define what “mechanical procedure” even meant.

So he invented a machine. Not a real one. An idealized abstraction: an infinite tape divided into cells, a head that could read and write symbols, and a little rulebook of states. Primitive. Utterly simple. And yet:

Turing proved something astonishing. There exists a specific Turing machine — a universal one — that, if you write the description of any other Turing machine on its tape, will perfectly simulate that machine. One fixed machine, simulating all possible machines. This is universality.

Together with Alonzo Church, he went further. The Church–Turing thesis claims that anything that can be computed by any effective procedure whatsoever — by a person with pencil and paper, by an abacus, by a factory of clerks, by any conceivable mechanism — can be computed by a Turing machine. The laptop you're reading this on is a physical approximation of one. So is your phone. So, in principle, is a system of water pipes, or a swarm of ants passing chemical signals. The substrate doesn't matter. The computation does.

David Deutsch — the physics

For decades, computer scientists treated Church–Turing as a statement about mathematics. In 1985, the physicist David Deutsch pointed out that this was a category error. Computation is not abstract. Every computation happens somewhere, using something, obeying the laws of physics. A claim about what can be computed is, whether you like it or not, a claim about physics.

Deutsch proposed a stronger principle — the physical Church–Turing thesis:

Every finitely realizable physical system can be perfectly simulated by a universal computing device operating by finite means.

Turing's machine, Deutsch showed, doesn't quite qualify. It's classical. Our universe isn't. When he worked out the implications, he had to invent a new kind of machine — the universal quantum computer — to patch the gap. A classical Turing machine cannot efficiently simulate an electron; a quantum computer can. The laws of physics, it turns out, dictate what universality really looks like.

Why this matters: virtual reality

Here is the punchline that Deutsch drew out in The Fabric of Reality. If a universal quantum computer can simulate any physical system, then in principle it can simulate the experience of being anywhere, in any environment, under any physics — real or imagined. A universal simulator of environments. That is what virtual reality is, taken to its logical conclusion. Not a toy. A consequence of the laws of physics.

This flips something in how you think about the world. The reason a program can be a chess engine on Tuesday and a weather model on Wednesday is the same reason physics permits rendering any world inside a machine: the universe is the kind of place where universality is possible. That is a highly non-trivial fact about physics. A different universe — with different laws — might not have allowed it. Ours does.

And so a thread runs from Lovelace's note about music in 1843, to Turing's tape in 1936, to Deutsch's quantum gates in 1985, to the headset on your desk. The same thread. One idea. A single machine — provided the universe is a computable sort of place — that can be anything.