Let \(M\) be a multi-tape Turing machine over a finite alphabet \(\Gamma \). The predicate asserts that \(M\) uses its work tapes unidirectionally: for every input string over \(\Gamma \), every number of steps \(t \in \mathbb {N}\), and every work tape of \(M\), the position of that work tape’s head after running \(M\) for \(t\) steps from its initial configuration on the input is nonnegative.

The enlarged tape alphabet used to fold a two-way infinite tape over a base alphabet \(\Gamma \): its symbols are triples \((b, u, v)\) where \(b\) is a Boolean origin flag and \(u\) and \(v\) are two independent payloads, each either a symbol of \(\Gamma \) or blank. The intent is that a nonnegative physical cell \(p\) carries the content \(u\) of the simulated cell \(p\) and the content \(v\) of the simulated cell \(-p-1\).

The injection of a base alphabet \(\Gamma \) into the folded alphabet sending a symbol \(a\) to the triple whose origin flag is unset, whose first payload is \(a\), and whose second payload is blank.

The coordinate-folding map \(\varphi \colon \mathbb {Z}\to \mathbb {Z}\) defined by \(\varphi (z) = z\) when \(z \ge 0\) and \(\varphi (z) = -z-1\) otherwise. It maps each negative cell \(z\) onto the nonnegative cell \(-z-1\); in particular \(\varphi (0) = \varphi (-1) = 0\), so \(\varphi \) is not the absolute value.

The Boolean recording on which side of the fold an integer coordinate \(z\) lies: true when \(z \ge 0\) and false when \(z \lt 0\).

The canonical packing of a folded-alphabet triple into an optional cell content: the untagged triple with both payloads blank is sent to the physical blank, and every other triple is kept as an actual symbol. This ensures that a physical cell never stores a symbol carrying no information.

The unpacking of a physical cell content over the folded alphabet — either a folded triple or blank — into a folded triple, interpreting a physical blank as the untagged triple with both payloads blank.

Given a two-way infinite tape content \(t \colon \mathbb {Z}\to \Gamma \cup \{ \square \} \) over a base alphabet \(\Gamma \) (with \(\square \) the blank), the folded tape assigns to each nonnegative physical cell \(p\) the canonical packing of the triple consisting of the flag “\(p = 0\)”, the content \(t(p)\), and the content \(t(-p-1)\); every negative physical cell is blank.

Given the current side of the fold, an origin flag, and a simulated move direction \(d \in \{ -1, 0, +1\} \), this operation returns the physical move to perform together with the new side: moves translate directly on the nonnegative side and are reversed on the negative side, while a crossing between simulated cells \(0\) and \(-1\) (detected by the origin flag) flips the side without issuing a physical move.

Reading a physical cell over the folded alphabet relative to a side: after unpacking the cell (a physical blank unpacks to the untagged triple of blanks), return the first payload when the side is the nonnegative one and the second payload otherwise.

Writing a possibly blank base symbol \(a\) into a physical cell over the folded alphabet, relative to a side: unpack the cell, replace the first payload by \(a\) when the side is the nonnegative one and the second payload otherwise, keep the origin flag and the untouched payload, and repack canonically (so a fully blank untagged result becomes a physical blank).

Given, for each of \(k\) work tapes, the current side of the fold and the physical cell under the head, this translates an action of a \(k\)-work-tape machine over a base alphabet \(\Gamma \) with state set \(S\) into an action over the folded alphabet whose states pair a state of \(S\) with a side for each tape (or are absent, meaning halt): writes become side-relative folded writes, moves are translated across the fold using the origin flags stored in the scanned cells, the emitted output symbol is embedded, and the successor state is paired with the updated sides.

The folded image of a configuration \(c\) of a \(k\)-work-tape machine over a base alphabet \(\Gamma \) with state set \(S\) on an input \(x\): a configuration over the folded alphabet on the symbol-wise embedded input, whose control state is the state of \(c\) paired with the side of each work head, whose work tapes are the folded tapes of those of \(c\), whose work head positions are the folded coordinates \(\varphi \) of those of \(c\), and whose input head position and output are transported along the embedding.

The partial inverse of the alphabet embedding: a folded triple whose origin flag is unset, whose first payload is a base symbol \(a\), and whose second payload is blank decodes to \(a\); every other folded triple decodes to nothing.

The action of a \(k\)-work-tape machine that halts immediately: it does not move the input head, writes nothing and issues no move on any work tape, emits no output symbol, and has no successor state.

The single initialization action of the folding simulator, parametrized by a target base state \(q\): without moving any head and without emitting output, it simultaneously writes the origin marker — the folded triple with flag set and both payloads blank — at the current cell of every work tape, and passes control to the state \(q\) with every tape recorded as being on the nonnegative side.

The action taken from the simulator’s fresh initial state when scanning a possibly absent folded input symbol: if the scanned symbol is absent or decodes to a base symbol, perform the initialization action toward a given base state \(q\); if it lies outside the range of the alphabet embedding, perform the same origin-marking writes but halt instead of entering \(q\). Thus no simulated transition precedes the validity check on the first input symbol.

For a multi-tape machine \(M\) over a finite alphabet \(\Gamma \) with decidable equality, the simulating machine over the folded alphabet: it has the same number of work tapes as \(M\), and its states are either a fresh initial state or a state of \(M\) paired with a side for each work tape. From the fresh state it performs the guarded initialization; thereafter it decodes the scanned input symbol (executing the stationary halt if the symbol lies outside the embedding’s range), reads the active payload of each work tape, and executes the translation of the corresponding transition of \(M\).

The safety invariant on a configuration \(c\) of a \(k\)-work-tape machine over the folded alphabet whose states are either a fresh initial state or a base state paired with per-tape sides, on an arbitrary folded-alphabet input: the control state of \(c\) is not the fresh initial state (it may be halted), every work head position is nonnegative, and on every work tape the origin flag obtained by unpacking each nonnegative cell \(p\) is set exactly when \(p = 0\).