Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
Please feel free to suggest alternative tags. –  Joel David Hamkins Jun 4 '13 at 0:59
    
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 4 '13 at 1: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 4 '13 at 1:22
    
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 4 '13 at 1:24
9  
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 4 '13 at 1:59
show 3 more comments

2 Answers

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.

share|improve this answer
1  
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 5 '13 at 2:19
2  
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 5 '13 at 2:58
add comment

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.

share|improve this answer
    
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 1:38
    
@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 6:05
    
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 2:57
    
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 5:38
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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