Undecidable word problem in subshift automorphism groups

08/28/2018

∙

by   Pierre Guillon, et al.

∙

0

∙

share

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.