On the conjugacy problem of cellular automata

DOI10.1016/J.IC.2020.104531MaRDI QIDQ2201790zbMATH OpenOpenAlexFDO

Publication date 17 September 2020

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1906.00796

cellular automata conjugacy undecidability

Dynamical aspects of cellular automata (37B15) Topological and differentiable equivalence, conjugacy, moduli, classification of dynamical systems (37C15) Cellular automata (computational aspects) (68Q80)

Abstract: Cellular automata are topological dynamical systems. We consider the problem of deciding whether two cellular automata are conjugate or not. We also consider deciding strong conjugacy, that is, conjugacy by a map that commutes with the shift maps. We show that the following two sets of pairs of one-dimensional one-sided cellular automata are recursively inseparable: (i) pairs where the first cellular automaton has strictly higher entropy than the second one, and (ii) pairs that are strongly conjugate and both have zero topological entropies. This implies that the following decision problems are undecidable: Given two one-dimensional one-sided cellular automata

F

and

G

: Are

F

and

G

conjugate? Is

F

a factor of

G

? Is

F

a subsystem of

G

? All of these are undecidable in both strong and weak variants (whether the homomorphism is required to commute with the shift or not, respectively). We also prove the same results for reversible two-dimensional cellular automata.

Review text

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.

Recommendations

Cites work

Cited in

(14)

This page was built for publication: On the conjugacy problem of cellular automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2201790)