No Tits alternative for cellular automata

  • Ville Salo

    University of Turku, Finland
No Tits alternative for cellular automata cover

A subscription is required to access this article.


We show that the automorphism group of a one-dimensional full shift (the group of reversible cellular automata) does not satisfy the Tits alternative. That is, we construct a finitely-generated subgroup which is not virtually solvable yet does not contain a free group on two generators. We give constructions both in the two-sided case (spatially acting group ) and the one-sided case (spatially actingmonoid , alphabet size at least eight). Lack of Tits alternative follows for several groups of symbolic (dynamical) origin: automorphism groups of two-sided one-dimensional uncountable sofic shifts, automorphism groups of multidimensional subshifts of finite type with positive entropy and dense minimal points, automorphism groups of full shifts over non-periodic groups, and the mapping class groups of two-sided one-dimensional transitive SFTs. We also show that the classical Tits alternative applies to one-dimensional (multi-track) reversible linear cellular automata over a finite field.

Cite this article

Ville Salo, No Tits alternative for cellular automata. Groups Geom. Dyn. 13 (2019), no. 4, pp. 1437–1455

DOI 10.4171/GGD/529