What the work claims
The Church–Turing thesis claims that every function calculable by an effective method is computable by a Turing machine — and vice versa. It identifies ‘effective calculability’ with three formally equivalent classes: Turing computable, λ-computable, and general recursive. It asserts that no computational procedure qualifies as an algorithm unless representable as a Turing machine.
How it was done
Church formalised effectively calculable functions as general recursive or λ-definable functions in 1935–36. Turing independently created the Turing machine model in 1936 — a theoretical device manipulating symbols on a tape — and used it to reformulate Gödel’s 1931 results. Church proved the Entscheidungsproblem undecidable using lambda calculus in his 1936 paper. Turing proved its unsolvability by showing the halting problem for Turing machines is undecidable, then introduced the universal Turing machine. Both showed their models were equivalent in computational power.
What holds up
The formal equivalence of Turing computability, λ-computability, and general recursiveness holds. Church and Turing both proved the Entscheidungsproblem unsolvable — Church via lambda calculus, Turing via the halting problem. The universal Turing machine’s capacity to simulate any algorithmic computation holds. The thesis remains unrefuted: no effective method has been shown to compute a function outside these classes.
What does not
It does not prove anything. It cannot be formally proven because ‘effective calculability’ is informally defined. It does not establish physical limits on computation. It does not cover non-algorithmic processes, real-time systems, or bounded-resource computation. It says nothing about efficiency, speed, memory, or implementation.
Why it matters beyond the lab
It anchors all digital computation. Every programming language, compiler, and CPU architecture assumes this thesis. It separates solvable from unsolvable problems in logic, mathematics, and computer science. It underpins modern cryptography, complexity theory, and the theoretical limits of AI — not as speculation, but as the accepted frame for asking ‘what can be computed?’
Is it worth your time
Yes. It defines the boundary of what can be computed — not as engineering limits, but as logical ones. It remains foundational for computing theory, programming language design, and AI theory. Its informal status means it cannot be bypassed by new hardware or algorithms; it must be confronted anew with each claim of ‘beyond-Turing’ computation.