Modular machine ($\mathcal{M}$)

A modular machine of modulus $m>1$ acts on pairs in ${\mathbb{N}}^2$. Each instruction $(a,b,c,R)$ or $(a,b,c,L)$ has $0\le a,b<m$ and $0\le c<m^2$, and at most one instruction is assigned to each residue pair $(a,b)$. The two transition types are $(mu+a,mv+b)\mapsto (m^{2}u+c,v)$ and $(mu+a,mv+b)\mapsto (u,m^{2}v+c)$. These finite arithmetic operations can encode a Turing machine; a designated terminal configuration can have a nonrecursive halting set.

A modular machine can be encoded by HNN extensions of $K={\mathbb{Z}}^2\ast ⟨t⟩$. The kernel of $K\to {\mathbb{Z}}^2$ has a free basis of a group $t(r,s)=x^{-r}{y}^{-s}t{x}^r{y}^s$. Associated-subgroup maps send these basis elements according to the two arithmetic transition types. In the resulting group, membership of $t(r,s)$ in the subgroup generated by $t$ and the instruction stable letters is equivalent to $(r,s)\in H_0(\mathcal{M})$. One more HNN extension centralizes that finitely generated subgroup, converting membership to equality and hence to the word problem for a group.

For a modular machine whose $(0,0)$ is terminal, $H_0(\mathcal{M})$ is the set of configurations whose forward computation reaches exactly $(0,0)$, including the zero-step computation there. It may differ from the set of configurations stopping at any terminal configuration. Determinism makes membership invariant along each instruction edge.