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. Eppstein - 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.
 Generation 0 |
 Generation 22,600 |
 Generation 24,085 |
 Generation 24,090 |
 Generation 113,088 Period 2 Osillator |
| Checker Board pattern seed "103" Universe 50 × 50. | ||||
The pattern shown above can be downloaded here and pasted into Chris Rowett's lifeviewer. A smaller pattern here takes fewer generation (1,327) to collapse.
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 n | f(n) = 0.001 n5.16 | R2 = 0.79 | Data |
| Rectangular width 142 trend with height n | f(n) = 15.48 n2.32 | R2 = 0.6 | Data |
| Rectangular height 142 trend with width n | f(n) = 0.11 n3.36 | R2 = 0.5 | Data |
| Square universe trend with size n | f(n) = 0.001 n5.02 | R2 = 0.99 | Graph |
| Rectangular width 142 trend with height n | f(n) = 30.39 n2.24 | R2 = 0.97 | Graph |
| Rectangular height 142 trend with width n | f(n) = 0.14 n3.37 | R2 = 0.95 | Graph |
Later work on diagonal bands in A Survey of State Symmetric Cellular Automata has put the above results into doubt. This found that the exponent in the fitted formulas above changes as the extra samples are added for larger universes. A better more consistant fit was found for step size of the random walk. For Holstein the step size of diagonal bands was found to change according to 0.6 n-0.5. Performing the same analysis for Checker Board Patterns has not yet been done.
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:
|
f(n)=0.31n1.96
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.