Gardens of Eden in the Game of Life
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.
arXiv comment16 pages + 5 pages of code; some figures