What Does the Church-Turing Thesis Assert About Computing?

The Church-Turing thesis asserts that any function computable by an intuitive, step-by-step algorithm can be computed by a Turing machine. In classical computing, this thesis establishes that seemingly different formal models of computation—specifically Alonzo Church's lambda calculus, Kurt Gödel's and Stephen Kleene's general recursive functions, and Alan Turing's Turing machines—all define the exact same class of computable functions.

The Three Foundational Models

During the 1930s, mathematicians developed three distinct formalisms to capture the informal notion of an "effective method" for solving problems:

  • Lambda Calculus: Introduced by Alonzo Church, this system expresses computation through function definition and application using variable binding and substitution. A simple identity function is written as \(\lambda x. x\).
  • General Recursive Functions: Developed by Kurt Gödel and refined by Stephen Kleene, this model builds computable functions over the natural numbers \(\mathbb{N}\) starting from basic primitives (zero, successor, and projection) combined with composition, primitive recursion, and the \(\mu\)-operator (minimization).
  • Turing Machines: Proposed by Alan Turing, this abstract mechanical device reads and writes symbols on an infinite tape according to a finite set of state-transition rules.

Equivalence of the Models

Although their syntax and mechanics look completely different, Turing and Church proved in 1936 that these three systems are mathematically equivalent. A function \(f: \mathbb{N} \to \mathbb{N}\) is \(\lambda\)-definable if and only if it is general recursive, and if and only if it is computable by a Turing machine.

Because any program in one model can be translated into an equivalent program in another, they share the same computational power and the same fundamental limitations, such as the undecidability of the halting problem.

Significance in Classical Computing

Because the Church-Turing thesis is a claim about the relationship between an informal concept (human-executable algorithms) and a formal mathematical model, it cannot be formally proved. Instead, it is supported by decades of evidence: every classical programming language and hardware architecture ever built—from C and Python to modern CPUs—is Turing-complete, meaning it can compute no more and no fewer functions than a Turing machine.