The Church-Turing Thesis
"Anything that can be computed by any mechanical procedure can be computed by a Turing machine."
"Anything that can be computed by any mechanical procedure can be computed by a Turing machine."
A function is effectively calculable (computable by some intuitive, finite, step-by-step procedure) if and only if it is computable by a Turing machine. In other words, the abstract Turing machine captures exactly what it means for anything to be computable at all; no genuine mechanical method escapes it.
Rated Heuristic: a dependable rule of thumb, not a proven theorem. The other 224.
The thesis draws its force from convergence. Several models of computation, invented independently on entirely different foundations (Turing machines, Church's lambda calculus, the general recursive functions, register machines) were each proven to define exactly the same class of computable functions. A function is computable in one if and only if it is computable in all. This coincidence of unrelated definitions, none ever exceeded by a stronger reasonable model, is the central evidence that they all capture the same intuitive notion.
The stronger claim that every function computable by any physical process is Turing-computable: a statement about physics, not mathematics, and genuinely debated.
The efficiency version, that any reasonable model can be simulated with only polynomial slowdown: challenged by quantum computing, where Shor's algorithm gives an apparent super-polynomial speedup.
It is the foundational bridge between the informal idea of computation and its precise mathematical model, licensing the whole theory of computability. Because of it, results proved about Turing machines (like the undecidability of the halting problem) are taken to apply to every possible computer and programming language.
It is a thesis, not a theorem, and cannot be formally proved, because one side of it ('effectively calculable') is an informal, pre-mathematical notion, and no proof can equate a precise class with a vague intuition. It could in principle be refuted by exhibiting an accepted mechanical procedure that no Turing machine computes, which has never happened. Its physical version, about what real devices can compute, depends on open physics; its efficiency version is challenged by quantum computing. These stronger claims are logically separate from the original and should not be conflated with it.
It is not a proven theorem: the equivalence of the various computation models is proved, but the thesis linking them to the informal notion of computability is not and cannot be. And the popular slogans about physical devices or efficient simulation are separate, contested theses, not the original claim.
Real as a rule of thumb, not as a theorem. The Church-Turing Thesis is rated Heuristic here: dependable enough to plan with, and with no proof behind it.
Rated from three sources. 225 of the 1,116 entries carry this rating. How the scale works.
The best-known laws are the least likely to rest on measurement.
Advanced independently in 1936 by Alonzo Church, via the lambda calculus and recursive functions, and Alan Turing, via his machines, with Church publishing slightly earlier; Stephen Kleene later named it, and Godel was persuaded specifically by Turing's analysis.
Everything above traces to doi.org, plato.stanford.edu and en.wikipedia.org, three sources in all, one of them the original publication rather than an account of it. Nothing is written from memory, and the method is written down. Spot an error or a better source? Suggest a fix.