One-Tape Simulation Normal Forms: Examples

The state set and both alphabets are finite, $a\mathrm{\ne }\bigsqcup$ ensures $\mathrm{\Sigma }\subseteq \mathrm{\Gamma }\setminus \{\bigsqcup \}$, and the designated states are pairwise distinct. There is exactly one nonhalting state $q_0$ and exactly two tape symbols, so the two displayed entries supply every required nonhalting pair exactly once. Both outputs have valid state, symbol and direction. Thus this is a legal stay-put machine.

The simulator has the two unmarked entries ${\delta }_N((q_0,0),a)=((q_{\mathrm{a}\mathrm{c}\mathrm{c}},1),a,R)$ and ${\delta }_N((q_0,0),\bigsqcup )=((q_{\mathrm{a}\mathrm{c}\mathrm{c}},1),\bigsqcup ,R)$. Its other six entries are, explicitly for each of the three values $p=q_0,q_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{r}\mathrm{e}\mathrm{j}}$, ${\delta }_N((p,1),a)=((p,0),a,L)$ and ${\delta }_N((p,1),\bigsqcup )=((p,0),\bigsqcup ,L)$. These eight entries exhaust its nonhalting pairs; the two unmarked halting states have none.

For input $a$, let $t(0)=a$ and $t(j)=\bigsqcup$ for $j\ge 1$. Its support is $\{0\}$. The original starts at $(q_0,0,t)$, reads $a$, writes $a$ at zero and stays there, giving $(q_{\mathrm{a}\mathrm{c}\mathrm{c}},0,t)$ after one step. It was initially nonhalting and is now accepting, so one is its exact halting time.

The simulator starts at $((q_0,0),0,t)$. Its $a$ entry writes $a$ and moves right, giving $((q_{\mathrm{a}\mathrm{c}\mathrm{c}},1),1,t)$. This is nonhalting because it is marked. It reads $t(1)=\bigsqcup$; the return entry writes $\bigsqcup$ and moves left from one to zero, giving $((q_{\mathrm{a}\mathrm{c}\mathrm{c}},0),0,t)$. Only this second state is accepting, so the exact halting time is two and every tape cell agrees with the original halt.

For empty input, $t_{\epsilon }(j)=\bigsqcup$ for all $j$, with empty support. Substituting the blank entries gives the original step $(q_0,0,t_{\epsilon }){⊢}_M(q_{\mathrm{a}\mathrm{c}\mathrm{c}},0,t_{\epsilon })$, and simulator steps $((q_0,0),0,t_{\epsilon }){⊢}_N((q_{\mathrm{a}\mathrm{c}\mathrm{c}},1),1,t_{\epsilon }){⊢}_N((q_{\mathrm{a}\mathrm{c}\mathrm{c}},0),0,t_{\epsilon })$. Both writes rewrite blank as blank. The marked state is nonhalting, so the respective times remain one and two.

To check a nonblank neighbor, use instead the finite-support tape $u$ with $u(0)=u(1)=a$ and $u(j)=\bigsqcup$ for $j\ge 2$, starting at head zero. The simulator reaches $((q_{\mathrm{a}\mathrm{c}\mathrm{c}},1),1,u)$ and uses the marked $a$ entry to reach $((q_{\mathrm{a}\mathrm{c}\mathrm{c}},0),0,u)$. At cell one it writes $a$ as $a$, not blank, and all other cells are untouched on the return. Thus the boundary macro preserves even a nonblank right neighbor.

For deletion use $Q=\{q_0,q_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{r}\mathrm{e}\mathrm{j}}\}$ with $\delta (q_0,a)=(q_{\mathrm{a}\mathrm{c}\mathrm{c}},a,S)$ and $\delta (q_0,\bigsqcup )=(q_{\mathrm{a}\mathrm{c}\mathrm{c}},\bigsqcup ,S)$. There are two required pairs, and these are exactly their entries; all output coordinates are valid. Hence the original is a legal machine. On the empty input with wholly blank tape $t_{\epsilon }$, its step is $(q_0,0,t_{\epsilon }){⊢}_M(q_{\mathrm{a}\mathrm{c}\mathrm{c}},0,t_{\epsilon })$, so it accepts.

For total replacement use $Q=\{q_0,p,q_{\mathrm{a}\mathrm{c}\mathrm{c}},q_{\mathrm{r}\mathrm{e}\mathrm{j}}\}$ and the four entries $\delta (q_0,a)=(p,a,S)$, $\delta (q_0,\bigsqcup )=(q_{\mathrm{r}\mathrm{e}\mathrm{j}},\bigsqcup ,R)$, $\delta (p,a)=(q_{\mathrm{a}\mathrm{c}\mathrm{c}},a,R)$, $\delta (p,\bigsqcup )=(q_{\mathrm{r}\mathrm{e}\mathrm{j}},\bigsqcup ,R)$. The nonhalting states are exactly $q_0,p$, so these four valid entries exhaust their product with the two-symbol tape alphabet. Replacing its sole $S$ by $R$ gives another total table on the same domain with only legal directions. Thus both the original and its naive ordinary replacement $P$ are valid machines.

Deleting both $S$ entries leaves no value at $(q_0,\bigsqcup )$, although $q_0$ is nonhalting and $\bigsqcup \in \mathrm{\Gamma }$. The resulting empty table is therefore not a total function on its required domain and is not a machine of this model. If one instead imposes the stated partial-table rejection convention, the same initial blank configuration encounters a missing entry and rejects immediately. This differs from the original acceptance on the same empty input. Thus the deletion claim fails under both readings, for distinct stated reasons.

On input $a$, write $t(0)=a$ and $t(j)=\bigsqcup$ for $j\ge 1$. The original takes $(q_0,0,t){⊢}_M(p,0,t){⊢}_M(q_{\mathrm{a}\mathrm{c}\mathrm{c}},1,t)$: the first instruction retains the head on $a$, which selects the accepting $p$ entry. Neither initial nor intermediate state is halting, so it accepts after exactly two steps.

The replacement takes $(q_0,0,t){⊢}_P(p,1,t){⊢}_P(q_{\mathrm{r}\mathrm{e}\mathrm{j}},2,t)$. The changed first direction makes $p$ scan $t(1)=\bigsqcup$, selecting the rejecting entry; its write leaves blank unchanged. It therefore rejects after exactly two steps. The witness input $a$ belongs to the original accepted language and not to the replacement's, disproving language preservation as well as exact computation preservation.

Finally, on an entirely blank tape at $h=0$, a substitute that makes a left move into a fresh nonhalting state and then a right move back, rewriting each scanned blank unchanged, has head trace $0,0,1$: $H_L(0)=0$ and $H_R(0)=1$. A stay-put move would end at zero. In contrast the correct macro has trace $0,1,0$ and preserves the full tape by F2. Thus even a two-move substitute needs the stated right-before-left order at this endpoint.