Translation-like actions by Z, the subgroup membership problem, and Medvedev degrees of effective subshifts

We show that every infinite, locally finite, and connected graph admits a translation-like action by 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,v1)≤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 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 Π₁⁰ Medvedev degrees. This extends a classification proved by Joseph Miller for Zᵈ,\,d≥1 .