1

Given a grid representing a state in Conway's game of life, if there is no pattern that leads to this state, this means that there exists a forbidden $N\times N$ pattern for some $N$.

If so what is the smallest $N$ such that an $N\times N$ pattern is forbidden? i.e. that it can't exist as a subregion of a next step of a state?

In other words, given all possible states (on a massive grid), evolve them by one time step. Find the smallest $N\times N$ pattern that never occurs. What is $N$? I think it will be as small as 3,4 or 5.

e.g. I think it might be unlikely that a $5\times 5$ pattern where each cell is 'alive' would be in any time step of the game of life (except possibly for the initial state). But I can't prove it.

zooby
  • 4,343
  • 3
    See https://en.wikipedia.org/wiki/Garden_of_Eden_(cellular_automaton) – Barry Cipra Oct 22 '20 at 01:44
  • @Barry I'm not sure that's quite the same as those Garden's of edens are the whole pattern not just a sub-pattern. Ah, yes, the term I'm after is "orphans" I believe. – zooby Oct 22 '20 at 01:46
  • It says the smallest "orhpan" is 8x12. Wow, that's disapointingly large! Apparently computer searches say that N>=7 – zooby Oct 22 '20 at 01:51

0 Answers0