Finding Mona Lisa in the Game of Life
avinayak.github.io
avinayak.github.io
There can be many, many images that evolve into a given target image in one generation.
As an example, you can add any number of “isolated enough” live cells to an image without changing the next generation. Such cells will simply die out.
For any isolated stable pattern that isn’t a garden of Eden (2), you can also either keep the stable pattern or replace it by one of its pre-images.
(1) that’s true, but not the best of arguments. Normally, the existence of gardens of Eden is proven from the existence of patterns that evolve into the same pattern and the pigeonhole principle, as its much easier to find such patterns than to find gardens of Eden.
(2) I’m not sure whether stable gardens of Eden exist, so that requirement maybe superfluous.
Though, a state which is stable, and which no other state leads to it, would be interesting.
Generalizing that notion, I think it would be interesting to take the directed graph of all patterns of a given dimension, turn it into an undirected graph, and look at the distribution of sizes of connected components (a state which is stable, and which has no other state leading into it would be a component of size 1)
If I understand correctly, many states can lead to the desired outcome. But would my suggested approach not simply yield one of the many possible initial Staates?