46
$\begingroup$

What is the behavior of Conway's game of life when the initial position is random? -- We can ask this question on an infinite grid or on an $n$ by $n$ table (planar or on a torus). Specifically suppose that to start with every cell is alive with probability $p$ and these probabilities are statistically independent. This question was motivated by a recent talk by Béla Bollobás on bootstrap percolation.

Many thanks for all the answers. A related question that I thought about is what is the situation for "noisy" versions of Conway's game of life? For example if in each round a live cell dies with probability $t$ and a dead cell gets life with probability $s$ and both $t$ and $s$ are small numbers and all these probabilities are independent.

Another example is to consider the following probabilistic variant of the rule of the game itself ($t$ is a small real number):

Any live cell with fewer than two live neighbours dies with probability $1−t$.

Any live cell with two or three live neighbours lives with probability $1−t$ on to the next generation.

Any live cell with more than three live neighbours dies with probability $1−t$.

Any dead cell with exactly three live neighbours becomes a live cell with probability $1−t$.

Following some comments below I asked about the computational power of such a noisy version over here.

Update: Related question Is there any superstable configuration in the game of life?

Improve this question
$\endgroup$
11
  • 4
    $\begingroup$ My experiments with GoL on a torus show that it eventually stabilises to a steady-state (modulo the alternating cross). You can see a video of one run at youtube.com/watch?v=tZTIiKcqdtI (the background is the same as what's happening on the torus). $\endgroup$
    – Andrew Stacey
    Commented May 31, 2013 at 11:39
  • 3
    $\begingroup$ Game of Life supports universal Turing machine that can even have self-replicating function. The Turing machine can run arbitrarily intelligent program. So, a question is "will the Game of Life universe with random initial position be filled with super-intelligent life forms, or will the chaos reign". I abstain from defining the meaning of "intelligent" :-) $\endgroup$
    – Boris Bukh
    Commented May 31, 2013 at 13:13
  • 4
    $\begingroup$ @Andrew Stacey: It is rather naive to base an answer on experimentation. For example, there is a positive probability that somewhere in your system (lets take it to be infinite) you'll encounter this: en.wikipedia.org/wiki/File:Gospers_glider_gun.gif $\endgroup$
    – André Henriques
    Commented May 31, 2013 at 15:39
  • 5
    $\begingroup$ @André Only on a mathematics forum could one argue that experimentation was no basis for assertion! Actually, I've yet to see a glider gun in my simulations so whatever that probability is then it'll be small. I suspect that it might be because it's on a torus so any glider gun that forms has a distinct possibility of shooting itself. $\endgroup$
    – Andrew Stacey
    Commented May 31, 2013 at 19:23
  • 6
    $\begingroup$ >so whatever that probability is then it'll be small< Let's say about $1−(1−(p^{20})(1−p)^{180})^{n^2/200}$. (I was too lazy to count the cells but you get the idea) Now here is the difference between a mathematician and a normal person. The mathematician believes that it is 1 and the normal person that it is 0. All existing computers are normal people, which makes it extremely hard to use them to do mathematics of this type... $\endgroup$
    – fedja
    Commented Jun 1, 2013 at 0:23

7 Answers 7

Reset to default
24
$\begingroup$

The most rigorous analysis of this that I know of is in:

N. M. Gotts. Self-organized construction in sparse random arrays of Conway's Game of Life. New Constructions in Cellular Automata, pp. 1–53. Oxford University Press, 2003.

In order to be able to actually prove something about what happens (in the face of undecidability results for general Life patterns) he considers the case of patterns that are very sparse (each cell initially alive i.i.d. with a very low probability $p$) for relatively short time scales (polynomial in $N=1/p$). Specifically, it looks from my reading that he calculates the asymptotic density of live cells for all times up to $N^{281/96}$, but cannot extend his methods past $N^3$ because somewhere between those two bounds events of unbounded complexity start dominating the density.

Improve this answer
$\endgroup$
9
  • 4
    $\begingroup$ Fundamental undecidability is not necessarily an obstacle to proving theorems about what will happen probabilistically. For example, even with Turing machines (which surely exhibit a robust undecidability phenomenon), we know with asymptotic probability one as the number of program states increases that the behavior of a Turing machine program on a one-way infinite tape is completely trivial. See jdh.hamkins.org/haltingproblemdecidable. For similar reasons, we might hope for advance also in the case of Life. Perhaps life is similarly decidable in most instances... $\endgroup$
    – Joel David Hamkins
    Commented May 31, 2013 at 19:32
  • 8
    $\begingroup$ Remember that, with an infinite field, "most instance" include somewhere every possible finite pattern. In order to say something about denser configurations or longer numbers of steps we would need to resolve the question of whether it is possible for a pattern to exist that can survive and robustly reproduce itself in an environment filled with random junk. If they can exist, then they may eventually come to be a significant fraction of the population. On the other hand if they cannot exist, then it is plausible that more simplistic analysis techniques can be applied. $\endgroup$
    – David Eppstein
    Commented Jun 1, 2013 at 1:00
  • $\begingroup$ @David Eppstein. I like very much your rephrasing of the question: this is exactly what one needs to think about. My bet is that the answer is "yes": there do exist patterns that can survive and robustly reproduce themselves (with an extremely low reproduction rate) in an environment filled with random junk. $\endgroup$
    – André Henriques
    Commented Jun 1, 2013 at 13:54
  • 1
    $\begingroup$ One would also want to know whether there were finite patterns that progressively expand and obliterate everything in an environment filled with random junk. Perhaps such monsters grow (and merge?), leaving behind an expanding eye of calm emptiness inside the hurricane, which is pushed off to infinity. $\endgroup$
    – Joel David Hamkins
    Commented Jun 2, 2013 at 0:38
  • 1
    $\begingroup$ @Joel: If such patterns exist, they will be roughly equi-distributed across space, and so your picture of "expanding eye which is pushed off to infinity" isn't quite correct. But indeed, what you are describing is a conceivable scenario. $\endgroup$
    – André Henriques
    Commented Jun 2, 2013 at 16:22
23
$\begingroup$

The first study of the game of life with random initial conditions that I could find was this paper:

F. Bagnoli, R. Rechtman and S. Ruffo, Some Facts of Life, Physica A 171, 249 (1991) doi:10.1016/0378-4371(91)90277-J.

In it they attempt a kind of mean-field analysis (which I haven't digested) as well as do some numerical experiments which suggest that the system approaches a nontrivial asymptotic density for all $0\lt p\lt 1$.

Here's a plot from their paper of results on 256 by 256 toruses (their $\rho_0=p$):

figure 3 from Bagnoli, Rechtman and Ruffo 1991

They also investigated the temporal behavior, however I found more detailed simulations and discussion of scaling in this paper:

J. B. C. Garcia, M. A. F. Gomes, T. I. Jyh, T. I. Ren, and T. R. M. Sales. Nonlinear dynamics of the cellular-automaton ‘‘game of Life’’. Phys. Rev. E 48, 3345–3351 (1993)

Here is a plot showing the average number of connected clusters of live sites versus time.

figure 1 from Garcia et al 1993

They summarize their findings as follows (below $\varphi$ represents some quantity like the number of live clusters or the total number of live sites, etc.):

For initial occupation probabilities satisfying $0.15\leq p \lt 0.75$, each one of the different statistical functions $\varphi$ describing the dynamics of the GL may be divided in general in three intervals: First, a region extending from $t =0$ to $t\simeq L^{1/2}$ presenting large fluctuations in $\varphi$; second, a scaling region characterized by a power-law dependence between $\varphi$ and $t$, from $t\sim L^{1/2}$ to $t\sim L^{4/3}$ and finally the "steady state" or stabilization region (the SOC [self-organized criticality] state of Bak, Chen, and Creutz [4]) extending from $t\sim L^{4/3}$ to infinite and characterized by small fluctuations of $\varphi$ around some average value $\varphi_0$. These results are obtained from extensive numerical simulations on lattices with different values of L. The critical exponents obtained in the scaling region are robust and do not depend on $p$, for $0.15\leq p \lt0.75$. [...] For low initial occupation ($p\lt 0.15$) or high density occupation ($p \geq 0.75$) the scaling region disappears, and now the domain for large fluctuations of $\varphi$ extends from $t =0$ to $t\sim L^{4/3}$. This region is followed by the "steady state" characterized by small fluctuations around an average value.

I didn't see any rigorous arguments in the papers I found but that doesn't mean there aren't any out there. In particular as Gil hints there is a strong connection to bootstrap percolation, and perhaps some of the theorems proven there apply here as well.

Improve this answer
$\endgroup$
15
$\begingroup$

The asymptotic dynamics of the Game of Life from a random starting field is unknown, and profoundly so. Experiments on small fields for small numbers of generations suggest that the asymptotic density is on the order of 1/20 for a wide range of initial probabilities. But these small experiments cannot answer the big questions. Perhaps there exists a high-density starting pattern that fits in a 1000x1000 square, which aggressively takes over the plane with copies of itself. If such a pattern exists, then it will occur with certainty in any random field that is large enough (say 2^(10^8) on a side). If it occurs, it takes over, and the asymptotic density will be much higher than 1/20.

Researchers disagree on whether such a "cancer" is possible (it would have to defend itself against "background radiation" emitted by its environment). The last time I talked to Gosper on this subject, he was convinced that it is possible; if he is right (and one bets against Gosper on such matters with great caution) then the long-term dynamics of the Game of Life is complicated and Darwinian.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ If you think there is a high-density cancer, then wouldn't you also find it reasonable to think that there could also be a less-dense cancer? In that case, one would expect both such kinds of cancers would appear in the random position, and so the eventual position would be one without a convergent asymptotic density, having pockets of various densities intertwined amongst one another unboundedly. $\endgroup$
    – Joel David Hamkins
    Commented Jun 6, 2013 at 2:07
4
$\begingroup$

I see no reason to expect a different answer to the questions:

(1) "What is the behavior of John Conway's Game of Life when the initial position is random?"

and

(2) "What is the behavior of Brian Silverman's Brian's Brain when the initial position is random?"

I therefore propose (2) as an alternate to Gil Kalai's question. The complexity of the Brian's Brain's is more visible at human time/space scales and, presumably, computer simulations can be trusted more than for Game of Life.
    It would be great if anyone could prove that a random initial position of Brian's Brain on an infinite grid results with almost certainty in a pattern that remains always non-empty as time goes to infinity? I suspect however, that this is a difficult problem.

Improve this answer
$\endgroup$
3
  • $\begingroup$ At least as observed for moderate size starting fields and relatively high densities of initial cells, Life tends to stabilize to scattered still lifes and oscillators, with longer-lived chaotic regions whose frequency is monotonically decreasing with time. If there are no replicators that can survive in junk etc., then in Life it seems plausible that with probability 1 any given cell eventually becomes periodic, although this is currently out of reach of proof. In contrast, Brian's Brain seems to stay chaotic for all time. So qualitatively they are very different. $\endgroup$
    – David Eppstein
    Commented Jun 13, 2013 at 23:52
  • $\begingroup$ What about glider guns? Strictly speaking, they don't replicate themselves, but they create junk... which might result (with a lot of luck) in the occurrence of another glider gun somewhere else far away. For "moderate size starting fields", I am of course forced to agree with you... but that's not what I had in mind when I wrote this answer. $\endgroup$
    – André Henriques
    Commented Jun 14, 2013 at 11:15
  • $\begingroup$ I think that, in fields of the typical sort of junk left over from a high-density random start, that a sequence of gliders fired into the junk (from a gun surrounded by empty space) will fairly quickly cause gliders to come back along a reverse track (endangering the gun). Over longer time scales the glider stream will cause the junk to slowly grow into the empty space, endangering the gun in a different way. So more active countermeasures would be needed to allow such a pattern to live and reproduce itself. $\endgroup$
    – David Eppstein
    Commented Jun 14, 2013 at 18:25
4
$\begingroup$

About the random version, a relevant reference is (IIRC):

Peter Gacs, Reliable computation with cellular automata. Journal of Computer System Science, 32(1):15–78, February 1986. Conference version at STOC’ 83.

(As well as subsequent works.) Essentially given a Turing-complete automaton - not sure about the terminology here - it can be made robust to noise by adding error-correction mechanisms. It is not about GoL, and tastes a bit more like low-temperature Glauber dynamics mixed with directed percolation, but the ideas might be relevant here.

Improve this answer
$\endgroup$
3
$\begingroup$

In the probabilistic scenario it seems unlikely that the density will be arbitrary low. As soon as the system would approach this state the would be a lot of empty space with infinitely many small living configurations. Several of these will be in space filling configurations. The small t value should then not be able to prevent a significant growth due to these configurations.

Improve this answer
$\endgroup$
0
$\begingroup$

It seems there is an easy solution to the „probabilistic variant of the rule of the game itself”.

If we ask about the situation after the infinite number of steps, the answer is: the system will end up in its absorbing state “all cells dead”.

First observe that in the „probabilistic variant of the rule of the game itself”, the state “all cells dead” is really an absorbing state - no cell has a chance to become live again.

Now, observe that in any current state, there’s always a non-zero probability of the next state being “all cells dead”. Each living cell in step t can be dead in step t+1 and each dead cell in step t can be dead in step t+1 with non-zero probability.

With infinite number of steps, an event with non-zero probability in every step will happen with probability one in some step.

The above is a general idea. To be more precise we should talk about asymptotic density of living cells being zero and not about ending up in a state of “all” cells being dead. Probably, the best way to start the analysis of the infinite grid case is to observe that in any step there’s a non-zero probability of the next state having arbitrarily low density of living cells. For further discussion see the comments below.

Improve this answer
$\endgroup$
10
  • 1
    $\begingroup$ If the number of cells is finite, yes. -- But if we have an infinite grid as assumed in the question, your argumentation works only for any finite part of the grid -- or am I missing something? $\endgroup$
    – Stefan Kohl ♦
    Commented Jun 9, 2013 at 12:42
  • 1
    $\begingroup$ I think of the infinite grid as infinitely many finite grids (“regions”). If each region tends to its absorbing state, the system (infinite grid) tends to a state where the density of living cells is approaching 0. Moreover, when the density of living cells is very low, the interaction between regions vanishes. You need 3 cells on the border of a neighbor region to “give birth” in a given region. There'll be infinitely many regions with some living cells. I see this fact as similar to e.g. the fact that there are infinitely many primes but their density is zero. Is my argument correct? $\endgroup$
    – helper
    Commented Jun 9, 2013 at 22:02
  • 1
    $\begingroup$ @helper: I don't agree with you. You say: "I think of the infinite grid as infinitely many finite grids (regions). If each region tends to its absorbing state, the system (infinite grid) tends to a state where the density of living cells is approaching 0". You assume that the speed at which a finite region tends to the empty state is greater than the speed at which information flows between the various finite regions. But I don't think that that's a correct assumption. $\endgroup$
    – André Henriques
    Commented Jun 9, 2013 at 22:11
  • 1
    $\begingroup$ @André Henriques I also say "when the density of living cells is very low, the interaction between regions vanishes. You need as many as three cells on the border of a neighbor region to “give birth” to a previously dead cell in a given region." $\endgroup$
    – helper
    Commented Jun 9, 2013 at 22:19
  • 2
    $\begingroup$ @helper The argument is definitely wrong. There are processes (e.g. the contact process with high enough propagation rate, or "slices" of directed percolation) which die in any finite volume for the reason you mention, but nevertheless admit invariant distributions with positive asymptotic density. $\endgroup$
    – Vincent Beffara
    Commented Jun 11, 2013 at 17:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .