Is black hole pattern possible in Conway’s Game of Life that eats/clears everything?

Is black hole pattern possible in Conway’s Game of Life that eats/clears the infinite universe plane ?

Formally, is there a pattern that satifies following requirements?

  1. The pattern has finite size.
  2. The universe plane has infinite size.
  3. Each cell outside the pattern is initially alive or dead randomly. That is it can contain all possible patterns, including other black holes if they are possible.
  4. For any finite region surrounding the pattern, all cells inside this region will be dead after finite generations and never back to life.

Edit:

  1. To describe this question more intuitively: Imagine there’s a circle that always expanding larger and larger and leaving the region inside it empty, no matter what patterns from the outside it collides.

  2. Originally there was another rule: If two or more black holes collide then they will merge into a bigger black hole. It was deleted before posting because I think it’s already covered by the third and the fourth rule. In addition, it’s hard for me to define and describe the merging formally.

  3. Thanks to @Vepir and @PM2Ring for mentioning related superstable configuration question. I believe this question is an extended version of the superstable configuration question which is an open problem. Because if such a black hole exists, it must be a supertable or become a supertable after finite generations.

Edit: After a bit further thinking, the metioned superstable configuration question inspired a simple but flawed answer about this question. See it below.

Answer

PS: I am not good at English, any help or suggestions to improve the question or the answer would be greatly appreciated.

Edit: Unfortunately, this answer has a flaw in that it applies Rule 4 on different generations of the black hole and the surrounding state. Thanks to @IlkkaTörmä for pointing this out. You may read the comments, @Yakk’s clearer but still flawed answer and @IlkkaTörmä’s explanation.


Original answer

Thanks to @Vepir and @PM2Ring mentions the related superstable configuration question which inspired this simple answer.

Assuming that such a black hole exists, after finite generations, it makes a finite(but can be arbitrarily large) still empty region inside it and this region will be empty all the time.

Consider these two patterns:

  • A: a descendant of a black hole with a large still empty region inside, that means no cell in that empty region can be back to life.
  • B: the same as A, except that a small still lifes pattern(eg. a 2×2 life block) is located at the centre of its large still empty region.

According to the rule 4, no cell in B surrounding the still lifes pattern can be back to life. Any still lifes pattern will keeps its state when it’s surrounded by an empty environment.

Then what if A collides with B since they are expanding larger and larger?

  1. If the still lifes pattern in B can be cleared in finite generations, that means one of the surrounding cells of the still lifes pattern must be back to life, which breaks the rule 4.
  2. If the still lifes pattern in B can not be cleared in finite generations, it also breaks the rule 4.

So the answer is: such a black hole pattern is impossible.


My attempt to explain (informally) why this is incorrect.

Blackhole pattern (BHP) is a pattern that satisfies OP’s rules. Roughly speaking, a BHP can clear any possible initial universe state.

Descendant of black hole pattern (D-BHP) is the pattern that derived from a BHP in any particular initial universe state(eg. an empty universe). Note that a D-BHP is NOT necessary to be a BHP because, by Rule 4, an N-generation-old D-BHP is only required to clear its own surrounding environment, which is an exact N-generation-old universe from the particular initial universe. For example, Garden of Eden can only occur in the initial universe so D-BHPs neither need to clear any orphans nor protect themselves from any orphans. A D-BHP aged enough finite generations will have an interior permanently dead region that can’t be populated any longer.

Pseudo descendant of black hole pattern (PD-BHP) is a pattern that looks like a D-BHP but it is in the initial universe or is a descendant of another PD-BHP. Note that a PD-BHP is NOT a D-BHP and can have junks(some alive cells) in its interior region. A PD-BHP doesn’t have to clear anything or protect itself in any universe aged any generations because it’s always in the wrong universe.

Now review the original answer, A is a D-BHP while B is a PD-BHP(or, more precisely, a descendant of another PD-BHP that looks like A). Case 1 does not break Rule 4 because B(with its still lifes inside) can be cleared and must be cleared by A by definition.

But how could that happen? Shouldn’t A and B have the same behaviour?

Note that when an initial universe with one BHP and one PD-BHP starts evolution, the PD-BHP is always some generations older than D-BHP by form. So they naturally can have different behaviour because of their different forms.

And if we put both A and B in any specified initial universe, both are PD-BHPs. In particular, with an empty surrounding universe, A have the same form as an N-generation-old D-BHP, so by Rule 4 we may assume it can clear those patterns that can occur in an N-generation-old universe from outside. But B is NOT necessary to be such a pattern because of injected lives. B may be an orphan pattern that can only occur in initial states. so by Rule 4, A is not required to clear B, and case 2 does not break Rule 4.

One potential possibility is that all D-BHPs are somehow counting their ages. When two potential D-BHPs meet, they merge as real D-BHPs if they have the same age, otherwise, the younger one eats and clears the other entirely because the older one must be a PD-BHP. I believe this is also impossible, but to prove it is far beyond my ability.

Attribution
Source : Link , Question Author : VainMan , Answer Author : VainMan

Leave a Comment