4 ms·

Would it be possible to create the inverse rules of the game of life and then starting from the image and simply go backwards until it is reasonably scrambled?

Someone 6y ago
No. The mapping isn’t invertible (that follows directly from the pigeonhole principle and the existence of gardens of Eden (1)) 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.
- drdeca 6y ago
  I would think that a stable state, because it leads to itself, and is therefore led to by itself, is therefore not a garden of eden? Though, a state which is stable, and which no other state leads to it, would be interesting.
  - Someone 6y ago
    Yes, of course! I agree it’s interesting, and think it warrants a special name. 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)
- jsilence 6y ago
  Thank you for the explanation! 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?
deleted 6y ago
[deleted]

Someone 6y ago

No. The mapping isn’t invertible (that follows directly from the pigeonhole principle and the existence of gardens of Eden (1)) 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.

drdeca 6y ago
I would think that a stable state, because it leads to itself, and is therefore led to by itself, is therefore not a garden of eden? Though, a state which is stable, and which no other state leads to it, would be interesting.
- Someone 6y ago
  Yes, of course! I agree it’s interesting, and think it warrants a special name. 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)
jsilence 6y ago
Thank you for the explanation! 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?

deleted 6y ago

[deleted]