Church-Turing Thesis
/tʃɜːrtʃ ˈtjʊə.rɪŋ ˈθiː.sɪs/ · Noun · Development · Origin: 1936
Definitions
The hypothesis that any function computable by an effective procedure can be computed by a Turing machine. Equivalently, lambda calculus, Turing machines, and all other reasonable models of computation are equally powerful.
In plain English: The claim that there's a hard ceiling on what any computer can ever calculate, and every programming language hits the same ceiling.
Example: "No matter what fancy language you invent, the Church-Turing thesis says it can't compute anything a Turing machine can't."
Origin Story
The unprovable claim that defines what computation means
The **Church-Turing thesis** emerged independently from two mathematicians in 1936. Alonzo Church defined computability using **lambda calculus**, while Alan Turing defined it using his abstract **Turing machine**. They proved their definitions were equivalent.
The thesis states that any function computable by an 'effective procedure' (an intuitive algorithm) can be computed by a Turing machine. It cannot be formally proved because 'effective procedure' is an informal concept -- but no counterexample has ever been found.
The thesis has profound implications: it means all programming languages are fundamentally equivalent in computational power. Python, C, Haskell, and even Minecraft's redstone circuits can all compute exactly the same set of functions. More power comes at the cost of efficiency, not capability.
Coined by: Alonzo Church, Alan Turing
Context: 1936 (independently)
Fun fact: Church was Turing's PhD advisor at Princeton, but they developed their equivalent formulations independently. Turing's paper was submitted just months after Church's, leading to an awkward situation. Church graciously acknowledged the equivalence, and the thesis bears both names.