5
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\begingroup$ 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. $\endgroup$ Feb 14, 2012 at 6:54
  • $\begingroup$ Thanks. Yes I'm trying to exclude some non-cyclic growth with this statement. I'll try to modify question. $\endgroup$ Feb 14, 2012 at 15:50
  • 1
    $\begingroup$ "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$. $\endgroup$ Feb 14, 2012 at 17:45
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 14, 2012 at 18:21
  • $\begingroup$ You're welcome. See below. $\endgroup$ Feb 15, 2012 at 1:43

1 Answer 1

9
$\begingroup$

[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.]

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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