Search Results

Documents authored by Törmä, Ilkka

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
Invited Talk
DOI: 10.4230/OASIcs.AUTOMATA.2021.4
Fixed Point Constructions in Tilings and Cellular Automata (Invited Talk)

Authors: Ilkka Törmä

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

Abstract
The fixed point construction is a method for designing tile sets and cellular automata with highly nontrivial dynamical and computational properties. It produces an infinite hierarchy of systems where each layer simulates the next one. The simulations are implemented entirely by computations of Turing machines embedded in the tilings or spacetime diagrams. We present an overview of the construction and list its applications in the literature.
Cite as

Ilkka Törmä. Fixed Point Constructions in Tilings and Cellular Automata (Invited Talk). 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. 4:1-4:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{torma:OASIcs.AUTOMATA.2021.4,
  author =	{T\"{o}rm\"{a}, Ilkka},
  title =	{{Fixed Point Constructions in Tilings and Cellular Automata}},
  booktitle =	{27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
  pages =	{4:1--4:13},
  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.4},
  URN =		{urn:nbn:de:0030-drops-140135},
  doi =		{10.4230/OASIcs.AUTOMATA.2021.4},
  annote =	{Keywords: Tilings, Wang tiles, cellular automata, multidimensional symbolic dynamics, self-simulation}
}
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