Document Open Access Logo

What Can Oracles Teach Us About the Ultimate Fate of Life?

Authors Ville Salo , Ilkka Törmä

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.131.pdf
  • Filesize: 1.12 MB
  • 20 pages

Document Identifiers

Author Details

Ville Salo
  • Department of Mathematics and Statistics, University of Turku, Finland
Ilkka Törmä
  • Department of Mathematics and Statistics, University of Turku, Finland

Funding

  • Salo, Ville: Research supported by Academy of Finland grant 2608073211.

Acknowledgements

We thank the anonymous referees for their useful suggestions, and the nice people of the ConwayLife forum for their interest.

Cite AsGet BibTex

Ville Salo and Ilkka Törmä. What Can Oracles Teach Us About the Ultimate Fate of Life?. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 131:1-131:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ICALP.2022.131

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Formal languages and automata theory
Keywords
  • Game of Life
  • cellular automata
  • limit set
  • symbolic dynamics

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. Nathalie Aubrun and Mathieu Sablik. Simulation of effective subshifts by two-dimensional subshifts of finite type. Acta Appl. Math., 126(1):35-63, August 2013. URL: https://doi.org/10.1007/s10440-013-9808-5.
  2. Robert Berger. The undecidability of the domino problem. Mem. Amer. Math. Soc. No., 66, 1966. 72 pages. Google Scholar
  3. François Blanchard. Topological chaos: what may this mean? Journal of Difference Equations and Applications, 15(1):23-46, 2009. URL: https://doi.org/10.1080/10236190802385355.
  4. Mike Boyle, Ronnie Pavlov, and Michael Schraudner. Multidimensional sofic shifts without separation and their factors. Transactions of the American Mathematical Society, 362(9):4617-4653, 2010. URL: https://doi.org/10.1090/s0002-9947-10-05003-8.
  5. John H. Conway. Email to Dean Hickerson. Private email group LifeCA, 1992. Provided by Dave Greene. Google Scholar
  6. Karel Culik, II, Jan Pachl, and Sheng Yu. On the limit sets of cellular automata. SIAM J. Comput., 18(4):831-842, 1989. URL: https://doi.org/10.1137/0218057.
  7. Oscar Cunningham. Response on ConwayLife forum (username macbi). https://conwaylife.com/forums/viewtopic.php?f=7&t=3180&start=125#p140295. Accessed: 2022-02-09.
  8. Alberto Dennunzio, Enrico Formenti, Darij Grinberg, and Luciano Margara. From Linear to Additive Cellular Automata. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), volume 168 of Leibniz International Proceedings in Informatics (LIPIcs), pages 125:1-125:13, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.125.
  9. Saliha Djenaoui and Pierre Guillon. The generic limit set of cellular automata. Journal of Cellular Automata, 14(5-6):435-477, 2019. URL: https://www.oldcitypublishing.com/journals/jca-home/jca-issue-contents/jca-volume-14-number-5-6-2019/jca-14-5-6-p-435-477/.
  10. Bruno Durand and Zsuzsanna Róka. The game of life: universality revisited. In Cellular automata (Saissac, 1996), volume 460 of Math. Appl., pages 51-74. Kluwer Acad. Publ., Dordrecht, 1999. Google Scholar
  11. Bruno Durand, Andrei Romashchenko, and Alexander Shen. Effective closed subshifts in 1D can be implemented in 2D. In Fields of logic and computation, volume 6300 of Lecture Notes in Comput. Sci., pages 208-226. Springer, Berlin, 2010. Google Scholar
  12. Noam D Elkies. The still-life density problem and its generalizations. arXiv, 1999. URL: http://arxiv.org/abs/math/9905194.
  13. Henryk Fukś. Explicit solution of the cauchy problem for cellular automaton rule. J. Cell. Autom., 12(6):423-444, 2017. URL: http://www.oldcitypublishing.com/journals/jca-home/jca-issue-contents/jca-volume-12-number-6-2017/jca-12-6-p-423-444/.
  14. Martin Gardner. Mathematical Games: The Fantastic Combinations of John Conway’s New Solitaire Game "Life". Scientific American, 223(4):120-123, 1970. Google Scholar
  15. Adam Goucher. Fully self-directed replication. https://cp4space.hatsya.com/2018/11/12/fully-self-directed-replication/. Accessed: 2022-04-20.
  16. Adam Goucher. Response on ConwayLife forum (username calcyman). https://conwaylife.com/forums/viewtopic.php?f=7&t=3180&start=100#p140273. Accessed: 2022-02-09.
  17. Gustav A. Hedlund. Endomorphisms and automorphisms of the shift dynamical system. Math. Systems Theory, 3:320-375, 1969. Google Scholar
  18. Lyman P. Hurd. Formal language characterizations of cellular automaton limit sets. Complex Systems, 1(1):69-80, 1987. Google Scholar
  19. N. Johnston and D. Greene. Conway’s Game of Life: Mathematics and Construction. Lulu.com, 2022. URL: https://books.google.fi/books?id=xSJlEAAAQBAJ.
  20. Jarkko Kari. Universal pattern generation by cellular automata. Theoret. Comput. Sci., 429:180-184, 2012. URL: https://doi.org/10.1016/j.tcs.2011.12.037.
  21. Steve Kass and Kathleen Madden. A sufficient condition for non-soficness of higher-dimensional subshifts. Proceedings of the American Mathematical Society, 141(11):3803-3816, 2013. URL: https://doi.org/10.1090/S0002-9939-2013-11646-1.
  22. Douglas Lind and Brian Marcus. An introduction to symbolic dynamics and coding. Cambridge University Press, Cambridge, 1995. URL: https://doi.org/10.1017/CBO9780511626302.
  23. Ville Lukkarila. Sensitivity and topological mixing are undecidable for reversible one-dimensional cellular automata. J. Cell. Autom., 5(3):241-272, 2010. URL: http://www.oldcitypublishing.com/journals/jca-home/jca-issue-contents/jca-volume-5-number-3-2010/jca-5-3-p-241-272/.
  24. Alejandro Maass. On the sofic limit sets of cellular automata. Ergodic Theory and Dynamical Systems, 15, 1995. URL: https://doi.org/10.1017/S0143385700008609.
  25. John Milnor. On the concept of attractor. Communications in Mathematical Physics, 99(2):177-195, 1985. URL: https://doi.org/10.1007/BF01212280.
  26. MiniSat 2.2. http://minisat.se/. Accessed: 2022-02-09.
  27. Period-48 glider gun - LifeWiki. https://conwaylife.com/wiki/Period-48_glider_gun. Accessed: 2022-02-09.
  28. PySAT 0.1.7.dev15. https://pysathq.github.io/. Accessed: 2022-02-09.
  29. Quadri-Snark - LifeWiki. https://conwaylife.com/wiki/Quadri-Snark. Accessed: 2022-02-09.
  30. Ville Salo and Ilkka Törmä. Game of Life agars. https://github.com/ilkka-torma/gol-agars, 2022. GitHub repository.
  31. Robert Wainwright. Lifeline vol. 6, 1972. Google Scholar
  32. Hao Wang. Proving theorems by pattern recognition II. Bell System Technical Journal, 40:1-42, 1961. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact