Turing Machine
A theoretical model of computation used to define the limits of what can be calculated.
A Turing machine is a theoretical model of computation that defines an abstract machine capable of performing any computation that can be carried out by any algorithm. Proposed by Alan Turing in 1936, it consists of a finite sequence of states, a tape divided into cells (each capable of holding a symbol), a head that can read, write, and move along the tape, and a set of transition rules. The machine operates by reading the symbol under the head, consulting its current state and the transition rules, and then performing actions: writing a symbol onto the tape, moving the head one cell left or right, and changing to a new state. The machine halts when it reaches a state for which no transition rule is defined for the current symbol. The Church-Turing thesis posits that any function computable by an algorithm can be computed by a Turing machine. This theoretical construct is fundamental to the theory of computation, computability, and complexity theory, providing a formal definition of what it means for a problem to be solvable by a computer. Despite its simplicity, it can simulate the logic of any computer algorithm.
graph LR
Center["Turing Machine"]:::main
Pre_computer_science["computer-science"]:::pre --> Center
click Pre_computer_science "/terms/computer-science"
Rel_antimatter_propulsion["antimatter-propulsion"]:::related -.-> Center
click Rel_antimatter_propulsion "/terms/antimatter-propulsion"
Rel_arpanet["arpanet"]:::related -.-> Center
click Rel_arpanet "/terms/arpanet"
Rel_artificial_consciousness["artificial-consciousness"]:::related -.-> Center
click Rel_artificial_consciousness "/terms/artificial-consciousness"
classDef main fill:#7c3aed,stroke:#8b5cf6,stroke-width:2px,color:white,font-weight:bold,rx:5,ry:5;
classDef pre fill:#0f172a,stroke:#3b82f6,color:#94a3b8,rx:5,ry:5;
classDef child fill:#0f172a,stroke:#10b981,color:#94a3b8,rx:5,ry:5;
classDef related fill:#0f172a,stroke:#8b5cf6,stroke-dasharray: 5 5,color:#94a3b8,rx:5,ry:5;
linkStyle default stroke:#4b5563,stroke-width:2px;
🧒 Explain Like I'm 5
It's like a super simple robot with a very long paper strip (tape) and a pencil; it follows a list of instructions to read, write, and move on the strip, and can do any calculation a real computer can.
🤓 Expert Deep Dive
The formal definition of a Turing machine $M = (Q, \Sigma, \Gamma, \delta, q_0, B, F)$ involves a set of states $Q$, an input alphabet $\Sigma$, a tape alphabet $\Gamma$ (where $\Sigma \subseteq \Gamma$ and $B \in \Gamma \setminus \Sigma$ is the blank symbol), a transition function $\delta: Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$, a start state $q_0 \in Q$, the blank symbol $B$, and a set of final/accepting states $F \subseteq Q$. The transition function dictates the machine's behavior: given the current state and the symbol read, it determines the next state, the symbol to write, and the direction to move the head (L for left, R for right). Undecidable problems, such as the Halting Problem, are formally proven to be unsolvable by any Turing machine, establishing the theoretical limits of computation. Variants like multi-tape Turing machines or non-deterministic Turing machines have equivalent computational power (can compute the same set of functions) but differ in efficiency or operational characteristics, forming the basis for complexity classes like P and NP.