On the conjugacy problem of cellular automata

DOI10.1016/J.IC.2020.104531zbMATH Open1459.37013arXiv1906.00796OpenAlexW2947207802MaRDI QIDQ2201790FDOQ2201790

Joonatan Jalonen, Jarkko Kari

Publication date: 17 September 2020

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

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.

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

Recommendations

• Conjugacy of one-dimensional one-sided cellular automata is undecidable
• Reversibility and surjectivity problems of cellular automata
• On computing the topological entropy of one-sided cellular automata
• Classification of elementary cellular automata up to topological conjugacy
• Topological dynamics of cellular automata: dimension matters

zbMATH Keywords

cellular automataundecidabilityconjugacy

Mathematics Subject Classification ID

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

Cites Work

• Textile systems for endomorphisms and automorphisms of the shift
• Endomorphisms and automorphisms of the shift dynamical system
• On the Limit Sets of Cellular Automata
• Languages, equicontinuity and attractors in cellular automata
• Title not available (Why is that?)
• Reversibility and surjectivity problems of cellular automata
• Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
• Multidimensional cellular automata: closing property, quasi-expansivity, and (un)decidability issues
• The Nilpotency Problem of One-Dimensional Cellular Automata
• Combinatorial constructions associated to the dynamics of one-sided cellular automata.
• Periodic points for onto cellular automata
• Periodicity and Immortality in Reversible Computing
• Classification of subshifts of finite type
• Finite entropy for multidimensional cellular automata
• Title not available (Why is that?)
• Linear sampling and the ∀∃∀ case of the decision problem
• Shifting and Lifting of Cellular Automata
• Conjugacy of One-Dimensional One-Sided Cellular Automata is Undecidable
• Permutive one-way cellular automata and the finiteness problem for automaton groups

Cited In (7)

• Title not available (Why is that?)
• Solving the parity problem in one-dimensional cellular automata
• Reversibility and surjectivity problems of cellular automata
• Frame cellular automata: Configurations, generating sets and related matroids
• Millions of 5-State $$n^3$$-Real Time Sequence Generators via Local Simulations
• On von Neumann regularity of cellular automata
• Cellular Automata, the Collatz Conjecture and Powers of 3/2

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)