Holstein Rules Cellular AutomataThis 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. Eppstein - Gliders in Life-Like Cellular Automata Checker Board PatternsVery 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.
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 ResultsI 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:
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 ModelIt 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. |
My Turing Machine in Conway's Game Life
Site by Paul Rendell. |
Last Update 05/November/2023 |
Comments to Paul Rendell |