Translation-like actions by \(\mathbb{Z} \), the subgroup membership problem, and Medvedev degrees of effective subshifts (Q6851207)

The paper studies translation-like actions by \(\mathbb Z\) on graphs and groups and analyzes algorithmic aspects of these actions together with applications to symbolic dynamics. A translation-like action of a group \(H\) on a metric space \((X,d)\) is a free action for which the displacement \(d(x,x\cdot h)\) is uniformly bounded for every \(h\in H\).\N\NOne of the main results proves that every infinite, connected, locally finite graph admits a translation-like action by \(\mathbb Z\). Moreover, the action can be chosen transitive if and only if the graph has either one or two ends and it can be arranged so that \(d(v,v\cdot1)\le3\) for every vertex \(v\). This strengthens a result of \textit{B. Seward} [Geom. Topol. 18, No. 1, 179--210 (2014; Zbl 1338.20041)], where the hypothesis required uniformly bounded vertex degree.\N\NThe paper also studies computability properties of such actions. It is shown that every finitely generated infinite group with decidable word problem admits a computable translation-like action by \(\mathbb Z\) with decidable orbit membership problem. As an application, the author studies Medvedev degrees of effective subshifts. Using computable translation-like actions, it is proved that for every finitely generated infinite group with decidable word problem the class of Medvedev degrees of effective subshifts coincides with the class of all \(\Pi^0_1\) Medvedev degrees, extending a result of \textit{J. S. Miller} [Proc. Am. Math. Soc. 140, No. 5, 1617--1622 (2012; Zbl 1246.37025)] for \(\mathbb Z^d\).