Gardens of Eden in the Game of Life

2019/12/02 by Salo, Ville, Törmä, Ilkka
#Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL)

paper · doi:10.48550/arxiv.1912.00692

Abstract

We prove that in the Game of Life, if the thickness-four zero-padding of a rectangular pattern is not an orphan, then the corresponding finite-support configuration is not a Garden of Eden, and that the preimage of every finite-support configuration has dense semilinear configurations. In particular finite-support Gardens of Eden are in co-NP.

Related

• Cultivating the Garden of Eden
• On the Garden of Eden theorem for non-uniform cellular automata
• Structure and computability of preimages in the Game of Life
• What can oracles teach us about the ultimate fate of life?
• Kolmogorov Complexity and the Garden of Eden Theorem