zbMATH — the first resource for mathematics

Undecidable word problem in subshift automorphism groups. (English) Zbl 07121066
van Bevern, RenĂ© (ed.) et al., Computer science – theory and applications. 14th international computer science symposium in Russia, CSR 2019, Novosibirsk, Russia, July 1–5, 2019. Proceedings. Cham: Springer (ISBN 978-3-030-19954-8/pbk; 978-3-030-19955-5/ebook). Lecture Notes in Computer Science 11532, 180-190 (2019).
Summary: This article studies the complexity of the word problem in groups of automorphisms (or reversible cellular automata) of subshifts. We show in particular that for any computably enumerable Turing degree, there exists a (two-dimensional) subshift of finite type whose automorphism group contains a subgroup whose word problem has exactly this degree. In particular, there are such subshifts of finite type where this problem is uncomputable. This remains true in a large setting of subshifts over groups.
For the entire collection see [Zbl 1416.68013].
68Qxx Theory of computing
Full Text: DOI