= Solution
Introduce <stable letters> $r_i$ for $i\in I$ and $\ell_j$ for $j\in J$, using $r_i^{-1}(\cdot)r_i$ and $\ell_j^{-1}(\cdot)\ell_j$ to implement the maps. Thus $K_{\mathcal M}$ is the multiple <HNN extension> of $K$ with the finite presentation
$$
\begin{aligned}
K_{\mathcal M}=\langle x,y,t,r_i,\ell_j\mid\;&[x,y]=1,\\
&r_i^{-1}x^mr_i=x^{m^2},\quad r_i^{-1}y^mr_i=y,\quad
r_i^{-1}t(a_i,b_i)r_i=t(c_i,0),\\
&\ell_j^{-1}x^m\ell_j=x,\quad\ell_j^{-1}y^m\ell_j=y^{m^2},\quad
\ell_j^{-1}t(a_j,b_j)\ell_j=t(0,c_j)\rangle.
\end{aligned}
$$
Here each family ranges over its finite instruction set. The enlarged subgroup denoted by $\langle t\rangle'$ is
$$
\boxed{L=\langle t\rangle'=\langle t,r_i,\ell_j:i\in I,j\in J\rangle\le K_{\mathcal M}.}
$$
The prime means this enlarged subgroup, not the <commutator subgroup> or the unrestricted <normal closure> of $t$.
The key relationship is
$$
\boxed{(r,s)\in H_0(\mathcal M)\iff t(r,s)\in L\qquad(r,s\ge0).}
$$
Here is a justification that also identifies the relevant intersection. Set
$$
T_H=\langle t(r,s):(r,s)\in H_0(\mathcal M)\rangle\le T_K,
\qquad B_H=\langle T_H,r_i,\ell_j\rangle.
$$
The basis calculation in the preceding part shows that intersections of $T_H$ with associated subgroups are generated by exactly the halting basis elements whose indices satisfy the appropriate congruences. Since the machine is deterministic and $(0,0)$ is terminal, halting at $(0,0)$ is equivalent for the two ends of every instruction edge. Therefore $\phi_i$ and $\varphi_j$ map these intersections onto the corresponding intersections in their targets. The same assertion holds on the integer lattices after declaring pairs with a negative coordinate nonhalting: the bounds on $a,b,c$ imply that each coordinate's sign is preserved by a transition and its inverse.
Apply <Britton's lemma> to a word in $B_H$ which represents an element of $K$. If it has stable letters, it must have a pinch. The base coefficient of that pinch lies in $T_H$ and an associated subgroup, and the intersection property just proved makes its transported image lie in $T_H$ again. Successive pinch removals therefore keep all base coefficients in $T_H$, and eventually remove every stable letter. It follows that
$$
K\cap B_H=T_H.
$$
Finally, $t=t(0,0)$ belongs to $T_H$, so $L\subseteq B_H$. In the opposite direction, induction backwards along any computation ending at $(0,0)$ shows that every halting basis element lies in $L$: if $t(r',s')$ for the next configuration is in $L$, then the transition identity expresses $t(r,s)$ as $r_it(r',s')r_i^{-1}$ or $\ell_jt(r',s')\ell_j^{-1}$. Thus $B_H=L$ and
$$
K\cap L=T_H.
$$
Because $T_H$ is generated by a subset of a <free basis of a group> of $T_K$, a single basis element $t(r,s)$ belongs to it exactly when $(r,s)$ is a halting index. This proves the boxed relationship.
Back to article page
