The group of reversible Turing machines and the torsion problem for $\Aut(A^{\mathbb{Z})$ and related topological fullgroups.

Abstract:

We introduce the group $RTM(G,n,k)$ composed of abstract Turing machines which use the group $G$ as a tape, use an alphabet of $n$ symbols, $k$ states and act as a bijection on the set of configurations. These objects can be represented both as cellular automata and in terms of continous functions and cocycles. The study of this group structure yields interesting results concerning computability properties of some well studied groups such as $\Aut(A^{\mathbb{Z})$ and the topological full group of the two dimensional full shift.
More precisely, given a finitely generated group $G = \langle S \rangle$, we define its torsion problem as the language formed by the words $w \in S^*$ which represent torsion elements in $G$. We show that the two examples mentioned above contain finitely generated subgroups for which  the torsion problem is undecidable.

Posted on Dec 14, 2016 in Dynamical Systems, Seminars