Structure and computability of preimages in the Game of Life
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908315495170048 |
|---|---|
| author | Salo, Ville Törmä, Ilkka |
| author_facet | Salo, Ville Törmä, Ilkka |
| contents | 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 \times 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_10198 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Structure and computability of preimages in the Game of Life Salo, Ville Törmä, Ilkka Formal Languages and Automata Theory Discrete Mathematics Dynamical Systems 68Q80 (Primary) 37B51 (Secondary) 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 \times 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. |
| title | Structure and computability of preimages in the Game of Life |
| topic | Formal Languages and Automata Theory Discrete Mathematics Dynamical Systems 68Q80 (Primary) 37B51 (Secondary) |
| url | https://arxiv.org/abs/2308.10198 |