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?
- The pattern has finite size.
- The universe plane has infinite size.
- 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.
- For any finite region surrounding the pattern, all cells inside this region will be dead after finite generations and never back to life.
Edit:
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.
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.
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?
- 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.
- 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