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.\n== The Physical and Strong Theses ==\n\nThe physical Church-Turing thesis asserts that any function computable by a physically realizable process is Turing-computable. This is a claim about physics, not mathematics — and it is far more vulnerable. Quantum computing initially appeared to challenge it: Richard Feynman suggested that quantum systems might require exponential classical resources to simulate, implying that nature computes something beyond Turing machines. The development of the quantum Turing machine and the circuit model of quantum computation showed that quantum computers remain within the Church-Turing framework — they do not compute non-Turing-computable functions — but they do violate the strong Church-Turing thesis, which claims that any physically realizable machine can be efficiently simulated by a probabilistic Turing machine. Shor's algorithm and Grover's search demonstrated that quantum computers offer super-polynomial and quadratic speedups, respectively, collapsing the strong thesis while preserving the physical one.\n\nThe distinction matters because the strong thesis was the implicit foundation of classical cryptography. If the strong thesis were true, then computational difficulty — the hardness of factoring, of discrete logarithms, of searching unstructured databases — would be an invariant across all physical computation substrates. Quantum computing proves that difficulty is substrate-dependent. What is hard for a classical Turing machine is not necessarily hard for a quantum circuit. This reframes the relationship between physics and computation: the limits of what can be efficiently computed are not logical limits but physical limits, contingent on which Hamiltonians nature permits us to engineer.\n\n== Computation Beyond the Thesis? ==\n\nBeyond quantum computing, several proposals claim to breach Turing computability itself. Hypercomputation schemes — involving closed timelike curves, relativistic oracles, or infinite-precision analog computation — exploit physical structures that may or may not exist. The Malament-Hogarth spacetime permits the solution of Turing-uncomputable problems by exploiting infinite proper time accumulation near black hole event horizons. Whether such spacetimes are physically realizable is an open question in general relativity, not computer science.\n\nThe more conservative challenge comes from continuous-time computation and analog neural networks. A machine with infinite-precision real numbers can in principle compute non-computable functions by encoding the answer in the nth decimal place of an initial condition. But physical systems do not have infinite precision: thermal noise, quantum uncertainty, and finite measurement resolution place finite bounds on analog computation. The physical Church-Turing thesis survives these challenges not because it has been proven, but because every proposed counterexample imports an unphysical idealization — infinite precision, infinite time, or infinite energy — that violates known physical law.\n\nThe Church-Turing thesis is not a theorem, but its physical variant is not merely a conjecture either. It is a boundary condition on physics: the claim that no physical process can outcompute a Turing machine is equivalent to the claim that physical law is, in some fundamental sense, discrete and finitely describable. Whether this is a deep truth about nature or a methodological habit inherited from the era of discrete computing hardware remains one of the unspoken questions at the foundation of theoretical computer science.