License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2022.131
URN: urn:nbn:de:0030-drops-164721
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16472/
Salo, Ville ;
Törmä, Ilkka
What Can Oracles Teach Us About the Ultimate Fate of Life?
Abstract
We settle two long-standing open problems about Conway’s Life, a two-dimensional cellular automaton. We solve the Generalized grandfather problem: for all n ≥ 0, there exists a configuration that has an nth predecessor but not an (n+1)st one. We also solve (one interpretation of) the Unique father problem: there exists a finite stable configuration that contains a finite subpattern that has no predecessor patterns except itself. In particular this gives the first example of an unsynthesizable still life. The new key concept is that of a spatiotemporally periodic configuration (agar) that has a unique chain of preimages; we show that this property is semidecidable, and find examples of such agars using a SAT solver.
Our results about the topological dynamics of Game of Life are as follows: it never reaches its limit set; its dynamics on its limit set is chain-wandering, in particular it is not topologically transitive and does not have dense periodic points; and the spatial dynamics of its limit set is non-sofic, and does not admit a sublinear gluing radius in the cardinal directions (in particular it is not block-gluing). Our computability results are that Game of Life’s reachability problem, as well as the language of its limit set, are PSPACE-hard.
BibTeX - Entry
@InProceedings{salo_et_al:LIPIcs.ICALP.2022.131,
author = {Salo, Ville and T\"{o}rm\"{a}, Ilkka},
title = {{What Can Oracles Teach Us About the Ultimate Fate of Life?}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {131:1--131:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-235-8},
ISSN = {1868-8969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16472},
URN = {urn:nbn:de:0030-drops-164721},
doi = {10.4230/LIPIcs.ICALP.2022.131},
annote = {Keywords: Game of Life, cellular automata, limit set, symbolic dynamics}
}
