MathDBUndecidability of doubly periodic Gardens of Eden in the Game of Life
Undecidability of doubly periodic Gardens of Eden in the Game of Life
A doubly periodic configuration in the Game of Life is a configuration with two independent spatial periods, and a Garden of Eden is a configuration with no preimage. Undecidability conjecture. The set of doubly periodic Gardens of Eden for the Game of Life is undecidable. If true, this would imply that not all semilinear configurations admit semilinear preimages. The paper presents this as an additional open decision problem.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Ville Salo and Ilkka Törmä, “Gardens of Eden in the Game of Life”, arXiv:1912.00692 (2019).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.