Paul Rendell's Cellular Automata rule Holstein Page

Holstein Rules Cellular Automata

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:

  A cell is born in an empty square if there are: 3, 5, 6, 7 or 8 neighboring live cells.  
  A cell survives if there are: 4, 6, 7, or 8 live cells. 

These rules are symmetrical. They can be rewritten:

  A live cell is dies if there are: 3, 5, 6, 7 or 8 neighboring dead cells.  
  A cell is not born if there are: 4, 6, 7, or 8 dead cells. 

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.

  • Initially there are 2 more live cells than dead ones. After one generation the number of live and dead cells becomes the same number and stays that way.
  • After the blow off stage the boundary along which the odd seed cell was placed and also the parallel boundary remains basically straight with shallow oscillating waves.
  • The other boundaries starts to move about. They becomes a wavy lines which moves about slowly driven by the oscillations on the straight boundaries.
  • The wavy lines are symmetrical about both of the straight boundaries.
  • In a very few cases the wavy lines become straight and the universe settles into a low period oscillation (osc). In all other cases the wavy lines move about until they touch (join at edge or neck in the middle) along one of the straight boundaries. The comers release and the narrow blocks shrink back to the stable lines leaving a stripe through the universe with straight edges supporting oscillating waves.

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:

  • Join. The corners touch close to the stable lines joining together then shrinking away to the other stable line.
  • Neck. The lines touch in the middle and split with both stubs shrinking back to the stable lines.
  • Osc. The wavy lines become straight supporting shallow oscillations and stops moving.
  • Immediate. The corners release immediately after the blow off stage.

Trend using all raw samples:

Square universe trend with size nf(n) = 0.001 n5.16 R2 = 0.79 Data
Rectangular width 142 trend with height nf(n) = 15.48 n2.32 R2 = 0.6 Data
Rectangular height 142 trend with width nf(n) = 0.11 n3.36 R2 = 0.5 Data

Trend using average samples:

Square universe trend with size nf(n) = 0.001 n5.02 R2 = 0.99 Graph
Rectangular width 142 trend with height nf(n) = 30.39 n2.24 R2 = 0.97 Graph
Rectangular height 142 trend with width nf(n) = 0.14 n3.37 R2 = 0.95 Graph

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

I am using a version of Mirek Wojtowicz's MJCell Java applet. The original is here. My version is here.

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:

with R2=0.53

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.
More typically the corner release comes after a similar time to a join type release. For example sq120bf1s8.mcl in the applet pattern library. A 118 square torus 4 square checker board seeded 21 cells from one edge. The number of live cells does change to equal the number of dead cells, but only after a few generations and leaves a small asymmetrical anomaly which causes the corner to release without a join after 243596 cycles.

My Turing Machine in Conway's Game Life

Site by Paul Rendell.

Last Update 29/January/2015

Comments to Paul Rendell