Let \(S\) and \(H\) be sets of control states, \(\iota : S \to H\) a map and \(r \in H\) a designated return state. Given an action \(a\) of a Boolean Turing machine with \(k\) work tapes and state set \(S\), its capture transform is the action of a machine with \(k+1\) work tapes and state set \(H\) that moves the input head as \(a\) does and performs \(a\)’s write and head move on each of the first \(k\) work tapes; on the last work tape it writes the bit \(b\) and moves right if \(a\) emits \(b\), and neither writes nor moves if \(a\) emits nothing; it emits nothing on the output tape; and its successor state is \(\iota (q')\) if \(a\) has successor state \(q'\), and \(r\) if \(a\) halts.

Let \(S\) and \(H\) be sets of control states, \(\iota : S \to H\) a map, \(r \in H\) a return state, and \(p\), \(o\) Boolean words. For a configuration \(c\) of a Boolean Turing machine with \(k\) work tapes and state set \(S\) on an input \(x\), with output word \(u\), its capture image is the configuration on \(x\) of a machine with \(k+1\) work tapes and state set \(H\) whose control state is \(\iota (q)\) if \(c\) is in state \(q\) and \(r\) if \(c\) is halted; whose input head and first \(k\) work tapes (contents and head positions) are those of \(c\); whose last work tape holds the word \(pu\) in cells \(0, \dots , |pu|-1\), blank elsewhere, with its head at cell \(|pu|\); and whose output tape holds \(o\).

Let \(S\) and \(H\) be sets of control states, \(\iota : S \to H\) a map and \(r \in H\) a designated return state. Given an action \(a\) of a Boolean Turing machine with \(k\) work tapes and state set \(S\), its forwarding transform is the action of a machine with the same \(k\) work tapes and state set \(H\) that has the same input-head move, the same writes and head moves on every work tape, and the same emitted bit (if any) as \(a\), and whose successor state is \(\iota (q')\) if \(a\) has successor state \(q'\), and \(r\) if \(a\) halts.

Let \(S\) and \(H\) be sets of control states, \(\iota : S \to H\) a map, \(r \in H\) a return state, and \(p\) a Boolean word. For a configuration \(c\) of a Boolean Turing machine with \(k\) work tapes and state set \(S\) on an input \(x\), its forwarding image is the configuration on \(x\) of a machine with \(k\) work tapes and state set \(H\) whose control state is \(\iota (q)\) if \(c\) is in state \(q\) and \(r\) if \(c\) is halted, whose input-head position, work-tape contents and work-head positions are those of \(c\), and whose output tape holds \(p\) followed by the output of \(c\).

Let \(M\) be a Turing machine over the Boolean alphabet with finitely many states, state set \(Q\), initial state \(q_0\) and \(k\) work tapes, and let \(b\) be a bit. The halt-redirected machine of \(M\) and \(b\) has \(k\) work tapes, control states the pairs \((s, \rho )\) with \(s \in Q\) and \(\rho \) either a bit or empty, together with one loop state \(\ell \), and initial state \((q_0, \text{empty})\). In state \((s, \rho )\) it performs \(M\)’s input move and work-tape writes and moves at \(s\) but emits nothing, updates the register to \(\rho '\), the bit \(M\) emits if there is one and \(\rho \) otherwise, and enters \((s', \rho ')\) if \(M\) moves to state \(s'\), while if \(M\) halts it halts when \(\rho ' = b\) and enters \(\ell \) otherwise; in state \(\ell \) it moves no head, writes and emits nothing, and stays in \(\ell \).

Let \(S\) be a set of states, \(b\) a bit, \(q\) either a state in \(S\) or the halting marker, and \(\rho \) either a bit or empty. The redirected control state, an optional element of \((S \times \{ \text{empty}, \mathrm{false}, \mathrm{true}\} ) \sqcup \{ \ell \} \), is the simulation state \((s, \rho )\) if \(q = s \in S\); if \(q\) is the halting marker, it is the halting marker when \(\rho = b\) (so never when \(\rho \) is empty) and the loop state \(\ell \) otherwise.

Let \(S\) be a set of states, \(b\) a bit, \(a\) an action of a Boolean Turing machine with \(k\) work tapes and state set \(S\), and \(\rho \) either a bit or empty. Let \(\rho '\) be the bit \(a\) emits if there is one, and \(\rho \) otherwise. The redirected action is the action on \(k\) work tapes with state set \((S \times \{ \text{empty}, \mathrm{false}, \mathrm{true}\} ) \sqcup \{ \ell \} \) that has the same input move and work-tape writes and moves as \(a\), emits nothing, and has successor \((s', \rho ')\) if \(a\) has successor \(s'\), while if \(a\) halts it halts when \(\rho ' = b\) and enters the loop state \(\ell \) otherwise.

Let \(M\) be a finite-state Turing machine over the Boolean alphabet and \(b\) a bit, and consider the halt-redirected machine of \(M\) and \(b\), which simulates \(M\) silently while recording the last bit \(M\) has emitted, halts when \(M\) halts with that bit equal to \(b\), and otherwise enters an idle loop state \(\ell \). For a configuration \(c\) of \(M\) on an input \(x\), let \(\rho \) be the last bit of the output of \(c\) (empty if that output is empty); the redirected image of \(c\) is the configuration of the halt-redirected machine on \(x\) with the input head, work tapes and work heads of \(c\), empty output, and control state \((q, \rho )\) if \(c\) is in state \(q\), while if \(c\) is halted it is halted when \(\rho = b\) and in \(\ell \) otherwise.

Let \(D\) be a finite-state Turing machine over the Boolean alphabet with \(k\) work tapes, state set \(Q\) and initial state \(q_0\), and let \(m \in \mathbb {N}\). The padded machine has \(k + m\) work tapes, state set \(Q\) and initial state \(q_0\); in state \(q\), reading input symbol \(\sigma \) and work-tape symbols \(w_0, \dots , w_{k+m-1}\), it performs \(D\)’s action at \((q, \sigma , w_0, \dots , w_{k-1})\) on the input head and the first \(k\) work tapes, with the same emission and successor state, while writing nothing on the last \(m\) work tapes and keeping their heads still.

Let \(D\), \(M_1\), \(M_2\) be finite-state Turing machines over the Boolean alphabet with \(k_D\), \(k_1\), \(k_2\) work tapes and state sets \(Q_D\), \(Q_1\), \(Q_2\). The timed conditional controller has \(k_D + k_1 + k_2 + 1\) work tapes, split into a decider block of \(k_D\) tapes, a branch block of \(k_1 + k_2\) tapes and one capture tape; its states are those of \(Q_D\), two administrative states (back and read), a rewind-start and a rewind-scan state for each bit \(\beta \), and those of \(Q_1 \sqcup Q_2\); and its initial state is \(D\)’s. In a state of \(D\) it performs \(D\)’s transition on the input and the decider block, writes \(D\)’s emitted bit (if any) on the capture tape and moves that head right, emits nothing, leaves the branch block idle, and enters the back state where \(D\) would halt; the back state moves the capture head one cell left and enters the read state; the read state reads the bit \(\beta \) under the capture head (\(\mathrm{false}\) if blank) and enters rewind-start for \(\beta \); rewind-start moves the input head left and enters rewind-scan; rewind-scan keeps moving the input head left while it reads an input symbol and, on reading the blank boundary, moves right and enters the initial state of \(M_1\) if \(\beta \) is \(\mathrm{true}\) and of \(M_2\) otherwise (all four administrative states writing and emitting nothing and keeping the other heads still); and in a state of \(M_i\) it performs \(M_i\)’s transition, including its emission and halting, on the input and on \(M_i\)’s own \(k_i\) tapes within the branch block, leaving all other work tapes idle.

Let \(D\), \(M_1\), \(M_2\) be finite-state Turing machines over the Boolean alphabet with \(k_D\), \(k_1\), \(k_2\) work tapes, and consider the timed conditional controller for them, whose work tapes form a decider block of \(k_D\) tapes, a branch block of \(k_1 + k_2\) tapes and one capture tape, and whose states include a copy of the states of \(M_1\) and \(M_2\). Let \(c\) be a configuration on an input \(x\) of the two-branch union machine (which runs \(M_1\) on the first \(k_1\) and \(M_2\) on the last \(k_2\) of its \(k_1 + k_2\) work tapes, according to whether its state belongs to \(M_1\) or \(M_2\)), let \(\tau \) and \(h\) be contents and head positions for \(k_D\) tapes, and let \(\beta \) be a bit. The branch-phase configuration is the controller configuration on \(x\) whose state is the copy of \(c\)’s state (halted if \(c\) is halted), whose input head and output are those of \(c\), whose decider block holds \(\tau \) with heads \(h\), whose branch block holds \(c\)’s work tapes and heads, and whose capture tape holds the bit \(\beta \) in cell \(0\), blank elsewhere, with its head at cell \(0\).

Let \(D\), \(M_1\), \(M_2\) be finite-state Turing machines over the Boolean alphabet with \(k_D\), \(k_1\), \(k_2\) work tapes, and consider the timed conditional controller for them, whose work tapes form a decider block of \(k_D\) tapes, a branch block of \(k_1 + k_2\) tapes and one capture tape, and whose states include a copy of the states of \(D\) and an administrative back state. For a configuration \(c\) of \(D\) on an input \(x\), with output \(u\), the decider-phase configuration is the controller configuration on \(x\) whose state is the copy of \(c\)’s state, or the back state if \(c\) is halted; whose input head is that of \(c\); whose decider block holds \(c\)’s work tapes and heads; whose branch block is blank with every head at cell \(0\); whose capture tape holds \(u\) in cells \(0, \dots , |u|-1\), blank elsewhere, with its head at cell \(|u|\); and whose output is empty.

Let \(D\), \(M_1\), \(M_2\) be finite-state Turing machines over the Boolean alphabet, and consider the timed conditional controller for them, whose work tapes form a decider block, a branch block and a capture tape, and whose states include a rewind-start state for each bit. For a configuration \(c\) of \(D\) on an input \(x\) and a bit \(\beta \), the ready-to-rewind configuration is the controller configuration on \(x\) in the rewind-start state for \(\beta \), with the input head of \(c\), the decider block holding \(c\)’s work tapes and heads, the branch block blank with every head at cell \(0\), the capture tape holding the bit \(\beta \) in cell \(0\), blank elsewhere, with its head at cell \(0\), and empty output.