Search Results

Documents authored by Salo, Ville

Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2022.131
What Can Oracles Teach Us About the Ultimate Fate of Life?

Authors: Ville Salo and Ilkka Törmä

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

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.
Cite as

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)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.ICALP.2022.131},
  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}
}
Document
DOI: 10.4230/OASIcs.AUTOMATA.2021.11
Von Neumann Regularity, Split Epicness and Elementary Cellular Automata

Authors: Ville Salo

Published in: OASIcs, Volume 90, 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)

Abstract
We show that a cellular automaton on a mixing subshift of finite type is a von Neumann regular element in the semigroup of cellular automata if and only if it is split epic onto its image in the category of sofic shifts and block maps. It follows from [S.-Törmä, 2015] that von Neumann regularity is decidable condition, and we decide it for all elementary CA.
Cite as

Ville Salo. Von Neumann Regularity, Split Epicness and Elementary Cellular Automata. In 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021). Open Access Series in Informatics (OASIcs), Volume 90, pp. 11:1-11:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{salo:OASIcs.AUTOMATA.2021.11,
  author =	{Salo, Ville},
  title =	{{Von Neumann Regularity, Split Epicness and Elementary Cellular Automata}},
  booktitle =	{27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
  pages =	{11:1--11:10},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-189-4},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{90},
  editor =	{Castillo-Ramirez, Alonso and Guillon, Pierre and Perrot, K\'{e}vin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.AUTOMATA.2021.11},
  URN =		{urn:nbn:de:0030-drops-140209},
  doi =		{10.4230/OASIcs.AUTOMATA.2021.11},
  annote =	{Keywords: cellular automata, elementary cellular automata, von Neumann regularity, split epicness}
}
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 About DROPS Imprint Privacy Contact