The statement
The Church-Turing thesis says, roughly, that anything that can be computed by an effective, step-by-step mechanical procedure can be computed by a Turing machine. Put the other way around, the Turing machine captures everything we mean when we say a function is “computable.”
The name combines two people. Alonzo Church proposed that his lambda calculus captured effective calculability, and Alan Turing, working independently in the 1930s, proposed that his machine model did. Soon afterward, it was shown that the two formalisms compute exactly the same functions, which gave the idea a lot of credibility.
Why it is a thesis and not a theorem
A theorem is a statement that can be proved from definitions and axioms. The Church-Turing thesis connects two different kinds of thing:
- A precise, mathematical object: the class of functions a Turing machine can compute.
- An informal, intuitive notion: what a human with pencil and paper could compute by following rules, or what “an algorithm” means in everyday language.
You cannot prove that an informal notion equals a formal one, because the informal side has no formal definition to reason about. If someone proposed a new way of computing and it turned out to do more than Turing machines, the thesis would be refuted, but no proof could ever show that no such thing exists. The status is closer to a well-tested scientific hypothesis, except that it is about definitions as much as about the world.
That is why careful writers say “thesis” and avoid saying it has been “proved.” It is also why the claim does not extend to anything that is not a well-defined mechanical procedure.
The evidence for it
The thesis is widely accepted for several reasons.
- Many independent models agree. Turing machines, the lambda calculus, general recursive functions, Post’s production systems and register or counter machines were all defined by different people with different motivations, and they all compute the same set of functions. Later models, including every mainstream programming language in an idealized form, also land on the same set.
- No counterexample has appeared. Despite decades of effort, nobody has produced a procedure that everyone agrees is mechanical and yet falls outside the class.
- The informal notion seems to have been captured well. When people examined what a human computer does, writing symbols and changing the next action based on what is seen, Turing’s argument was that a machine with a finite set of states and a tape can mimic each of those actions.
Notice that these are reasons for confidence, not proofs. The agreement among models is itself a theorem (each pair can simulate the other), but the claim that these models match the intuitive idea is the part that stays a thesis.
How it gets used
In practice the thesis is often used as a shortcut in proofs. Instead of writing out a full Turing machine, an author describes an algorithm in informal terms and says “by the Church-Turing thesis, a Turing machine exists that does this.” That is acceptable when the algorithm is clearly mechanical, but it is a convenience, not a loophole.
It also underlies completeness arguments for odd languages. When someone claims that a language is Turing complete, the thesis explains why that is a meaningful milestone: it says the language is as powerful as any algorithmic system can be. A proof that a language is universal usually works by building a translation from one language into another, which relies on the standard recipe for showing completeness.
The thesis also frames undecidability. If you accept it, then proving that no Turing machine can solve the halting problem is the same as saying no algorithm of any kind can, which is the strong reading people usually have in mind.
What it does not say
Some common misunderstandings are worth clearing up.
- It says nothing about speed or memory. Two systems can compute the same functions while one is vastly faster than the other. A stronger statement about efficiency is a separate matter, sometimes called the extended thesis, and it is much more debated.
- It does not say computers can do everything. The halting problem shows there are well-defined questions no algorithm can answer.
- It is not contradicted by quantum computers. They are generally understood to compute the same set of functions as ordinary machines, though possibly with a different cost for certain problems. That is a statement about efficiency, not about what is computable.
- It does not claim to describe the physical universe. Whether nature contains processes that can compute beyond Turing machines is a separate question, sometimes discussed under the name “physical” Church-Turing thesis, and it is open and speculative.
Why it matters for esoteric languages
The thesis explains why a tiny language can be taken seriously as a computing system. If a system can imitate a Turing machine, then by the thesis it can do anything any algorithmic system can do. That gives meaning to the claim of Turing completeness, and it is the reason a strange language with a handful of symbols, such as one of the tape languages, can be given the same theoretical standing as a large industrial one.