Turing machine
In plain wordsAn imaginary, extremely simple computer — a read-write head moving along an endless tape — that Alan Turing used in 1936 to define exactly what can be computed at all.
An idealized computer consisting only of finitely many control states and a read–write head on an endless strip of symbol squares; a fixed rulebook says, for each pairing of state and scanned symbol, which symbol to leave, which way to step and which state to adopt. It can simulate every known model of algorithmic computation, and the Church–Turing thesis holds that it captures exactly what is effectively computable. A universal Turing machine simulates any other machine from a description on its tape — the theoretical template of the stored-program computer. Turing used the model to prove some problems undecidable, most famously what was later named the halting problem: no machine can decide, for every program and input, whether it will eventually stop. A system that can simulate any Turing machine is 'Turing-complete'. In AI it anchors debates about the limits of computation and of minds, underlies Kolmogorov complexityKolmogorov complexity, n.: How briefly something can be described by a computer program that recreates it exactly: a million zeros needs only a tiny program, while a truly random string needs one about as long as itself. and Solomonoff inductionSolomonoff induction, n.: A mathematical recipe for ideal prediction: consider every computer program that could have produced the data so far, trust shorter programs more, and predict what they would output next., and frames studies of what transformers can compute, which are Turing-complete only under idealized assumptions such as unbounded precision or unlimited chain of thoughtchain of thought, n.: Getting an AI to write out its reasoning step by step before giving an answer, the way a student shows their working. This often makes answers to math and logic problems more accurate. steps.
With an external scratchpad and unbounded steps the system is Turing-complete in principle; in practice the context window limits it.
Origin
Described by Alan Turing in 'On Computable Numbers, with an Application to the Entscheidungsproblem', submitted in 1936 and published in the Proceedings of the London Mathematical Society (volume 42, 1936–37); he called it an 'a-machine' (automatic machine). Alonzo Church, whose lambda calculus proved equivalent, coined 'Turing machine' in his 1937 review of the paper in the Journal of Symbolic Logic. Turing never used the word 'halting'; Martin Davis introduced 'halting problem' in lectures in 1952.
Related
- Kolmogorov complexityKolmogorov complexity, n.: How briefly something can be described by a computer program that recreates it exactly: a million zeros needs only a tiny program, while a truly random string needs one about as long as itself.
- Solomonoff inductionSolomonoff induction, n.: A mathematical recipe for ideal prediction: consider every computer program that could have produced the data so far, trust shorter programs more, and predict what they would output next.
- big O notationbig O notation, n.: Shorthand for how the cost of a computation grows as the problem gets bigger. Saying attention costs 'O(n²)' means doubling the length of the text roughly quadruples the work.
- Computing Machinery and IntelligenceComputing Machinery and Intelligence, prop. n.: Alan Turing's 1950 essay asking whether machines can think. It proposed a conversation test in place of that question, answered objections to thinking machines and suggested that machines might learn like children.
- chain of thoughtchain of thought, n.: Getting an AI to write out its reasoning step by step before giving an answer, the way a student shows their working. This often makes answers to math and logic problems more accurate.
- computational theory of mindcomputational theory of mind, n.: The idea that thinking is a kind of computation: the mind processes information by following rules, much as a computer runs a program, and the brain is the machine doing it.
Sources
- Turing, A. M. (1936–37). On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, s2-42.
Mentioned in
big O notationbig O notation, n.: Shorthand for how the cost of a computation grows as the problem gets bigger. Saying attention costs 'O(n²)' means doubling the length of the text roughly quadruples the work., Gödel's incompleteness theoremsGödel's incompleteness theorems, n.: Two famous results from 1931 showing that any consistent set of rules for doing arithmetic leaves some true statements unprovable, and cannot prove that it is itself free of contradictions., Kolmogorov complexityKolmogorov complexity, n.: How briefly something can be described by a computer program that recreates it exactly: a million zeros needs only a tiny program, while a truly random string needs one about as long as itself., Solomonoff inductionSolomonoff induction, n.: A mathematical recipe for ideal prediction: consider every computer program that could have produced the data so far, trust shorter programs more, and predict what they would output next.