The Church–Turing Thesis

The Church–Turing thesis asserts that every function computable by any effective procedure is computable by a Turing machine, equating the informal idea of an algorithm with a precise mathematical model.

Definition

The Church–Turing thesis is the claim that the intuitively computable functions are exactly the functions computable by a Turing machine, equivalently by the lambda calculus or the general recursive functions; it is a thesis rather than a theorem because the intuitive notion is not formally defined.

Scope

This topic covers the statement of the thesis, the convergent evidence from independently proposed models, the distinction between the original thesis about effective computability and stronger physical or complexity-theoretic variants, and the role of the thesis as a bridge between intuition and formal proof in computability theory.

Core questions

• What does it mean to identify the informal notion of algorithm with a formal model?
• Why is the convergence of independent models taken as strong evidence for the thesis?
• Is the thesis a mathematical theorem, a definition, or an empirical claim?
• How do physical and complexity-theoretic versions go beyond the original statement?

Key theories

Convergence of computation models

Turing machines, Church's lambda calculus, and Gödel and Herbrand's recursive functions were shown to define exactly the same class of functions, and this independent agreement is the principal evidence offered for the thesis.

Status as a thesis, not a theorem

Because the intuitive notion of effective procedure is not formalized, the claim cannot be proven; it is accepted as a foundational identification that lets informal algorithmic arguments stand in for formal Turing-machine constructions.

Clinical relevance

The thesis licenses the everyday practice of describing algorithms in high-level pseudocode rather than as Turing machines, since any reasonable notion of effective procedure is assumed to be Turing-equivalent; it also frames debates about whether physical or quantum devices could ever compute beyond the Turing-computable.

History

In 1936 Church proposed identifying effective calculability with lambda-definability, and Turing independently argued for his machine model, after which Turing, Kleene, and others proved these and the recursive functions equivalent. Gödel, initially skeptical, came to regard Turing's analysis as conclusive, and the combined claim became known as the Church–Turing thesis.

Debates

Can physical computation surpass the Turing limit?

The original thesis concerns effective procedures, but stronger physical versions claim that no physically realizable device can compute non-Turing-computable functions. Proposals for hypercomputation and the implications of quantum mechanics keep this extended claim contested, even as the classical thesis remains essentially unchallenged.

Key figures

• Alonzo Church
• Alan Turing
• Kurt Gödel
• Stephen Kleene

Seminal works

• church1936
• turing1937

Frequently asked questions

Why is it called a thesis rather than a theorem?

It connects a formal model to the informal idea of an effective procedure, and that informal idea has no mathematical definition to prove things about. The strong evidence is that every independent attempt to formalize computation has yielded the same class of functions, but this support is conceptual rather than a proof.

Do quantum computers refute the Church–Turing thesis?

No. Quantum computers may solve some problems faster, but they compute exactly the same class of functions as Turing machines, so the original thesis about what is computable stands. They bear instead on the stronger complexity-theoretic version concerned with efficiency rather than computability.