Eliminating a stay-put transition at the left boundary

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.