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.

^{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 2x2 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.

This is not an aswer, but an explanation of why VainMan's answer and Yakk's answer are incorrect (or at least incomplete and not easily fixable). The proposed method, if it were correct, works in more generality than Conway's Life. It proves the following:

Theorem (incorrect). Let $F$ be a cellular automaton in any dimension, with any finite neighborhood, with any finite set of states per cell. Choose a distinguished "dead" state $q_0$. If $F$ has a still life with finitely many non-$q_0$ cells, then it can't have a black hole pattern that satisfies rules 1-4.

But this theorem is false. There is a technique for constructing one-dimensional cellular automata (explained in some detail in this paper, sections 3.1 and 3.2) that behave as follows.

1. There are two distinguished states, $*$ (initializer) and $\#$ (wall). The $*$-state can't be produced by the CA, and every $*$ disappears in one step. Hence the $*$ is an orphan pattern: it can only be present in the initial configuration.
2. $*$-states send signals to the left and right that produce $\#$s exactly halfway between each pair of $*$s. These signals and walls are called "properly initialized". A wall will remain in place until some special circumstance destroys it (the details depend on the application). The space between the signals consists of dead cells.
3. A properly initialized signal destroys all patterns in its path, replacing them by dead cells, except other properly initialized signals. This means that the segment of cells between two properly initialized walls will be completely dead. This is the most nontrivial property of the construction, and I don't have room to explain it in detail here.

We can now modify this construction as follows:

4. Every wall $\#$ is destroyed in one step, and becomes a dead cell.
5. There is an additional state $S$, which stays as $S$ if surrounded by dead cells, and behaves exactly like a dead cell otherwise. In particular, it is destroyed if a signal passes over it.

Now a single $*$-cell is a black hole. It will shoot signals to the left and right, which destroy everything in their path except for other properly initialized signals. If a right-going signal encounter a properly initialized left-going signal, they will annihilate each other and produce a $\#$, which immediately destroys itself. The left-going signal must have a right-going counterpart further to the right, which in turn can destroy a left-going signal if it meets one, and so on. Also, a single $S$-cell is a still life by construction. Thus this CA is a counterexample to the Theorem.

This is an attempt to make @VainMan's answer a bit more clear.

Let A be a black hole pattern with a 100x100 empty region in the middle that is guaranteed to be blank no matter what. I will seek to prove that A cannot exist. It is pretty clear that A must be able to exist for any black hole pattern to exist, because the rules state that black holes eventually blank out regions. We just take any black hole pattern, play it forward until we get the 100x100 guaranteed blank region, and call that A.

Let B be a A, but with a 2x2 stable dot right in the middle of the 100x100 region.

Now, given a universe with A in it, the 100x100 region will be blank and never come to life, and eventually (by assumption) every cell will go blank.

If we take the same universe, except we replace A with B, the dot must survive forever. It is too far from the edge of the 100x100 blank region to influence any of the rules of life on any other cell, so the B universe ends being blank... except for a 2x2 stable dot.

This is fine, and doesn't yet cause a problem. We never claimed B was a black hole, just that A was.

So now we create the AA universe. This is a universe with two copies of A in it. We can consider A0 to be the black hole, in which case the 100x100 region must remain blank, and eventually everything becomes blank. We can consider A1 to be the black hole, in which case the 100x100 region must remain blank, and eventually everything becomes blank.

Because the rules of life don't care which one we consider to be the black hole, both above statements must be true; so there are two 100x100 regions which are blank, and never become non-blank, and eventually the entire universe goes blank.

Next, consider the AB universe. This is an exact copy of the AA universe but with one of the A patterns replaced with a B -- a single dot is added to the middle of the 100x100 region.

The evolution of the rest of the universe continues; with the exception of that dot, nothing in the 100x100 region for either the A or the B ever becomes non-blank. This means that dot cannot die.

But this universe has an A, and an A qualifies as a black hole. This is a contradiction; the 2x2 dot in the B cannot be erased by the A.

So no such pattern as A can exist, and thus no black hole can exist.

Ok there is a flaw. I implicitly assumed that the fact a given region becomes blank from now on is a fact we can know irrespective of the content outside of the region.

The OP only requires that the region become blank after a finite number of generations. That finite number can depend on the state of the rest of the universe.

So, the injection of the second A into AA could cause the 100x100 region to become non-blank.

So I have to be less sloppy, and prove that a black hole implies a pattern like A exists.

Suppose there is no finite descendant of the black hole with a 100x100 region that is never filled regardless of the rest of the universe.

Then we simply continue to populate the universe in such a way that the 100x100 region is never always blank. If we can, then we have failed at producing a black hole, because we have a description of an infinite game of life state where at any finite time, in the future that 100x100 region gains life after that point.

If we ever reach a point where there is no such way to populate the rest of the universe such that the 100x100 region ever has a living cell in it again, then we have found our A.

We then create a B from this A, create universe AB, then generate a contradiction.

SuperNova

If you relax requirement 4, you may be left with a pattern which is similar, but perhaps possible: a "ring of fire" which grows continuously and consumes everything in its path except for another SuperNova. When two SuperNovas meet, they pass through each other harmlessly, continuing to expand.

Now, if you allow an infinite number of such SuperNovas to populate the start state, then the world becomes reduced to expanding SuperNovas after they clear out the random junk. But if the SuperNova population is finite, then at some point, they will all meet at the midpoint of the two furthest SNs and effectively form the Black Hole effect that you describe.

Note that allowing SNs to pass through each other takes care of the fact that one might form with junk in its interior. This also implies that you need at least 2 SNs to guarantee a "clean" Black Hole.

Of course, trying to find a pattern that grows in this manner is highly non-trivial, and well beyond my capabilities. ;) But I hope folks agree that there is no obvious barrier to its existence.

Collapsing Black Hole

Alternatively, the full Black Hole you describe may be possible if the "ring of fire" proceeds in both directions (both outwardly and inwardly), but the shrinking ring consumes every pattern until it collapses to nothing. This pattern would need to result in mutual annihilation on contact (which results in the "merging" you describe), and would guarantee that the population of dead cells is constantly growing (over a sufficiently large granularity).

My intuition is that solving the collapsing ring would tell you whether the pattern is possible at all, which is nice, because the collapsing ring must always finish in finite time, and will likely be proportional to its initial size. Also note that the "ring" need not be "round" in the proper sense of the term. It might be square, rectangular, hexagonal, or some other exotic shape. It might not even have a fixed geometry, and may "slither" chaotically as it shrinks.

Opaque Black Holes are Impossible

I believe all the arguments about still lifes prove a weaker result than claimed, which is that opaque black holes are impossible. By "opaque", we mean that when two black holes meet, they merge. And the reason should be obvious after some reflection: the premise is that a BHP can "eat" everything in its path. But if two BHPs merge, then clearly, they are not eating everything.

Analysis

The problem is this: a BHP can clear its interior, but it can only do so finitely many times. A BHP must be expanding on average, or it will never achieve the goal of clearing the world state. The slow "speed of light" makes this problem especially acute, since it means it cannot make large jumps across space. Therefore, there must always exist some state which contains a BHP event horizon, and immortal junk in the interior (because whatever cleaning mechanisms the BHP has are already exhausted). We may call this state the "infinite stasis box". It is protected from all interference, because it is surrounded by a growing field that consumes anything which could tamper with it. A BHP which encounters this state is unable to consume it, because the event horizons merge. The BHP becomes its own worst enemy, because a BHP is the only thing which a BHP cannot consume.

Transparent Black Holes are Impossible

If we abandon the assumption that BHPs merge, then we end up with "transparent" BHPs, which pass through each other harmlessly (note that the behavior on contact should be symmetrical, or Bad Things will happen). The SuperNova I described in another answer is an example of such a BHP. Fortunately, a SuperNova BHP really can clear the universe...of everything except SuperNovas! And if the universe is infinitely randomly populated without bias, then there will be an infinite number of SuperNova event horizons within it, expanding forever. They will simply turn the universe into a dynamic puddle of SNs.

All Black Holes are Impossible

The root problem is that a BHP must have a memory of which region it has cleared. That's because it may only clear a region a finite number of times (by requirement 4). An algorithm without an explicit memory still has an implicit one: the "start at a point and expand outwards" simply uses the current origin + radius as the "memory" of what is cleared. It is easy to see how that memory can be corrupted. A more sophisticated BHP could explicitly encode the space it has cleared in its structure, thereby allowing it to "purge" any interior spaces that might hold junk. But an infinite plane of BHPs will contain an infinite number of BHPs with corrupted memory, including memories that "know" a particular region is clear, but still contain junk. Since any particular state may be the start state, it is impossible to encode memory in the life universe, because a "memory" is a statement about a particular set of cells, and there is no causal force which guarantees that the correspondence between the memory and the referent of the memory actually holds. Therefore, no BHP can actually tell whether it has cleared any given patch of space or not, and therefore, no BHP can exist.

===EDIT===

The Infinite Time Fractal

When I said: "No memory is possible", I was not talking about Life in general. It is well-known that Life is Turing-complete, and anyone who has studied glider guns can imagine how to construct bits of a Turing machine within a Life universe. What I was talking about is the special Life board which is infinitely large and randomly initialized without any particular bias (a uniform distribution is not necessary; any random distribution that does not explicitly exclude/prevent any particular finite sized pattern is suitable, I believe). This board has special properties.

First, this board must contain every finite-sized pattern. If it didn't, then I would question the randomness of the initialization. It means that for every opportunity it had to insert the pattern into the board, it "chose" not to, and it did so an infinite number of times. I'm pretty sure that's the opposite of randomness. Technically, to be precise, we should say that every finite pattern is almost certainly present. That is, it has probability 1, even though we are not technically guaranteed that it is present.

Second, there is no way to distinguish the initial state. This is the real problem, and what makes it fundamentally different from a sterile board containing a Turing machine. While one might claim that the initial state has "maximum entropy", that can only be true in the global sense. If it is generated truly randomly, then local regions must also contain patterns which are sparse. And these patterns will look exactly like a more random state which has been iterated $N$ times. In particular, the initial state must contain a copy of every finite region iterated through all of its distinct states.

To elaborate, an $n \times m$ region has $2^{nm}$ possible configurations, and all of the time evolutions of any of those configurations also exists in this space. In this sense, one can say that "all points of time exist in the start state". More precisely, all time evolutions of every finite size pattern exist simultaneously somewhere in the start state. This is why there are no clocks in the Infinite Time Fractal: there are an infinite number of clocks, and they read an infinite number of times. And this is why no memory is possible: there is no reliable initial state from which a memory could be established.

This is also why it is impossible to measure age: two objects with an "internal clock" can appear randomly in the initial state with readings which say they are 10 and 10,000 generations old, respectively. There is absolutely no way for them to know that, in fact, this state is the start state, and not the 10th or 10,000th generation. So even if some object initializes with a "proper" clock, the ones which are born "broken" will ultimately wreck whatever scheme relies upon the accuracy of clocks/memory.

The only way for a life board to know that a state was the initial state is to compute the global entropy. But information cannot move faster than 1 cell/generation (and gliders are more like 1/4 cell/gen), so it will take an infinite time to perform this computation. Any attempt to compute it for a finite bubble risks sampling bias.

Finite Universe

Of course, this suggests that BHPs might be possible in an infinite Life board which is only finitely populated. Whether the live cells must also fit within a finite region is an interesting open question. There is still the problem that a given pattern within a randomly initialized universe cannot tell the time. However, perhaps there is a way to reliably detect the edge of the [possibly expanding] universe, and use that as a kind of absolute reference.

>>> EDIT 2 <<<

Garden of Eden

While a Garden of Eden may only exist in an initial state, this is of no help to BHPs. The only situation we need to consider is when two potential-BHPs encounter each other. It doesn't matter if they are true BHPs, D-BHPs, PD-BHPs, or something else. It only matters if their time-evolution behaves like a BHP, clearing out everything in its path. Their response to contact ultimately decides whether BHPs are possible or not.

We already noted that transparent BHPs are impossible, because their failure to consolidate on contact means that every additional BHP increases the number of times a cell may be modified. An infinite number of BHPs thereby precludes requirement 4. More generally, any contact which is "conservative" has this problem. By "conservative", I mean that the number of BHPs after contact is the same as the number before. Therefore, BHP contact must inherently be destructive. At least one of the BHPs must die. The merge policy makes it ambiguous as to which one "dies", since they coalesce into a single BHP. The "young eats old" policy makes it explicit which BHP must die.

So as long as we have accurate clocks, we've solved the problem, right? Well, no. The problem is that you cannot make the clocks mean what you want them to mean. Suppose that a "true BHP" must be born with 0 interior cells and a clock set to 0. Thereafter, it grows, and as it grows, its clock increments. As long as your universe is initialized with exactly one BHP pattern, and it is a true BHP, then everything works just fine.

The problem, naturally, is the children (cue Back to the Future music). While it is possible to make a clock which counts time perfectly, it is not possible to make a clock which never lies. After 1000 generations, the true BHP will produce a D-BHP with a clock set to 1000. But what happens when that BHP encounters another BHP whose clock is also set to 1000? We know that they must merge, or one must eat the other. Since the counter is the only data we have to distinguish them, then one eating the other is arbitrary. The logical choice is for them to coalesce into a bigger BHP. But this only works if the other BHP started life as a true BHP. If it actually started life as a PD-BHP, with a large interior containing immortal junk, then we are right back to square 1, and the clocks did us no good at all.

The problem here is that the clock is a proxy for "cleared region memory" as described above. The value of the clock is exactly a memory cell saying: "the interior of this BHP is empty". When the clock is attached to a non-empty BHP, then the clock becomes a liar. And there is no way to guarantee that such a PD-BHP never forms in the random universe. Even worse, statistically speaking, you are guaranteed that such a PD-BHP forms...in fact, you are guaranteed that an infinite number of them form! And on top of that, that they will contain every finite stable configuration in their interior! Every possible kind of lasting junk which could populate a PD-BHP will occur. It is the worst possible kind of failure you could imagine.

Note that it doesn't matter whether the clock was initialized by a Garden of Eden pattern or not, because two different BHPs may be "properly initialized" w.r.t. clocks, but say very different things about their interiors. This is what I meant by: "there is no causal force which can guarantee correlation between a memory and its referent". The clock is a "memory" which says: "This internal region is cleared." But you cannot ensure that the referenced state is actually true.

Broken Clock

The real problem with clocks is that they stop. At least, the broken ones do. And these won't be right even twice a day. A clock must have a mechanism to advance time. A proper timed-BHP will have such a clock, which is both the "current time" value + a "time-incrementing circuit". However, I claim that for any such clock, it is also possible to have a BHP with a "current time" value + a "do-nothing circuit". This is a dead clock which never advances. A BHP with such a non-functioning clock eventually becomes immortal, because every functioning BHP eventually becomes older than it, and it slays them, one by one. And, in the Infinite Time Fractal universe, if it is possible, then it will occur, and do so infinitely often. On top of do-nothing clocks, there are reverse clocks, random clocks, probably even Ackermann and Collatz clocks. Your precious BHPs will have to contend with all of them, and it will lose.

Memory, Memory, Memory

Please note that all of these mechanisms are merely an attempt to prove that some region of space is permanently dead. And all the failure modes boil down to the inability to prove that such a correspondence is true, rather than false. There are many additional complications that a BHP would face, but at the end of the day, the absence of a reliable memory is the Achilles Heel which cannot be cured.