= Solution
The base <free product> for the <group encoding of a modular machine> is
$$
\boxed{K=\langle x,y,t\mid xy=yx\rangle\cong\mathbb Z^2*\mathbb Z,\qquad
t(r,s)=x^{-r}y^{-s}t x^r y^s.}
$$
The letters $x,y$ generate the first factor, and $t$ generates the second. Let $T_K$ be the <kernel> of the <group homomorphism> $K\to\langle x,y\rangle\cong\mathbb Z^2$ that kills $t$. Then
$$
T_K=\langle t(r,s):r,s\in\mathbb Z\rangle
$$
is a <free group> with this displayed <free basis of a group>. Indeed every word in $K$ can be rewritten as a product of such conjugates followed by an element of $\langle x,y\rangle$, so they generate the kernel. A freely reduced product of these conjugates is nontrivial by the <normal form theorem for a free product>: after combining adjacent occurrences of the same conjugate, different successive indices give a nonzero intervening $x,y$-syllable. Thus there is no relation among the proposed basis elements.
For clarity, a <modular machine> of modulus $m>1$ has at most one instruction for each residue pair $(a,b)$, with $0\le a,b<m$ and $0\le c<m^2$. Its right and left transitions are respectively
$$
(mu+a,mv+b)\longmapsto(m^2u+c,v),\qquad
(mu+a,mv+b)\longmapsto(u,m^2v+c).
$$
Its <halting set at a designated terminal configuration> $H_0(\mathcal M)$ consists of the nonnegative pairs whose forward computation reaches $(0,0)$, including $(0,0)$ itself. These formulas explain the exponents in the associated-subgroup maps below.
Back to article page
