37

This question spins off of Gil Kalai's recent question on Conway's game of life for a random initial configuration.

There are numerous configurations in the game of life that are known to be stable---such as blocks, beehives, blinkers and toads---in the sense that if they appear on an otherwise empty board or on part of the board that remains otherwise empty, then they will persevere (or at least reappear on some period) into the indefinite future. All of the common examples of such configurations, however, seem to disintegrate when placed into a hostile environment; when they are hit by a glider or other spaceship, for example, these common stable configurations can be completely ruined.

My question is whether there is any superstable configuration, which can survive even in any hostile environment.

Question 1. Is there any superstable configuration in the game of life?

Specifically, let us define that a finite configuration is superstable, if it can survive in any environment, no matter how hostile, meaning that if it should ever appear on the board, then it will definitely reappear later in exactly that same position, regardless of what else is happening on the board. Perhaps the position is somehow isolated, absorbing whatever is happening around it; or perhaps it is a strong source of some kind, spewing out gliders or other objects, regardless of what else is around it; or perhaps it is some core surrounded by encircling vacuum-cleaners, traveling patterns that sweep up whatever might interfere.

This question is related to Gil Kalai's, in that if there are such superstable configurations, then we will expect that the infinite random position will have them with some (albeit very small) density, which will enable us to prove lower bounds on the density of the expected living infinite random position.

One can also imagine a glider version of superstability, where the pattern survives, but with some nonzero displacement:

Question 2. Is there any superstable glider?

That is, is there a finite pattern that, regardless of the environment in which it is placed, will repeat itself at some future time with some displacement? A strong form of such a superstable glider would ask also that it be a vacuum cleaner, meaning that it glides around in any given environment while leaving only empty cells in its wake.

Question 2b. Is there a superstable glider vacuum?

I can imagine a small glider that erases everything in its path; or perhaps there is a kind of moving wall, which steadily pushes against whatever it faces, leaving emptiness behind. If there were such a superstable glider vacuum that also moved in a definite direction, then of course there could be no superstable stationary position, since otherwise we could vacuum it up.

Another alternative would seem to be that every finite configuration in the game of life is destructible, in the sense that one can design for it an especially hostile environment, leading to eventual death.

Question 3. Is every finite configuration destructible?

In other words, can every finite configuration in the game of life be extended to a larger configuration whose development leads in finite time to a position with no living cells? A weaker version of this would ask merely that the configuration be extended to a configuration such that eventually, the original configuration does not recur on any subportion of the board.

Community
  • 1
Joel David Hamkins
  • 224,022
  • 1
    Please feel free to suggest alternative tags. – Joel David Hamkins Jun 04 '13 at 00:59
  • 1
    Why do you ask for a finite superstable configuration? Is it obvious there is an infinite superstable configuration that is not cofinite? – Boris Bukh Jun 04 '13 at 01:14
  • 1
    The connection to Gil's question is made most easily with finite superstable configurations. But indeed I would anyway be interested to learn of nontrivial infinite superstable configurations. Meanwhile, there are, of course, trivial infinite superstable configurations, which specify every positions---imagine, for example, a sea of parallel gliders moving in unison. – Joel David Hamkins Jun 04 '13 at 01:22
  • 1
    Incidentally, I suppose the same questions can be made for any of the other cellular automata, such as Brian's Brain. – Joel David Hamkins Jun 04 '13 at 01:24
  • 15
    How could there be a superstable vacuum glider? You could take two of them, make them run into each other, and then they'd both have to leave nothing in their wake, but they'd also both have to keep on moving. – Sam Hopkins Jun 04 '13 at 01:59
  • 1
    Sam, yes, that seems to answer answer question 2b! And there can be no such moving vacuum walls as I had imagined, since they would similarly erase each other when set in opposite directions. – Joel David Hamkins Jun 04 '13 at 02:11
  • 1
    But I suppose that one can still imagine superstable gliders that bounce off of each other and other things, but which when moving linearly do not leave a trail. For example, perhaps they vacuum up any sufficiently small position? Or perhaps they have a "nozzle," with the feature that they vacuum up any position contained within the nozzle, and if they are confronted with something outside the nozzle in their direction of travel then they stall or change direction? – Joel David Hamkins Jun 04 '13 at 02:22
  • 1
    I think a version of Sam's technique should apply, or at least help characterize, superstable configurations. Namely, what should happen if you place two superstable configurations close to one another? If one is rotated, it may be that they eliminate each other. I would be unsurprised if we could solve the halting problem with a finite set of (copies of) superstable configurations. Gerhard "Just Thinking Out Loud Again" Paseman, 2013.06.10 – Gerhard Paseman Jun 10 '13 at 16:13
  • 1
    A pattern has been recently found which has the property that if it exists in a universe, it must have been there since the beginning of time regardless of what happened on the outside cells: https://www.conwaylife.com/forums/viewtopic.php?t=&p=140258#p140258 – Cihan Jan 20 '22 at 12:09

2 Answers2

28

The existence of a "superstable configuration" is a long-standing open question in the Game of Life community. Years ago I saw Conway ask it as follows: Is there a finite $N$ and a configuration $C$ in an $N \times N$ square that contains some live cell $c$ and guarantees that $c$ will remain live for all time, regardless of what is placed outside the $N \times N$ square in the initial configuration? I think the expectation is that no such $C$ exists but a proof would be very difficult.

Noam D. Elkies
  • 77,218
  • 2
    Thanks very much for your answer. Surely there are configurations that survive quite robustly in many different hostile environments. Do you know what are the best record-holders? Perhaps there are nearly superstable configurations, which survive in, say, any very low density environments, with no two adjacent live cells on their boundaries. There would seem to be many approximations to the question of this kind. Is anything known about them? – Joel David Hamkins Jun 05 '13 at 02:19
  • 7
    Sorry, I don't think there's anything interesting known of this kind. If there were a good notion of "record holder" then I imagine one could always do better by increasing $N$ and expanding the configuration to defeat a known attack. But in fact it doesn't seem that any configuration is known that can even survive an arbitrary finite barrage of gliders (which can come from far away). – Noam D. Elkies Jun 05 '13 at 02:58
  • 1
    @NoamD.Elkies: I thought I encountered an eater that could take any kind of glider collision once, but it went down spectacularly when I collided two gliders next to it. I don't think any configuration can exist if both gliders and spaceships can be launched at its corners. – Joshua May 03 '22 at 19:56
  • Is the variant of Conway's question in which $c$ is only required to be live infinitely often open? Or with 'periodically'? – Olof Sisask Jul 18 '22 at 20:40
  • Ah, I guess @NoamD.Elkies's comment about no configuration being known that can survive an arbitrary finite barrage of gliders answers my question. – Olof Sisask Jul 18 '22 at 20:55
3

I think it could be of interest to mention that something meeting the definition of a finite superstable configuration exists if we add arbitrarily little noise to the original rules of the GoL (Conway's game of life for random initial position). The configuration is trivial – completely empty finite region. Via an argument in the spirit of the second Borel–Cantelli lemma, we see that “if it should ever appear on the board, then it will definitely reappear later in exactly that same position, regardless of what else is happening on the board”. Sorry if this is off-topic.

Community
  • 1
helper
  • 166
  • 2
    Indeed, if we allow the rules to have random noise, then it would seem that every finite position is superstable, in the sense that any given finite position has some nonzero chance of appearing in any given location at the very next time step, and so with probability one it will eventually appear there infinitely many times. Needless to say, this is a considerably weaker notion of stability than I had had in mind. – Joel David Hamkins Jun 11 '13 at 01:38
  • 1
    @Joel I'm not so sure that ANY finite position will eventually appear in ANY given location INFINITELY MANY times. My serious doubts are related to the fact that if we think of an arbitrarily large finite grid "all cells dead" is an absorbing state (trapping state). As stated in the answer above, I think of the situation in the variant with noisy original GoL rules (mathoverflow.net/questions/132402/…). With infinite grid we have the issue of an interaction between finite regions. However, with very low density the interaction vanishes – helper Jun 11 '13 at 06:05
  • 1
    My understanding of the noisy rules is that, with small probability, a cell can turn on or off regardless of its surroundings. So any finite position has some small chance of appearing, regardless of what else is there, and so this will happen infinitely many times. – Joel David Hamkins Jun 14 '13 at 02:57
  • 2
    Isn’t your understanding in conflict with the second “noisy” variant proposed by Gil Kalai (“probabilistic variant of the rule of the game itself”)? I mean his question on game of life for random initial position. One of the rules says that any dead cell with exactly three live neighbours becomes a live cell with probability 1−t. It’s the only rule related to currently dead cells. It implies that some dead cells (with less or more living neighbors) has zero probability of becoming live (turning on) in the next step. My answer and comment referred exactly to this variant. – helper Jun 17 '13 at 05:38