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

Intro

The question is about Game of Life.

Let us denote the set of points obtained from initial configuration $A$ after $m$ steps as $A(m)$ (we are only interested in finite initial configuration, i.e. those one which formed by finite number of marked cells).

Let us denote the number of marked cells at configuration $A$ as $N(A)$. Then increment at $m$-th step could be computed as $i(A, m) = \max(0, N(A(m+1)) - N(A(m))$.

Majority of configurations doesn't grow in size after some number of steps. There are known examples which grows linearly or quadratically in time. For all of this examples the relative increment decay as times goes by: $\frac{i(A,m)}{N(A(m))} \to 0$ as $m \to \infty$.

Question

Is it possible to prove some uniform result of this type:

is it true that $\forall \epsilon > 0$ (may be some other restriction) $\exists M_\epsilon$ such that $\forall A$ (for any arbitrary chosen initial configuration) and $\forall m > M_\epsilon$: $\frac{i(A,m)}{N(A(m))} < \epsilon$?

May be it makes sense for some good family of initial configurations $A$?


This is rather a probe question which I asked with a hope to find some references or ideas in answers which will direct me in more useful settings.

share|improve this question
2  
The "beacon", en.wikipedia.org/wiki/File:Game_of_life_beacon.gif is a counterexample to the question as stated (though it's probably not what you are looking for). It oscillates between two states of 6 and 8 living cells, which means it has relative growth of $1/3$ infinitely many times. –  Johan Wästlund Feb 14 '12 at 6:54
    
Thanks. Yes I'm trying to exclude some non-cyclic growth with this statement. I'll try to modify question. –  Kirill Shmakov Feb 14 '12 at 15:50
1  
"Sawtooth" patterns are counterexamples too, with the same pair $(N(A(m)),N(A(m+1)))$ and the same $i(A,M)>0$ occurring infinitely often but for different configurations. See the Wikipage en.wikipedia.org/wiki/Sawtooth_(cellular_automaton) [add the closing parenthesis to the URL if necessary]. More simply, a spaceship gun of even period has $N(A,m) \rightarrow \infty$ but $i(A,2m)/N(A,2m)$ approaches a positive limit as $m \rightarrow \infty$. –  Noam D. Elkies Feb 14 '12 at 17:45
1  
Thank you for this counter example, it answers the question. I think, the most reasonable way to close the question is to post this comment as an answer, which I'll accept. –  Kirill Shmakov Feb 14 '12 at 18:21
    
You're welcome. See below. –  Noam D. Elkies Feb 15 '12 at 1:43
add comment

1 Answer

up vote 9 down vote accepted

[expanded from the comment above]

There cannot be such a result. The simplest aperiodic counterexample is a "lightweight spaceship gun" of even period $p$, whose $m$-th generation has population $9m/p + O(1)$ or $12m/p + O(1)$ according to the parity of $m$, whence $i(A,m)/N(A(m)) \rightarrow 1/3$ in one congruence class mod $2$.

There are also more complicated counterexamples such as "sawtooth" patterns whose population at time $m$ oscillates between $O(1)$ and $cm+O(1)$, and for which the same pair $\bigl(N(A(m)),N(A(m+1))\bigr)$ and the same $i(a,M)>0$ occurs infinitely often but for different configurations.

In general it's a reliable heuristic that if you imagine any kind of behavior of a pattern in Conway's Game of Life then either it's obviously impossible (e.g. exponential growth, or an aperiodic pattern that always stays within a fixed rectangle), or somebody has wasted devoted enough time and/or ingenuity to construct a pattern showing that behavior.

[For the benefit of those who know little more of Conway's Game of Life than the basic rules: a "spaceship" or "ship" of period $n$ is a finite pattern $S$ that after $n$ steps reappears shifted by some translation $T$, and thus moves through space with speed $T/n$. A period-$p$ "gun" $G$ for a spaceship $S$ is a finite pattern whose $p$-th generation is the disjoint union of $G$ with a copy of $S$ that does not further interact with $G$; thus $G$ produces a stream of ships of type $S$. The first few Life ships have period $4$; the smallest of these, the glider, has constant population (namely 5) so cannot be used here, but the next-smallest, the "lightweight spaceship" (LWSS), alternates between populations of $9$ and $12$, so works for any even $p$. If you know a glider gun of sufficiently large period $p$ (and the classic $p=30$ of Gosper's gun is large enough) then you can position three of them to make an LWSS gun by colliding their glider streams.]

share|improve this answer
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.