Let \(M\) be a Turing machine over an alphabet \(\Gamma \) with no work tapes, and let \(M'\) be the machine obtained from \(M\) by adding one unused work tape. For every configuration \(c\) of \(M\) on an input \(x\), one transition of \(M'\) applied to the embedding of \(c\) (same state, input position, and output; blank added tape with head at the origin) equals the embedding of the configuration obtained by one transition of \(M\) from \(c\); this also holds when \(c\) is halted.

Let \(M\) be a Turing machine over an alphabet \(\Gamma \) with no work tapes that computes a function \(f\) on words over \(\Gamma \) within time \(T\), i.e. on every input \(x\) the run of \(M\) has halted after \(T(\left\lvert x\right\rvert )\) steps with output \(f(x)\). Then the machine obtained from \(M\) by adding one unused work tape also computes \(f\) within time \(T\).

Let \(c\) be a configuration of a \(k\)-work-tape machine and \(j \in \mathbb {Z}\). Transducing the block encoding coordinate \(j\) (with unrecorded left-neighbour flags) by the forward-sweep visit rule, starting from the control table associated with \(j\), yields exactly the control table associated with \(j+1\) together with the same block with left-neighbour head flags recorded.

Let \(c\) be a configuration of a \(k\)-work-tape machine, \(\alpha \) an action of that machine, and \(j \in \mathbb {Z}\). Folding the backward-sweep visit rule for \(\alpha \) over the reversed block encoding coordinate \(j\) (with recorded left-neighbour flags), starting from the table of head flags at coordinate \(j+1\), yields the table of head flags at coordinate \(j\) together with the reversed block encoding coordinate \(j\) of the configuration obtained by applying \(\alpha \) to \(c\).

Let \(c\) be a configuration of a \(k\)-work-tape machine, \(j \in \mathbb {Z}\), and \(n \in \mathbb {N}\). The forward sweep over the concatenation of the \(n\) unread blocks at coordinates \(j, \dots , j+n-1\), started from the control table at \(j\), ends in the control table at \(j+n\) and produces the corresponding blocks with left-neighbour head flags recorded.

Let \(c\) be a configuration of a \(k\)-work-tape machine, \(\alpha \) an action of that machine, \(j \in \mathbb {Z}\), and \(n \in \mathbb {N}\). The backward sweep for \(\alpha \) over the reversed concatenation of the \(n\) read-marked blocks at coordinates \(j, \dots , j+n-1\), started from the table of head flags at coordinate \(j+n\), ends in the table of head flags at \(j\) and produces the reversed unread blocks of the configuration obtained by applying \(\alpha \) to \(c\).

Let \(c\) be a configuration of a \(k\)-work-tape machine and \(j \in \mathbb {Z}\) a coordinate such that no work-tape head of \(c\) is at \(j\) and every work tape of \(c\) is blank at \(j\). Then the unread block encoding coordinate \(j\) equals the blank unmarked block.

Every block encoding a single coordinate of a configuration of a \(k\)-work-tape machine is a list of length \(k\), in both its unread and read-marked forms.

A zone of \(n\) consecutive blocks of a configuration of a \(k\)-work-tape machine has length \(n \cdot k\).

For any family of blocks indexed by \(\mathbb {Z}\) and any \(j \in \mathbb {Z}\) and \(n, m \in \mathbb {N}\), the zone of \(n+m\) blocks starting at \(j\) is the concatenation of the zone of \(n\) blocks starting at \(j\) with the zone of \(m\) blocks starting at \(j+n\).

Moving the input head one step in any direction commutes with the transport of head positions from an input word to its symbol-wise encoding.

Let \(c\) be a configuration of a \(k\)-work-tape machine on input \(x\), and let \(d\) be a configuration of any machine over the enlarged sweep alphabet on the symbol-wise encoded input whose input head is at the transported position of \(c\)’s input head. Then decoding the input symbol scanned by \(d\) yields exactly the input symbol scanned by \(c\).

Consider the two-way infinite partial tape assembled from a position \(z \in \mathbb {Z}\), a list \(r\) of optional symbols occupying cells \(z, z+1, \dots \), and a list \(l\) occupying cells \(z-1, z-2, \dots \) (all unlisted cells blank). Overwriting the cell at \(z\) with a value \(b\) yields the tape assembled from \(z\), \(l\), and the list whose first entry is \(b\) followed by the tail of \(r\).

Consider a one-work-tape configuration in forward-facing zipper form: work head at cell \(z\), a list \(r\) occupying cells \(z, z+1, \dots \), a list \(l\) occupying cells \(z-1, z-2, \dots \), an input-head position, and an accumulated output. Applying an action that writes a symbol \(b\) at the current cell, moves the work head left, moves the input head in a given direction, optionally emits one output symbol, and enters a given optional state produces the backward-facing zipper at \(z-1\): cells \(z, z+1, \dots \) hold \(b\) followed by the tail of \(r\), cells \(z-1, z-2, \dots \) hold \(l\), the input head has moved in the given direction, and the output is extended by the emitted symbol.

Consider a one-work-tape configuration in backward-facing zipper form: work head at cell \(z\), a list \(r\) occupying cells \(z, z-1, \dots \), and a list \(l\) occupying cells \(z+1, z+2, \dots \). Applying the sweep action that writes a symbol \(b\) at the current cell, moves the work head right, leaves the input head and output unchanged, and enters a state \(q'\) yields the forward-facing zipper at \(z+1\): cells \(z, z-1, \dots \) hold \(b\) followed by the tail of \(r\), and cells \(z+1, z+2, \dots \) hold \(l\).

For the single-tape simulator of a machine \(M\) with \(k\) work tapes: from any forward-facing zipper configuration whose control is in the initialization phase with counter \(0\), running exactly \(k\) transitions writes, one cell per step while moving right, the encoded marked blank block over the next \(k\) cells, ending in the initialization phase with counter \(k\) and with the work head advanced by \(k\) cells; the input head, output, and remaining tape contents are unchanged.

For the single-tape simulator of a machine \(M\) with \(k\) work tapes and any source state \(q\): from any backward-facing zipper configuration whose control is in the left-extension phase carrying \(q\) with counter \(0\), running exactly \(k\) transitions writes the encoded unmarked blank block in reversed cell order while moving left, ending in the left-extension phase with counter \(k\) and the work head moved left by \(k\) cells; the input head and output are unchanged.

For the single-tape simulator of a machine \(M\) with \(k\) work tapes, a source state \(q\), and a read table \(s\): from any forward-facing zipper configuration whose control is in the right-extension phase carrying \(q\) and \(s\) with counter \(0\), running exactly \(k\) transitions writes the guard block determined by \(s\) while moving right, ending in the right-extension phase with counter \(k\), still carrying \(q\) and \(s\), with the work head advanced by \(k\) cells; the input head and output are unchanged.

Folding the identity visit rule — which returns its control state and each visited cell unchanged — over any list of cells returns the initial state and the unchanged list.

In a backward-facing zipper configuration (work head at cell \(z\), a list \(r\) occupying cells \(z, z-1, \dots \), a list \(l\) occupying cells \(z+1, z+2, \dots \)), applying the sweep action that writes a symbol \(b\) at the current cell without moving, leaves the input head and output unchanged, and enters a state \(q'\) replaces the first entry of \(r\) by \(b\) and the control state by \(q'\), leaving everything else fixed.

Let \(M\) be a machine with \(k\) work tapes over a finite alphabet \(\Gamma \) and let \(x\) be an input word. Running the single-tape simulator for exactly \(2k+2\) transitions from its initial configuration on the symbol-wise encoded input reaches the canonical between-steps configuration representing the initial configuration of \(M\) on \(x\), with a zone of one block at coordinate \(0\) and work head at absolute cell \(-1\).

Applying a stationary phase-change action — no write, no head movement, no output — to a forward-facing zipper configuration replaces only the control state and leaves the tape, input head, and output unchanged.

Applying a stationary phase-change action — no write, no head movement, no output — to a backward-facing zipper configuration replaces only the control state and leaves the tape, input head, and output unchanged.

Let \(M\) be a machine with \(k \ge 1\) work tapes and let \(c\) be a configuration of \(M\) in a non-halted state \(q\) such that every work-tape head of \(c\) is at a coordinate at least \(a\) and every work tape of \(c\) is blank at \(a-1\). From the canonical between-steps configuration for \(c\) with a zone of \(n\) blocks starting at \(a\), running the simulator for exactly \(k + 1 + (n+1)k + 1\) transitions extends the zone by a blank block at \(a-1\), performs the forward sweep over all \(n+1\) blocks — collecting the scanned symbol of every source tape into the control and recording left-neighbour head flags in the cells — and ends in the right-extension phase carrying \(q\) and the completed read table for coordinate \(a+n\), with the read-marked encoded blocks enclosed by boundary markers on the tape and the input head and encoded output preserved.

Let \(M\) be a machine with \(k \ge 1\) work tapes and let \(c\) be a configuration with a state \(q\) such that every work-tape head of \(c\) is at a coordinate strictly less than \(a+n\) and every work tape of \(c\) is blank at \(a+n\). From the configuration reached after the forward sweep — the right-extension phase carrying \(q\) and the read table for coordinate \(a+n\), with the read-marked encoded blocks for coordinates \(a-1, \dots , a+n-1\) on the tape between boundary markers — running exactly \(k + 1 + (n+2)k + 1\) transitions writes the right guard block, performs the transition of \(M\) from \(q\) on the scanned input symbol and the collected work-tape symbols (moving the input head and emitting output accordingly), sweeps backward applying that action to every block, and reaches the canonical between-steps configuration of the resulting source configuration with a zone of \(n+2\) blocks starting at \(a-1\).

Let \(M\) be a machine with \(k \ge 1\) work tapes and let \(c\) be a configuration in a non-halted state \(q\) whose work-tape heads all lie in the interval \([a, a+n)\) and whose work tapes are blank at \(a-1\) and at \(a+n\). Then, from the canonical between-steps configuration for \(c\) with a zone of \(n\) blocks starting at \(a\), exactly \((2n+5)k + 4\) transitions of the single-tape simulator reach the canonical between-steps configuration for the configuration obtained by one step of \(M\) from \(c\), with a zone of \(n+2\) blocks starting at \(a-1\) and the absolute work-head position lowered by \(k\).

The function \(\sigma _k\) defined by \(\sigma _k(0) = 2k+2\) and \(\sigma _k(t+1) = \sigma _k(t) + (4t+7)k + 4\) satisfies, for all \(k, t \in \mathbb {N}\),

The function \(\sigma _k\) defined by \(\sigma _k(0) = 2k+2\) and \(\sigma _k(t+1) = \sigma _k(t) + (4t+7)k + 4\) satisfies \(\sigma _k(t) \le (9k+6)(t+1)^2\) for all \(k, t \in \mathbb {N}\).

Let \(M\) be a machine with \(k \ge 1\) work tapes over a finite alphabet, let \(x\) be an input word, and suppose the run of \(M\) from its initial configuration on \(x\) has not halted at any time \(t \lt \tau \). Then for every \(t \le \tau \), running the single-tape simulator for exactly \(\sigma _k(t)\) transitions (the exact simulation time after \(t\) source steps) from its initial configuration on the symbol-wise encoded input reaches the canonical between-steps configuration representing the configuration of \(M\) after \(t\) steps, with a zone of \(2t+1\) blocks starting at coordinate \(-t\) and work head at absolute cell \(-tk - 1\).