Vol. I a living index of named laws · est. mmxxvi no ads · no account
The Law Tomeindex of named laws

The Church-Turing Thesis

"Anything that can be computed by any mechanical procedure can be computed by a Turing machine."
In plain English

What does The Church-Turing Thesis mean?

A function is effectively calculable (computable by some intuitive, finite, step-by-step procedure) if and only if it is computable by a Turing machine. In other words, the abstract Turing machine captures exactly what it means for anything to be computable at all; no genuine mechanical method escapes it.

Reliability

Rated Heuristic: a dependable rule of thumb, not a proven theorem. The other 224.

Lineage
1936COINED
How it works

How does The Church-Turing Thesis work?

The thesis draws its force from convergence. Several models of computation, invented independently on entirely different foundations (Turing machines, Church's lambda calculus, the general recursive functions, register machines) were each proven to define exactly the same class of computable functions. A function is computable in one if and only if it is computable in all. This coincidence of unrelated definitions, none ever exceeded by a stronger reasonable model, is the central evidence that they all capture the same intuitive notion.

Where you'll see it

What are examples of The Church-Turing Thesis?

Lambda calculus equals machines Anything definable in Church's lambda calculus, a formalism of pure symbolic substitution, can be computed by a Turing machine and vice versa, two utterly different systems picking out one identical class of functions.
Recursive functions equal machines The general recursive functions of Herbrand and Godel coincide exactly with the Turing-computable functions: again an independently motivated definition landing on the same class.
No stronger reasonable model In ninety years, every proposed model of mechanical computation (cellular automata, real programming languages, quantum machines for what is computable) has turned out to compute at most the Turing-computable functions, never more.
Types & variants

What are the types of The Church-Turing Thesis?

The physical Church-Turing thesis§

The stronger claim that every function computable by any physical process is Turing-computable: a statement about physics, not mathematics, and genuinely debated.

The extended thesis§

The efficiency version, that any reasonable model can be simulated with only polynomial slowdown: challenged by quantum computing, where Shor's algorithm gives an apparent super-polynomial speedup.

Why it matters

Why does The Church-Turing Thesis matter?

It is the foundational bridge between the informal idea of computation and its precise mathematical model, licensing the whole theory of computability. Because of it, results proved about Turing machines (like the undecidability of the halting problem) are taken to apply to every possible computer and programming language.

Working with it

How do you apply The Church-Turing Thesis?

  • Treat Turing-computable as computable — when reasoning about what any algorithm can do, use the Turing machine as the stand-in for computation in general.
  • Read the equivalences as evidence — take the coincidence of independent models on one function class as the reason to accept the thesis, not a proof of it.
  • Separate the versions — keep the original computability thesis distinct from the physical and efficiency versions, which are separate and contested claims.
Where it breaks down

What are the limits of The Church-Turing Thesis?

It is a thesis, not a theorem, and cannot be formally proved, because one side of it ('effectively calculable') is an informal, pre-mathematical notion, and no proof can equate a precise class with a vague intuition. It could in principle be refuted by exhibiting an accepted mechanical procedure that no Turing machine computes, which has never happened. Its physical version, about what real devices can compute, depends on open physics; its efficiency version is challenged by quantum computing. These stronger claims are logically separate from the original and should not be conflated with it.

What it doesn't say

What are common misconceptions about The Church-Turing Thesis?

It is not a proven theorem: the equivalence of the various computation models is proved, but the thesis linking them to the informal notion of computability is not and cannot be. And the popular slogans about physical devices or efficient simulation are separate, contested theses, not the original claim.

Is it real?

Is The Church-Turing Thesis real?

Real as a rule of thumb, not as a theorem. The Church-Turing Thesis is rated Heuristic here: dependable enough to plan with, and with no proof behind it.

Rated from three sources. 225 of the 1,116 entries carry this rating. How the scale works.

Occasionally printedin printed books: one of 240 names in its band, of 903 measured
25 of 69entries in software & systems carry the same rating

The best-known laws are the least likely to rest on measurement.

Origin

Where did The Church-Turing Thesis come from?

Advanced independently in 1936 by Alonzo Church, via the lambda calculus and recursive functions, and Alan Turing, via his machines, with Church publishing slightly earlier; Stephen Kleene later named it, and Godel was persuaded specifically by Turing's analysis.

How the name spread

When did people start saying “The Church-Turing Thesis”?

1800coined 19362019
How often “Church - Turing Thesis” appears in printed English, which takes hold around 1976 and peaks around 2014. The idea dates to 1936: the phrase took about 40 years to reach print in any quantity, which is the gap this chart measures. Source: Google Books Ngrams.

What we checked

  • 1,116entries in the tomeListed one by one on the browse page.
  • 1,116of them citing a sourceOpen any entry: its sources sit at the foot of the page.
  • 2,489source references in allEach is named, and linked wherever the source is online.