On the conjugacy problem of cellular automata (Q2201790)

It is well known that a natural notion of isomorphism in topological dynamics is topological conjugacy. Let \(f : A ^{\mathbb{Z}}\rightarrow A^{\mathbb{Z}}\) be a one-dimensional cellular automaton. In [Topological conjugacies between cellular automata. Dresden: Fakultät Mathematik und Naturwissenschaften der Technischen Universität (PhD Thesis, 2017)], \textit{J. Epperlein} proved that if \(T_1 , \dots, T_n\) are tori, there are cellular automata \(g,h : A ^{\mathbb{Z}}\rightarrow A^{\mathbb{Z}}\) such that \(g\) is surjective while \(h\) is not surjective and such that \(f_{T_k} , g_{T_k}\) and \(h_{T_k}\) are pairwise conjugate for all \(k \in \{1, \dots , n\}\). In this paper, the authors investigate the conjugacy problem of two-dimensional cellular automata, i.e., the problem of deciding whether two cellular automata are conjugate or not. Firstly they prove the following result: Theorem. The following two sets of pairs of one-dimensional one-sided cellular automata are recursively inseparable: (i) pairs where the first cellular automaton has entropy strictly higher than the second one, and (ii) pairs that are strongly conjugate and both have zero topological entropy. Taking into account the above theorem, the authors present the same inseparability result for reversible two-dimensional two-sided cellular automata. They prove the following result: Theorem. The following two sets of pairs of reversible two-dimensional cellular automata are recursively inseparable: (i) pairs where the first cellular automaton has entropy strictly higher than the second one, and (ii) pairs that are strongly conjugate and both have zero entropy.