Undecidable word problem in subshift automorphism groups

Pierre Guillon (1) , Emmanuel Jeandel (2) , Jarkko Kari (3) , Pascal Vanier (4)

1 I2M - Institut de Mathématiques de Marseille
2 MOCQUA - Designing the Future of Computational Models
3 University of Turku
4 LACL - Laboratoire d'Algorithmique Complexité et Logique

This article studies the complexity of the word problem in groups of automorphisms of subshifts. We show in particular that for any Turing degree, there exists a subshift whose automorphism group contains a subgroup whose word problem has exactly this degree.

Domaines: Complexité [cs.CC]; Systèmes dynamiques [math.DS]; Théorie des groupes [math.GR]

Pierre Guillon, Emmanuel Jeandel, Jarkko Kari, Pascal Vanier. Undecidable word problem in subshift automorphism groups. Computer Science in Russia 2019, Jul 2019, Novosibirsk, Russia. ⟨hal-01862896v2⟩