2

When I was experimenting with the Game of Life by John Conway, I realised that any n by n diagonal square does not die off at the end; it always reaches a state where it oscillates or does not continue to evolve any further. A diagonal square looks something like this: A 50 by 50 diagonal square

However, I was not able to find a suitable proof for this. I have tried using induction, but was unable to find something that was useful. Anyone who could come up with a proof for this discovery would be appreciated.

1 Answers1

2

Technically your claim is not true for all $n$: the 1×1 diagonal square (i.e. a single live cell) dies off in one generation.

Also, in general, almost all sufficiently large and dense random GoL patterns leave behind stable or oscillating ash, frequently also emitting one or more gliders (or rarely other spaceships). Thus, in a general sense, your observation is not particularly surprising.

Of course, a diagonal square is not a random pattern, and it might be possible for patterns in a particular family like that to evolve in ways that are not typical of random patterns. However, it turns out that large diagonal squares initially evolve in a way that fills the area of the original square with unstable chaotic patterns quite similar to those typically arising from random soups (with matching symmetry).


Specifically, on the first time step, all but the corner squares of a filled $n×n$ square die off due to overpopulation, while the cells immediately outside the edges of the square become live, producing a hollow diagonal square with blunted corners like this:

Golly screenshot of a Conway's Game of Life pattern showing a filled diagonal square of live cells and its next generation descendant

Now, the diagonal lines themselves are stable, since each live cell in them has two live neighbors. The three-cell vertical lines at the corners, however, will propagate inwards towards the center of the square, with their ends supported by the diagonal lines:

Golly screenshot showing the next four generations of the same initial diagonal square pattern in Conway's Game of Life

Note that the complex patterns left behind the lines at the corners (shown in red in the picture above) cannot influence the evolution of the moving vertical lines and the diagonals supporting them (shown in white), as the lines are propagating at one cell per time step (i.e. at lightspeed) towards the center and any influences from behind simply cannot catch up.

Now, it's a well known observation in Conway's Game of Life that such orthogonal lines propagating at lightspeed tend to generate complex chaotic patterns behind them. In particular, the line of cells just behind the front line effectively emulates Wolfram's one-dimensional elementary CA rule 23 which, being an odd-numbered rule, has the property generating a 1:1 alternating pattern of dead and live cells from any initial condition. This alternation then drives the evolution of patterns of cells on the lines further back, preventing it from stagnating.

The result is that, after about $n$ generations, your initial $n×n$ diagonal square of all live cells has essentially turned into a roughly $n×n$ diagonal square of (symmetrical) random chaos. And typically this chaos will then stabilize over subsequent generations, usually leaving behind one or more still lifes, oscillators and/or gliders. I doubt it's possible to prove anything very general about the composition of this ash, and indeed it's not impossible that all of it might disappear just by chance for some $n > 1$ that we simply haven't found yet. But as $n$ becomes larger, the likelihood of this happening gets smaller and smaller.