Normalized fixed halting machine for boone simulation

Give each symbol $a$ an undotted copy $a$ and a dotted copy $\dot{a}$. Let $f$ send accepting state to $q_0$, rejecting state to a new state $\mathrm{\ell }$, and each other state to its tagged simulator copy. Add a new start state $z$. On any undotted $a$, its instruction writes $\dot{a}$ and enters $f(p_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}})$. This also defines initialization for empty input, by writing ${\dot{s}}_0$.

For each table entry $(p,a)\mapsto (p^{\mathrm{\prime }},b,D)$ and bit $d\in \{0,1\}$, add a fresh intermediate state $j_{p,a,d}$. In state $f(p)$ scanning $a^{(d)}$, write $b^{(d)}$ and enter $j_{p,a,d}$. On $b^{(d)}$, this intermediate state moves in direction $D$ and enters $f(p^{\mathrm{\prime }})$, except that for $d=1,D=L$ it writes the same $b^{(1)}$ without moving and enters $f(p^{\mathrm{\prime }})$. Every other symbol in that intermediate state goes by a no-op write to $\mathrm{\ell }$. State $\mathrm{\ell }$ no-op writes every symbol and stays in $\mathrm{\ell }$. The unused dotted inputs at $z$ also go to $\mathrm{\ell }$. There are no entries at $q_0$. The cases are disjoint and exhaust every nonstopping state/symbol pair. Their indexing sets are finite, so this is a literal finite deterministic table.

After initialization, the unique dot is at cell zero; undotting the nonnegative tape gives precisely $R$'s initial tape, and all negative cells are blank. Suppose this invariant holds at a simulated nonhalting state. The first instruction writes precisely $R$'s new symbol, retaining the dot bit. The second instruction scans that very symbol, so it follows the designated intermediate branch. Away from zero it makes $R$'s move. At zero a left move is the no-op specified in step 2.1, while a right move reaches cell one. Thus no negative cell is visited and the unique dot is neither lost nor copied. The next macro boundary has exactly $R$'s new head, tape and mapped state. Repeating this calculation proves the invariant after every simulated step.

The macro boundaries occur at times $1+2n$ until a halting outcome. Every intervening time is the intermediate state for the preceding table entry, so a run cannot reach $q_0$ in an unaccounted intermediate step. If $R$ accepts at step $n$, $T$ reaches $q_0$ at time $1+2n$. Conversely the only reached entry into $q_0$ finishes a macro whose target is acceptance. Rejection reaches $\mathrm{\ell }$ and loops forever; an infinite nonhalting run gives infinitely many two-instruction macros. This proves both stopping directions and divergence.

Represent the two-sided tape after any finite time by the finite interval containing the input and all visited cells, including the scanned cell. A move out of that interval adjoins one blank at the appropriate end; a write changes only its scanned cell. These are exactly the five finite-description cases (write, internal/end right, internal/end left), with nonempty scanned right segment. Extra unvisited blanks do not change the infinite-tape run. Thus the constructed machine has the finite-description interface used by the semigroup construction.

Computing $v$ merely tests whether the input is empty and, in that case, writes one blank symbol in its finite-word encoding. A decider for $T$'s stopping language composed with this procedure would decide membership of every binary $w$ in $HAL{T}_{TM}$ by step 4.1, contradicting [F1]. The same fixed table works for all $w$, including words of lengths zero and one.