Church-Turing Thesis

Definition: The Church-Turing Thesis is the foundational claim that any function which is “effectively calculable” — computable by some finite, mechanical, step-by-step procedure a human or machine could in principle carry out — is exactly the set of functions computable by a Turing machine. It was formulated independently in 1936 by Alonzo Church, working with the lambda calculus, and Alan Turing, working with his machine model, and the two formalizations were shortly afterward proven to define precisely the same class of functions. Unlike a theorem, it can never be formally proved, because one side of the equivalence — “effectively calculable” — is an informal, intuitive notion rather than a mathematical object; nearly a century of failed attempts to find a broader, still-intuitively-mechanical model of computation is the closest thing to evidence it has.

Formal Definition

The thesis asserts {f : f is effectively calculable} = {f : f is Turing-computable}
The left-hand side is deliberately informal — “effectively calculable” means computable by a finite procedure using a bounded set of unambiguous instructions, in finitely many steps, without insight or guessing
The right-hand side is fully formal, defined by the 7-tuple Turing machine model described in Turing Machine
Because one side is not formally defined, the equation can never be proven in the mathematical sense — it can only be supported by convergent evidence, which is why it is a thesis, not a theorem
A function is Turing-computable if some Turing machine, given an encoding of its input, halts and produces the correct output for every input in the function’s domain
Formal restatements provably equivalent to Turing-computability include λ-definability, general recursive functions, and Post’s production systems — see Variants below
The thesis is sometimes split into a “bold” reading (all reasonable models of computation are Turing-equivalent) and a narrower historical reading (specifically, human step-by-step calculation matches Turing-computability) — most modern usage intends the bolder, more general reading

How It Works

Bridges informal and formal: the thesis is the load-bearing link between “algorithm” as humans intuitively use the word and “Turing machine” as a precisely defined mathematical object — every claim like “there’s no algorithm for X” secretly relies on this bridge
Multiple independent formalizations converge: Church’s lambda calculus (functions and substitution), Turing’s machine (tape and states), Gödel and Kleene’s general recursive functions (built from primitive recursion and minimization), and later Markov algorithms and register machines were all developed for different reasons and later proven to compute exactly the same set of functions
Equivalence proofs, not the thesis itself, are theorems: it IS a theorem, fully provable, that lambda calculus and Turing machines compute the same functions — what’s NOT provable is that this shared class equals “everything a human could compute by rote procedure”
The thesis is falsifiable in principle: a genuine counterexample — a function generally agreed to be mechanically computable by some clear step-by-step procedure, yet provably not Turing-computable — would refute it; none has ever been found despite deliberate searching
It licenses using any equivalent model interchangeably: once a problem reduces to lambda calculus, general recursive functions, or a register machine program, results about Turing machines transfer automatically, because the thesis guarantees they describe the same computational universe
It says nothing about efficiency: the thesis concerns only which functions ARE computable, not how many steps or how much memory computing them takes — two Turing-equivalent models can differ by exponential factors in efficiency while both satisfying the thesis equally
Extended forms make stronger physical claims: the Physical Church-Turing Thesis extends the claim to physical processes in the universe (any physically realizable computation is Turing-computable), a substantially bolder and more contested claim than the original thesis about human effective calculability
It is a ceiling, not a recipe: the thesis says what class of functions is reachable in principle, it says nothing about HOW to construct an algorithm for any particular function — plenty of functions are Turing-computable in theory yet no one has ever found a concrete algorithm for them

Why It Matters

Every undecidability proof (see Halting Problem and Decidability) is only meaningful because the thesis licenses treating “no algorithm exists” and “no Turing machine exists” as the same claim — without it, undecidability results would only describe one specific formal model
It justifies programming language design freedom: any two Turing-complete languages are provably interchangeable in what they CAN compute (see Turing Completeness), so language choice is legitimately about ergonomics and safety, never about raw computational reach
It underwrites complexity theory’s stability: classes like P and NP are defined relative to Turing machines, but thanks to the thesis they’re considered robust, model-independent notions of “efficiently solvable,” not artifacts of one formalism
It draws the line between mathematics and engineering for hard problems: if a problem is proven not effectively calculable, no future hardware, architecture, or clever algorithm working within classical mechanical procedure can change that verdict
It shaped the philosophical question of what minds and machines can, in principle, do — debates about artificial intelligence and the computability of cognition often trace back to whether the brain’s operations fall under “effectively calculable” at all
It gives every equivalence proof between new computational models (a new esoteric language, a new hardware paradigm) a shared standard to be measured against, rather than requiring each new model to be evaluated against every other model pairwise

Under the Hood: The Three-Way Equivalence Chain

Turing machines to lambda calculus: any Turing machine’s configuration — state, tape contents, head position — can be encoded as a lambda term, and one application of the transition function δ can be expressed as a lambda term transforming one encoded configuration into the next
Lambda calculus to Turing machines: conversely, any lambda expression can be mechanically reduced (beta reduction) by a Turing machine manipulating a tape-based representation of the expression tree, applying substitution rules step by step
General recursive functions as a third bridge: Gödel and Kleene formalized computable functions starting from a small base — zero, successor, projection — closed under composition, primitive recursion, and the minimization (μ) operator; Kleene proved this class exactly coincides with both lambda-definable and Turing-computable functions
Turing’s own 1937 proof: in the follow-up paper “Computability and λ-definability,” Turing directly proved his machine model and Church’s lambda calculus compute the same class of functions, cementing the “Church-Turing” pairing in the name
Register machines close the loop: Shepherdson and Sturgis (1963) proved simple register machines — unbounded memory cells manipulated by increment, decrement, and jump-if-zero instructions — are also equivalent, reassuring evidence the equivalence isn’t an artifact specific to tapes or symbolic substitution
Post’s production systems and Markov algorithms: string-rewriting formalisms developed independently for logic and linguistics were also proven Turing-equivalent, adding still more independently-motivated routes to the same computational ceiling
The pattern that emerges: every serious attempt to formalize “mechanical procedure,” regardless of starting vocabulary — tapes, functions, rewriting rules, registers — lands on the exact same class of functions, which is the empirical weight behind an otherwise unprovable thesis

Key Argument: Why the Thesis Cannot Be a Theorem

A mathematical theorem requires every term in its statement to be formally defined within an agreed axiomatic system
“Turing-computable” is fully formal, defined by the 7-tuple machine model, with no ambiguity about what counts
“Effectively calculable” is not formal — it’s an appeal to intuition about what an idealized human, with unlimited time, paper, and patience, could carry out by rote, unambiguous steps
Any attempted formal definition of “effectively calculable” would itself be just another formal model — and asserting THAT model captures the true informal notion runs into the identical problem one level up
This is why the strongest possible evidence for the thesis is convergence: independently motivated formalizations landing on the same class of functions, rather than a single deductive proof
The thesis could in principle be falsified — discovering a widely-agreed “effectively calculable” procedure that provably escapes Turing-computability would refute it — but it cannot be positively proven, only repeatedly corroborated
This asymmetry, falsifiable but not provable, is why philosophers of computation sometimes compare the thesis’s epistemic status to a scientific law rather than a mathematical result — closer to a conservation law than to a geometric theorem

Lambda calculus (Church, 1936): functions defined purely through abstraction and application, with computation proceeding via beta reduction — the original alternative formalization that motivated the thesis’s name
General recursive functions (Gödel/Kleene): functions built from a minimal base set closed under composition, primitive recursion, and unbounded search (the μ-operator) — the formalization most directly rooted in mathematical logic
Register machines / RAM model: unbounded arrays of integer-holding registers manipulated by a small instruction set — closer in spirit to how real computer architectures are organized
Cellular automata: grids of simple cells updating in parallel by local rules (e.g. Conway’s Game of Life) — proven Turing-equivalent despite having no explicit “state machine” or “tape” at all
Physical Church-Turing Thesis: the stronger, more contested extension claiming any process realizable in the physical universe can be simulated by a Turing machine — debated in the context of quantum mechanics, relativistic computing, and hypothetical exotic physics
Hypercomputation proposals: speculative models — infinite-time Turing machines, Malament-Hogarth spacetimes, oracle-based “computers” — that claim to compute beyond the Turing-computable set; none has a physically realized instance, and all remain controversial precisely because they’d falsify the physical thesis if real
Markov algorithms: a Soviet-developed string-rewriting formalism using ordered pattern-replacement rules, independently proven Turing-equivalent, and historically influential in the development of early formal language and parsing theory

Key Theorems and Results

Turing’s 1937 equivalence proof: formally established that lambda-definability and Turing-computability define the same class of functions, the theorem that gave the thesis its combined name
Kleene’s Normal Form Theorem: every general recursive function can be expressed using just one application of the minimization operator wrapped around a primitive recursive function, simplifying the recursive-function/Turing-machine equivalence proof
Shepherdson-Sturgis Theorem (1963): proved register machines Turing-equivalent, extending the convergence evidence to a model structurally close to physical computer hardware
Deutsch’s quantum extension (1985): proposed the “quantum Church-Turing thesis,” that a universal quantum computer can efficiently simulate any physical process — reopening the physical thesis question and motivating quantum complexity theory
Gandy’s theorem (1980): derived Turing-computability as a necessary consequence of a small set of physically-motivated axioms about discrete mechanical devices, one of the more rigorous attempts to turn the physical thesis into something closer to a real theorem
The non-existence of a refuting counterexample: perhaps the most cited “result” isn’t a theorem at all but a negative fact — no function has ever been exhibited that is agreed to be effectively calculable yet provably not Turing-computable, despite explicit searches by generations of logicians
Church’s own theorem on the Entscheidungsproblem: Church proved, independently of Turing, that no algorithm decides validity in first-order logic, using lambda calculus rather than machines, giving the thesis two structurally different origin proofs rather than one

Comparison: Church-Turing Thesis vs Its Extensions vs Turing Completeness

	Church-Turing Thesis	Physical Church-Turing Thesis	Quantum Church-Turing Thesis	Turing Completeness
What it claims	Effectively calculable = Turing-computable	Any physical process is Turing-simulable	Efficient physical simulation needs only quantum-Turing-equivalent power	A specific system can simulate any Turing machine
Status	Nearly universally accepted, unprovable thesis	Debated, especially regarding quantum/relativistic physics	Actively researched, tied to quantum complexity theory	Provable or checkable for a concrete system
Concerns computability or efficiency?	Computability only	Computability only	Efficiency (polynomial-time simulation)	Computability only
Proposed by	Church and Turing, 1936	Various, mid-to-late 20th century	David Deutsch, 1985	Community usage following Turing’s model
Empirically threatened by	Nothing so far	No known physical counterexample	Open — depends on quantum complexity theory results	N/A — checkable directly per system
Can be challenged by	A verified effectively-calculable, non-Turing-computable function	A physically realized hypercomputer	A proven efficient classical simulation gap, or the lack of one	Showing the system cannot simulate some Turing machine

Common Pitfalls

Calling it the “Church-Turing Theorem” — it is explicitly not a theorem, and thesis-versus-theorem is the single most common mix-up in casual discussion
Believing the thesis says all computational models are equally fast — it makes zero claims about efficiency, only about which functions can be computed at all given unbounded time and memory
Assuming the thesis has been “proven” because lambda calculus and Turing machines were proven equivalent — that equivalence is a real theorem, but it only shows two FORMAL models match each other, not that either matches the informal notion of “effectively calculable”
Treating hypercomputation proposals as established refutations — no hypercomputer has ever been physically built or empirically demonstrated, so these remain speculative models, not counterexamples
Confusing the original thesis about human effective calculability with the Physical Church-Turing Thesis about all physical processes — the second is a strictly stronger, more contested claim the first doesn’t itself make
Assuming quantum computers threaten the thesis — they don’t compute any new functions beyond the Turing-computable set, they only conjecturally offer speedups for some problems, a complexity question, not a computability one
Thinking the thesis is unique to computer science — it originated in mathematical logic answering Hilbert’s Entscheidungsproblem, and its philosophical tail extends well beyond either field
Assuming the thesis implies every effectively calculable function has a SHORT or PRACTICAL algorithm — it only guarantees existence of some Turing machine computing it, which could still require astronomically many steps

Worked Example: Tracing One Function Through Three Models

Take the simple function double(n) = 2n on natural numbers
As a Turing machine: a machine reads a unary-encoded n, then writes an extra copy of each mark it sees, doubling the block length, halting when the input block is exhausted
As a lambda term: double = λn. λf. λx. n f (n f x) using Church-encoded numerals, doubling via nested function application rather than any tape at all
As a general recursive function: double(0) = 0 and double(n+1) = double(n) + 2, built from primitive recursion over the base successor and addition functions
All three constructions, sharing no notation, no “state,” and no “tape” in common, compute exactly the same input-output mapping for every natural number n — the equivalence the thesis rests its case on, replayed for one trivial function instead of the general theorem
Try to imagine a fourth, genuinely different “effectively calculable” way to double a number that escapes all three formalizations — the difficulty of even conceiving such a thing is itself the informal evidence the thesis leans on

Worked Example: Doubling a Number on a Register Machine

A register machine — one of the models proven Turing-equivalent — computes double(n) = 2n using two registers, R1 (input) and R2 (output, starts at 0), and a tiny four-line program: L1: if R1 = 0 goto L4, else decrement R1 and goto L2; L2: increment R2; L3: increment R2 and goto L1; L4: halt. Tracing it on input n = 2:

Step	Line	R1 before	R2 before	Action	R1 after	R2 after
1	L1	2	0	R1 ≠ 0, decrement R1, goto L2	1	0
2	L2	1	0	increment R2, fall through to L3	1	1
3	L3	1	1	increment R2, goto L1	1	2
4	L1	1	2	R1 ≠ 0, decrement R1, goto L2	0	2
5	L2	0	2	increment R2, fall through to L3	0	3
6	L3	0	3	increment R2, goto L1	0	4
7	L1	0	4	R1 = 0, goto L4	0	4
8	L4	0	4	halt	0	4

The machine halts with R2 = 4, correctly computing 2 × 2, using nothing but decrement, increment, and conditional jump — the same doubling function computed by the Turing machine and lambda term in the previous worked example, by a third route entirely.

Applications Beyond Pure Theory

Language-agnostic algorithm design: the thesis is why a whiteboard algorithm sketched in pseudocode can be trusted to be implementable in any real programming language without first checking that language’s “power” — they’re all provably equivalent
Compiler correctness and cross-language transpilation: tools translating code between Turing-complete languages rely implicitly on the thesis-backed guarantee that no computable behavior is lost in translation, only syntax and efficiency change
Quantum computing research framing: the quantum extension is precisely what focuses quantum computing research on efficiency and complexity questions rather than computability questions — see P vs NP Complexity Classes
Philosophy of mind and AI: debates over whether human cognition is “computable” in principle often reduce to whether the brain’s operations count as effectively calculable, directly invoking the thesis’s scope and limits
Legal and policy reasoning about software: arguments that any algorithm can in principle be implemented in any Turing-complete system, relevant to software patents and export controls on cryptographic code, rest on the thesis holding across implementations
Textbook and curriculum design: the standard order of teaching Turing machines, then lambda calculus or recursive functions, then proving them equivalent, exists specifically to build intuition for the thesis before naming it explicitly

Best Practices (How to Reason About the Thesis)

When explaining the thesis, state clearly which side is formal (Turing-computability) and which is informal (effective calculability) — most confusion stems from treating both sides as equally rigorous
Never call it “proven” — describe it as “supported by every independent formalization attempted so far,” which is accurate and captures why it’s trusted despite being unprovable
Distinguish the original thesis from its Physical and Quantum extensions explicitly when precision matters — conflating them overstates what the base thesis actually claims
When someone proposes a “hypercomputer,” ask what physical mechanism realizes it — the thesis’s resilience comes specifically from the absence of any physically demonstrated counterexample, not from a logical impossibility of one
Keep computability and efficiency arguments separate — invoking the thesis to argue two systems are “equally practical” is a category error, it only speaks to what’s computable at all
When presenting equivalence proofs (lambda calculus, recursive functions, register machines), frame them as evidence FOR the thesis, never as the thesis itself being proven
When a new computational model is proposed, check first whether it can simulate a register machine or a two-counter machine — the fastest route to placing it within (or, rarely, credibly outside) the Turing-computable class

FAQ

Why is it called a “thesis” instead of a “law” or “theorem”? Because it links a formal mathematical object, Turing machines, to an informal, intuitive notion, effective calculability, that cannot itself be given a rigorous definition — no genuine proof is possible, only accumulating evidence.

Did Church or Turing come first? Church published his lambda-calculus-based version first in 1936; Turing’s paper appeared shortly after the same year, developed independently, and the two were quickly shown equivalent, which is why both names attach to the thesis.

Does quantum computing violate the Church-Turing Thesis? No — quantum computers are believed to offer speed advantages for specific problems, a complexity-theoretic question, but they don’t compute any function outside the Turing-computable set, so the original thesis stands unchallenged.

Is there any known function that is effectively calculable but not Turing-computable? None has ever been found or agreed upon, despite explicit searching by generations of logicians and computer scientists — this absence, rather than a proof, is the thesis’s main support.

What’s the difference between the thesis and Turing completeness? The thesis is a claim about the boundary of computability itself, applying to every model; Turing completeness is a checkable property of one specific system, asking whether it reaches that boundary — see Turing Completeness.

Could future physics ever overturn the thesis? The original thesis is fairly insulated from physics, but the Physical Church-Turing Thesis could in principle be overturned by a physically realized hypercomputer — none currently exists, and most proposals rely on unphysical idealizations like infinite precision or infinite time.

Does the thesis mean every computable function has a practical algorithm? No — it only guarantees that some Turing machine computes the function eventually, with no bound on how many steps that might take; a function can be computable in principle and still be utterly infeasible to compute in practice.

History

David Hilbert’s 1928 Entscheidungsproblem asked for a mechanical decision procedure for first-order logic, setting up the question both Church and Turing would independently answer
Alonzo Church proposed identifying “effective calculability” with lambda-definability in 1936, publishing his negative solution to the Entscheidungsproblem using this identification
Alan Turing, unaware of Church’s work in progress, published his own independent formulation using the machine model later that same year, also solving the Entscheidungsproblem negatively
Turing then spent 1936-1938 at Princeton studying under Church, during which the formal equivalence between lambda calculus and Turing machines was worked out and published
Stephen Kleene coined the term “Church’s Thesis” in his later work, and the now-standard “Church-Turing Thesis” name became common once the equivalence with Turing’s model was widely recognized
The thesis’s scope broadened over subsequent decades, from Church and Turing’s original claim about human effective calculability to the Physical Church-Turing Thesis and, from the 1980s onward following Deutsch’s work, the Quantum Church-Turing Thesis
Emil Post published closely related independent work on effective calculability and canonical systems around the same period, sometimes prompting the fuller name “Church-Turing-Post Thesis” in more historically careful texts

Common Interview Questions

“Why is the Church-Turing Thesis not provable?” — expect an answer centered on the informal, undefined nature of “effectively calculable” on one side of the equation
“Name three models proven equivalent to Turing machines” — expect lambda calculus, general recursive functions, and register machines, or cellular automata and Post systems, among the answers
“Does the thesis say anything about efficiency?” — expect a firm “no,” with a clear explanation that computability and complexity are separate questions
“What would it take to disprove the thesis?” — expect mention of exhibiting a function agreed to be effectively calculable by some clear mechanical procedure yet provably not Turing-computable
“How does the thesis relate to quantum computing?” — expect a distinction between the unchallenged base thesis and the actively researched, efficiency-focused quantum extension
“Is the human brain Turing-computable?” — expect an acknowledgment that this is open and philosophically contested, hinging on whether cognition counts as an effective procedure at all, not a settled technical question

Example

When Alonzo Church’s lambda calculus and Alan Turing’s machine model — invented independently, using entirely different vocabularies, within months of each other in 1936 — were proven mathematically equivalent, it became the founding piece of evidence for the thesis bearing both their names. Every modern programming language, general recursive function definition, and register-machine assembly program has since joined that same equivalence class, which is precisely why a Python script, a Turing machine program, and a raw lambda expression are, at the level of what they can ultimately compute, indistinguishable — see Turing Machine for the formal model this thesis is anchored to.

Referenced by

Dig deeper

Spot an error in this note?