Computable Functions and the Church-Turing Thesis

Computable functions are those a mechanical procedure can evaluate, and the Church-Turing thesis identifies this informal notion with several precise mathematical models that all define the same class.

Definition

A function is computable if some Turing machine, equivalently some partial recursive definition, produces its output on every input where it is defined; the Church-Turing thesis asserts that this mathematically precise class coincides with the intuitive class of effectively calculable functions.

Scope

This topic covers Turing machines, the partial recursive functions built from basic functions by composition, primitive recursion, and minimization, the lambda calculus and register machines, the proofs that these models are equivalent, universal machines, and the Church-Turing thesis that they capture all effective computation.

Core questions

• What is a Turing machine and how does it define a computation?
• How are the partial recursive functions generated from basic operations?
• Why do all reasonable models of computation define the same functions?
• What is the status and significance of the Church-Turing thesis?

Key theories

Turing machine model

A Turing machine is a finite-state device operating on an unbounded tape, and the functions it computes formalize the notion of an algorithm in terms of elementary symbol manipulation.

Equivalence of models

Turing machines, the partial recursive functions, the lambda calculus, and register machines all compute exactly the same class of functions, demonstrating the robustness of the notion of computability.

Universal machine and enumeration

There is a universal Turing machine that simulates any machine given its code, so computable functions can be effectively enumerated and treated as data, the basis of self-reference results.

Clinical relevance

The notion of a computable function is the foundation of theoretical computer science: the universal machine prefigures the stored-program computer, the equivalence of models justifies a single robust definition of algorithm, and the framework supplies the precise setting in which undecidability and complexity are studied.

History

In 1936 Church defined effective calculability via the lambda calculus and Turing via his machines, and the two notions were soon proved equivalent to Kleene's recursive functions. The resulting Church-Turing thesis became the accepted definition of algorithm, and Turing's universal machine became a conceptual ancestor of the general-purpose computer.

Key figures

• Alan Turing
• Alonzo Church
• Stephen Cole Kleene
• Emil Post

Seminal works

• cutland1980
• turing1936
• sipser2013

Frequently asked questions

Are some functions not computable?

Yes. Because programs can be enumerated but functions cannot, a counting argument shows most functions are not computable, and specific examples such as the halting function are provably uncomputable. Computability is a genuine restriction on which functions algorithms can evaluate.

Does the Church-Turing thesis limit what computers can do?

It says that no model of effective computation extends the class of computable functions beyond Turing machines. Faster hardware or different architectures change efficiency, not the boundary of what is computable in principle, so the thesis sets an absolute limit on algorithmic solvability.