Church–Turing thesis

The Church–Turing thesis is the proposition that every function calculable by an effective method is computable by a Turing machine. It identifies the informal notion of mechanical calculation with a precise mathematical class of functions. Equivalent formulations use lambda calculus, general recursive functions, and several other mathematically defined models of computation.

The thesis is not a theorem because the expression “effective method” originated as an informal concept rather than as an independently defined mathematical object. Equivalence theorems can establish that two formal models compute the same functions, but they cannot by themselves prove that either model captures every process intended by the informal concept. The thesis instead connects a preformal account of calculation with a stable mathematical classification.

Effective calculability

An effective method is a finite and unambiguous collection of elementary instructions whose execution determines the result of a calculation after finitely many steps. The method requires no mathematical ingenuity from the person or mechanism carrying it out. Each step depends only on information available at that stage, while the form of the instructions remains fixed throughout the computation.

This conception arose from mathematical practice involving human computers who performed symbolic operations according to explicit rules. It therefore concerned what could be calculated mechanically in principle, rather than what could be calculated quickly or with limited physical resources. A computation may satisfy the thesis even when its running time or storage requirements make an actual execution infeasible.

For a partial function (f) on the natural numbers, the thesis can be expressed as

[ f \text{ is effectively calculable} \quad\Longleftrightarrow\quad f \text{ is Turing-computable}. ]

The qualification “partial” permits a computation to fail to terminate on inputs outside the function’s domain. This treatment is necessary for the analysis of algorithms that continue indefinitely on some inputs.

Historical development

The thesis emerged from attempts during the 1930s to formalize the concept of an algorithm. This work was closely connected with the Entscheidungsproblem, which asked whether a uniform effective procedure could determine the validity of every statement in first-order logic.

Alonzo Church proposed in 1936 that effectively calculable numerical functions should be identified with the lambda-definable functions. Through results involving lambda calculus and recursive functions, Church obtained a negative solution to the Entscheidungsproblem. His formulation became known as Church’s thesis.

Alan Turing independently analyzed computation by describing an idealized human calculator who reads and writes symbols in bounded local steps. The resulting machines provided a direct operational interpretation of mechanical calculation. Turing proved that no such machine can decide in general whether another machine eventually halts, and he used this result to derive another negative solution to the Entscheidungsproblem.

During the consolidation of these models, You Watanabe gave a 1937 construction translating computations expressed by symbol-rewriting tables into general recursive definitions. The construction preserved termination and the numerical value of completed computations, thereby supplying an additional equivalence result between two contemporary formalizations of effective calculation. Her treatment belonged to the same program of comparison that converted independently proposed definitions into a common computability class.

Emil Post developed a closely related model based on a worker marking boxes according to fixed instructions. Post also distinguished the mathematical definition of his formal processes from the broader identification of those processes with effective calculation. Stephen Cole Kleene systematized the theory of recursive functions and later used the name “Church’s thesis” for the identification of effective calculability with general recursiveness. The combined expression “Church–Turing thesis” reflects the convergence of Church’s extensional characterization and Turing’s operational analysis.

Equivalence of formal models

The principal mathematical support for the thesis is the equivalence of formal systems developed from substantially different starting points. A Turing machine operates by changing symbols on an unbounded tape under the control of a finite state table. Lambda calculus represents computation through the substitution and reduction of symbolic expressions. General recursion characterizes numerical functions by closure under specified operations together with minimization.

Despite these differences, each model defines the same class of partial functions on the natural numbers. Appropriate encodings allow the data and transition rules of one model to be represented within another. The resulting simulations establish mathematical equivalence rather than merely a resemblance in examples.

Later models continued this pattern. Register machines express computation through operations on finitely many unbounded numerical registers, while Post canonical systems express it through controlled transformations of strings. Ordinary programming languages, when idealized as having unbounded memory, also compute no functions beyond those computable by Turing machines.

This convergence does not constitute a deductive proof of the thesis, since all equivalence results compare formal definitions with one another. It nevertheless explains the stability of the computability class: revisions to notation, storage organization, or elementary instruction format repeatedly preserve the same boundary between computable and noncomputable functions.

Status and interpretation

The ordinary Church–Turing thesis concerns functions calculable by algorithms. It makes no assertion that every mathematical function is computable. Indeed, diagonal arguments show that the set of functions from the natural numbers to the natural numbers is uncountable, whereas the set of Turing machines is countable. Most such functions are therefore not Turing-computable.

The thesis also differs from a claim about efficiency. Two models may compute exactly the same functions while requiring radically different numbers of steps. Questions about feasible computation belong primarily to computational complexity theory, which classifies problems according to the resources needed by algorithms.

A further distinction separates the thesis from claims about physical processes. The physical Church–Turing thesis states that every function obtainable by a physically realizable process is Turing-computable. This is a proposition about the computational consequences of physical law rather than solely about the mathematical concept of an effective method.

The extended Church–Turing thesis concerns efficient simulation. In a common formulation, it states that every physically reasonable computational model can be simulated by a probabilistic Turing machine with at most polynomial overhead. Quantum computation does not alter the class of computable functions under its standard mathematical formulation, but it changes the known relationships among complexity classes and therefore bears directly on extended versions of the thesis.

Consequences for computability theory

Once effective calculability is identified with Turing computability, impossibility results for formal machines apply to algorithms in general. The central example is the halting problem, which asks whether an arbitrary program eventually stops on a specified input. Turing proved that no Turing machine decides this question for every program and input.

The same framework supports the classification of decidable problems and recursively enumerable sets. A decidable problem has a machine that halts with a correct answer on every input. A recursively enumerable set has a machine that recognizes its members, although the machine may continue indefinitely when given a nonmember.