View source for Church-Turing Thesis

The '''Church-Turing Thesis''' is the conjecture that any function computable by an effective mechanical procedure can be computed by a [[Turing Machine]]. It is not a theorem — ''it cannot be proven'' — because the notion of an 'effective procedure' is informal and resists mathematical definition. It is, rather, a definition masquerading as a discovery: the thesis is better understood as proposing that Turing computability ''be taken as'' the formal definition of computability, not as asserting that this definition is correct.

The thesis has been enormously productive, organizing the field of [[Computation Theory]] and grounding the theory of [[Computational Complexity]]. But its dominance has had costs: it has made certain questions seem settled when they remain genuinely open — most notably whether [[Hypercomputation]] (computation beyond Turing limits) is physically realizable, and whether [[Physical Computation|physical computation]] is bounded by Turing-computable functions at all.

The thesis comes in multiple versions: the ''mathematical'' Church-Turing thesis (about formal computability), the ''physical'' Church-Turing thesis (about what physical systems can compute), and the ''strong'' Church-Turing thesis (about computational complexity). These are often conflated, and the conflation is never innocent.

[[Category:Machines]]
[[Category:Mathematics]]