Boone semigroup histories detect halting

A write replacement in either direction changes the state and its following scanned symbol, retaining the two outer markers and a nonempty right segment. Internal right swaps $q_a{s}_j{s}_{\beta }$ with $s_j{q}_b{s}_{\beta }$; both sides retain a scanned symbol. End right swaps $q_a{s}_{j}h$ with $s_j{q}_b{s}_{0}h$; the displayed $h$ must be the right outer marker, so the inverse deletes exactly the added blank and restores the earlier scanned cell. Internal left swaps $s_{\beta }{q}_a{s}_j$ with $q_b{s}_{\beta }{s}_j$; both sides have a scanned cell. End left swaps $h{q}_a{s}_j$ with $h{q}_b{s}_0{s}_j$; the displayed $h$ must be the left outer marker, and the inverse again restores a nonempty scanned segment. Since there is exactly one state letter, any applicable contextual transition occurs at that state. All five families therefore preserve augmented shape in both directions.

At $q_0$, erasing or inserting the first right tape letter via $q_{0}s=q_0$ preserves augmented shape, including the empty segment. The equation $s{q}_{0}h=q_{0}h$ applies exactly when the right segment is empty, removing or inserting the last left tape symbol. Finally $h{q}_{0}h=q$ changes exactly the whole word: the markers must be the two outer markers and there are no remaining tape symbols. Conversely $q$ occurs alone in the augmented domain and expands to $h{q}_{0}h$. Thus every symmetric derivation starting at $C(w)$ stays in the augmented domain.

At a nonstopping configuration the unique table entry fixes the instruction. The symbol adjacent to the moved side is either a tape symbol or the outer marker, so exactly one internal/end family applies. At $q_0$ with nonempty right tape the unique forward rule erases its first symbol. With empty right tape and nonempty left tape it erases the last left symbol. With both empty it sends $h{q}_{0}h$ to $q$, which has no successor. Thus the oriented graph on augmented configurations has at most one successor per vertex. Self-loops, if present, do not affect this assertion.

If $T$ stops, its finite description history gives the same transition replacements until $hU{q}_{0}Vh$. Erase the $\mathrm{\mid }V\mathrm{\mid }$ right symbols, then the $\mathrm{\mid }U\mathrm{\mid }$ left symbols, then use $h{q}_{0}h=q$. This constructs a finite derivation from $C(w)$ to $q$.

Conversely, suppose $C(w)=q$. Among finite derivations choose one of least length, $z_0=C(w),\dots ,z_n=q$. It has no repeated vertex or self-loop, since deleting the intervening segment would shorten it. The last edge is forward because $q$ has no successor. If any earlier edge were backward, there would be consecutive edges $z_{j-1}\leftarrow z_j\to z_{j+1}$. Uniqueness of the successor would give $z_{j-1}=z_{j+1}$, contrary to minimality. Every edge is therefore forward. The initial state is not $q_0$; reaching $q$ requires first reaching $q_0$, and before that first occurrence all edges are actual machine steps. Thus $T$ stops. Least length is a least natural number of a nonempty set; it uses no arbitrary choice.

Steps 4.1 and 4.2 prove the two implications. For empty input $v(w)=s_0$ supplies the scanned cell; for one-symbol input the end rules apply as specified. Empty cleanup segments were included explicitly, so these cases do not require a stronger invariant.