Let \(M\) be a finite-state binary-alphabet Turing machine and \(M^{\mathrm{acc}}\) its halting recognizer, a machine with a distinguished loop state \(\ell \) in which it moves no head, writes and emits nothing, and remains in \(\ell \). For every input \(x\), every configuration \(C\) of \(M^{\mathrm{acc}}\) on \(x\) whose state is \(\ell \), and every \(t \in \mathbb {N}\), running \(M^{\mathrm{acc}}\) for \(t\) steps from \(C\) yields \(C\) itself; in particular it never halts.

Let \(M\) be a finite-state binary-alphabet Turing machine with state set \(Q\), \(x\) an input, \(C\) a configuration of \(M\) on \(x\), and \(a\) an action of \(M\). Let \(b\) be the last bit on \(C\)’s output tape (\(0\) if empty), and let \(\Phi (C)\) be the recognizer configuration with \(C\)’s head positions and tape contents, empty output, and state \(\mathrm{enc}(s,b)\), where \(s\) is \(C\)’s state and \(\mathrm{enc}(s,b) = (s,b)\) for \(s \in Q\), halt for a halted \(s\) with \(b=1\), and a loop state for a halted \(s\) with \(b=0\). Then applying to \(\Phi (C)\) the action with \(a\)’s head moves and writes, no output, and successor state \(\mathrm{enc}(s', b')\) (\(s'\) the successor of \(a\), \(b'\) the bit \(a\) emits, or \(b\) if none) gives exactly \(\Phi (a(C))\), where \(a(C)\) is the result of applying \(a\) to \(C\).

Let \(M\) be a finite-state binary-alphabet Turing machine with state set \(Q\), and let \(M^{\mathrm{acc}}\) be its halting recognizer: same work tapes, states \((q,b) \in Q \times \{ 0,1\} \) plus a stationary loop state \(\ell \), simulating \(M\) with output suppressed and the last emitted bit recorded, halting where \(M\) halts with recorded bit \(1\) and entering \(\ell \) where it halts with bit \(0\). For a configuration \(C\) of \(M\) on an input \(x\), let \(\Phi (C)\) be the configuration of \(M^{\mathrm{acc}}\) with \(C\)’s head positions and work-tape contents, empty output, and state \((q,b)\), halted, or \(\ell \) according as \(C\) is in state \(q\), halted with last output bit \(1\), or halted with last output bit \(0\) (the bit \(b\) being the last output bit, \(0\) if none). Then for every such \(C\), one step of \(M^{\mathrm{acc}}\) from \(\Phi (C)\) yields \(\Phi (C')\), where \(C'\) is the result of one step of \(M\) from \(C\) (a halted configuration stepping to itself).

Let \(M\) be a finite-state binary-alphabet Turing machine with state set \(Q\), and let \(M^{\mathrm{acc}}\) be its halting recognizer: same work tapes, states \((q,b) \in Q \times \{ 0,1\} \) plus a stationary loop state \(\ell \), start state \((q_0, 0)\), simulating \(M\) with output suppressed and the last emitted bit recorded, halting where \(M\) halts with recorded bit \(1\) and entering \(\ell \) where it halts with bit \(0\). For every input \(x\) and every \(t \in \mathbb {N}\), the configuration of \(M^{\mathrm{acc}}\) after \(t\) steps on \(x\) has the same head positions and work-tape contents as the configuration \(C_t\) of \(M\) after \(t\) steps on \(x\), an empty output tape, and state \((q,b)\), halted, or \(\ell \) according as \(C_t\) is in state \(q\), halted with last output bit \(1\), or halted with last output bit \(0\), where \(b\) is the last output bit of \(C_t\) (\(0\) if none).

Let \(M\) be a finite-state binary-alphabet Turing machine and \(p : \{ 0,1\} ^{*} \to \{ 0,1\} \) a predicate such that on every input \(x\) the machine \(M\) eventually halts with the single bit \(p(x)\) as its output. Let \(M^{\mathrm{acc}}\) be the halting recognizer of \(M\), which simulates \(M\) with output suppressed while recording the last bit \(M\) emits (initially \(0\)), halts when \(M\) halts with recorded bit \(1\), and otherwise enters a loop state in which it does nothing forever. Then for every input \(x\), \(M^{\mathrm{acc}}\) halts on \(x\) (for some output \(w\) and some \(t\), it halts within \(t\) steps with output \(w\)) if and only if \(p(x) = 1\).

Let \(w = w_0 \cdots w_{m-1}\) and \(x\) be binary strings, and let \(P_w\) be the machine with no work tapes and states \(\{ 0, \ldots , m\} \) which, starting in state \(0\), emits \(w_i\) and moves to state \(i+1\) in each state \(i \lt m\), and in state \(m\) copies the input bit by bit, halting at the first blank. For every \(i \le m\), after \(i\) steps on input \(x\) the machine \(P_w\) is in state \(i\), its input head is still on the first input cell, and its output tape holds the first \(i\) bits \(w_0 \cdots w_{i-1}\) of \(w\).

Let \(w = w_0 \cdots w_{m-1}\) and \(x = x_1 \cdots x_n\) be binary strings, and let \(P_w\) be the machine with no work tapes and states \(\{ 0, \ldots , m\} \) which emits \(w_i\) and advances to state \(i+1\) in each state \(i \lt m\), and in state \(m\) emits the scanned input bit and moves its input head right, halting at a blank. For every \(i \le n\), running \(P_w\) on input \(x\) for \(i\) steps from the configuration in state \(m\) with the input head on the first input cell and output \(w\) yields the configuration in state \(m\) with the input head on cell \(i+1\) and output \(w\, x_1 \cdots x_i\).

Let \(w = w_0 \cdots w_{m-1}\) be a binary string and \(P_w\) the machine with no work tapes and states \(\{ 0, \ldots , m\} \) which first emits \(w_0, \ldots , w_{m-1}\) one per step without moving its input head, then copies the input bit by bit while moving right, halting at the first blank. Then for every binary input \(x\), \(P_w\) halts within \(|w| + |x| + 1\) steps with output the concatenation \(wx\).

Let \(\alpha = \alpha _1 \cdots \alpha _m\) be a binary string, and for a binary string \(x\) let \(\langle \alpha , x \rangle = \alpha _1\alpha _1 \cdots \alpha _m\alpha _m\, 0\, 1\, x\) be the pairing encoding (\(\alpha \) with every bit doubled, then the separator \(01\), then \(x\)). The machine with no work tapes that first emits the fixed word \(\alpha _1\alpha _1 \cdots \alpha _m\alpha _m\, 01\) one bit per step and then copies its input bit by bit, halting at the first blank, halts on every input \(x\) within \(2|\alpha | + |x| + 3\) steps with output \(\langle \alpha , x \rangle \).

Let \(\alpha \) be a fixed binary string, and for binary strings \(x\) let \(\langle \alpha , x \rangle \) be the pairing encoding: \(\alpha \) with every bit doubled, followed by \(01\), followed by \(x\). Then the map \(x \mapsto \langle \alpha , x \rangle \) is polynomial-time computable: some finite-state binary-alphabet Turing machine computes it within \(C \cdot (n+1)^c\) steps on inputs of length \(n\), for constants \(C, c \in \mathbb {N}\).