The robustness we have been collecting
The two guides before this one quietly built a case. 'Many Tapes, Many Models, Same Power' showed that handing a Turing machine extra tapes does not let it compute anything new: a multitape machine can always be simulated on one tape, paying only a polynomial price in time. 'Nondeterministic Turing Machines' showed the same for guessing: a nondeterministic machine recognises no new languages — a deterministic one can simulate it, at worst with an exponential slowdown. Different tape counts, deterministic or guessing — same class of computable functions every time. The machine is shockingly hard to change in any way that matters.
A natural worry remains, though. Maybe all of that is just inbreeding: every variant we tried was still a Turing machine wearing a costume — still a head shuffling along a tape. Perhaps the tape itself is a prison, and a model built on a totally different idea — no tape, no head, no states — could break out and compute more. This guide confronts that worry head-on by leaving the tape behind entirely. We will meet rivals designed from completely different first principles, by different people, often before or alongside Turing, and ask the only question that matters: do they compute MORE than a Turing machine, less, or exactly the same?
Lambda calculus: computing with nothing but functions
Alonzo Church's lambda calculus arrived in the 1930s, a touch before Turing's machine, and it could hardly look more different. There is no tape, no clock, no state — there are only functions, and a single rule for applying them. You build expressions out of three things: a variable like x; a function, written 'lambda x. body', meaning 'take an input named x and return body'; and an application '(f a)', meaning 'feed a into f'. That is the whole language. No numbers, no booleans, no loops are built in. It is the bare idea of 'a rule that takes an input and produces an output', and nothing else.
Computation is one move repeated: beta reduction, which is just substitution. When a function meets an argument, you copy the body and replace every occurrence of the parameter with the argument — '(lambda x. x x) a' becomes 'a a'. Run that move over and over until no application is left to reduce, and the expression you are stuck with is your answer. The miracle is that this single substitute-and-repeat is enough to encode everything. Numbers become functions (the number 3 is encoded as 'apply a function three times'); true and false become functions that pick one of two inputs; even recursion is bottled up in a self-applying expression. With no loop construct at all, lambda calculus computes every function a Turing machine can — Church and Turing proved their two models pick out the very same class.
Recursive functions and register machines
A third rival is even more austere: the recursive functions, built by Gödel, Kleene and others as pure mathematics over the natural numbers, with no machine of any kind in sight. You start from three trivially-simple seed functions — the constant zero, the 'add one' successor, and projections that just pick one argument out of a list — and you are allowed exactly two ways to glue functions together: composition (feed the output of some functions into another) and primitive recursion (define f at n+1 in terms of f at n, the schoolbook way you define factorial or addition). These rules alone capture an enormous swathe of functions, but provably not all of them.
The piece that completes the set is one more operator: minimisation, the 'search for the smallest n that works' move — keep trying n = 0, 1, 2, ... until some condition first comes true. That single search is what introduces the possibility of running forever (the search might never find its target), and it is exactly the ingredient that lifts the merely-primitive-recursive functions up to the full partial recursive functions. And that full class, Kleene proved, is identical to the Turing-computable functions. Notice the pattern: the dangerous, possibly-non-halting operator is the price of full power — just as a Turing machine's ability to loop forever is the price of its full power.
If functions feel too abstract, here is a model that looks like a baby computer: the register machine (also called a counter machine). It has a handful of registers, each holding one natural number, and a tiny program of numbered instructions — essentially just 'add one to register r', 'subtract one from register r', and 'if register r is zero, jump to line k, otherwise go to the next line'. That is the entire instruction set. It feels like assembly language stripped to the bone, with no tape anywhere, yet a counter machine with as few as two registers is already Turing-complete. Same destination, a road that looks nothing like a tape.
Cellular automata and real languages
Let us push the diversity to its limit. A cellular automaton has no central control at all — just a long row of cells, each holding one of a few colours, all updating at once on every tick according to a fixed local rule like 'my next colour depends only on me and my two neighbours'. It is a self-organising grid, the universe of Conway's Game of Life and of Stephen Wolfram's elementary rules. Surely THIS, with no program counter and no head, computes less? No: certain cellular automata (the famous Rule 110 among them) are Turing-complete. You can lay out an input as a starting pattern of colours and read a computation off the rippling stripes that evolve.
And the rival you already know best: a real programming language. Python, C, Java, Haskell, even a spreadsheet's formula engine — each, given unbounded memory, computes exactly the Turing-computable functions, no more and no less. This is the everyday face of the deep result. When someone says a language is Turing-complete, they mean precisely this: it can simulate a Turing machine, and therefore it can express any computation any other reasonable model can. It is also why surprising systems — the type checker of C++ templates, the SQL with recursion, even some configuration formats and a few games — turn out, to their designers' alarm, to be Turing-complete by accident.
Wildly different models -- one shared class of computable functions:
MODEL its primitive move built around
--------------------- ---------------------------------- -----------------
Turing machine write a cell, step L/R a tape + head
Lambda calculus beta reduction (substitute) functions only
Recursive functions compose / recurse / minimise numbers only
Register / counter m. inc, dec, jump-if-zero registers + lines
Cellular automaton update every cell by a local rule a grid of cells
Real prog. language run one statement whatever it has
Each pair has been PROVEN able to simulate the other:
TM <--> lambda <--> recursive fns <--> register m. <--> ...
so all of them recognise/compute the SAME set. Equivalence, not coincidence.What the convergence means — and what it does not prove
Step back and feel the force of it. People with different goals — a logician studying functions, a mathematician formalising arithmetic, an engineer imagining a machine, a scientist watching grids self-organise — set out from totally unrelated starting points, and every single road arrived at the exact same destination. These are not loose family resemblances; each equivalence is a hard theorem, a concrete recipe for simulating one model inside another. This web of proofs is what we mean by equivalent models of computation, and it is the strongest evidence we have for one big idea.
- Pick any two models from the list — say lambda calculus and Turing machines.
- Show how to encode every Turing machine as a lambda expression that mimics it step for step, so anything a TM computes, lambda calculus computes too.
- Show the reverse: write a Turing machine that performs beta reduction on an encoded lambda expression, so anything lambda calculus computes, a TM computes too.
- Two simulations, one in each direction, force the two computable-function classes to be IDENTICAL — and chaining such pairs links all the models into a single class.
That big idea is the Church–Turing thesis: anything that can be computed by ANY mechanical, effective procedure at all can be computed by a Turing machine. The convergence of every formal model we can dream up is its supporting evidence. But here is the crucial honesty, and the whole subject of the next guide: the thesis is NOT a theorem. The equivalences above are theorems — they connect formal models to formal models. The thesis instead connects the formal idea 'Turing-computable' to the fuzzy, intuitive, pre-mathematical idea 'computable by any effective method whatsoever'. You cannot prove a precise thing equals an imprecise thing; you can only gather overwhelming evidence and decline to bet against it. So far, in ninety years, nobody has built a remotely plausible physical or formal procedure that computes something a Turing machine cannot.