Turing machine
Theoretical computing model
A Turing machine is an abstract mathematical model of computation, consisting of an infinite tape divided into cells, a head that reads and writes symbols, and a set of rules governing its behavior.
Proposed by Alan Turing in 1936, it formalizes what it means for a function to be computable.
Despite its simplicity, a Turing machine can simulate any algorithm, making it foundational to computer science and the theory of computability: The problem is undecidable—no Turing machine can solve it.
- computabilityAlgorithmic solvability of problems
- decidabilityAlgorithmic resolution capability
- imitation gameMachine intelligence assessment
- computerElectronic calculating device
- Chomsky hierarchyClassification of formal grammars
algorithm · universal · context-free grammar · rule · symbolic logic · tape · processor · recursion · mechanical · deterministic · proof · Church · mathematics · theoretical · head · states · binary · halting
- Computer Sciencealgorithm, binary, boolean, recursion, iteration
- Computing HistoryENIAC, UNIVAC, mainframe, mainframes, punch card
- automataNFA, PDA, transducer, acceptor, recognizer
- Computabilitycomputability, decidability, completeness
- computation modelsautomata, transducer, acceptor, recognizer
- state spacesground state, excited state, quantum state, mixed state, superposition
Turing machinesilicon chip
Integrated circuit on semiconductor
CPU · microprocessor · digital computer · analog computer · laptop