A notion of effectiveness for subshifts on finitely generated groups

Nathalie Aubrun (1) , Sebastián Barbieri (1) , Mathieu Sablik (2)

1 MC2 - Modèles de calcul, Complexité, Combinatoire
2 IMT - Institut de Mathématiques de Toulouse UMR5219

We generalize the classical definition of effectively closed subshift to finitely generated groups. We study classical stability properties of this class and then extend this notion by allowing the usage of an oracle to the word problem of a group. This new class of subshifts forms a conjugacy class that contains all sofic subshifts. Motivated by the question of whether there exists a group where the class of sofic subshifts coincides with that of effective subshifts, we show that the inclusion is strict for several groups, including recursively presented groups with undecidable word problem, amenable groups and groups with more than two ends. We also provide an extended model of Turing machine which uses the group itself as a tape and characterizes our extended notion of effectiveness. As applications of these machines we prove that the origin constrained domino problem is undecidable for any group of the form subject to a technical condition on G and we present a simulation theorem which is valid in any finitely generated group.

Mots clés: Models of computation; Turing machines; Word problems; Symbolic dynamics

Domaines: Systèmes dynamiques [math.DS]; Probabilités [math.PR]; Combinatoire [math.CO]; Complexité [cs.CC]; Informatique et langage [cs.CL]; Mathématique discrète [cs.DM]; Théorie de l'information [cs.IT]; Système multi-agents [cs.MA]

Nathalie Aubrun, Sebastián Barbieri, Mathieu Sablik. A notion of effectiveness for subshifts on finitely generated groups. Theoretical Computer Science, 2017, 661, pp.35-55. ⟨10.1016/j.tcs.2016.11.033⟩. ⟨hal-01970761⟩