Robust Machine Models and Universal Computation

By [L1], each coded machine $M$ has one definite description tuple $\mathrm{Desc}(M)$ of some fixed length $3+3(m-2)n$, and $<mi\; mathvariant="normal">⌜</mi>M<mi\; mathvariant="normal">⌝</mi>$ is exactly the tuple code of that tuple.

A total decoder first uses [L2] to parse the unary arity header and then exactly that many self-delimiting entries. If the parse fails or leaves unread bits, it returns the malformed token; otherwise it recovers one finite tuple of binary words.

If $<mi\; mathvariant="normal">⌜</mi>M<mi\; mathvariant="normal">⌝</mi>=<mi\; mathvariant="normal">⌜</mi>N<mi\; mathvariant="normal">⌝</mi>$, then the global injectivity in [L2] gives equality of the decoded tuples, including their arities, so $\mathrm{Desc}(M)=\mathrm{Desc}(N)$. By [L1], that common tuple records the same values of $m$, $s$, $n$, and every transition triple for both machines. Hence $M=N$.

The decoder then checks the shape demanded by [L1]: every entry must be a canonical binary numeral; the tuple must have length $3+3(m-2)n$ for the recovered first three numerals; one must have $m\ge 3$, $n\ge 1$, and $0\le s<n$; and every transition entry must lie in $Q_m\times {\mathrm{\Gamma }}_n\times \{0,1\}$. If any check fails, the decoder returns the malformed token. If all checks pass, those data determine one coded deterministic one-tape machine.

Step 2.1 proves injectivity, and steps 1.2 and 2.2 produce a total decoder. Therefore the chosen machine coding is injective and effectively decodable.

Before simulation, $\widehat{M}$ uses a finite preprocessing routine to place virtual cell $j$ of every tape at physical cell $2j$. On the first tape it shifts the finite input symbols to the even cells and writes # in the intervening odd cells; every blank work tape starts with a tagged blank at cell $0$. Tagged copies of all simulated symbols at physical cell $0$ let the control detect the left boundary. Heads on tapes not currently being prepared execute harmless right-then-left bounces, and the finite routine is padded to return every head to cell $0$. Thus preprocessing uses only left/right moves, terminates on every finite input, and begins each simulated step with every head on an even cell.

Consider one transition of $M$ that writes $b_1,\dots ,b_k$, requests $D_i\in \{L,R,S\}$, and has next state $p$. Replace it by a two-step macro through a fresh auxiliary state that remembers $p$ and the requested directions. In the first microstep, $\widehat{M}$ writes $b_i$ at the scanned even cell—using its tagged copy at physical cell $0$—and moves head $i$ by $R$ for $D_i\in \{R,S\}$, by $L$ for a nonboundary $D_i=L$, and by $R$ for a boundary-clamped $D_i=L$. In the second microstep, each scanned odd cell is treated as a spacer whether it already contains # or is a fresh blank, and is written as #; head $i$ then moves $R$ for virtual $R$ and $L$ in the other three cases. The net displacements $RR,RL,LL,RL$ represent virtual right, stay, nonboundary left, and clamped left, respectively. Because $k$ and the alphabets are fixed, the finitely many tuples of spacer symbols and direction cases fit in a finite transition table.

After step 2.1, every traversed odd cell is a separator, each $b_i$ occupies the correct even cell, origin symbols remain tagged, and every head is on the even cell encoding its simulated successor position. Hence the represented virtual configuration is exactly the one-step result of $M$, including left-boundary clamping and moves into previously unrepresented blank cells.

Apply the macro to every source transition. If its remembered state $p$ is halting, $\widehat{M}$ postpones entering that state while a finite routine copies the first tape's even cells cell-for-cell to ordinary cells $0,1,\dots$, removes the origin tag, preserves internal blanks, and erases all separators and later encoded cells; unused tape heads execute harmless bounces during this cleanup. Only then does it enter the corresponding halting state. By step 3.1, induction on simulated steps gives the same acceptance, rejection, divergence, and exact first-tape output on the original unencoded input.

Therefore the matching behavior in step 4.1 means, by [F1], that $\widehat{M}$ preserves every recognized or decided language and every computed partial function.

Given a right-infinite-tape machine, let a two-way simulator use tagged copies of tape symbols at cell $0$, so it can recognize the simulated boundary. Every ordinary move is copied directly except a simulated left move at cell $0$: after performing the write, the simulator moves right in a fresh auxiliary state and then left without changing the intervening symbol, thereby returning to cell $0$ in the requested next state. If that next state is halting, it is postponed until the return move; before any halt, a finite sweep removes the origin tag. Hence the two-way simulator never visits a negative cell and has exactly the source machine's accept, reject, divergence, and output behavior.

For the converse, enlarge the one-way simulator's finite alphabet by ordered pairs, marked copies, and special origin symbols. It converts ordinary contiguous input into a folded representation by finitely many sweeps: cell $0$ stores the two-way origin, while cell $n\ge 1$ stores the ordered pair of symbols at $+n$ and $-n$, initially with every negative component blank. Exactly one stored symbol or pair component is marked to record the simulated head. Because every configuration has finite tape support and one head position, initialization terminates and every folded encoding has finite support.

A simulated move changes only one stored symbol and the marked component. Moving right from $+n$ to $+(n+1)$ or left from $-n$ to $-(n+1)$ shifts the mark one cell to the right; moving left from $+n$ to $+(n-1)$ or right from $-n$ to $-(n-1)$ shifts it one cell to the left; and the four boundary transitions through the origin move the mark between cell $0$ and cell $1$. Thus one deterministic one-tape machine can update the folded representation by a finite local macro for each source transition.

Induction on simulated steps shows that the folded machine represents the current two-way configuration exactly. On a simulated halt it postpones its own halting state and scans the finite folded encoding. If every negative component is blank, it copies the nonnegative components cell-for-cell to cells $0,1,\dots$, preserving internal blanks, and erases all auxiliary cells. If some negative component is nonblank, the source has no ordinary-word output by [F1]; the simulator likewise leaves a fixed malformed pattern consisting of a blank cell $0$ followed by a nonblank auxiliary marker. It then enters the corresponding halting state. Thus it preserves acceptance, rejection, divergence, and whether—and which—ordinary word is output. If a local macro uses stay-put housekeeping, [L1] removes it without changing behavior.

Combining steps 1.1 and 3.1, the two conventions have identical behavior on every input; by [F1], they therefore recognize and decide the same languages and compute the same partial functions.

Enlarge the simulator's finite tape alphabet by fresh delimiters and marked copies of the simulated symbols. On its ordinary input, $S_M$ first makes finitely many sweeps to write $k$ blocks separated by #_1,\dots,#_{k-1}. A block records the simulated tape prefix from cell $0$ through at least both its head and its rightmost nonblank cell, and exactly one recorded symbol is marked to indicate the head. The first block initially records the input (or one marked blank for empty input), and every other block initially consists of one marked blank. Thus initialization terminates and the encoding invariant represents the entire finite-support contents and head position of every simulated tape.

In one simulation cycle, the one-tape machine $S_M$ first scans once from left to right, reads the $k$ marked symbols, and stores in its finite control the unique transition of $M$ determined by the current state and those symbols.

The machine then makes finitely many return sweeps, rewrites each old marked symbol, and places its new mark at the simulated successor head position. A left move from simulated cell $0$ leaves the mark at that cell, matching the library's clamped left boundary. If a right move leaves the recorded prefix, $S_M$ shifts the delimiter and the entire encoded suffix following that block one cell right (or extends the last block into the blank suffix) and inserts a marked blank cell. These operations preserve all later blocks and restore the invariant from step 1.1.

After the passes from steps 2.1 and 3.1, the encoding represents precisely the next $k$-tape configuration of $M$. If the simulated state is halting, $S_M$ postpones entering its own halting state while it copies the first block cell-for-cell, with the mark removed and internal blank cells preserved, to tape cells beginning at $0$, and erases every later cell, delimiter, and auxiliary symbol. It then enters the corresponding halting state. Hence its final tape is exactly the simulated first tape, not merely a compaction of its nonblank symbols. Induction on simulated steps now proves identical acceptance, rejection, divergence, and first-tape output on every original input.

Eliminate any temporary stay-put motion in the one-tape bookkeeping as follows. Replace each instruction that writes $b$, stays, and enters state $p$ by an instruction that writes $b$, moves right, and enters a fresh auxiliary state remembering $p$. For every symbol $c$ read in that state, write $c$ unchanged, move left, and enter $p$. The intermediate head position is at least $1$, so the left move returns to the original cell even when that cell was $0$. The tape contents and original head position are restored after the two-step macro; if $p$ is halting, it is entered only on the second step. The finite set of source instructions gives finitely many new states, and every macro terminates, preserving divergence as well as both halting outcomes and the final tape.

Hence the matching behavior in step 4.1 means, by [F1], that $S_M$ recognizes and decides the same languages and computes the same partial functions as $M$.

After $j$ steps of $M$, each simulated head has moved by at most $j$ cells from its initial position, so tape $i$ can have visited only the cells in an interval of length at most $\mathrm{\mid }w\mathrm{\mid }+j+1$. Therefore the explicit block for tape $i$ in the encoding from [L1] has length $O(\mathrm{\mid }w\mathrm{\mid }+j+1)$, with an implied constant depending only on the fixed machine $M$.

Summing over the fixed number $k$ of tapes, and absorbing the fixed delimiter overhead, the whole one-tape encoding after $j$ simulated steps has length at most $c_M^{\mathrm{\prime }}(\mathrm{\mid }w\mathrm{\mid }+j+1)$ for some constant $c_M^{\mathrm{\prime }}>0$.

One simulation cycle of $S_M$ at stage $j$ performs a constant number of full sweeps across that length-$O(\mathrm{\mid }w\mathrm{\mid }+j+1)$ encoding and, when needed, one local shift of a suffix of the same order. Hence the time for the $j$th simulated step is at most $c_M^{\mathrm{\prime }\mathrm{\prime }}(\mathrm{\mid }w\mathrm{\mid }+j+1)$ for some constant $c_M^{\mathrm{\prime }\mathrm{\prime }}>0$.

The initial encoding from [L1] takes $O_M(\mathrm{\mid }w\mathrm{\mid }+1)$ time and space: the simulator makes a fixed number of sweeps over the input and writes a fixed number of blocks and delimiters. Adding this setup cost to the estimate from step 3.1 for $j=0,1,\dots ,t-1$ gives $O_M(\mathrm{\mid }w\mathrm{\mid }+1)+{\sum }_{j=0}^{t-1}{c}_M^{\mathrm{\prime }\mathrm{\prime }}(\mathrm{\mid }w\mathrm{\mid }+j+1)\le O_M(\mathrm{\mid }w\mathrm{\mid }+1)+c_M^{\mathrm{\prime }\mathrm{\prime }}t(\mathrm{\mid }w\mathrm{\mid }+1)+c_M^{\mathrm{\prime }\mathrm{\prime }}\frac{t(t-1)}{2}\le c_M(\mathrm{\mid }w\mathrm{\mid }+t+1{)}^2$ for a suitable constant $c_M$, including when $t=0$. Together with step 2.1, this proves the claimed linear space bound and quadratic time bound.

If a deterministic one-tape Turing machine recognizes $L$, then the same transition graph viewed as a nondeterministic machine with singleton choice sets also recognizes $L$.

Conversely, suppose a nondeterministic one-tape machine $N$ recognizes $L$. Build a deterministic multitape machine $D$ that, on input $w$, enumerates all finite branch-choice strings of lengths $0,1,2,\dots$. For each choice string $\alpha$ of length $d$, the machine $D$ simulates $N$ on $w$ for $d$ steps, following at the $r$th branching point the ${\alpha }_r$th available transition when that transition exists and abandoning $\alpha$ otherwise.

By [L1], $N$ accepts $w$ exactly when some finite accepting branch exists. If such a branch has length $d$, its sequence of local branch choices is one of the strings tested in step 1.2, so $D$ eventually finds it and accepts. If no accepting branch exists, every tested choice string fails to end in acceptance, so $D$ never accepts. Thus $D$ recognizes the same language as $N$.

Any temporary stay-put moves introduced while $D$ manages its work tapes can be removed by [L4], and then [L3] yields a deterministic one-tape machine recognizing the same language as $D$.

Steps 1.1 and 3.1 prove that nondeterministic and deterministic one-tape machines recognize exactly the same languages, in the sense of [L2].

Let $M$ be a deterministic one-tape Turing machine. A RAM/register program can simulate $M$ by storing the current state and head position in distinguished registers and storing the finitely many nonblank tape cells in addressed memory entries. One program macro reads the currently addressed tape symbol, consults the finite transition table of $M$, updates that symbol and the control registers, and increments or decrements the stored head position according to the chosen transition.

Conversely, let $P$ be a RAM/register program. Build a deterministic multitape Turing machine $N_P$ whose work tapes store the program counter, the finitely many currently nonzero memory entries as a sorted list of address-value pairs, and scratch data for arithmetic and list maintenance. Each instruction type from [L1] is implemented by a finite Turing-machine subroutine: copy and arithmetic operate on binary numerals on work tapes, indirect addressing searches the address-value list, and zero entries are inserted or deleted so that the stored list remains finite.

Induction on the number of simulated steps shows that the RAM/register program from step 1.1 reproduces the full computation of $M$ on every binary input, including acceptance, rejection, divergence, and final output. Hence every Turing-recognizable language and every Turing-computable partial function is RAM/register realizable.

Again by induction on computation length, the multitape machine $N_P$ from step 1.2 reproduces exactly the accept, reject, divergence, and output behavior of $P$ on the standard input layout.

By [L4], $N_P$ has an equivalent deterministic one-tape simulation. Combining this with steps 2.1 and 2.2, the RAM/register and deterministic Turing-machine models recognize the same languages in the sense of [L2] and compute the same partial functions in the sense of [L3].

Construct $I_{\mathrm{s}\mathrm{t}\mathrm{e}\mathrm{p}}$ as a one-tape machine that uses marked tape symbols and repeated finite sweeps to maintain delimited work zones. On input $z$, it first parses $z=1^{\mathrm{\ell }}0xy$ with $\mathrm{\mid }x\mathrm{\mid }=\mathrm{\ell }$: it marks the initial $\mathrm{\ell }$ ones, copies exactly the next $\mathrm{\ell }$ bits into the machine-code zone, and copies the remaining suffix into the configuration-code zone. A missing separator or fewer than $\mathrm{\ell }$ following bits is malformed. These marking, copying, comparison, and delimiter operations require only finite control and repeated one-tape sweeps.

The interpreter applies the concrete finite parser from [L1] to the machine-code zone $x$. It then parses $y$ block-by-block using $c(w)=1^{\mathrm{\mid }w\mathrm{\mid }}0w$: the first recovered block gives $r$, the next two give $q$ and $h$, and the next $r+1$ blocks give $a_0,\dots ,a_r$. It rejects a missing or truncated block, any block that is not a canonical numeral $\mathrm{bin}(j)$, and any unread bits after these $r+4$ blocks. It also checks the configuration conditions from [L2]: $q<m$, $h\le r$, every $a_j<n$, and $a_r\mathrm{\ne }0$ whenever $r>h$. Each check is a finite comparison of delimited binary words and is performed by the same marking-and-sweep method. If the pair parse, machine parse, configuration parse, or any check fails, $I_{\mathrm{s}\mathrm{t}\mathrm{e}\mathrm{p}}$ erases its tape and halts with output $\epsilon$.

If the recovered state is accepting or rejecting, then [L2] says the configuration is halting. In that case $I_{\mathrm{s}\mathrm{t}\mathrm{e}\mathrm{p}}$ copies the unchanged configuration code to the leftmost output zone, erases the other zones, and halts.

Otherwise the configuration is nonhalting. The interpreter scans the decoded transition table to find the entry for $(q,a_h)$, replaces $a_h$ by the recorded symbol $b$, and updates the state and head position exactly by [L3], including the clamp at cell $0$. If the new head position is $r+1$, it appends a blank block so that the scanned cell is represented. It then removes precisely the trailing blank blocks whose indices exceed both the new head position and the last nonblank cell, recomputes the new value of $r$, and re-encodes every numeral canonically. All of these are finite scans of the delimited table and work zones.

By [L3], step 3.2 produces exactly the canonical code of the unique one-step successor. Steps 1.1 and 2.1 halt with $\epsilon$ on every malformed input, while steps 3.1 and 3.2 cover the halting and nonhalting valid configurations. Thus the single fixed deterministic one-tape machine just constructed has exactly the behavior claimed.

Build a deterministic multitape machine $W$ that, on input $⟨<mi\; mathvariant="normal">⌜</mi>M<mi\; mathvariant="normal">⌝</mi>,\widehat{w}⟩$, first decodes the coded machine $M=(m,s,n,\tau )$ from the first component and the input word $w\in {\mathrm{\Sigma }}_s^{\ast }$ from the second component block-by-block. It then copies $<mi\; mathvariant="normal">⌜</mi>M<mi\; mathvariant="normal">⌝</mi>$ to one work tape, constructs the encoded initial configuration of $M$ on input $w$ on a second work tape, and reserves a third work tape for running the one-step interpreter from [L3].

The machine $W$ now iterates the interpreter from [L3]. Before each cycle it checks whether the current code represents an accepting or rejecting configuration and stops the iteration if so; otherwise it replaces that code by the one-step successor returned by the interpreter. This state check, rather than equality of successive codes, detects halting.

Induction on the number of interpreter cycles shows that the maintained configuration code is always the code of the current configuration of $M$ on input $w$. Therefore, if $M$ halts with output $u$, then $W$ eventually reaches the halting configuration code, decodes the represented output word $u$, writes its binary code $\widehat{u}$ in its own output convention, and halts. If $M$ diverges, the iteration never reaches a halting configuration code, so $W$ diverges as well. Thus $W$ has exactly the behavior required by [L1] and [L2].

Finally, [L4] converts the deterministic multitape interpreter $W$ into an equivalent deterministic one-tape machine. By step 3.1, that one-tape machine is universal for the chosen coding.

Enumerate all binary words in shortlex order and run the total decoder from [L2] on each word. Whenever the decoder reports malformed input, output nothing; whenever it returns a coded machine, output that machine.

By [L1], every coded machine $M$ has some binary code $<mi\; mathvariant="normal">⌜</mi>M<mi\; mathvariant="normal">⌝</mi>$, and shortlex enumeration eventually reaches that code. At that stage the decoder returns $M$, so every coded machine appears somewhere in the output stream.

By injectivity in [L2], two different binary words cannot decode to the same coded machine. Therefore the procedure from step 1.1 lists each coded deterministic one-tape Turing machine exactly once and gives an effective enumeration.

Let $M_{\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{p}}=(3,0,1,{\tau }_{\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{p}})$, where the unique transition is ${\tau }_{\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{p}}(0,0)=(0,0,1)$. Its input alphabet is empty, so its unique input word is $\epsilon$. On that input the machine keeps state $0$ forever, moves right at every step, and never reaches a halting state. Hence it has no halting computation history on $\epsilon$, so by [L2] it diverges on $\epsilon$.

By [L3], there exists at least one universal machine $U$. By [L1], the run of $U$ on the coded input $⟨<mi\; mathvariant="normal">⌜</mi>M_{\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{p}}<mi\; mathvariant="normal">⌝</mi>,\widehat{\epsilon }⟩$ must reproduce the divergence from step 1.1. Hence $U$ does not halt on that instance.

A machine that fails to halt on some instance does not decide a yes-or-no halting problem on all instances. Step 2.1 therefore contradicts the false claim [A1].