This is one of a class of Cellular Automata. A Cellular Automata consists of a field of cells. A cell must be in one of fixed number of states. For these rules there are just 2 states called live and dead. The state of a cell in the next generation is dependant only on its current state and the current state of its 8 neighbor. There are an astonishing number of patterns that change in interesting ways. Conway's Game Life is the most widely know set of rules in this class.
The Holstein rules are:
These rules are symmetrical. They can be rewritten:
The patterns formed by these rules are very limited. Their are a handful of period 2 oscillators and stable patterns and not much else. However 3 Gliders have been found - see D. Eppstin - Gliders in Life-Like Cellular Automata
Checker Board Patterns
Very little happens to most patterns under Holstein rules. Most islands of one state in the other simply shrink to nothing. In particular sharp corners disappear and the islands becomes more rounded as they shrinks. If two square islands touch corners these corner will be stable due to the symmetrical rules. A checker board pattern can fill a closed universe such as a torus and create some interesting effects. When such a checker board pattern is run there is an initial blow off phase where the horizontal and vertical lines are broken in to shallow waves of low period. So far so good, everything is symmetrical.
Adding a single cell along one boundary of a checker board pattern creates an initial asymmetry. The odd thing is how consistent the results are regardless of where along the boundary or how big the universe is. There are very few exceptions. The following describes the smallest checker board of just 4 squares, 2 live and 2 dead.
Check board patterns with more that 4 squares show how unstable the corners are in less symmetrical conditions. The single extra cell on one boundary causes most of the corners release immediately following the blow off stage. The remaining boundaries are again straight with oscillations in one direction and wavy in the other. The remaining blocks behaves in the same way as above.
I define the release point as the generation when there are is a clear gap of 2 cells. This is ideal for manual detection. However I might have to move to automatic detection to increase the number of samples. I expect to find that some sizes of the universe that promote resonance. For automatic detection it will be more sensible to take the release point as half way through the phase change. The exact definition will need to be chosen with care.
Checker Board Results
I am currently trying to determine how the time to release the corners varies with the size of the universe. For a square universe it appears to be about n5 where n is the universe size.
In the data the 'type of end' is:
Trend using all raw samples:
Trend using average samples:
More data is needed to get these numbers a bit closer together. The trend for variable width shows a larger R2 for a power trend than a straight line. However looking at the graph of averaged results this is not very convincing. The trend for variable height shows a good R2. However there are only 4 samples so this is probably luck. I suspect the numbers for this series to end up differently.
Applet Notes / Source
Full source code of the applet is available here.
Pattern Data can be cut and pasted when "View Pattern Text" is selected. Only MCL format is produced as this has the WRAP option. An extra data line has been added to MCEll FORMAT. this is #CYCLE. It shows the current cycle (Generation). Thus it is possible to save a pattern part way through a long sequence and restore the cycle number.
To set the board size fill in the numbers and press 'ENTER' while the focus is in one of the board dimension text boxes.
The step button with the variable step field acts differently to the fixed step buttons. It works with "Run Until" and "While changes >" and "Refresh" while the fixed step buttons do just that.
The Standard Deviation for the number of cells changing state per cycle gives the Standard Deviation of the sample rather than an estimate for the population.
Random Walk Model
It may be possible to model the release of the corners of a 4 square checker board as a random walk on a circle.
The simplest model would have two walkers starting at opposite sizes of a circle then both walk at random until they meet. A simple Monte Carlo simulation gives the meeting time f(n) for a circle size n as:
A little more realistic model might have pairs of walkers say male and female. The members of a pair are constrained to stay within a distance of each other. The sequence ends when a male from one pair meets a female from the other. The conundrum is how to model the link between partners. The wavy boundary will probably not stretch much beyond an angle of 30o. I expect that as this is approached the probability of partners moving away from each other gets lower.
Seeding After Blow off
Seeding after blow off is not the same as seeding before blow off. If the basic checker board pattern is run until it settles down into a low period oscillation before the odd seed cell is added a wider range of results is produced.
In particular the corners can release without joining. An example is the 120 square torus 4 square checker board seeded 8 cells from the corner after blow off with a single cell pattern at the corners (sq120bf1s8.mcl in the applet pattern library). This releases the corner straight away but leaves a stable 90o corner. This can be used to make a stable island.
My Turing Machine in Conway's Game Life
Site by Paul Rendell.
Last Update 29/January/2015
Comments to Paul Rendell