A1 Journal article – refereed

On the conjugacy problem of cellular automata

List of Authors: Joonatan Jalonen, Jarkko Kari

Publisher: Elsevier Inc.

Publication year: 2020

Journal: Information and Computation

Journal name in source: Information and Computation

ISSN: 0890-5401

eISSN: 1090-2651

DOI: http://dx.doi.org/10.1016/j.ic.2020.104531

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.