In this blog post I will try to prove some facts about extension of Conway's game of life to transfinite number of steps.
Definitions[]
For a given cell C we denote by \(C_\alpha\) the value of C at step \(\alpha\) (where 1 means the cell is alive, 0 means cell is dead). If \(C_\alpha=1\) and exactly 2 or exactly 3 of its neighbours are alive at step \(\alpha\), set \(C_{\alpha+1}=1\). If \(C_\alpha=0\) and exactly 3 of its neighbours are alive at step \(\alpha\), set \(C_{\alpha+1}=1\). Otherwise, set \(C_{\alpha+1}=0\). If \(\alpha\) is a limit ordinal, set \(C_\alpha=\text{limsup}_{\beta<\alpha}C_\beta\).
For the pattern P which is a function \(C\rightarrow C_0\) we say that P is stable if \(\forall\alpha\forall C: C_\alpha=C_0\). Equivalently, \(\forall C:C_0=C_1\).
We say that P stabilizes if \(\exists\alpha\forall C: C_\alpha=C_{\alpha+1}\). We say that P dies if \(\exists\alpha\forall C: C_\alpha=0\).
We say that P is an oscillator if \(\forall C\forall\alpha\exists\beta>\alpha:C_\beta=C_0\).
If P is an oscillator, let its period be defined as the smallest ordinal \(\tau\) such that \(\forall\alpha\forall C:C_\alpha=C_{\alpha+\tau}\)
For the patterns I'm going to use either RLE or macrocell file format, which can be copy-pasted directly into Golly.
Questions arising[]
Given a pattern P one can ask few things: does P eventually die? stabilize? oscillate? If so, how many steps does it take? Because (obviously) answer might depend on a pattern, it's more natural to ask for complexity of these questions. For normal (finite time) GoL, problem of deciding if the pattern stabilizes is equivalent to halting problem, so one can suspect that ITGoL stabilization problem is equivalent to ITTM halting problem, although I can't see how one can prove it.
We can also ask - what are the possible stabilization times? pattern death times? times before pattern starts oscillation? oscillation periods? Two questions I stuck upon: can a pattern have stabilization time exactly \(\omega+1\)? Can a pattern have transfinite period?
Theorems[]
First theorem will prove the first bound on possible lengths of time before pattern starts oscillating. This is so called "classical cofinality argument":
Theorem 1: Let pattern P evolve according to specified rules. Then the pattern starts oscillating before \(\omega_1\)
- Fix any ordinal \(\alpha<\omega_1\). Suppose for cell \(C\) we have \(C_{\omega_1}=0\). Then there is an ordinal \(\beta_C<\omega_1\) such that \(\forall\beta>\beta_C.\beta<\omega_1:C_\beta=0\). We know that \(\bigcup\beta_C\), where union is over all \(C\), is a countable union of countable ordinals, thus countable. We can assume \(\alpha>\delta\). Let us now enumerate all cells \(C_1,C_2,C_3,...\) (we can assume there is infinitely many of them) which have value \(1\) at \(\omega_1\). Then there is an ordinal \(\tau_{1,1}>\alpha\) such that \(C_1\) has value 1 at \(\tau_{1,1}\). There is an ordinal \(\tau_{2,1}>\tau_{1,1}\) such that \(C_2\) has value 1 at \(\tau_{2,1}\). There is an ordinal \(\tau_{1,2}>\tau_{2,1}\) such that \(C_1\) has value 1 at \(\tau_{1,2}\). And so on, we get an infinite sequence \(\tau_{1,1}<\tau_{2,1}<\tau_{1,2}<\tau_{3,1}<\tau_{2,2}<\tau_{1,3}<\tau_{4,1}<...\) of countable ordinals. At step being their union, \(\tau\), we have that all of \(C_1,C_2,C_3,...\) have value 1. Thus, for every \(C\) we have \(C_\alpha=C_{\omega_1}\). One easily verifies that this implies oscillation.
In many cases we can do better:
Theorem 2: Let P be a finite inital pattern (in fact, we can use computable, arithmetical, hyperarithmetical or even ITTM-computable here, but that's beyond the point). If P stabilizes, then it does so before stage \(\lambda\). If P eventually oscillates, then it starts not later than at \(\zeta\) and with period at most \(\Sigma\).
- It's easy to see that there is a machine M which starts on empty input and can simulate evolution of P. It's also quite trivial to see that one step of ITGoL can be simulated in \(\omega\) steps of M. Let make machine M' which simulates evolution of P and looks at each pair consecutive patterns and compares them. If P stabilizes, then M' halts, and this happened at step before \(\lambda\). Because \(\omega\lambda=\lambda\) we have that M' simulated at most that many steps of ITGoL, so pattern stabilizes before \(\lambda\). For second claim, we use similar reasoning, along with classical result by Welch, that snapshot of any ITTM at step \(\zeta\) repeats at stage \(\Sigma\). We also use facts that \(\omega\zeta=\zeta,\omega\Sigma=\Sigma\).
Patterns[]
First, some "trivial" patterns, which show that every finite number is a possible death time:
1 step: o$bo! 2 steps: o$bo$2bo$3bo! 3 steps: o$bo$2bo$3bo$4bo$5bo! 4 steps: o$bo$2bo$3bo$4bo$5bo$6bo$7bo!
This is obviously extendible. Next one shows that \(\omega\) is possible death time too:
bo$2bo$3o!
Now we will look at a less trivial example:
3o!
This is a blinker, arguably the simpliest non-trivial pattern in GoL, where it's an oscillator with period 2. However, in this transfinite time extension, at step \(\omega\) it becomes a cross, which evolves into traffic lights - pattern of four blinkers. At step \(\omega2\) each of these becomes a cross and blows up, and this continues. It isn't obvious that this process will ever terminate, but turns out this pattern stabilizes after \(\omega5+25\) steps.
The above happens for many oscillators - after step \(\omega\), they just blow up. Some of them, however, can survive the \(\omega\)-th step. Two of the examples are beacon and spark coil:
Beacon: 2o$2o$2b2o$2b2o! Spark coil: 2o4b2o$obo2bobo$2b4o$obo2bobo$2o4b2o!
Now I'll show some patterns which stabilize after transfinite time: first two, fountain and figure eight, take \(\omega+2\) steps to stabilize:
Fountain:
b2ob2o$b2ob2o$2bobo$obobobo$obobobo$2o3b2o!
Figure eight:
3o$3o$3o$3b3o$3b3o$3b3o!