Vertaisarvioitu alkuperäisartikkeli tai data-artikkeli tieteellisessä aikakauslehdessä (A1)

On the conjugacy problem of cellular automata

Julkaisun tekijät: Joonatan Jalonen, Jarkko Kari

Kustantaja: Elsevier Inc.

Julkaisuvuosi: 2020

Journal: Information and Computation

Tietokannassa oleva lehden nimi: Information and Computation

ISSN: 0890-5401

eISSN: 1090-2651



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:


pairs where the first cellular automaton has strictly higher entropy than the second one, and


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.

Last updated on 2021-24-06 at 09:19