Systematic survey of small patterns
Posted: November 28th, 2018, 7:47 am
This is the first of what is planned as a series of posts, about the systematic survey I’m doing of small Game of Life patterns (by which I mean, patterns with few cells). The main aims are first to confim the finding by Paul Callahan in 1997 that there are no infinite growth patterns with fewer than 10 cells; and second to catalog all those with 10 cells, confirming or refuting the hypothesis that all these develop into either block-laying or glider-stream switch engines. Simsim reported in 2014 (on the “23 cells quadratic growth (new record)” thread viewtopic.php?f=2&t=1483#p14143) having done a maybe-not-quite-complete search of 10-cell patterns consisting of two clusters (see below for my definition of a “cluster”), but no systematic survey of the single-cluster cases has been attempted as far as I know. I aim to cover every case and eventually, to produce a fully-documented account of what I’ve done – in effect, a proof that I have a complete enumeration of infinite-growth patterns with no more than 10 cells, although it’s unlikely to come up to the standards of rigour a mathematics journal would require. This is all in the service of the investigation of “Sparse Life” (infinite fields of arbitrarily low initial density) that I’ve pursued on and off since the 1970s, and am now resuming after a long break. I’m working in Python 2.7, with the actual pattern runs performed in Golly. I have Python code to check whether a pattern is “quiescent”, meaning it consists only of still-lifes, oscillators, gliders and *WSSs which will not interact in future. The code would mark patterns containing any other kind of spaceship as non-quiescent, and also requires a “period” parameter, which tests whether the non-spaceship part of the pattern is the same after a set number of steps; hence patterns containing oscillators of periods that are not factors of this parameter would be marked non-quiescent. All patterns marked as non-quiescent are therefore checked to see why they have been so marked. Varying the period, and some aspects of the code, allow for searches for outcomes other than infinite growth (oscillators of different periods, gliders, *WSSs).
A cluster, by the definition I’m working with, consists of one or more polyplets. A polyplet is a set of on-cells connected orthogonally or diagonally, so that there’s a path between any two on-cells (when I refer simply to the “cells” of a pattern I mean the on-cells; I’ll only use the latter term when needed for clarity) that goes through no off-cells. If there is more than one polyplet, then adding all the off-cells that both border more than one polyplet, and have at least three on-cell neighbours, must produce a single polyplet. Thus by this definition, two separate clusters may share a common neighbouring off-cell (or for larger clusters, more than one such neighbour), as long as none of these neighbours itself has three on-cell neighbours. Additionally, every on-cell in the whole cluster must belong to at least one 3*3 square of cells containing at least 3 on-cells (this condition excludes some groups that would otherwise meet the definition, but include a 2-plet where only one of the cells is in such a 3*3 square; the other member of the 2-plet could then be removed without changing the successor pattern).
For the purpose of checking for any infinite growth patterns of less than ten cells, it makes sense to check smaller patterns first, so the search is divided into a series of sub-searches checking 3, 4, 5…9 cell patterns, I’ve currently completed work on the patterns up to 8 cells – and of course found no infinite growth, but have some findings to report in a later post (apart from the main aims, I’ll also report on any interesting findings along the way). I have catalogued all the 9-cell single-cluster patterns, but not yet run them, and done preliminary work for the two- and three-cluster 9- and 10-cell patterns. Taking this approach, we need only consider patterns that grow at step 1 (I use the term “step” where some prefer “generation”): any that reduce their cell-count (number of on-cells) at step 1 will already have been checked, and any that remain at the same cell-count must lead, possibly through a chain of successors with the same cell-count, to a pattern with either decreased or increased cell-count. If the former, the successor with decreased cell-count will already have been checked; if the latter, it will be found in the current sub-search. In the ten-cell case, since I want a full enumeration of infinite-growth patterns, ten-cell patterns with ten-cell successors will need to be checked. Also, for two- and three-cluster patterns, it is only failure of the total cell-number to grow at step 1 that automatically eliminates a pattern: one or (in the twin-cell case) even two clusters may shrink while the total grows.
A cluster, by the definition I’m working with, consists of one or more polyplets. A polyplet is a set of on-cells connected orthogonally or diagonally, so that there’s a path between any two on-cells (when I refer simply to the “cells” of a pattern I mean the on-cells; I’ll only use the latter term when needed for clarity) that goes through no off-cells. If there is more than one polyplet, then adding all the off-cells that both border more than one polyplet, and have at least three on-cell neighbours, must produce a single polyplet. Thus by this definition, two separate clusters may share a common neighbouring off-cell (or for larger clusters, more than one such neighbour), as long as none of these neighbours itself has three on-cell neighbours. Additionally, every on-cell in the whole cluster must belong to at least one 3*3 square of cells containing at least 3 on-cells (this condition excludes some groups that would otherwise meet the definition, but include a 2-plet where only one of the cells is in such a 3*3 square; the other member of the 2-plet could then be removed without changing the successor pattern).
For the purpose of checking for any infinite growth patterns of less than ten cells, it makes sense to check smaller patterns first, so the search is divided into a series of sub-searches checking 3, 4, 5…9 cell patterns, I’ve currently completed work on the patterns up to 8 cells – and of course found no infinite growth, but have some findings to report in a later post (apart from the main aims, I’ll also report on any interesting findings along the way). I have catalogued all the 9-cell single-cluster patterns, but not yet run them, and done preliminary work for the two- and three-cluster 9- and 10-cell patterns. Taking this approach, we need only consider patterns that grow at step 1 (I use the term “step” where some prefer “generation”): any that reduce their cell-count (number of on-cells) at step 1 will already have been checked, and any that remain at the same cell-count must lead, possibly through a chain of successors with the same cell-count, to a pattern with either decreased or increased cell-count. If the former, the successor with decreased cell-count will already have been checked; if the latter, it will be found in the current sub-search. In the ten-cell case, since I want a full enumeration of infinite-growth patterns, ten-cell patterns with ten-cell successors will need to be checked. Also, for two- and three-cluster patterns, it is only failure of the total cell-number to grow at step 1 that automatically eliminates a pattern: one or (in the twin-cell case) even two clusters may shrink while the total grows.