On the conjugacy problem of cellular automata

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

Authors Joonatan Jalonen, Jarkko Kari

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

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)

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.

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

Cites work

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

Cited in

(13)

• Solving the parity problem in one-dimensional cellular automata
• scientific article; zbMATH DE number 7339755 (Why is no real title available?)
• Sensitivity and topological mixing are undecidable for reversible one-dimensional cellular automata
• Reversibility and surjectivity problems of cellular automata
• Conjugacy of one-dimensional one-sided cellular automata is undecidable
• Frame cellular automata: Configurations, generating sets and related matroids
• Millions of 5-State $$n^3$$-Real Time Sequence Generators via Local Simulations
• Classification of elementary cellular automata up to topological conjugacy
• Distortion in one-head machines and cellular automata
• Decision problems for cellular automata and their semigroups
• Cellular Automata, the Collatz Conjecture and Powers of 3/2
• On von Neumann regularity of cellular automata
• Computational complexity of \(k\)-block conjugacy

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)