Any real-world computation can be translated into an equivalent Turing machine computation. A TM is the general model of computation.
Formerly known as Church’s thesis. First formulated by Alonzo Church. Treated as a conjecture, not a mathematical theorem, because “real-world computation” has no formal definition.
Accepted because:
- No counterexample proposed in 90+ years.
- All other theoretical computation models proven equivalent to TMs.
- Enhanced TMs (multi-tape, nondeterministic, probabilistic) provide no additional computing power.
- TM operations capture all steps essential to human computation.
Implications
Limits of Computation
If no TM can solve a problem, no algorithm can. The thesis converts questions about “what is computable” into questions about Turing machines.
Problems beyond TM capability:
- The Halting Problem
Given a TM and input, decide if the TM halts. Proven undecidable by diagonalization. - Rice’s Theorem
Any non-trivial semantic property of a TM’s language is undecidable.
Undecidability Transfer
To show a new problem is undecidable, reduce a known undecidable problem (typically the Halting Problem) to . If a TM for existed, it would solve the Halting Problem, a contradiction.
Hierarchy of Problems
The thesis anchors the Chomsky hierarchy at the top:
- Decidable problems correspond to recursive languages.
- Semi-decidable problems correspond to recursively-enumerable languages.
- Everything above Type 0 is beyond any computation.