Turing machine

A Turing machine is an abstract computational model with a finite control, an unbounded tape and a head that reads, writes and moves on the tape.

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 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 relativized complexity class ${\mathcal{C}}^A$ allows every machine defining $\mathcal{C}$ to query the same oracle $A$.