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

Abstract

We show that every infinite, locally finite, and connected graph admits a translation-like action by $\mathbb{Z}$, and that this action can be taken to be transitive exactly when the graph has either one or two ends. The actions constructed satisfy $d(v,v\ast 1)\le 3$ for every vertex $v$. This strengthens a theorem by Brandon Seward. We also study the effective computability of translation-like actions on groups and graphs. We prove that every finitely generated infinite group with decidable word problem admits a translation-like action by $\mathbb{Z}$ which is computable and satisfies an extra condition which we call decidable orbit membership problem. As a nontrivial application of our results, we prove that for every finitely generated infinite group with decidable word problem, effective subshifts attain all ${\Pi }_1^0$ Medvedev degrees. This extends a classification proved by Joseph Miller for ${\mathbb{Z}}^d,d\ge 1$.