A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
Conjugacy of one-dimensional one-sided cellular automata is undecidable
Tekijät: Joonatan Jalonen, Jarkko Kari
Toimittaja: Tjoa A., Bellatreche L., Biffl S., van Leeuwen J., Wiedermann J.
Konferenssin vakiintunut nimi: International Conference on Current Trends in Theory and Practice of Computer Science
Kustantaja: Springer Verlag
Julkaisuvuosi: 2018
Journal: Lecture Notes in Computer Science
Kokoomateoksen nimi: SOFSEM 2018: Theory and Practice of Computer Science
Tietokannassa oleva lehden nimi: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Vuosikerta: 10706
Aloitussivu: 227
Lopetussivu: 238
ISBN: 978-3-319-73116-2
eISBN: 978-3-319-73117-9
ISSN: 0302-9743
DOI: https://doi.org/10.1007/978-3-319-73117-9_16
Rinnakkaistallenteen osoite: https://research.utu.fi/converis/portal/detail/Publication/30428067
Two cellular automata are strongly conjugate if there exists a shift-commuting conjugacy between them. We prove that the following two sets of pairs (F, G) of one-dimensional one-sided cellular automata over a full shift are recursively inseparable:
(i) pairs where F has strictly larger topological entropy than G, and
(ii) pairs that are strongly conjugate and have zero topological entropy.
Because there is no factor map from a lower entropy system to a higher entropy one, and there is no embedding of a higher entropy system into a lower entropy system, we also get as corollaries that the following decision problems are undecidable: Given two one-dimensional one-sided cellular automata F and G over a full shift: 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). It also immediately follows that these results hold for one-dimensional two-sided cellular automata.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
