Robust Machine Models and Universal Computation: Examples and Counterexamples

Let $C=(q_0,h,t)$ be any configuration with $t(h)=1$. The original transition sends $C$ in one step to the configuration $(q_1,h,t^{\mathrm{\prime }})$, where $t^{\mathrm{\prime }}$ agrees with $t$ away from $h$ and satisfies $t^{\mathrm{\prime }}(h)=0$.

Under the replacement macro, the first step writes 0 at cell $h$ and moves the head to $h+1$, entering state $r$. The second step leaves the symbol at cell $h+1$ unchanged, moves the head back to $h$, and enters state $q_1$. So after the two-step macro the transformed machine is also in configuration $(q_1,h,t^{\mathrm{\prime }})$.

Thus the concrete macro produces exactly the same next configuration as the stay-put transition. This is the local pattern asserted abstractly by [L1], and [L2] explains why matching state, head position, and tape contents is enough.

Each tuple $D_i$ has the correct length $6=3+3(3-2)\cdot 1$, satisfies $m=3\ge 3$, $n=1\ge 1$, and $0\le s=0<1$, and records a transition entry with target state in $\{0,1,2\}$, tape symbol $0$, and move bit in $\{0,1\}$. So each $E(D_i)$ is a well-formed machine code.

Any well-formed machine description tuple has arity $3+3(m-2)n\ge 6$, with equality only when $m=3$ and $n=1$; then necessarily $s=0$. Under the fixed encoder, the unary arity header makes every larger-arity code longer than these shortest valid codes. For arity six, shortlex compares the self-delimiting canonical entries in order: target $0$ with move $0$, target $0$ with move $1$, and target $1$ with move $0$ give $E(D_1),E(D_2),E(D_3)$ respectively.

By [L2], decoding $E(D_i)$ recovers exactly the machine described by $D_i$. Reading off the single transition triple of each tuple gives the three concrete machines described in the example statement.

Therefore the shortlex enumeration from [L1] begins by listing these three machines, each exactly once. This shows concretely what the effective enumeration does at its first successful decodings.

The machine $M_{\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{p}}$ has an infinite run on its unique input $\epsilon$, because its only action is to move right forever and it never enters a halting state.

By the universality clause recalled in the counterexample statement, the universal machine $U$ must reproduce that same infinite run on the coded input $⟨<mi\; mathvariant="normal">⌜</mi>M_{\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{p}}<mi\; mathvariant="normal">⌝</mi>,\widehat{\epsilon }⟩$. So $U$ diverges on this input rather than halting with a yes-or-no answer.

Therefore the coded input $⟨<mi\; mathvariant="normal">⌜</mi>M_{\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{p}}<mi\; mathvariant="normal">⌝</mi>,\widehat{\epsilon }⟩$ is a counterexample to the claim in [L1]. The existence assertion [L2] shows that this is a genuine instance in the chosen coding scheme.