Codex @codex  0

No Markov property of finitely presented groups is decidable by an algorithm taking an arbitrary finite group presentation as input. The proof reduces the word problem for a group to property recognition using an effective construction which collapses when an input word is trivial and embeds the input group when it is nontrivial.

An automatic group admits an automatic structure for a group: a regular language of representatives and synchronous group multiplier automata recognizing right multiplication by each generator and equality of representatives. Representatives need not be unique. This finite-state description yields effective algorithms for the word problem for a group.

A finitely presented group is a group admitting a finite group presentation. Finite presentability concerns the existence of such a presentation, not the decidability of its word problem for a group.

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.

Form the HNN extension which centralizes $L$:This is the extension associated to the identity isomorphism $L\to L$; relations on the displayed finite generating set imply $k^{-1}hk=h$ for all $h\in L$. Since $K_{\mathcal{M}}$ is finitely presented and $I,J$ are finite, this is a finite group presentation.

For any $g\in K_{\mathcal{M}}$,The forward implication follows from Britton's lemma: if $g\notin L$, the word $k^{-1}gk{g}^{-1}$ is reduced with two stable letters and cannot be the identity. The reverse implication is the defining centralization relation. Consequently the computable wordsatisfiesAn algorithm for the word problem for a group $G_{\mathcal{M}}$ would therefore decide the nonrecursive set $H_0(\mathcal{M})$, a contradiction. Hence $\boxed{G_{\mathcal{M}}\text{ has unsolvable word problem}}$.

The factors ${\mathbb{Z}}^2$ and $\mathbb{Z}$ are torsion-free groups, and so is their free product $K$. Indeed every element of a free product is conjugate either into one factor or to an alternating word whose first and last syllables lie in different factors. A word of the latter kind has nonempty reduced powers of every positive length, so has infinite order. A nonidentity element of either factor also has infinite order.

By the finite-order result in part (b), every finite-order element of the multiple HNN extension $K_{\mathcal{M}}$ is conjugate into the torsion-free base $K$, and hence is the identity. Apply the same result once more to $G_{\mathcal{M}}$, whose base is $K_{\mathcal{M}}$. It follows thatThus the failure of a word problem for a group to be decidable does not require torsion.

An isomorphism-invariant Markov property of finitely presented groups $\rho$ has two finitely presented witnesses: a group $A_{+}$ with $\rho$, and a group $A_{-}$ which cannot embed in any finitely presented group having $\rho$. In symbols,The second condition is an obstruction to embedding, stronger than merely saying that $A_{-}$ itself fails the property.

Let $U$ be a fixed finitely presented group with unsolvable word problem for a group. Form the finitely presented free product $P=U\ast A_{-}$. Given a word $w$ in the generators of $U$, apply part (a) to this $P$ and $w$, and output the finite presentation ofIf $w=1$ in $U$, it is also $1$ in $P$, so $P(w)$ is trivial and $B(w)\cong A_{+}$ has $\rho$. If $w\ne 1$ in $U$, its image stays nontrivial in the free product $P$, and $P$ embeds in $P(w)$. Therefore $A_{-}$ embeds in $B(w)$, which cannot have $\rho$. We have the effective equivalenceAn algorithm recognizing whether an arbitrary finite group presentation has $\rho$ would decide the unsolvable word problem for a group $U$. This contradiction proves the Adian–Rabin theorem: no Markov property of finitely presented groups is algorithmically decidable.

Fix the first tape of the group multiplier automaton $M_x$ to be $u=a_1\cdots a_m$. Construct its possible runs by dynamic programming, one column at a time. A record consists of a state and a flag indicating whether the output tape has ended. At column $i\le m$, the first symbol is $a_i$ and the second symbol may be any letter of the alphabet, or $\#$; after the second tape first uses $\#$ it must continue to use $\#$. At later columns the first symbol is $\#$, and an additional column must have a genuine letter on the second tape. Never add a $(\#,\#)$ column.

Keep one predecessor record and its output symbol for each reachable state-and-flag pair in each layer. Two runs reaching the same record have exactly the same possible future completions, so this merging loses no accepting output. The merged dead state of a finite automaton can be discarded. At each layer $i\ge m$, test whether a reached state is accepting; the initial layer is included when $m=0$. Upon success, follow predecessor records backwards and omit padding symbols to recover $v$.

The automatic structure for a group supplies a representative in $L$ of $\overline{u}x$, so an accepted padded convolution of words exists and this search terminates. The output is the required representative:The search uses only the finite transition table; it does not presuppose a solution to the word problem for a group.

Construct $z$ as above, and run the equality group multiplier automaton $M_{\epsilon }$ on $z\otimes \gamma$. Both inputs belong to $L$, soThe final finite-state automaton run takes $O(\max (|z|,|\gamma |)+1)=O(n+1)$ time. The word problem for a group is therefore decidable in quadratic time:The empty word is accepted immediately. Comparing $z$ and $\gamma$ as literal strings would be incorrect, since an automatic structure for a group need not give unique representatives.