31
$\begingroup$

If the initial state of Conway's game of life is a line of $n \in [0,100]$ alive cells, then it vanishes completely after some steps iff $n \in \{0,1,2,6,14,15,18,19,23,24 \}$. See below for $n=24$.
enter image description here

Question: Is such a line non-vanishing for any $n \in [25,\infty)$?

Edit

Definition: a finite pattern $p$ has a weak period $wp$ if for any cell $c$ in the grid, there is $k>0$ such that the set of cells which are neighbours of neighbours of neighbours... ($k$ times) of $c$, is periodic of period $wp$ after sufficiently many generations, from the initial state $p$.

The sequence A061342 gives the weak period $wp_n$ of a line of $n$ alive cells. By combining the checking above with the fact that $wp_n \ge 2$ for $n \in [84,1000]$, we deduce that the pattern is non-vanishing for $n \in [25,1000]$. We observe that for $n=500$, four gliders are produced on the boundaries after $435$ steps, but $435<500$, so this must happens $\forall n \ge 500$. Assuming that these gliders (or others) are perpetual (as stated implicitly by Nathaniel Johnston in A061342, although without reference, while the proof could be non-trivial, as pointed out by Will Sawin in the comments), the answer to the above question would be yes.

Definition: a finite pattern $p$ is weakly-vanishing if any cell $c$ in the grid becomes perpetually dead after sufficiently many generations (depending on $c$), from the initial state $p$.

Improved question: Is there a weakly-vanishing line of $n$ alive cells with $n \in [25,\infty)$?

Stronger question: Is $wp_n \ge 2$ for any $[84,\infty)$ ?


Tobias Fritz pointed out in the comments that there is a one-cell thick pattern with infinite growth (see this page), but it is disconnected. Bonus question: Can that happen in the connected case?

$\endgroup$
17
  • 1
    $\begingroup$ Is your question about all $n>24$ or just $n\in[25,100]$? Also, you state "iff", but are the non-vanishing instances actually known? (e.g. eventually periodic) $\endgroup$ Commented Dec 13, 2017 at 14:28
  • 1
    $\begingroup$ @JoelDavidHamkins: for $n \in [0,100]$ I have checked that the vanishing happens iff $n \in \{0,1,2,6,14,15,18,19,23,24 \}$. The question is about $n>24$ (and so $n>100$ after my checking). $\endgroup$ Commented Dec 13, 2017 at 14:45
  • 1
    $\begingroup$ @JoelDavidHamkins: $n=10$ produces a pattern of period $15$, but that's not the point of this question. $\endgroup$ Commented Dec 13, 2017 at 15:14
  • 2
    $\begingroup$ What do you mean by stationary component? Do you know that the pattern can be decomposed for long times into gliders/spaceships plus something that happens in a bounded region? This is not always the case, e.g. there even are patterns that grow quadratically (pentadecathlon.com/lifeNews/2011/05/…). $\endgroup$ Commented Dec 13, 2017 at 18:05
  • 4
    $\begingroup$ How do you know the gliders are perpetual? Couldn't something else catch up and stop them? Or can you rule that out? $\endgroup$
    – Will Sawin
    Commented Dec 13, 2017 at 19:08

1 Answer 1

6
$\begingroup$

Just to help develop intuition - here is a fragment of a typical evolution for large $n$ (made with Golly)

enter image description here

$\endgroup$
10
  • 1
    $\begingroup$ I presume that this is large (size) $n$ and large (time) $t$. But does this screen shot correspond to $n$ and $t$ of comparable size? Or are we looking here at a case of $0<<n<<t$? $\endgroup$ Commented Dec 15, 2017 at 9:27
  • $\begingroup$ @AndréHenriques To my shame I did not record exact numbers, but your last suggestion is correct: $n$ is around $23000$ and $t$ is around 2 million. $\endgroup$ Commented Dec 15, 2017 at 10:00
  • 1
    $\begingroup$ The first glider produced (at $t=435$, visible here at extreme left) did not exceed the half high of the pyramid, so here $t$ must be less than $23000$. $\endgroup$ Commented Dec 15, 2017 at 13:31
  • 3
    $\begingroup$ It should be straightforward to prove that this Sierpinski triangle pattern continues to be generated for arbitrarily large lines of live cells (and therefore that the answer to the original question is yes). The only potential issue is the case analysis needed to handle what happens when the two Sierpinskis growing from either end meet at the middle of the line. $\endgroup$ Commented Dec 16, 2017 at 20:34
  • 1
    $\begingroup$ If you try big enough starting lines (I tried around 500,000) you can see that the lines down the middles of each big triangular void (where the gliders meet) eventually become periodic. In the image above, the biggest complete triangles appear to have about three periods within them. $\endgroup$ Commented Dec 25, 2017 at 7:51

You must log in to answer this question.

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