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 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.