Turing machine

A Turing machine is a model of computation with finite control, a tape of cells and a head scanning one cell at a time. An instruction of a Turing machine uses the current state and scanned symbol to determine a new state, a written symbol and a head movement. The finite transition rules form the machine's description; the tape supplies storage without a fixed global bound.

In a standard input convention, a finite word occupies part of an otherwise blank tape. A Turing machine configuration records the state, head position and tape contents, so the next-configuration relation determines each computation step. A machine can accept, reject or continue indefinitely. Recognizing a formal language permits nontermination on some nonmembers; deciding it requires an answer on every input.

The separation between a finite rule table and unbounded reusable storage makes the model useful for proving general statements about algorithms. Alan Turing's 1936 paper introduced this style of machine to analyze effective calculation; its original examples produce successive digits of numbers.^[ref] Multitape Turing machines change the storage organization and possible step counts while retaining the same computability power.

An oracle Turing machine is a Turing machine with an additional query operation for a fixed formal language $A$. It writes a finite query $x$ on a designated tape and receives the membership answer $x\in A$ in one oracle step. Writing the query still takes ordinary machine work. The oracle's internal solution procedure is excluded from the cost model.

For example, a machine with an oracle for Boolean satisfiability can ask whether a given Boolean formula has a satisfying assignment. By fixing variables one at a time and querying satisfiability again, it can recover an assignment with at most one additional query per variable. The example turns decision access into search access; it does not provide an ordinary fast satisfiability solver. Oracles let computability theory and computational complexity theory compare problems while making the granted information explicit.^[ref]

A designated tape alphabet symbol occupying unused cells of a Turing machine. It is excluded from the input alphabet, so a finite input word occupies a finite region of an otherwise blank tape.

A finite string describing a Turing machine's states, alphabets, transition rules and designated initial and halting states. Standard encodings have a decidable language of valid descriptions. A syntactic property of an encoding need not be an extensional property of programs; for example, adding an unreachable state changes state count without changing the accepted formal language.

A Turing machine with a fixed finite number of tapes and a head for each tape. One transition reads the scanned symbols, updates them and moves the heads. This model accepts the same computably enumerable languages as a single-tape Turing machine, but step counts can differ.

A Turing machine with one read-write tape. Every multitape Turing machine can be simulated by a single-tape Turing machine, using delimited tape portions and marked head positions. The simulation preserves the accepted formal language and whether a computation halts, while possibly increasing time complexity.

A deterministic single-tape Turing machine that leaves every scanned symbol unchanged and moves one cell right after every nonhalting transition. Such machines decide exactly the regular languages. A deterministic finite automaton simulates the finite control, with accepting states determined by the blank-only continuation after the input; conversely, a machine simulating a deterministic finite automaton halts on the first blank.

An instantaneous description records the current control state, head position, and tape contents. For a tape blank outside a finite window, a word $huqvh$ records the symbols $u$ to the left of the head and $v$ from the scanned cell rightward, with unrecorded cells blank. If $v$ is empty, the head scans an implicit blank. Extra outer blanks can represent the same infinite tape. The instruction of a Turing machine determines its successor description.

For a Turing machine, the one-step binary relation between Turing machine configurations specified by its Turing machine instructions. Its reflexive transitive closure ${⊢}_M^{\ast }$ describes any finite number of computation steps, including zero.

For a deterministic single-tape Turing machine, an instruction reads a state $q$ and scanned tape symbol $a$, writes $b$, changes state to $p$, and moves the head one cell left, one cell right, or not at all according to $D$. The state and tape alphabets are finite; an undefined transition halts. A dedicated terminal state can be introduced by directing undefined transitions to it without changing whether computation halts.

Encode the cells immediately left of the head in a reversed positional stack $L$, and the current and right cells in $R$. Quotient and remainder by the alphabet base read and remove cells; multiplication by that base pushes a cell. The resulting local tape transitions are primitive recursive, which makes them directly implementable on Church numerals.

A modular machine of modulus $m>1$ acts on pairs in ${\mathbb{N}}^2$. Each instruction $(a,b,c,R)$ or $(a,b,c,L)$ has $0\le a,b<m$ and $0\le c<m^2$, and at most one instruction is assigned to each residue pair $(a,b)$. The two transition types are $(mu+a,mv+b)\mapsto (m^{2}u+c,v)$ and $(mu+a,mv+b)\mapsto (u,m^{2}v+c)$. These finite arithmetic operations can encode a Turing machine; a designated terminal configuration can have a nonrecursive halting set.

A modular machine can be encoded by HNN extensions of $K={\mathbb{Z}}^2\ast ⟨t⟩$. The kernel of $K\to {\mathbb{Z}}^2$ has a free basis of a group $t(r,s)=x^{-r}{y}^{-s}t{x}^r{y}^s$. Associated-subgroup maps send these basis elements according to the two arithmetic transition types. In the resulting group, membership of $t(r,s)$ in the subgroup generated by $t$ and the instruction stable letters is equivalent to $(r,s)\in H_0(\mathcal{M})$. One more HNN extension centralizes that finitely generated subgroup, converting membership to equality and hence to the word problem for a group.

For a modular machine whose $(0,0)$ is terminal, $H_0(\mathcal{M})$ is the set of configurations whose forward computation reaches exactly $(0,0)$, including the zero-step computation there. It may differ from the set of configurations stopping at any terminal configuration. Determinism makes membership invariant along each instruction edge.

In a deterministic computation, every configuration and input symbol determine at most one next configuration.

A reversible computation has an injective transition function, so its preceding configuration can be recovered from its current configuration. Any finite classical computation can be simulated reversibly while retaining enough workspace to uncompute its temporary results.

A reversible circuit is composed of bijective gates. The Toffoli gate is universal for reversible Boolean computation when ancillary bits are available.

A nondeterministic computation may have several possible next configurations and accepts when at least one computation path accepts.

An oracle machine may query membership in a fixed language in one computation step.

A function oracle supplies access to an unknown function $f$: given an allowed input $x$, one query returns $f(x)$. Query complexity counts these accesses separately from known local computation. A classical query receives one definite answer; a quantum oracle specifies coherent access through a unitary operator, allowing inputs in quantum superposition. The distinction is part of the access model, not a change to the mathematical function.

A Boolean quantum oracle preserves $x$ and adds a one-bit value $f(x)$ into an answer qubit by exclusive or. On known computational-basis states, its output determines the same value as a classical function oracle query.

A relativized complexity class ${\mathcal{C}}^A$ allows every machine defining $\mathcal{C}$ to query the same oracle $A$.