A pile of coincidences that demands an explanation
Walk back through the last three guides and notice the pattern. A Turing machine with one tape and a Turing machine with fifty tapes compute the same languages (the many tapes only buy at most a polynomial speedup, never new power). A nondeterministic Turing machine computes nothing a deterministic one cannot — the deterministic machine just pays an exponential slowdown to search the tree of guesses. And then lambda calculus, recursive functions, register or counter machines, even cellular automata and your favourite programming language all turned out to define exactly the same class of computable functions. None of these models was designed to match the others. They were invented in different decades, by different people, with totally different intuitions.
When wildly different attempts to formalize the same vague idea keep landing on the identical answer, that is not luck — it is evidence that the vague idea was real and that we have caught it. The vague idea here is the oldest one in this whole subject: what does it mean to compute something by a mechanical procedure? Before the 1930s 'algorithm' was an informal notion — a recipe a clerk could follow with paper, pencil, and no creativity. The models above are attempts to make that notion exact. The fact that they all coincide is the central empirical observation of the theory of computation, and it cries out for a name.
What the thesis actually claims
The Church–Turing thesis is the claim that these formal models capture the informal notion completely: anything that can be computed by ANY mechanical, finite, step-by-step procedure at all — by a clerk with unlimited paper and time, by any conceivable machine, by any algorithm in any language — can be computed by a Turing machine. In one line: the intuitively computable functions are exactly the Turing-computable functions. This is what lets us stop writing 'computable by a Turing machine, or a register machine, or…' and simply write decidable or 'computable', confident the word means the same thing under every reasonable model.
Note carefully the two sides of the equation. One side, 'Turing-computable', is a precise mathematical object — we have a definition, we can prove things about it. The other side, 'intuitively computable by a mechanical procedure', is deliberately informal — it is a claim about the real world and about what the word 'effective procedure' has always meant to mathematicians. The thesis is a bridge between a formal concept and an informal one. That structure is exactly why it occupies a strange status, which the next section is about.
Why it is a thesis, not a theorem
Here is the subtle part that trips up almost everyone the first time. We have PROVEN, with full mathematical rigour, that lambda calculus and Turing machines and register machines define the same functions — those are honest theorems, because all three are precise definitions you can compare. But the Church–Turing thesis is not one of those. It cannot be proven, because one side of it — 'every possible mechanical procedure' — is not a mathematical object. You cannot quantify over a fuzzy intuitive notion and prove a theorem about it. To prove it you would first have to formalize 'mechanical procedure', and then your formalization would just be one more model whose equivalence you would have to argue informally all over again. The informality never fully goes away.
So what kind of statement is it? It is closer to a law of nature than to a theorem — a claim about reality that we believe overwhelmingly because of accumulated evidence, but that is in principle falsifiable. The evidence is enormous: every single model anyone has ever proposed for 'effective computation', across ninety years of trying hard to break the pattern, has turned out to be either equivalent to the Turing machine or strictly weaker. To refute the thesis, someone would only need to exhibit a genuinely mechanical procedure — something a clerk with paper could carry out, by clear finite rules — that computes a function no Turing machine can. Nobody ever has. That is why we accept it. But 'accept on overwhelming evidence' is not the same as 'prove', and an honest course never blurs the two.
Turing-complete: borrowing the power
Once you accept that the Turing machine marks the ceiling of mechanical computation, a wonderfully practical word falls out. A model of computation is Turing-complete if it can simulate any Turing machine — equivalently, if it can compute every Turing-computable function. By the thesis, Turing-complete is the strongest a model can ever be: it can compute everything that is computable at all. This is why we can say, casually but accurately, that Python, C, Java, lambda calculus, and even some toys nobody would program in are 'all equally powerful'. They differ enormously in convenience and speed, not one bit in what is ultimately computable.
Proving something is Turing-complete is usually a simulation argument, and the recipe is the one running through this whole rung. To show a model M is Turing-complete, show M can imitate a Turing machine: represent the tape (often as two stacks, or a list, or a big number), represent the head's position and the current state, and show that for each Turing transition delta(q, a) = (p, b, direction) there is a corresponding step in M that updates the represented configuration the same way. If M can faithfully step a represented Turing machine forever, M can compute whatever that Turing machine computes. The same trick, run the other way, is how we proved the rival models EQUAL the Turing machine rather than merely matching it on examples.
Turing machine M simulated inside model X
------------------ --------------------------
tape ... a b | c d ... -> leftpart = [b, a, ...] (a stack)
head over c current = c
rightpart = [d, ...] (a stack)
state q -> state = q
one TM step delta(q,c) = (p, x, RIGHT):
write x at head, go right, enter p
becomes in X:
current := x ; push current onto leftpart
current := pop(rightpart) ; state := p
X is Turing-complete <=> it can keep doing this forever, faithfully.Two theses, and the bridge to the universal machine
It pays to separate two claims that sound similar but are not. The Church–Turing thesis is about what is computable AT ALL, ignoring efficiency. There is a stronger, separate conjecture — the extended (or strong) Church–Turing thesis — which adds a claim about cost: that any reasonable model can be simulated by a Turing machine with only a polynomial-time slowdown, so 'efficiently computable' is also model-independent. The plain thesis is on extremely firm ground; the extended one is genuinely contested. Quantum computers are the famous pressure point: they appear to solve some problems (like factoring) faster than any known classical algorithm, which would dent the EXTENDED thesis — but, importantly, a quantum computer is NOT known to compute anything a Turing machine cannot, so the plain thesis stands untouched, and a quantum computer is not believed to crack NP-complete problems efficiently either.
- See a pile of equivalent models (tapes, nondeterminism, lambda calculus, register machines, real languages) all computing the same functions — established by proofs in the earlier guides.
- Promote that observation to a claim about ALL effective procedures: the Church–Turing thesis. Accept it on overwhelming evidence, not proof, because one side is informal.
- Cash it out as a usable word: a model is Turing-complete if it can simulate a Turing machine, and that is the most powerful any model can be.
- Keep efficiency separate: the EXTENDED thesis (polynomial-time simulation) is a different, contested claim that quantum computing puts under real pressure.
There is one more consequence so important it gets its own guide next. If every reasonable model can be simulated, then in particular a Turing machine can simulate a Turing machine. That is not a triviality — it means we can build ONE fixed machine that takes a description of any other machine, plus that machine's input, and faithfully runs it. To do that we first need to write a Turing machine down as a string the way we write data, which is exactly the idea of encoding a machine. The result is the universal Turing machine — the theoretical ancestor of every stored-program computer, the thing that turns 'a machine per task' into 'one machine, programmed per task'. The Church–Turing thesis tells you such universality is possible at all; guide 5 builds the machine.