The word and order problems for self-similar and automata groups (Q784904)

The article concerns undecidability results for self-similar groups (Theorem A), automata groups (Theorem B), and contracting groups (Theorem C), and also offers different specific versions of the core theorems for the different classes of groups. Recall that \textit{self-similar} groups (also called \textit{functionally-recursive} groups) are those groups \(G\) so that there is a faithful action of \(G\) on a set \(\mathcal{A}^*\) of finite words over some finite alphabet \(\mathcal{A}\), where this action is induced by some map \(\overline{\Phi}:\mathcal{A}\times G\to G\times\mathcal{A}\) and a rule \[ (a_1a_2\dots a_m)^g=a_1'(a_2a_3\dots a_m)^{g'} \] with \((g',a_1')=\overline{\Phi}(a_1,g)\). The class of self-similar groups is large, e.g., containing \textit{V. Nekrashevych}'s iterated monodromy groups [Lond. Math. Soc. Lect. Note Ser. 387, 41--93 (2011; Zbl 1235.37016)]. In the further case that \(G\) is a self-similar group generated as a semigroup by a finite set \(S\) of generators (e.g., if \(S\) is inverse closed) we obtain a lift \(\Phi\) of \(\overline{\Phi}\) obtained by restricting to the generators of \(G\): that is, the map \(\overline{\Phi}:\mathcal{A}\times S\to F_S\times\mathcal{A}\) for \(F_S\) the free monoid on \(S\). The map \(\Phi\) is a finite set of combinatorial data that determines the action of \(G\) on \(\mathcal{A}^*\), and hence determines \(G\), and which opens the door for investigating decidability properties for these groups. In this case, we say that \(G\) is presented by \(\Phi\) and write \(G=\langle\Phi\rangle\). The first theorem is in this context: Theorem A. There is no algorithm that, given \(\overline{\Phi}:\mathcal{A}\times S\to F_S\times\mathcal{A}\) and \(s\in S\), determines if \(s=1\) in \(\langle \Phi\rangle\). If we now assume that the length of \(g'\) is at most the length of \(g\) in the \(S\) generating set, and if we ensure that the identity \(1\) is in the set \(S\) by adding it in if necessary, then \(G=\langle \Phi\rangle\) becomes an \textit{automata group}. In this case, the map \(\Phi\) takes the form \(\overline{\Phi}:\mathcal{A}\times S\to S\times\mathcal{A}\). The class of automata groups remains quite mysterious while containing many groups of abiding research interest (e.g., finitely generated linear groups [\textit{A. M. Brunner} and \textit{S. Sidki}, Int. J. Algebra Comput. 8, No. 1, 127--139 (1998; Zbl 0923.20023)] as well as groups of intermediate growth [\textit{R. I. Grigorchuk}, Sov. Math., Dokl. 28, 23--26 (1983; Zbl 0547.20025); translation from Dokl. Akad. Nauk SSSR 271, 30--33 (1983)]). In this context we have: Theorem B. There is no algorithm that, given \(\overline{Phi}:\mathcal{A}\times S\to S\times\mathcal{A}\) and \(s \in S\), determines the order of \(s\) in \(\langle \Phi\rangle\), namely the cardinality of \(\langle s\rangle\). Giving a (new) solution to Question 7.2.1(a) of [\textit{R. I. Grigorchuk} et al., in: Dynamical systems, automata, and infinite groups. Transl. from the Russian. Moscow: MAIK Nauka/Interperiodica Publishing. 128--203 (2000; Zbl 1155.37311); translation from Tr. Mat. Inst. Steklova 231, 134--214 (2000)] (\textit{P. Gillibert} announced a solution to this question in July 2017 for automata groups, which appears in [J. Algebra 497, 363--392 (2018; Zbl 1427.20040)], while \textit{J. Belk} and \textit{C. Bleak} show the problem is undecidable for groups generated by initial asynchronous transducers in [Trans. Am. Math. Soc. 369, No. 5, 3157--3172 (2017; Zbl 1364.20015)] (the original context of the question)). In fact, the article under current review shows the further undecidability results: given \(a\in A\), \(s\in S\) and the induced action of \(\langle \Phi\rangle\) on the Cantor space \(A^\omega\), in the context of Theorem A one cannot determine if \(a^\omega\) is fixed by \(s\), and in the context of Theorem B one cannot determine the cardinality of the orbit of \(a^\omega\) under the action of \(\langle s\rangle\). Finally, if we assume \(G\) is finitely generated, self-similar, and that there are constants \(\lambda<1\) and \(C\) with \(|g'|\leq \lambda\cdot|g| + C\) for all \(g\in G\) then we say that \(G\) is a \textit{contracting group}. In this context if we replace \(S\) by all words of length less than \(C/(1-\lambda)\) over the original \(S\) then we have \(|g'|\leq |g|\), so these groups are again automata groups. The final result (Theorem C) is that the order and orbit order problems which are undecidable for automata groups (the two versions of Theorem B mentioned above) remain undecidable even in this more restricted subclass of groups. Overall, the writing and proofs are clear and the results are very strong. The main method is to encode Minsky machines in self-similar groups but the authors also give an explanation of Theorem B using tilings.