Source Count: 13 | Weighted Score: 28 | Source Confidence: [3/5] | Primary Tier: 1 | Last Updated: March 10, 2026
Keywords: Turing machine, computability, decidability, halting problem, Church-Turing thesis, algorithm, recursion, Gödel, incompleteness, lambda calculus, recursive function, universal machine, undecidable, computable, enumerable, Post, computation, formal system, decision problem, Entscheidungsproblem
Category Tags: information computation, computability, Turing machine, logic
Cross-References: ZD_1_01 — Information Computation Overview · ZD_1_05 — Computational Complexity · V_1_01 — Mathematics Information Overview · ZD_1_13 — Kolmogorov Complexity

QUICK SUMMARY

The Turing machine — a mathematical model of computation defined by Alan Turing in his 1936 paper "On Computable Numbers, with an Application to the Entscheidungsproblem" — is the foundational formalism of theoretical computer science, providing a precise definition of what it means for a function to be computable and establishing the existence of problems that are fundamentally unsolvable by any algorithmic process. A Turing machine consists of: (1) an infinite tape divided into cells, each of which can hold a symbol from a finite alphabet; (2) a head that can read and write symbols on the tape and move one cell left or right; (3) a state register that stores the machine's current state (from a finite set of states); and (4) a transition function (the "program") that, given the current state and the symbol under the head, specifies: what symbol to write, which direction to move the head, and what state to transition to. Despite its extreme simplicity, the Turing machine can simulate any algorithmic computation: any problem that can be solved by a modern computer, by any programming language, by any conceivable mechanical procedure, can be solved by an appropriately programmed Turing machine (given sufficient time and tape). This assertion — the Church-Turing thesis — is not a mathematical theorem but a hypothesis supported by the convergence of multiple independent formalisms: Turing machines (Turing 1936), lambda calculus (Alonzo Church 1936), general recursive functions (Gödel-Herbrand-Kleene), and Post machines (Emil Post 1936) all define exactly the same class of computable functions. No physical process, computing device, or algorithm has ever been shown to compute a function that a Turing machine cannot — this universality is one of the most remarkable facts in science. The Universal Turing Machine — a Turing machine that can simulate any other Turing machine given its description as input — is the theoretical ancestor of the stored-program computer: it separates the machine (hardware) from the program (software), demonstrating that a single machine can perform any computable task by changing its program. Turing's most profound result was proving that certain problems are undecidable — no algorithm can solve them for all possible inputs. The Halting Problem is the canonical example: given the description of a Turing machine $M$ and an input $w$, determine whether $M$ halts (produces an answer) on $w$ or runs forever. Turing proved (by a diagonal/self-referential argument) that no Turing machine can solve the Halting Problem for all possible $(M, w)$ pairs — the problem is undecidable. This result is closely related to Gödel's Incompleteness Theorems (1931): Gödel showed that any consistent formal system powerful enough to express arithmetic contains true statements that cannot be proved within the system (First Incompleteness Theorem), and that such a system cannot prove its own consistency (Second Incompleteness Theorem). Turing's undecidability and Gödel's incompleteness are different manifestations of the same fundamental limitation: self-referential systems hit barriers that cannot be overcome within the system. The implications are profound: there is no universal algorithm for determining mathematical truth; there is no algorithm that can verify whether an arbitrary program is bug-free; certain optimization, tiling, and logical problems are provably unsolvable in general. Yet Turing's framework also establishes the positive boundary of computation: the class of computable functions is rich, robust (invariant across formalizations), and captures an enormous range of practical and mathematical problems. The study of the structure within undecidability — degrees of unsolvability, the arithmetical hierarchy, oracle machines, relative computability — constitutes the field of recursion theory (computability theory), one of the pillars of mathematical logic.

1. VERIFIED CLAIMS (Tier 1 — Mathematical / Peer-Reviewed / Foundational)

1.1 Turing's 1936 Paper

• Turing (1936, Proceedings of the London Mathematical Society): "On Computable Numbers, with an Application to the Entscheidungsproblem" — defined the Turing machine formalism; proved the existence of a universal Turing machine; proved the unsolvability of the Entscheidungsproblem (the decision problem: is there an algorithm that can determine, for any statement in first-order logic, whether it is provable?) by reducing it to the Halting Problem; this paper is one of the most important in the history of mathematics and computer science
• The paper was submitted in May 1936, weeks after Church published his own proof of the undecidability of the Entscheidungsproblem using lambda calculus — the two approaches were quickly shown to be equivalent

1.2 Church-Turing Thesis

• The thesis: every function that can be computed by any "effective procedure" (any mechanical, step-by-step, finitely describable method) is computable by a Turing machine — this is an empirical hypothesis, not a proven theorem, but it has never been refuted
• The remarkable convergence of Turing machines, lambda calculus, general recursive functions, Post machines, Markov algorithms, and many other formalisms all defining the same class of computable functions provides overwhelmingly strong evidence for the thesis
• The extended Church-Turing thesis (sometimes called the "strong" thesis) adds that Turing machines can simulate any physical computation with at most polynomial overhead — this stronger claim is challenged by quantum computing (see Tier 2)

1.3 The Halting Problem and Undecidability

• Proof of undecidability: by contradiction — assume a Turing machine $H$ exists that decides, for any machine $M$ and input $w$, whether $M$ halts on $w$. Construct a machine $D$ that, given $M$, runs $H(M, M)$ and does the opposite: if $H$ says $M$ halts on $M$, $D$ loops forever; if $H$ says $M$ loops on $M$, $D$ halts. Running $D$ on its own description $D$ yields a contradiction: $D(D)$ halts iff $D(D)$ does not halt. Therefore $H$ cannot exist.
• This is the computational analog of the liar paradox and of Gödel's diagonal construction — self-reference generates undecidability

2. CREDIBLE CLAIMS (Tier 2 — Academic / Debated but Well-Supported)

2.1 Quantum Computing and the Extended Church-Turing Thesis

• Quantum computers (Deutsch 1985, Shor 1994) can solve certain problems exponentially faster than any known classical algorithm (integer factoring, discrete logarithm) — if quantum speedup is genuine (as all evidence suggests), the extended Church-Turing thesis (polynomial equivalence) is false
• However, quantum computers do not compute any function that a classical Turing machine cannot — they compute the same functions, just faster for some problems; the basic Church-Turing thesis (same class of computable functions) is not affected

2.2 Hypercomputation

• Hypercomputation — the proposal that physical systems might compute functions beyond the Turing-computable (e.g., through infinite-precision real-number computation, relativistic spacetime computation, or exotic physical processes) — has been proposed by Copeland, Siegelmann, and others; mainstream computer science considers hypercomputation speculative and unsupported by physical evidence — no physical process has been demonstrated to compute a non-Turing-computable function

3. SPECULATIVE CLAIMS (Tier 3 — Possible but Unverified)

3.1 Human Minds as Super-Turing Systems

• Penrose (1989, The Emperor's New Mind): argued that Gödel's incompleteness theorems show that human mathematical understanding cannot be replicated by any algorithmic process — humans can "see" the truth of Gödel sentences that no formal system can prove; therefore human cognition involves non-algorithmic processes (Penrose proposed quantum gravity effects in microtubules — see Orchestrated Objective Reduction). Most logicians and AI researchers reject Penrose's argument (Feferman 1995, Hofstadter, Dennett) — the inference from "no single formal system captures all mathematical truth" to "the mind is not a formal system" involves questionable assumptions

4. DUBIOUS CLAIMS (Tier 4 — No Credible Source / Contradicted by Evidence)

4.1 Computers Can Solve Any Problem

• [FALSE] The common misconception that given enough time and memory, a computer can solve any well-defined problem — Turing's 1936 result proved that some well-defined problems (the Halting Problem, and infinitely many others) are provably unsolvable by any computer, regardless of time or memory

COUNTER-ARGUMENTS

• Hypercomputation debate: Whether physical processes can exceed Turing-computability remains contested. Martin Davis (2004, 2006) argued that all proposed hypercomputation models (Malament-Hogarth spacetimes, analog neural networks, quantum computation) either involve physically unrealizable idealizations or conflate precision with computability. Proponents like Toby Ord and Tien Kieu have argued that quantum mechanics or relativistic spacetimes might permit super-Turing computation, though no experimental realization exists
• Penrose's non-computable mind: Roger Penrose (The Emperor's New Mind, 1989; Shadows of the Mind, 1994) argued via a Gödelian argument that human mathematical understanding is non-computable, implying consciousness involves processes beyond Turing machines. This has been challenged by Solomon Feferman, Stewart Shapiro, and Hilary Putnam, who argued that Penrose's Gödelian argument contains a fallacy — it assumes mathematicians are consistent, which cannot be known from the inside
• Church-Turing thesis scope: The original Church-Turing thesis concerns effective calculability, not physical computability. Gualtiero Piccinini and Oron Shagrir have emphasized that extending it to a physical thesis (the universe cannot compute beyond Turing limits) is an empirical claim, not a mathematical theorem, and remains open

IMAGES

No images assigned yet.

BIBLIOGRAPHY

1. Turing, A.M. s2-. [submitted 1936] | 1937 | "On Computable Numbers, with an Application to the Entscheidungsproblem" | Proceedings of the London Mathematical Society | ∅ | 42.1::230–265 | ∅ | ∅ | doi:10.1112/plms/s2-42.1.230 | ∅ | ∅ | ∅
2. Church, A | 1936 | "An Unsolvable Problem of Elementary Number Theory" | American Journal of Mathematics | ∅ | 58.2::345–363 | ∅ | ∅ | doi:10.2307/2371045 | ∅ | ∅ | ∅
3. Gödel, K | 1931 | "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I" | Monatshefte für Mathematik und Physik | ∅ | 38::173–198 | ∅ | ∅ | doi:10.1007/bf01700692 | ∅ | ∅ | ∅
4. Davis, M | 1958 | ∅ | Computability and Unsolvability | ∅ | ∅ | New York: McGraw-Hill | ∅ | doi:10.2307/2964019 | ∅ | ∅ | Reprint: Dover, 1982
5. Sipser, M. | 2013 | ∅ | Introduction to the Theory of Computation | ∅ | ∅ | Boston: Cengage Learning | 3rd | isbn:9781133187790 | ∅ | ∅ | ∅
6. Hodges, A | 2014 | ∅ | Alan Turing: The Enigma | ∅ | ∅ | Princeton, NJ: Princeton University Press | ∅ | ∅ | ∅ | ∅ | ∅
7. Copeland, B.J (ed.) | 2004 | ∅ | The Essential Turing | ∅ | ∅ | Oxford: Oxford University Press | ∅ | isbn:9780198250807 | ∅ | ∅ | ∅
8. Post, E.L | 1936 | "Finite Combinatory Processes — Formulation 1" | Journal of Symbolic Logic | ∅ | 1.3::103–105 | ∅ | ∅ | ∅ | ∅ | ∅ | ∅
9. Rogers, H | 1967 | ∅ | Theory of Recursive Functions and Effective Computability | ∅ | ∅ | New York: McGraw-Hill | ∅ | ∅ | ∅ | ∅ | Reprint: MIT Press, 1987
10. Soare, R.I | 2016 | ∅ | Turing Computability: Theory and Applications | ∅ | ∅ | Berlin: Springer | ∅ | ∅ | ∅ | ∅ | ∅
11. Penrose, R | 1989 | ∅ | The Emperor's New Mind: Concerning Computers, Minds, and the Laws of Physics | ∅ | ∅ | Oxford: Oxford University Press | ∅ | ∅ | ∅ | ∅ | ∅
12. Deutsch, D | 1985 | "Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer" | Proceedings of the Royal Society A | ∅ | 400.1818::97–117 | ∅ | ∅ | doi:10.1098/rspa.1985.0070 | ∅ | ∅ | ∅
13. Feferman, S | 1995 | "Penrose's Gödelian Argument" | Psyche | ∅ | 2.7::21–32 | ∅ | ∅ | ∅ | ∅ | ∅ | ∅

CROSS-REFERENCE INDEX

No cross-references yet.