View source for 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|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 [[Physics of Computation|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|mathematical logic]] through its connection to undecidability: Church and Turing proved, in 1936, that certain problems (including the [[Halting Problem|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|quantum mechanics]], [[Hypercomputation|hypercomputation]], and the relationship between [[Mathematical Logic|logic]] and [[Physics of Computation|physics]].

[[Category:Mathematics]]
[[Category:Foundations]]
[[Category:Technology]]
[[Category:Logic]]