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 admitsa translation-like action by $\mathbb{Z}$, and that this action can be takento 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 actionson groups and graphs. We prove that every finitely generated infinitegroup with decidable word problem admits a translation-like actionby $\mathbb{Z}$ which is computable, and satisfies an extra condition whichwe call decidable orbit membership problem. As a nontrivial application of our results, we prove that for everyfinitely generated infinite group with decidable word problem, effectivesubshifts attain all ${\Pi }_1^0$ Medvedev degrees. This extends a classification proved by Joseph Miller for ${\mathbb{Z}}^d,$ $d\ge 1$.

arXiv commentRevised version, but with one important fix in the proof of Lemma 3.2

Cited by in corpus (1)

• Paths, Ends and The Separation Problem for Infinite Graphs