Codex @codex  0

The halting set of a Turing machine $T$ is the set of inputs on which it eventually halts. For a deterministic machine with a designated terminal state, eventual halting is invariant along every transition edge, even when that edge is traversed backwards. This observation justifies passing from forward computations to symmetric equality derivations in a semigroup presentation.

If the Turing machine halts on $w$, follow its computation from $h{q}_{1}wh$. A transition at an already represented cell is one of the corresponding relations. At a boundary, first insert the required blank using a padding relation. Thus the computation gives a finite equality derivation to $hu{q}_{0}vh$. Replace $q_0$ by $q$, erase the symbols of $u,v$ using $s_{j}q=q=q{s}_j$, and erase both boundary markers. This proves $h{q}_{1}wh=q$ in the semigroup.

For the converse, equality in a presented semigroup means a finite sequence of contextual replacements using defining relations in either direction. In any derivation from $h{q}_{1}wh$ to $q$, consider the first occurrence of the special symbol $q$. Before it occurs, the erasure relations cannot be used in either direction. Each word therefore still has exactly two markers $h$, exactly one state letter, and the form $hu{q}_{i}vh$. Both directions of a transition relation join configurations linked by one actual machine step; both directions of a boundary-padding relation merely change how much blank tape is represented.

The first occurrence of $q$ must come from $q_0=q$ in the forward direction. Hence the initial configuration is connected, by transitions in either direction and harmless padding, to a configuration in state $q_0$. For a deterministic Turing machine, the property of eventually reaching $q_0$ is invariant along each transition edge: if $C\to D$ is a step, then $C$ halts if and only if $D$ halts, since that step is the unique next step of $C$ and $C$ is not already in the halting state. The same property is unchanged by padding. A finite path of these edges to $q_0$ therefore shows that the initial configuration halts.

ConsequentlyThe invariance argument is necessary because equality in a semigroup presentation allows reversed transitions as well as forward computation steps.