1 Formal definition
A Turing machine is formally defined as a mathematical model consisting of a finite set of states, an infinite tape divided into cells, a tape head, and a transition function. The definition provides an unambiguous description of the machine's operation, allowing for rigorous analysis of computation.
1.1 Components
The machine is built from four primary components that together determine its behavior.
1.1.1 Tape
The tape is an infinite linear sequence of cells, each capable of storing exactly one symbol from a finite alphabet. The alphabet includes a special blank symbol (often denoted as ␣ or B), which indicates an empty cell. The tape extends indefinitely in both directions, though at any given time only a finite portion contains nonblank symbols.
1.1.2 Head
The tape head is a read–write mechanism that can move left or right along the tape, one cell at a time. At each step, it reads the symbol in the current cell and, based on the machine's current state, either writes a new symbol over the current one or leaves it unchanged. The head then moves to an adjacent cell as directed by the transition function.
1.1.3 State register
The state register holds the current state of the machine. The set of states is finite, with a distinguished initial state (or start state). Some states are designated as halting (or accepting/rejecting) states; when the machine enters a halting state, computation ceases.
1.1.4 Transition function
The transition function is a mapping that takes the current state and the symbol read from the tape and produces a triple: the next state, the symbol to write, and a direction (left or right). This function defines all possible moves of the machine. In a deterministic Turing machine, the mapping is a function; in a nondeterministic variant, it is a relation.
1.2 Formal notation
To allow precise mathematical reasoning, Turing machines are often expressed in a compact notation.
1.2.1 7-tuple representation
A deterministic Turing machine can be formalized as a 7‑tuple (Q, Σ, Γ, δ, q₀, B, F), where:
- Q is a finite set of states.
- Σ is a finite input alphabet (does not contain the blank symbol).
- Γ is a finite tape alphabet (Σ ⊆ Γ, and the blank symbol B ∈ Γ \ Σ).
- δ: Q × Γ → Q × Γ × {L, R} is the transition function.
- q₀ ∈ Q is the initial state.
- B ∈ Γ is the blank symbol.
- F ⊆ Q is the set of halting (final) states.
1.2.2 Example transition table
A simple machine that increments a unary number (represented by repeated 1s) might have the following transition table:
| State | Symbol | Write | Move | Next state | |
|---|---|---|---|---|---|
| q0 | 1 | 1 | R | q0 | |
| q0 | B | 1 | L | q1 | |
| q1 | 1 | 1 | L | q1 | |
| q1 | B | B | R | q2 |
This table shows that from state q0, on reading a 1 the head moves right; on reaching a blank it writes a 1, moves left, and goes to q1; then moves left until a blank, then halts in q2.
2 Operational semantics
The operational semantics describes how the machine evolves step by step from an initial configuration to a halting configuration.
2.1 Step-by-step execution
A configuration of a Turing machine is a triple (current state, tape contents, head position). Starting from the initial configuration (with the tape containing the input, the head at the leftmost input symbol, and the machine in the start state), the machine repeatedly applies the transition function. Each application updates the state, writes a symbol, and moves the head. This process continues until a halting state is reached, or indefinitely if the machine never halts.
2.2 Halting and acceptance
The machine halts when it enters a state from the set F. In decision problems, halting in an accepting state (e.g., a designated “yes” state) indicates acceptance; halting in a rejecting state indicates rejection. Some formulations treat all halting states uniformly, while others distinguish between accept and reject states.
2.3 Computing a function
To compute a function f: Σ* → Σ* (or a partial function), the machine is started with the input written on the tape. If it eventually halts, the contents of the tape (often a designated portion) are taken as the output. The machine is said to compute f if for every input in the domain of f, it halts with the correct output, and for inputs outside the domain, it does not halt (or halts in a rejecting state).
2.4 Decision problems
A decision problem is a yes–no question about inputs. A Turing machine decides a language L if, for every input string over the alphabet, it halts and accepts if the string belongs to L, and halts and rejects otherwise. Languages that can be decided by some Turing machine are called recursive (or decidable). Those that can only be recognized (the machine halts on acceptance but may loop on rejection) are recursively enumerable (or semidecidable).
3 Variants and extensions
Several modifications to the basic model have been studied, often to capture different aspects of computation or to prove equivalence results.
3.1 Multitape Turing machine
A multitape Turing machine has several tapes, each with its own independent head. The transition function now depends on the states and the symbols read from all tapes and can write symbols on each tape and move each head independently. Every multitape machine can be simulated by a single‑tape machine with at most a quadratic slowdown, so they are computationally equivalent to the basic model.
3.2 Nondeterministic Turing machine
A nondeterministic Turing machine allows the transition function to give multiple possible moves for a given state‑symbol pair. The machine is said to accept an input if there exists some sequence of choices that leads to an accepting configuration. Nondeterministic machines are not more powerful than deterministic ones in terms of what functions they can compute (they both define the same set of recursively enumerable languages), but they may solve certain problems much faster in terms of time complexity.
3.3 Oracle machine
An oracle machine is a Turing machine with an additional “oracle tape” and a special state that allows it to query an external set (the oracle). The machine writes a query on the oracle tape and enters a query state; in one step the oracle answers whether the query belongs to the set.
3.3.1 Definition and usage
Formally, an oracle machine is a Turing machine with an extra tape and a designated query state. When the machine enters the query state, the oracle tape’s contents are considered as a question; the next state is either a “yes” state or a “no” state, depending on whether the string is in the oracle set. This allows the study of relative computability.
3.3.2 Relationship to Turing degrees
Oracle machines give rise to the concept of Turing reducibility: a set A is Turing reducible to a set B if an oracle machine with oracle B can decide A. The equivalence classes of sets under this reducibility are called Turing degrees, which form a rich mathematical structure.
3.4 Universal Turing machine
A universal Turing machine (UTM) is a single Turing machine that can simulate any other Turing machine given a description of that machine on its tape. It embodies the idea of a stored‑program computer.
3.4.1 Construction
The construction involves encoding the transition table and initial tape contents of an arbitrary machine M onto the tape of the UTM. The UTM then interprets the encoding step by step, updating its own tape to mimic M’s computation. Alan Turing described such a machine in his 1936 paper, proving that a single fixed machine can perform any computation that any Turing machine can perform.
3.4.2 Stored-program concept
The universal Turing machine is a theoretical precursor to the stored‑program concept used in modern computers, where both data and instructions are stored in the same memory. This idea was later adopted by von Neumann architecture.
4 Computability and limitations
The Turing machine model provides a precise way to discuss what can and cannot be computed.
4.1 Church–Turing thesis
The Church–Turing thesis states that any function that can be computed by an effective (mechanical) procedure can be computed by a Turing machine. This is not a theorem but a widely accepted hypothesis, because all known models of computation—lambda calculus, general recursive functions, register machines—have been shown to be equivalent to the Turing machine.
4.2 Undecidable problems
An undecidable problem is a decision problem for which no Turing machine exists that always halts with the correct answer. Such problems lie beyond the reach of algorithmic solution.
4.2.1 Halting problem
The halting problem asks whether a given Turing machine will eventually halt when started on a particular input. Alan Turing proved in 1936 that no Turing machine can solve this problem for all possible inputs. This is the classic example of an undecidable problem.
4.2.2 Rice's theorem
Rice's theorem generalizes the undecidability of the halting problem: any non‑trivial property of the partial function computed by a Turing machine is undecidable. “Non‑trivial” means the property is neither always true nor always false for all computable functions. For example, it is undecidable whether a machine computes a constant function or whether it ever outputs a specific symbol.
4.3 Turing completeness
A system is called Turing complete if it can simulate a universal Turing machine. This means that, given enough memory and time, the system can compute anything that is computable.
4.3.1 Equivalent models
Many formal systems and programming languages have been proven Turing complete: the lambda calculus, the untyped lambda calculus with combinators, cellular automata (e.g., Conway's Game of Life), the Brainfuck programming language, and most modern general‑purpose programming languages.
4.3.2 Minimal Turing machines
Researchers seek the smallest possible universal Turing machine in terms of number of states and symbols. The smallest known universal machines have, for example, two states and three symbols, or one state and many symbols. These results are of theoretical interest and often rely on intricate encodings.
5 Historical development
The Turing machine emerged from foundational work in mathematical logic during the early 20th century.
5.1 Alan Turing's 1936 paper
In his paper “On Computable Numbers, with an Application to the Entscheidungsproblem” (1936), Alan Turing introduced the concept of a computing machine to solve Hilbert’s Entscheidungsproblem (decision problem). He showed that there is no general algorithm to decide whether a given mathematical statement is provable, by reducing it to the undecidability of the halting problem.
5.2 Influence on early computers
Turing’s theoretical model influenced the design of early electronic computers. The idea of a stored‑program machine, derived from the universal Turing machine, was central to the EDVAC and other early designs. Turing himself worked on practical computing machines, such as the Automatic Computing Engine (ACE) at the National Physical Laboratory.
5.3 Subsequent refinements
After Turing, mathematicians and computer scientists refined the model: formal 7‑tuple definitions, multitape variants, nondeterministic versions, and oracle machines were introduced. The theory of computational complexity (e.g., time and space hierarchies) built directly on the Turing machine as a reference model.
6 Applications in modern theory
The Turing machine remains a fundamental tool in theoretical computer science.
6.1 Complexity theory
Complexity classes such as P, NP, PSPACE, and EXPTIME are defined using Turing machines with resource bounds (time or space). The famous P vs. NP problem asks whether every problem whose solution can be checked quickly (in polynomial time) can also be solved quickly in the deterministic Turing machine model.
6.2 Programming language semantics
The semantics of programming languages are often described in terms of an abstract machine; the Turing machine provides a baseline for proving that a language can compute all computable functions (i.e., it is Turing complete). Operational semantics, denotational semantics, and abstract state machines all connect to the Turing machine model.
6.3 Artificial intelligence
In AI, Turing’s 1950 paper “Computing Machinery and Intelligence” introduced the Turing test, which is distinct from the Turing machine but rooted in the same concept of symbolic computation. The Turing machine also underlies the theoretical limits of AI: for example, no algorithm can decide in general whether a machine exhibits true understanding (a variant of the halting problem).
7 Pedagogical and cultural impact
The Turing machine is a staple of computer science education and has entered popular culture.
7.1 Use in textbooks
Nearly every introductory textbook on theory of computation presents the Turing machine as the canonical model of computation. It is used to teach topics such as decidability, reducibility, and the Church–Turing thesis. Many exercises ask students to design simple Turing machines for tasks like addition, multiplication, or string reversal.
7.2 Turing machine simulators
Several software simulators allow users to define and run Turing machines interactively. These tools are used in classrooms to demonstrate how even a simple set of rules can perform complex computations. Online simulators and programming challenges (e.g., Turing machine game) have made the concept accessible to hobbyists.
7.3 In popular culture
The Turing machine has appeared in films, novels, and puzzles. For instance, the concept of a “universal machine” inspired the fictional “Universal Turing Machine” in the television series *The Big Bang Theory*. It also features in science fiction as a metaphor for any system that can simulate arbitrary processes. Alan Turing’s life and work, including the Turing machine, were dramatized in the film *The Imitation Game* (2014).