Deleting stay-put instructions need not preserve computation

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.