28
$\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$
  • 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$ – Joel David Hamkins Dec 13 '17 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$ – Sebastien Palcoux Dec 13 '17 at 14:45
  • 1
    $\begingroup$ @JoelDavidHamkins: $n=10$ produces a pattern of period $15$, but that's not the point of this question. $\endgroup$ – Sebastien Palcoux Dec 13 '17 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$ – Tobias Fritz Dec 13 '17 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 Dec 13 '17 at 19:08
5
$\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$
  • 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$ – André Henriques Dec 15 '17 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$ – მამუკა ჯიბლაძე Dec 15 '17 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$ – Sebastien Palcoux Dec 15 '17 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$ – David Eppstein Dec 16 '17 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$ – David Eppstein Dec 25 '17 at 7:51

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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