5 ms·

The theorem is whether there exists an "isolated" state, one that is unreachable from every other state.

goldenkey 5y ago
No, that's what a Garden Of Eden state is and they are extremely different from the configuration for this theorem. A Garden of Eden state at time t has no possible states before time t - there is nothing that could have produced it. It can only be reached by starting with GoL set to it, it has no past - only a future. https://en.wikipedia.org/wiki/Garden_of_Eden_(cellular_automaton) https://en.wikipedia.org/wiki/Garden_of_Eden_(cellular_autom... Conway's theorem asks whether there is a self-replicating pattern whose only ancestor is itself. By induction, this also means its only predecessor is also itself. The states that satisfy this theorem have infinite past and future states that all contain the same specific pattern.
- sp332 5y ago
  The configuration in the article is a Garden of Eden, but it is also a still life. Also, while the past is fixed, the future might look different from interference from outside.
  - OscarCunningham 5y ago
    It's technically not a Garden of Eden, because it has a predecessor, namely itself. But it is nearly a GoE, in the sense that it only has one predecessor.
  - cma 5y ago
    Is that only with the stabilizers shown in yellow, or do they have some other purpose?
    - andrewthehacker 5y ago
      The purpose of the cells in yellow is to turn the patch relevant to this discussion into a still life: it's already got the property of "must exist in gen N-1 if it is in gen N" without those yellows, but this serves to keep it from destabilizing instantly.
- contravariant 5y ago
  > future states that all contain the same specific pattern. Past yes, but probably not future surely? I see no reason such a pattern couldn't be broken by outside influence somewhere in the future.
  - kevincox 5y ago
    If I am understanding correctly that is not the case. The point of the "don't care" squares in the diagram is that the pattern will continue no matter what they are so any outside interference is irrelevant. It won't be sufficient to change the pattern.
    - contravariant 5y ago
      But if you leave those squares all empty it won't keep the original pattern, so I'm not sure how that can be right.
      - dvgrn 5y ago
        Right -- this discovery is about identical states extending into the past, not into the future. A Conway's Life pattern that has to stay the same into the indefinite future would be an impenetrable wall, and we don't know of any such thing in the Life rule. It hasn't exactly been proved impossible, but nobody seriously thinks that such a thing exists. I think it _can_ easily be proven that a finite stable (period 1) impenetrable wall can't exist. It's trivial to find a way to attack the corners, and almost equally trivial to find something that makes a change at any edge.
        galaxyLogic 5y ago
        Right you can break it, but can you prevent its reincarnation?
        contravariant 5y ago
        Well yeah, in fact it would be impossible to rebuild.

No, that's what a Garden Of Eden state is and they are extremely different from the configuration for this theorem. A Garden of Eden state at time t has no possible states before time t - there is nothing that could have produced it. It can only be reached by starting with GoL set to it, it has no past - only a future. https://en.wikipedia.org/wiki/Garden_of_Eden_(cellular_automaton) https://en.wikipedia.org/wiki/Garden_of_Eden_(cellular_autom... Conway's theorem asks whether there is a self-replicating pattern whose only ancestor is itself. By induction, this also means its only predecessor is also itself. The states that satisfy this theorem have infinite past and future states that all contain the same specific pattern.

sp332 5y ago
The configuration in the article is a Garden of Eden, but it is also a still life. Also, while the past is fixed, the future might look different from interference from outside.
- OscarCunningham 5y ago
  It's technically not a Garden of Eden, because it has a predecessor, namely itself. But it is nearly a GoE, in the sense that it only has one predecessor.
- cma 5y ago
  Is that only with the stabilizers shown in yellow, or do they have some other purpose?
  - andrewthehacker 5y ago
    The purpose of the cells in yellow is to turn the patch relevant to this discussion into a still life: it's already got the property of "must exist in gen N-1 if it is in gen N" without those yellows, but this serves to keep it from destabilizing instantly.
contravariant 5y ago
> future states that all contain the same specific pattern. Past yes, but probably not future surely? I see no reason such a pattern couldn't be broken by outside influence somewhere in the future.
- kevincox 5y ago
  If I am understanding correctly that is not the case. The point of the "don't care" squares in the diagram is that the pattern will continue no matter what they are so any outside interference is irrelevant. It won't be sufficient to change the pattern.
  - contravariant 5y ago
    But if you leave those squares all empty it won't keep the original pattern, so I'm not sure how that can be right.
    - dvgrn 5y ago
      Right -- this discovery is about identical states extending into the past, not into the future. A Conway's Life pattern that has to stay the same into the indefinite future would be an impenetrable wall, and we don't know of any such thing in the Life rule. It hasn't exactly been proved impossible, but nobody seriously thinks that such a thing exists. I think it _can_ easily be proven that a finite stable (period 1) impenetrable wall can't exist. It's trivial to find a way to attack the corners, and almost equally trivial to find something that makes a change at any edge.
      - galaxyLogic 5y ago
        Right you can break it, but can you prevent its reincarnation?
        contravariant 5y ago
        Well yeah, in fact it would be impossible to rebuild.