Church-Turing thesis

The Church-Turing thesis is the claim that the intuitive notion of an effectively computable function — a function that can be computed by a systematic, mechanical procedure — coincides exactly with the class of functions computable by a Turing machine (equivalently, by Alonzo Church's lambda-calculus, or by any of several other equivalent formalisms proposed in 1936). The thesis is not a theorem; it cannot be proved, because 'effective computability' is an informal concept. It is a claim that the formal definition captures the informal one correctly.

The Church-Turing thesis has two importantly different readings. The weak reading is that every function a human computer could in principle compute is Turing-computable — a claim about human computational capacity. The strong reading is that every physically realizable computation is Turing-computable — a claim about physical computation that bears on questions about quantum computing, analog computation, and whether the brain performs computations not equivalent to Turing machine computations.

The thesis is foundational for mathematical logic through its connection to undecidability: Church and Turing proved, in 1936, that certain problems (including the halting problem and the decision problem for first-order logic) have no computable solution. These results depend on the thesis — they establish that no Turing machine can solve these problems, and the thesis licenses the move to 'no effective procedure can solve them.'

Whether the strong reading is true — whether physical computation is bounded by Turing computability — remains an open foundational question connected to quantum mechanics, hypercomputation, and the relationship between logic and physics.