The Church–Turing thesis is a central idea in the theory of computation that characterizes what it means for a function or problem to be effectively computable. Informally, the thesis asserts that any calculation that can be carried out by a human following a definite procedure can also be performed by a simple abstract device known as a Turing machine. This claim is not a mathematical theorem but a broadly accepted definition connecting intuitive notions of algorithmic procedure with formal models of computation.
Formal equivalences and meaning
Several formal models were developed in the 1930s and shown to be equivalent in power. Among these are the Turing machine model, Alonzo Church's lambda calculus, and the class of general recursive functions. The Church–Turing thesis identifies the informal concept of "effective calculability" with this shared class of functions. In practice the thesis implies that if a problem can be solved by any of these models it can be solved by the others. See also the notion of Turing machine and how it serves as the standard model.
History and context
The idea emerged from independent work by Alonzo Church and Alan Turing in the 1930s. Church proposed a formalization based on the lambda calculus; Turing introduced his abstract machine and used it to analyze computation and decidability. Their results, together with related developments in recursion theory, led to the consensus that these formal systems capture the intuitive idea of algorithmic computation. The thesis is related to foundational results like Gödel's incompleteness theorems, which highlight intrinsic limits on formal systems and decidability.
Consequences, limits, and practice
A direct consequence is the concept of Turing completeness: a programming language or system is called Turing complete if it can simulate a Turing machine and thus express any computable function. The thesis also makes clear that there are well-defined limits to what algorithms can accomplish—classic examples include the undecidability of the halting problem and other noncomputable decision problems. Practical computing, however, also concerns resources such as time and memory, topics addressed by computational complexity theory rather than by the thesis itself.
Variants and notable distinctions
Several related formulations exist. The original, sometimes called the Church–Turing thesis, ties informal computability to the equivalence class of concrete models. Stronger informal statements propose that any physically realizable computing device can be simulated by a Turing machine; these "physical" or "extended" versions are debated in light of models like quantum computing. While quantum and probabilistic machines can change efficiency and the types of feasible algorithms, they are generally viewed as operating within extended frameworks that do not overturn the core identification of effectively computable functions.
For further reading about computation and machines, see general resources on computers and foundational models of computation such as the Turing machine. Additional material is available through surveys and textbooks on computability and complexity theory that examine how the Church–Turing thesis underpins modern theoretical computer science.