A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Structure and computability of preimages in the Game of Life
Tekijät: Salo, Ville; Törmä, Ilkka
Kustantaja: Elsevier BV
Kustannuspaikka: AMSTERDAM
Julkaisuvuosi: 2025
Journal: Theoretical Computer Science
Tietokannassa oleva lehden nimi: Theoretical Computer Science
Lehden akronyymi: THEOR COMPUT SCI
Artikkelin numero: 115237
Vuosikerta: 1042
Sivujen määrä: 19
ISSN: 0304-3975
eISSN: 1879-2294
DOI: https://doi.org/10.1016/j.tcs.2025.115237
Verkko-osoite: https://doi.org/10.1016/j.tcs.2025.115237
Rinnakkaistallenteen osoite: https://research.utu.fi/converis/portal/detail/Publication/491819155
Conway's Game of Life is a two-dimensional cellular automaton. As a dynamical system, it is well-known to be computationally universal, i.e. capable of simulating an arbitrary Turing machine. We show that in a sense taking a single backwards step of the Game of Life is a computationally universal process, by constructing patterns whose preimage computation encodes an arbitrary circuit-satisfaction problem, or, equivalently, any tiling problem. As a corollary, we obtain for example that the set of orphans is coNP-complete, exhibit a 6210 x 37800-periodic configuration whose preimage is nonempty but contains no periodic configurations, and prove that the existence of a preimage for a periodic point is undecidable. Our constructions were obtained by a combination of computer searches and manual design.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
