114
$\begingroup$

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.

$\endgroup$
15
  • $\begingroup$ Is the BHP (black hole pattern) in a fixed location, or can it move? Is it ok if an isolated BHP expands to arbitrarily large (but finite) size, but returns back to its core configuration? What happens if the starting pattern consists of just 2 separated BHPs? Do they eat each other? $\endgroup$ – PM 2Ring Jun 14 at 12:32
  • 3
    $\begingroup$ I also think that proving that this is impossible is very difficult, because the existence of a "superstable configuration" (a finite stable pattern that can survive in any random configuration) is believed to be impossible, but still remains an open problem. $\endgroup$ – Vepir Jun 14 at 15:23
  • 3
    $\begingroup$ Related, a universal eater: conwaylife.com/forums/viewtopic.php?t=1818 $\endgroup$ – PM 2Ring Jun 14 at 15:41
  • 6
    $\begingroup$ From comments on one of the answers, a black hole pattern and a superstable configuration are mutually exclusive. The black hole pattern must consume everything (implying a superstable configuration cannot exist), whilst a superstable configuration must resist any advancing barrier (implying a black hole pattern cannot exist). Whilst this doesn't prove the existence of either, it allows a proof of existence of one to be converted into a proof of non-existence of the other, so see also mathoverflow.net/questions/132687/… $\endgroup$ – Steve Jun 15 at 16:30
  • 1
    $\begingroup$ I found this black hole oscillator. It is called the “ring of fire”. $\endgroup$ – Tyma Gaidash Jul 13 at 2:16
22
+500
$\begingroup$

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.

$\endgroup$
17
  • 3
    $\begingroup$ "Assuming that such a black hole exists, all its possible descendants are also black holes." This seems false to me. The set of descendants breaks rule 3: the patterns are not surrounded by random cells, but cells that are evolved from random cells after one or more generations. In particular their surroundings can't contain orphan patterns. $\endgroup$ – Ilkka Törmä Jun 14 at 20:44
  • 1
    $\begingroup$ @VainMan Now you're using Rule 4 on descendants of black holes, but you don't know if they're black holes or not. $\endgroup$ – Ilkka Törmä Jun 14 at 21:05
  • 2
    $\begingroup$ Rule 4 says that if you have a black hole in your initial state, then something happens. It doesn't say anything about the situation where the initial state has a descendant of a black hole, unless that entire state is descended from a state containing a black hole. $\endgroup$ – Ilkka Törmä Jun 14 at 21:37
  • 2
    $\begingroup$ @Vepir Yes, B is neither a black hole nor a descendant of a black hole. But B is a possible initial pattern on the starting plane. And it's the same as A, a descendant of a black hole, except the small still lifes pattern inside. So I think it should have same behaviors as A, since the small still lifes pattern will not have any effect on B. $\endgroup$ – VainMan Jun 14 at 21:39
  • 1
    $\begingroup$ I don't think case 1 is a contradiction. Rule 4 only states that "all cells inside this region will be dead after finite generations", and not in which generation that must happen or by which process. Yes, they were not permanently killed by B, but they can be killed by A. If they are eventually permanently dead, it's enough. So, even if some of the cells come back to life inside of B, if they eventually die (by A in this case), and remain dead, rule 4 is satisfied. $\endgroup$ – Luiz Martins Jun 14 at 23:15
20
$\begingroup$

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:

  1. Every wall $\#$ is destroyed in one step, and becomes a dead cell.
  2. 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.

$\endgroup$
5
  • 2
    $\begingroup$ Ah; if the black holes can provably communicate how long they have been in existence (by being provably only N steps away from an orphan), when two black holes collide they can prove that their interiors are empty to each other. A "fake" event horizon with a stable seed inside can be detected, because after N generations there is no way it could have form. And I didn't prove I could "fake" a black hole with a stable seed in a void. $\endgroup$ – Yakk Jun 15 at 14:12
  • $\begingroup$ I am by no means sure I understood all this, so feel free to not bother if explaining the details would be too much effort. So for example, we start with ` ..*..` --> ..l_r.. --> ..l___r..; this is a single black hole. What concept prevents us from initializing any part outside the black hole pattern to ..l_S_r.. (basically @Yakk 's B) to prove that ..*.. is not actually a proper black hole? Has it something to do with what you call "properly initialized"? Or did you not mean that signals are states as I understood it? $\endgroup$ – Silly Freak Jun 15 at 15:02
  • $\begingroup$ This theorem is too powerful to disprove the Life result, isn't it? The theorem could be false, while the BHP theorem is true, no? $\endgroup$ – Lawnmower Man Jun 15 at 18:54
  • 1
    $\begingroup$ @SillyFreak Each signal is formed by a pair of states moving at different speeds, so the picture is more like ..*....Ll_rR....L_l___r_R....L__l_____r__R... The distance between the two states encodes the "age" of the signal. When two signals collide, a bunch of auxiliary signals is created. They compare the signals' ages and either destroy the older signal (if they're different) or destroy both and create a wall (if they're equal). A diagram is shown on page 13 of the linked paper. $\endgroup$ – Ilkka Törmä Jun 15 at 21:23
  • 6
    $\begingroup$ @LawnmowerMan I haven't proved anything about the existence of black holes in Life. I only show that the proposed proofs are incorrect, but the claim (there is no BHP in Life) could be true. $\endgroup$ – Ilkka Törmä Jun 15 at 21:26
13
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – Pedro Tamaroff Jun 17 at 13:01
7
$\begingroup$

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.

$\endgroup$
5
  • 3
    $\begingroup$ What happens if you have a large enough supernova "arc"? It will be able to pass through another supernova (until it degrades), despite not satisfying the conditions of the question. It seems that this rules out your solution. $\endgroup$ – CJ Dennis Jun 14 at 23:30
  • $\begingroup$ @CJDennis Each supernova only touches a region of space once. Therefore, if there are N supernovas, each region will get passed over by one no more than N times, after which it remains dead. If there are an infinite number of them, then it doesn't satisfy the requirements, as described. $\endgroup$ – Lawnmower Man Jun 15 at 18:49
  • 1
    $\begingroup$ The problem with supernova is that there can be at most a single supernova pattern. (This pattern might occur multiple times, but you get into difficulty when one supernova with a given pattern encounters a supernova from a different pattern) $\endgroup$ – Taemyr Jun 16 at 11:38
  • $\begingroup$ @Taemyr technically that can't happen. By definition, a supernova wipes out everything in its path, and passes harmlessly through other copies of itself. If two patterns claim to have this property, then their behavior on contact tells us the truth: either they disrupt each other, making neither a true SN, or they pass through, making them compatible variations of the same SN. $\endgroup$ – Lawnmower Man Jun 16 at 18:17
  • $\begingroup$ Reread my comment. - Especially the first sentence. $\endgroup$ – Taemyr Jun 17 at 8:42
6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – Pedro Tamaroff Jun 17 at 13:02
6
$\begingroup$

This is not an answer to the question but a description of the properties that a potential Black Hole Pattern (BHP) could have that would invalidate some of the attempted proofs in other answers. And so, to repair those proofs, they would have to conclusively prove that there cannot exist a pattern with one or more of these properties.

Garden of Eden

Consider that for any given pattern, there is the pattern that it will produce in the next generation, its children, and then there are the set of patterns that could have produced this pattern from the previous generation, its parents. For any given pattern, there is necessarily only 1 child pattern (since GoL is deterministic), and but there is not necessarily only 1 parent pattern for a given pattern. Since many different patterns lead to extinction, it should be clear that an empty board has many potential parent patterns. However, not every pattern has any parents at all. Some patterns cannot be produced by any previous state and if they exist on the board, they can only exist a priori (from the beginning) and cannot arise later through generation evolution; these are called Garden of Edens (GoE).

Further, there are some patterns that have parents, but whose only parents are GoE patterns, that is, patterns which can only be produced by a specific GoE and by no other means. I'll call these Garden of Eden Descendants (GoE-D).

Take some GoE $g_0$ that produces some GoE-D $g_1$. And $g_1$ produces $g_2$ and so on to $g_n$. Where every $g_i$ in this chain is a pattern whose only parent is $g_{i-1}$. I'll call a chain of these $g_0$ through $g_n$, where no pattern in the chain is stable and each step in the chain is unique, a Garden of Eden Clock (GoE-C). It's a clock because if we are given an arbitrary board and on it, we find that the board contains the pattern for some $g_i$ in the chain, then we can know for certain that this board has been evolved for at most $i$ steps and no more than that. This is because if we find $g_i$, on the previous step (if there was one) we must have had $g{i-1}$ since $g_i$ has no other parents. And if we look back further, we would eventually get to $g_0$ and since $g_0$ has no parents, there cannot have been a previous step. This doesn't tell us that the board couldn't be younger than $i$. After all it could have just been initialized with $g_i$ to start with. But definitively it can be no older. For example, if we are given a board and we find on it somewhere both a $g_3$ and a $g_{40}$, we can further conclude that the $g_{40}$ pattern must not have started as a $g_0$ since the existence of the $g_3$ lets us know that the board has been evolving for at most 3 generations. So, that $g_{40}$ must have started as either a $g_{37}$, $g_{38}$, $g_{39}$ or $g_{40}$, and then evolved deterministically from there to where it is now.

Now, not all chains are going to be infinite. In fact almost all aren't. In general, a chain will at some point end and either stabilize to some static or oscillating state or will decay into another pattern that has an alternative parent pattern that could have produced it that is not a GoE-C. However, I as of yet have seen no proof that there cannot exist a GoE-C of infinite length. Also note that a GoE-C of infinite length would have to grow in size indefinitely because for any given finite bounded area, there are a finite number of possible states. And if a state was repeated, the pattern would now be oscillating, static, and/or reached a state that no longer has unique parentage.

Horizons

Here, I will describe the general potential behavior of a BHP. If there is a BHP it need not follow this exact behavior, but this is a behavior it could have.

Suppose that it starts with no empty interior that it never touches. That is, all cells within some bounding box defining the finite initial pattern must be either alive or dead just as prescribed, or else the pattern comes apart. Let 'H' mark the boundary of the pattern and '~' mark an area of the pattern where cells may or may not be alive or change their status at some point in the future.

H~~H

But at some later time, the pattern evolves to have an empty interior giving us an inner horizon inside which no cells ever become alive again, and an outer horizon, the extent to which our BHP has evolved into. Let 'h' represent the inner horizon and '_' represent a region of dead cells which will never again be brought back to life.

H~~~h___h~~~H

These two horizons will not necessarily expand at the same rate. But the outer horizon must expand faster than the inner horizon. And leaving behind this interior that is never touched ensures it meets property #4 of the original question.

Mergers and Fakes

Assume we have a BHP that evolves with the above properties over time, that the initial BHP is a $g_0$ of some infinite GoE-C chain, and that it has two horizons expanding at different rates leaving a dead region in the middle. There is the possibility that in addition to our original BHP that we have placed on the board, there could be any number of copies anywhere else on the board. When two BHPs are expanding and their outer horizons meet, if they are both true BHPs that were initialized at $g_0$, then they must either merge, or one needs to wipe through the other to preserve its own dead interior. We cannot have them merely pass through each other, or else an infinite number of BHP's on the board would have their interiors coming back to life an infinite number of times which, as pointed out in other answers, would violate rule 4.

Since GoL is Turing Complete it could be that the BHP is capable of recognizing and overriding any other horizon it finds that has higher generation number. This may involve both of their entire outer horizons merging together and comparing, and it need not be any human understandable algorithm, may differ from generation to generation, and this behavior may even be unproveable as with Turing Completeness comes the Halting Problem, and it may be that proving that lower generation numbers overriding higher generation numbers is undecidable but nonetheless true.

Now, one might postulate some "fake" COE-D. Take some real $g_i$ after it has developed a dead interior, and then add some stable shape inside the dead region. Call this new combined pattern $f_i$ which is identical to $g_i$ except for having some stable junk 'j' on the interior:

g_i:  H~~~h___h~~~H
f_i:  H~~~h_j_h~~~H

From the exterior, these would be indistinguishable. And so, if a $g_i$ encountered an $f_i$, they would either merge, never clearing each others interior, or perhaps even the $f_i$ would preserve its own junk on the interior and wipe out the interior of the $g_i$. However, consider that each pattern is a GoE-C. So, there would exist a progression:

g_0: HH
g_1: H~H
g_2: H~~H
g_3: H~~~H
g_4: H~hh~H
g_5: H~~h_h~~H
g_6: H~~~h__h~~~H
g_7: H~~~~h___h~~~~H

For $g_0$ through $g_4$ there is as of yet no interior in which to place any extra junk. So, if we want to initialize some fake on our board to start with, we'd have to start with say $g_5$ and make an $f_5$:

f_5: H~~hjh~~H

And from then on, that $f_5$ would have to evolve exactly as a $g_5$ would except for leaving the junk in the middle. This $f_5$ pattern itself would be a GoE because it has no parent at all. Unlike $g_5$ which evolves uniquely from $g_4$, this $f_5$ cannot come from some other parent since the pattern between the inner and outer horizons is already assumed to have a unique parrent. But since it's initialized as being identical to $g_5$, if it were to meet any BHP-D that was initialized as $g_0$, when they meet, our fake would appear to be 5 generations older than the real BHP-D and so the younger real BHP-D would override and clear the interior of the fake.

Conclusion

A pattern that behaved like this will all these properties would foil any proof which relied on constructing some universe with fake black holes in it because this pattern would be able to wipe out any fakes since the real thing will always be a younger generation number than any fake that could have junk in it.

Now, I think that it's highly unlikely that such a pattern with all these properties exists, but the individual properties have already shown to be exhibited by one or more real patterns:

There are space nonfillers which cover a hole empty board, activating and then deactivating forever more every cell.

There are patterns which are uniquely descended from Garden of Eden patterns.

There are patterns that fully implement Turing Machines themselves and can thus perform arbitrary logic.

And there are patterns which can cause extinction of some other patterns.

Now, I think it's highly unlikely that such a BHP with all of these properties exists. But a proper proof that one does not, would have to explicitly rule out a pattern of this type.

$\endgroup$
-2
$\begingroup$

There's one slight issue with your question. You want it to eventually cause an infinite board to be empty. You also want the black hole itself to be an ever expanding circle. If the circle expands on an infinite board, the board will never be empty, because it will always contain the ever-expanding circle. In fact, the live cell count will go up, because the circumference of the circle is growing larger and larger. Therefore, following the rules you provided, no: There can be no such pattern.

$\endgroup$
3
  • 5
    $\begingroup$ Nowhere does the question state that the infinite plane must be empty. It says that the interior of the black hole must be empty, i.e. it clears the plane as it grows. If the black hole is infinitely large, it contains an infinite empty area, despite it being made of living cells. $\endgroup$ – CJ Dennis Jun 16 at 1:15
  • 1
    $\begingroup$ Technically, it doesn't require the "interior" of the BHP to be empty, either. ;) It merely says that the population of "permanently dead" cells must be growing without bound. More precisely, for every cell $i$ on the board, there must exist some finite number $N_i$ such that after $N_i$ generations, that cell is permanently dead. $\endgroup$ – Lawnmower Man Jun 16 at 1:24
  • 2
    $\begingroup$ I think that there's a useful analogy here in the difference between "pointwise convergence" and "uniform convergence" (which are of course not the same thing, but easy to get confused by in the limit). $\endgroup$ – Daniel R. Collins Jun 16 at 3:53

Not the answer you're looking for? Browse other questions tagged or ask your own question.