Waves, Crystals and Chaos
A Survey of State Symmetrical Cellular Automata
0. Contents
- Introduction
- Definitions
- Blowoff
- Category Chaos
- Category Crystallising
- Category Minimal
- Category Structural
- Category Wave
- Boundary Waves in H1D8^{RS}
- Edge Behaviour
- Small Universe Crystallisation
- Random Walk Drag
- Summary
- Appendix DataSets
- References
Introduction top
This is a survey of all state symmetrical two state two dimensional cellular automata with rules based on cell counts using a Moore Neighbourhood in a closed torus universe. It finds three main classes of interesting behaviour, waves, crystals and chaos. Chaotic behaviour when the universe fills with ever changing patterns. Wave behaviour where the boundary between areas of different state supports complex waves. Crystallisation when the universe fills with unchanging patterns which often have low period oscillators trapped in them. In addition to minimal behaviour two small groups of rules show edge effects and the Structural properties. The edge effects are one dimensional oscillators on stable boundaries and the structural properties show up when the universe size has a major impact on the evolution of random patterns. The Fredkin replicator cellular automata being the prime example.
In more detail all rules where classified into 4 categories:
- Chaos. Patterns expand to full the universe and are chaotic.
- Crystallising. Patterns expand to fill the universe and become primarily static sometimes trapping oscillators.
- Minimal. Patterns stop changing after a few generations.
- Structural. The universe size has a major impact on the evolution of random patterns.
- Waves. Random patterns shrink but diagonal bands support complex waves which perform a random walk.
Some rules where found to have the following Boundary effects:
- Waves. Boundaries between areas of different state supports complex waves.
- Edge Effects. Stable boundaries between areas of different state have trapped one dimensional oscillators.
The term state symmetrical is used to describe Cellular Automata (CA) that have the property that the states are all equivalent. The initial condition of the universe of any CA is defined by the pattern made by the different states that the cells initially have. A Cellular Automata is state symmetrical if the value of the different states make no difference to the evolution of the pattern. More formally initial patterns are made by attributing each cell in the universe to one of n states P_{1} .. P_{n} each of which takes a value mapped on a 1:1 basis from the n states CA_{1} .. CA_{n}. Of the CA. In a state symmetrical CA the outcome is the same for all 1:1 mappings.
This survey limits itself to 2 state 2D CAs with rules based on cell counts using a Moore Neighbourhood. There are 256 distinct state symmetrical CAs. The survey was done using Golly a tool for running CAs. A control panel StateSymCP was written in lua to aid this investigation. Statistical analysis was performed with the help of the package. These CAs are traditionally defined by the number neighbourhood counts for a cell to be born and for a live cell to survive. The most studied state symmetrical CA is known as Day & Night which is defined as: B3678/S34678. The state symmetry is seen in that the list for survive is the opposite of the list for not survive (not Survive count = 8 - survive count) thus a state symmetrical CA can be defined just by the rules for being born. Following the practice of Wolfram we shall treat the counts on which cells are born as bits in a binary number bit 0 set 1 for born on count zero thus B3678 is the binary number 1 1100 1000, however to combine brevity with ease recovery of the bit positions we will use a hexadecimal notation giving H1C8 for this rule. The binary notation is used in some descriptions below adding X to mean either 1 or 0.
The number of gliders found in each rule is mentioned when listing gliders in each category. This information comes from David Eppstein's glider pattern data base.
Definitions top
Initial Pattern
The square torus universe is initialised with half the cells of each state as far as possible. This is done in one of three ways:
- Random
- Diagonal Bands
- Orthogonal Bands
- A Random Diamond Island
Complimentary Rules
Every CA has a complimentary CA that creates the same patterns by one CA changing state when the other does. In binary notation the complimentary rule is the rules ones' compliment. E.g. Rule Day & Night is B3678/S34678 which in notation defined above is 1 1100 1000 or H1C8. Its compliment is B01245/S0125 which is 0 0011 0111 or H037. H1C8 + H037 = H1FF the definition for ones' compliment. In general we will use the even rule of the complimentary pair to identify a rule and where useful include the other in round brackets e.g. H1D0(H02F).
Golly always runs the even rule for both rules of a complimentary pair as it is not easy to run the odd rule in an open universe. Golly's RuleLoader was used to create three state definition to allow the odd rules to be run.
Seeds
The seed is used to initialise the random sequence for the random initializations. When initialising with bands the seed pattern is used to modify one boundary by adding or removing cells in the following way. The seed is made up of the characters '0', '1' ,2' or '3' where each character dictates the state of successive pairs of cells one on each side of the boundary. These cell pairs normally define the boundary by being of opposite state. The characters have the following effects:
'0' No change '1' The boundary cell perpendicularly above changes state '2' The boundary cell perpendicularly below changes state '3' Both boundary cells change state |
F#1 Seeds on an Orthogonal band |
F#2 Seeds on a Diagonal band |
The seed can unbalance the proportion of cells in each state as will a universe whose size is an odd number. The sequence of patterns created by a seed can not be predicted with the exception of rules in the Structural Category.
Symmetrical seeds on initial bands can create symmetrical patterns. The symmetry of the seed does not effect the symmetry of a random pattern. Both mirror symmetry and rotation symmetry occur. On diagonal bands symmetry occurs when pairs of symbols align with the zigzag pattern of the diagonal boundary. Seed "12" is rotational symmetrical on both diagonal and orthogonal bands but seed "102" is only rotationally symmetrical on an orthogonal band. Symmetrical patterns generate half the variation of non symmetrical patterns and preserve the ratio of cells of each state from one generation to another.
Strobing, Reverse Strobing
Strobing is the flashing behaviour which one of the complementary pair of rules often exhibits. A rule and its complement both show the same sequence of patterns but the states which make up the patterns differ. If the state of a cell changes state under one rule then it would not under the complementary rule and visa versa. In a universe which has all cells with the same state (e.g. is empty) even rules cause no change and odd rules cause a complete state charge every generation.
A rule is said to exhibit reverse strobing if after running for a while the even rule typically strobes a pattern more than its complement. In this document where appropriate ^{RS} is appended to the rule name to indicate reverse strobing e.g. H072^{RS}. It is easier to see the changes over one generation viewing the odd rule when reverse strobing occurs.
A test was performed of all the Chaos and Structural category rules to see how often an arbitrary cell changed state creating the Strobe Ratio Data. The measurement was made over 240 runs of 200 generations between each chaos CA and it's complementary CA. The 240 runs where made up of the combinations of 60 seeds and 4 widths. A strobe ratio of less than 1 indicates normal strobing and a ratio greater than 1 indicates reverse strobing. The strobing type of H016 and H116 are unexpected both look like they reverse strobe but the measured strobing ratios of 0.78 and 0.8 respectively imply otherwise.
Another measure taken is the State Change Ratio. This is calculated as the proportion of the 256 different neighbourhood pattern that cause a state change for the a rule compared to the number that the complimentary rule would have caused. In general this was similar to the strobe ratio but with the strobe ratio showing a larger range. At the low end is rule H088 which had a Strobe Ratio of 0.1 and a Sate Change Ratio of 0.33 while at the height end rule H076^{RS} had a State Change ratio of 9.14 and a State Change Ratio of just 2.88.
Golly will accept the rule for either complementary pair but will actually run the one which does not strobe an empty universe. Golly's rule RuleLoader feature was used to create a three state rule where one state is not used but satisfies Golly's condition that there is a state that does not change when zero neighbours of the that state. This was embedded in a lua script StateSymCP developed to investigate state symmetrical cellular automata. This script allows swapping between complimentary pair rules and helps the investigation of reverse strobing.
Static Debris
Static Debris is the small still life and short period oscillators often left in islands of one state which only effect the pattern when a boundary moves over them.
Random Walk Speed/Drag
The speed a boundary round the universe moves is referred to as the Random Walk Speed and is a characteristic of Category Wave. An object moving at random will on average be a distance from its starting point which is proportional to the square of the time elapsed. A boundary made up of linked objects each of which is moving at random while remaining linked will not have moved so far.
The term Random Walk Drag is used to express the amount that a rule's behaviour effects its Random Walk Speed.
Fluid
A fluid is a chaotic mixture of the two states which has a characteristic proportion of cells of one type to the other. If the ratio is 50:50 this term is not useful but a ratio of 3:2 would imply one of 2:3 as well. No measurement of fluid ratio has been attempted to date.
End Rate Analysis
Patterns under rules in the Crystallising and Wave categories settle down to a final state after a time which tends to be longer in larger universes. For rules in the Crystallising category this is when the universe becomes crystallized. For Wave rules this is when peaks in the waves beak through the band and the band collapses. Crystallising was also observed in some rules in the Chaos category for small universes see Small Universe Crystallisation below.
The following algorithms are used is End Rate Analysis.
- Oscillator: the number of generations until oscillation is determined.
- Break: In Universes initialised with a band the number of generations until the band breaks is determined.
- Chaos: The number of generations until the longest line of cells of the same state is below a fixed level or the population falls below a fixed level.
Blowoff top
When the universe is initialised with two bands of opposite state some rules will generate lines of cells parallel to the band in sections which are not modified by the seed. This is termed Blowoff. The following describe the behaviour with seed "0".
Blowoff from Orthogonal bands
Two types of Blowoff occur. Stable Blowoff where parallel lines spread through the universe and Resonating Blowoff where lines spread through the universe and also change width each generation. In both cases newly created lines of cells change state next generation so stable Blowoff creates strobing parallel lines in even rules.
- B-S1: Rules with the binary patterns X X1XX 1XX0, that is both B6 and B3, generate strobing parallel lines all one cell wide.
- B-R1: Rules with the binary patterns X X0XX 1XX0 generate strobing parallel bands of varying width.
Blowoff from Diagonal bands
Types of Blowoff
F#1 B-R1/S1/1/1S Gen 1 53x53 seed "0" |
F#2 B-R2/S2 Gen 1 53x53 seed "0" |
F#3 B-R4/S4 Gen 1 53x53 seed "0" |
F#4 B-R1 H00C Gen 500 53x53 seed "0" |
F#5 B-R2 H006 Gen 500 53x53 seed "0" |
F#6 B-R4 H00A Gen 500 53x53 seed "0" |
F#7 B-S1 H03C^{RS} Gen 12 53x53 seed "0" |
F#8 B-S2 H182 Gen 6 53x53 seed "0" |
F#9 B-S4 H01A Gen 7 53x53 seed "0" |
B-R1: The 1st generation is a single diagonal line. Subsequently generating strobing parallel bands of varying width. Rules with the binary patterns X X00X 1100, X X1X0 1100 and X X010 1100. See F#1 and F#4.
B-R2 The 1st generation is pair of diagonal lines meeting at the corners. Subsequently generating strobing parallel bands of varying width.
Rules with the binary patterns X XXXX 0X10 excluding X 000X 0010. See F#2 and F#5.
B-R4 The 1st generation is pair of diagonal lines meeting at 2 sides. Subsequently generating strobing parallel bands of varying width.
Rules with the binary patterns X XXX0 1X10. See F#3 and F#6.
B-S1 stable 1st generation is a single diagonal line
Rules with the binary patterns X XX11 1100 add additional diagonal lines each generation giving a strobing checkerboard pattern.
Rules with the binary patterns X X101 1100 result in strobing bands of varying width ending quickly in a P2 oscillator dominated by bands three cells wide.
See F#1 and F#7.
B-S2 The 1st generation is pair of diagonal lines meeting at the corners
Rules with the binary patterns X XX00 0010 add additional diagonal lines also joined at the corners each generation. See F#2 and F#8.
B-S4 stable 1st generation is pair of diagonal lines meeting on 2 sides
Rules with the binary patterns X XX00 0010 add additional diagonal lines each generation giving a pattern of strobing parallel lines. See F#3 and F#9.
B-1 1st generation is a single diagonal line, no change in subsequent generations.
>Rules with the binary patterns X XX0X 1000. See F#1.
B-1S 1st generation is a single diagonal line, no change in subsequent generations.
Rules with the binary patterns X XXX1 1X10 strobe the single line. See F#1.
Category Chaos top
Chaos patterns expand to full the universe and are chaotic, these CAs show four distinct visual patterns Maze, Network, Flecks and Uniform. Maze pattern show vertical and horizontal lines with right angle corners. Network rules produce network patterns from the interleaving of two fluids each dominated by different a state. Flecks rules show small short lived islands of a single state that are appear and disappear quickly, some migrate as their boundaries change. Uniform patterns occur when a large portion of the cells change state almost at random like white noise forming no visible structures.
Chaos rules can be divided into the following categories:
- Maze: large 12 rules and small 31 rules
- Network: Large Network 35 rules, Medium Network 31 rules and Small Network 11 rules
- Flecks 19 Rules
- Uniform 15 rules
Subcategory Maze
The division into Large and Medium sub categories was done arbitrarily by observation.
Chaos Large Maze Rules:
H072^{RS}, H074^{RS}, H076^{RS}, H088, H08A, H08C, H172^{RS}, H174^{RS}, H176^{RS}, H188, H18A,H18C
Large Maze Rules with Gliders:
H074(1)
Chaos Small Maze Rules:
H026, H034^{RS}, H038^{RS}, H044, H046, H058^{RS}, H094, H098, H0A6, H0B4^{RS},
H0B6^{RS}, H0B8^{RS}, H0BA^{RS}, H0C6, H0EA^{RS}, H0EC^{RS}, H126, H134^{RS}, H138^{RS}, H144,
H146, H158^{RS}, H16C^{RS}, H194, H1A6, H1B4^{RS}, H1B6^{RS}, H1B8^{RS}, H1BA^{RS}, H1C6,
H1EC^{RS}
Small Maze Rules with Gliders:
H058(1),H0B4(1),H0B8(1),H134(1),H158(3),H1B8(3)
Large Maze Rules patterns are made up of orthogonal lines one cell wide with right angle junctions. The universe is divided into stable areas with continually moving boundaries between them. In small universes the universe crystallizes. In principle some large universes could crystallize if a stable pattern can tessellate it completely. F#10 shows rule H088 as an example of a large maze with scattered small changes over one generation.
Small Maze Rules patterns are very chaotic with small areas of up to 10 cells square changing slower giving the impression of flickering cross shapes when viewed running. The flickering shapes appear independent not joining into a network as would subcategory Large.
Subcategory Network
The division into Large, Medium and Small sub categories was done arbitrarily by observation.
Chaos Large Network Rules:
H016^{RS}, H01A, H01C^{RS}, H01E^{RS}, H022, H02E^{RS}, H04E^{RS}, H05E^{RS}, H062, H064,
H08E^{RS}, H09C^{RS}, H09E^{RS}, H0A2, H0AE^{RS}, H0CE^{RS}, H0D2, H0E2, H0E4, H116^{RS},
H11A^{RS}, H11C^{RS}, H122, H12E^{RS}, H14E^{RS}, H162, H164, H19C^{RS}, H1A2, H1AE^{RS},
H1CE^{RS}, H1D2, H1DC^{RS}, H1E2, H1E4
Chaos Large Network Rules with Gliders:
H1E4(3)
Chaos Medium Network Rules:
H014, H02C^{RS}, H036^{RS}, H03A^{RS}, H04C, H052, H056, H05A^{RS}, H05C^{RS}, H06E^{RS},
H096, H09A^{RS}, H0A4, H0AC^{RS}, H0B2, H0C4, H0DC^{RS}, H0EE^{RS}, H114, H12C^{RS},
H136^{RS}, H14C, H15A^{RS}, H15C^{RS}, H16E^{RS}, H196, H19A^{RS}, H1A4, H1AC^{RS}, H1B2,
H1EA^{RS}
Chaos Medium Network Rules with Gliders:
H1A4(2)
Chaos Small Network Rules:
H032, H066, H0CC, H0E6, H132, H13A^{RS}, H152, H166, H1C4, H1D4, H1E6
Chaos Small Network Rules with Gliders:
H1D4(1)
The universe consists of two or more interlaced fluids. Within each network pockets expand and contract. The pockets often contain small islands of the other fluid which join and break off from the edge as the network connections continually break and reform. The interface between the fluids is often an area of chaos. The subdivision into Large Medium and Small was done visually. F#11 shows the reverse strobing rule H1E1(H016) as an example of a large network with considerable change over one generation. The changes for rule H016 are all the cells which did not change in H1E1.
Subcategory Flecks
Chaos Flecks Rules:
H010, H018, H028, H048, H04A, H06C^{RS}, H0A8, H0D4, H0D6^{RS}, H0D8^{RS},
H118, H128, H148, H156, H198, H1CC, H1D6, H1D8^{RS}, H1EE^{RS}
Chaos Flecks Rules with Gliders:
H028(2),H048(2),H0A8(8),H0D8(5),H128(4),H148(5),H1D8^{RS}(2)
Random patterns in which small short lived islands of a single state appear. In some rules the islands vanish very quickly in others persist for a few generations changing shape and migrating around. F#12 to F#15 show an example of a fleck in rule H0A8 lasting over 12 generations it is nearly invisible in static images but stand out from the background of change.
Small Universe Crystallisation is discussed further below. Rule H1D8^{RS} has some wave behaviour which is described separately below.
Subcategory Uniform
Chaos Uniform Rules:
H012, H024, H02A, H06A^{RS}, H092, H0CA, H0DA^{RS}, H112, H124,
H12A, H14A, H16A^{RS}, H192, H1CA, H1DA^{RS}
Chaos Uniform Rules with Gliders:
None
The universe changes chaotically with no structure.
Category Crystallising top
There are 77 CAs that crystallise to fill the universe will a fixed pattern. Gliders have been found in four of these CAs. An analysis was performed on how long it took for the universe to crystallize with universes of different sizes and with 60 different seeds The results are the FindEnd10-50 Data Set. This also identified the period of any low period oscillators that might have been trapped in the crystal. Some CAs where never observed with trapped oscillators while others had more that one narrow band round the universe with trapped oscillating patterns resulting in an oscillation period too long to measure. In some cases a narrow band round the universe is a one dimensional CA. It is noted that some of these the one dimensional CAs are not state symmetric see Trapped One Dimensional Cellular Automata.
The type of pattern made when the universe is initialised with a band is greatly affected by the type of Blowoff.
(a) Generation 0 |
(b) Generation 10 |
(c) Generation 33 |
(a) Generation 0 |
(a) Generation 10 |
(a) Generation 39 |
F#16 H002 Universe 50 cells square seed "13" | F#17 H0BE^{RS} Universe 50 cells square seed "13" |
These CAs can be sub categorised by the way crystallisation progresses and by the type of pattern after crystallisation.
Crystallising Network Rules:
H03C^{RS}, H042, H0BC^{RS}, H0C2, H102, H13C^{RS}, H142, H1BC^{RS}, H1C2
Crystallising Network Rules with Gliders:
None
Interlaced networks connected diagonally. Some of these rules have solid Blowoff with initial diagonal bands but more interesting crystals with initial orthogonal bands. F#18 shows Rule H03C^{RS}.
Crystallising Maze Rules:
H004, H006, H008, H00A, H00C, H00E, H078^{RS}, H07A^{RS}, H084, H086, H0F2^{RS}, H0F4^{RS}, H0F6^{RS}, H0FA^{RS}, H104, H106, H108, H10A, H10C, H10E, H178^{RS}, H17A^{RS}, H184, H186, H1F2^{RS}, H1F4^{RS}, H1F6^{RS}, H1FA^{RS} and H1FC^{RS}
Crystallising Maze Rules with Gliders:
H078(2),H0F4(1),H178(3),H1F4(2)
Alternate lines in maze like patterns. Two of these (H078^{RS} & H178^{RS}) are border line Minimum changes category as for some seeds the CAs crystallisation halts almost immediately. F#19 shows H008.
Crystallising Blobs Rules:
H020, H03E^{RS}, H040, H060, H0A0, H0DE^{RS}, H0E0, H11E^{RS}, H15E^{RS}, H160, H18E^{RS}, H19E^{RS}, H1A0, H1BE^{RS}, H1C0, H1DE^{RS} and H1E0.
Crystallising Blobs Rules with Gliders:
None
Blobs of each state consolidate from the chaos with single or double cell islands dotted in them some of which are oscillators. In some rules the boundaries of the blobs support waves which die away. Similar in appearance to H09E^{RS} in chaos where the boundaries do not stabilise. F#20 shows H18E^{RS}.
Crystallising Minimal Rules:
H07C^{RS}, H07E^{RS}, H082, H0BE^{RS}, H0FC^{RS}, H0FE^{RS}, H13E^{RS}, H17C^{RS}, H17E^{RS}, H182, H1FE^{RS}.
Crystallising Minimal Rules with Gliders:
None
Patterns expand into empty space and crystallise with minimal change. H082, H07E^{RS}, H0BE^{RS} and H182 have longer period oscillators than the others. H07E^{RS} and H0BE^{RS} particularly from diagonal bands. The two images above of H07E^{RS} in F#22 where made with seed "13" in a universe 50 cells square with an orthogonal band which has an oscillation period of 224 generations. F#21 and F#22 show H07E^{RS}.
Crystallising Edge Rules:
H030, H050, H090, H0B0, H0D0, H110, H130, H150, H190, H1B0 and H1D0.
Crystallising Edge Rules with Gliders:
None
Edge behaviour is described in subsection 10. When initialised with a random pattern these rules behave in a similar fashion to the Wave Category rules.
The types of pattern after crystallisation from a random pattern are :
F#18 H03C^{RS} Network |
F#19 H008 Maze |
F#20 H18E^{RS} Blobs |
F#21 H07E^{RS} Minimal |
The type minimal initialised from an orthogonal band :
(a) Generation 20 |
(b) Generation 21 |
F#22 H07E^{RS} Minimal |
Category Minimal top
Crystallising Minimal Rules:
H000, H002, H070, H080, H0C0, H0F0, H0F8^{RS}, H100, H120, H140
H170, H180, H1F0, H1F8^{RS}
Crystallising Minimal Rules with Gliders:
None
The behaviour of these rules can be defined as rules where the evolution stops in less generations than the universe size They all have a final population ratio of 4:5 or closer in FindEnd10-50 Data Set.
Minimal rules generate the almost the same pattern whether a cell is born with 8 neighbours or not e.g. H0C0 and H1C0. The difference being limited to isolated single dead cells left when cells are not born with 8 neighbours.
Sub Category- No change: H000, H100.
Sub Category- Still Life after a few generations: H002, H080, H0C0, H0F8^{RS}, H120, H140, H180, H1F0, H1F8^{RS}
Sub Category- Edge: H070, H0F0, H170
Category Structural top
Structural Rules:
H054, H0AA, H154 and H1AA
Structural Rules with Gliders:
None
All these rules have a State Change Ratio very similar to the Strobe Ratio which is almost 1.
Rule | Strobe Ratio | State Change Ratio |
H054 | 0.97 | 0.97 |
H0AA | 0.98 | 1 |
H154 | 0.97 | 0.98 |
H1AA | 1.02 | 1.02 |
T#1 Structural Rules Strobe Ratio and State Change Ratio
The rule H0AA has special symmetry. The rule is called Fredkin and is B1357/S02468 in the B/S notation in the binary notation used here it is 0 1010 1010. CA Fredkin in an unbounded universe is a replicator. A patten size n × n becomes nine copies, one where the original was with 8 new copies centres m cells apart after m generations where m is larger then n and m = 2^{2k} and k is an integer. More generally if j is the smallest integer such that n2^{2j} the universe only contains copies of the original pattern at generations p×(2^{2j}) for every integer p > 0 and seemingly random pattern at other generations. Further details can be found in PEDRO and CHUA's work.
In a torus universe the result is dependent on the universe size. In a universe size 2^{n} × 2^{n} the original pattern reappears after 2^{n - 1} generations. In other sizes either the original reappears or one of the successor patterns reappears periodically.
The rules H154 and H1AA also exhibit Structural features. They crystallize in small universes and apart from very small universes the oscillation time of the final pattern is the same for all initial seeds in the same size universe.
(a) Generation 0 |
(b) Generation 1 |
(c) Generation 14 |
(d) Generation 15 |
(e) Generation 16 |
(f) Generation 17 |
F#23 Fredkin CA:H0AA Universe size 32 × 32 The original pattern re-appears from chaos. Seed "000000013" |
Category Wave top
Wave Rules with Gliders:
H068, H0C8, H0E8, H168, H1A8, H1C8 and H1E8
Wave Rules with Gliders:
H068(3),H0C8(11),H0E8(5),H168(3),H1A8(14),H1C8(20),H1E8(3)
Rule H1D8^{RS} has some wave behaviour but is different from the others and not categorized as Wave but as Subcategory Flecks. It's wave behaviour is described separately below.
Category Wave rules support complex waves on boundaries between areas of different state. When seeded with a random pattern all rules in the Category Wave form blocks of similar state and convex boundaries shrink. This leads to either one state dominating containing islands of the other state or separate bands of each state forming round the universe. In the former case the result that the islands continue to shrink leading to an empty universe possibly with Static Debris. This is very similar to rules of the Edge subcategory of Category Crystallising. In the latter case complex waves form on the bands which perform a random walk ending either in a collapse of one of the bands when the boundaries touch or both boundaries becoming frozen probably with trapped oscillators in them.
An interest in checkerboard patterns instigated this survey and one feature of rules with interesting checkerboard patterns is that they also support walking diagonal boundaries. This survey identified eight CA rules that exhibit deep waves on the diagonal boundaries. The seven described in this section and H1D8^{RS} described below Gliders have been found in all of theses CAs. All these rules generate Blowoff from straight orthogonal boundaries, B-R1 for H1A8 and B-S1 in the others. From diagonal boundaries H0C8 and H1C8 have B-1 and the others have B-1S Blowoff.
These rules are examined in detail using an initial pattern with half the universe one state and the other half the other state. This is set out as diagonal bands and complex waves form along the seeded boundary. Initialised with horizontal bands Blowoff occurs leading to unpredictable results which include islands shrinking to nothing, bands with all boundaries having complex waves, chaos with large islands forming and disappearing and checkerboard patterns with static horizontal boundaries and complex waves on vertical boundaries.
Diagonal Bands with Asymmetrical Seeds
Asymmetrical waves form along the seeded boundary and it performs a random walk until it meets another boundary, one area then collapses and shrinks leaving the universe all one state sometimes with Static Debris. The Wave Break data set contains the results of an analysis of how many generations it took for boundaries of a wave to touch an a gap appear in the band. All the rules in Category Wave have diagonal Blowoff of either B-1 or B-1S so the initial band is lined with a row of cells connected diagonally after one generation. This is static thereafter in B-1 and strobes in B-1S. This line of cells means that when a waving boundary touches a static boundary changes quickly run along the whole boundary setting it oscillating. The analysis identified how the time to collapse changes with universe size. The seeds used for the analysis where chosen to avoid generating symmetrical waves.
(a) Generation 6,498 |
(a) Generation 6,507 |
(a) Generation 6,518 |
(a) Generation 65,29 |
(a) Generation 6,538 |
F#50 H0E8 Universe 50 cells square seed "1113" Breaking at Generation 6,518 |
The (b) Figs. below show the statistical fit for both the number of generations = a × e ^{b × U} and for the number of generations = a × U ^{b} where U is the size of the universe. The statistical relationship gives a different result over different size ranges as shown in the (c) Figs. below and discussed further in subsection Random Walk Drag.
H068 F#26 (a) |
F#26 (b) |
F#26 (c) changes in b from a × e^{b × U} with U |
H0C8 F#27 (a) |
F#27 (b) |
F#27 (c) changes in b from a × e^{b × U} with U |
H0E8 F#28 (a) |
F#28 (b) |
F#28 (c) changes in b from a × e^{b × U} with U |
H168 F#29 (a) |
F#29 (b) |
F#29 (c) changes in b from a × e^{b × U} with U |
H1A8 F#30 (a) |
F#30 (b) |
F#30 (c) changes in b from a × e^{b × U} with U |
F#53 (a) |
F#53 (b) |
H1C8 F#31 (a) |
F#31 (b) |
F#31 (c) changes in b from a × e^{b × U} with U |
A very anomalous result in H1C8 with an initial diagonal band seeded "13" in a universe 45 cells square. After the state 0 band broke it rejoined but now with both sides walking. The state 0 band broke again but before the large state 0 island shrank the state 1 band broke thus reforming the bands but this time in an orthogonal orientation. The boundaries of this band found a stable configuration with some trapped period 2 oscillators after 2,080 generations.
H1E8 F#32 (a) |
F#32 (b) |
F#32 (c) changes in b from a × e^{b × U} with U |
Rule H1E8 from a random initial pattern sometimes forms orthogonal bands which often stabilise with long period oscillators trapped, e.g. Universe size 75 seed "113" stabilised a band after 741 generations with a period of 1098.
Symmetrical Seeded Bands
When the seed on an initial orthogonal boundary has mirror symmetry the wave generated does not perform the usual random walk and the number of cells of each state is constant. The wave always passing through two fixed points one in the symmetrical centre of the seed and the other at the opposite side of the universe. If the wave amplitude exceed the width of the band the wave must breakdown however if the universe dimensions are even both bands are of equal width so the equality of the number of cells in each states is preserved. The result is that the wave alternates between horizontal and vertical passing through a mixture in between. Rule H0C8 usually forms stable orthogonal boundaries which stops the oscillation.
(a) Generation 0 |
(b) Generation 397 |
(c) Generation 5490 Period 6 Oscillator |
F#33 H0C8 28 × 28 cell universe Seed "000000000000012" |
Waves on Orthogonal Bands
After Blowoff islands of single state emerge from chaos. These can join up to form of bands or checkerboard patterns or one state may dominate. Bands and checkerboard patterns may have stable boundaries or walking boundaries. Walking boundaries will eventually meet and result in one state dominating a universe which is either empty or with small still life patterns or small oscillators. H1A8 has not been observed forming checkerboards.
- The type of islands that emerge is greatly affected by the universe size. The rules H0C8, H0E8, H168, H1C8 and H1E8 all have strobing Blowoff of single cell lines B-S1.
- If the universe height is divisible by two but not by four then the Blowoff lines meet in phase resulting in a band of synchronised Blowoff opposite the seed. Bands and checkerboard patterns are common.
- If the universe height is divisible by four the Blowoff lines meet out of phase in both band. This leaves two double width Blowoff bands which can lead to double bands and checkerboard patterns.
- If the universe height is an odd number of cells, Blowoff lines meet in phase in one band and out of phase in the other. Bands with two wavy boundaries are common but often one state dominates as bands fail to form or are quickly broken.
In addition to the rotational symmetry found on diagonal bands an orthogonal band can have mirror symmetry. Any seed consisting of just '0' and '3' will create a pattern where both sides of the boundary are reflections of each other with opposite state. These rules can generate symmetrical patterns on an orthogonal boundary from other seeds as well. If the pattern develops mirror symmetry when the universe is an even height the original boundaries will remain anchored if they service Blowoff although the symmetry is not always easy to see through chaotic patterns.
(a) Universe height divisible by four |
(b) Odd universe height |
(c) Universe height divisible by two but not four |
F#34 H0E8 an Orthogonal band with seed "11321" results in Strobing Blowoff |
(a) H168 44 × 44 seed "112" Checkerboard Pattern |
(b) H1E8 45 × 45 seed "1120011" "Orthogonal Band" |
(c) H1E8 44 × 44 seed "113" "Rotated Orthogonal Band" |
(d) H0C8 44 × 44 seed "11321" "Double Band" |
(e) H068 44 × 44 seed "11321" "Chaos" |
F#35 Various outcomes from an Orthogonal band and Blowoff |
Wave Behaviour in Rule H1D8^{RS} top
Rule H1D8^{RS} is classified as chaos with flecks It always goes to chaos in large universes when initialised with a random patten. It can crystallize in a small one. While in the other rules with Wave Behaviour any island of one state will shrink to Static Debris in H1D8^{RS} a randomly initialised universe remains chaotic. An island of single state will become an island of chaos with some peculiar behaviour described below. Initialised with orthogonal bands the Blowoff goes directly to chaos. However if the orthogonal bands have jagged edges to prevent Blowoff they generate chaos which spreads through the universe at a constant speed.
Initialised with a diagonal band chaos spreads quickly along the seeded boundary forming a third band of chaos which has complex waves on both sizes. In large universes this band expands very slowly until both bands of single state collapse leaving the universe full of chaos. In small universes, particularly if the seed is mirror symmetric, after one single state band has collapsed the band of chaos itself collapses leaving Static Debris in an otherwise empty universe.
H1D8^{RS} (a) Universe 50 × 50 seed "13" Generation 200 |
(b) Generations to Band Break |
(c) Generations to Universe Chaos or Empty |
F#36 The time for the universe to become chaotic |
(a) Proportion of Chaos results in F#36 (c) |
(b) Small Universe Crystallization |
F#51 The time for the universe to become chaotic |
The proportion of results that end in chaos changes with the size of the universe. This is related to the size of islands of chaos which expand rather than contract. The initial downward section in F#51 (a) is caused by small universe crystallization shown in the end rate analysis of F#51 (b) using the FindEnd10-30Chaos Data Set .
The H1D8^{RS} Random Diamond Island data set analysed whether a diamond shaped random patterns of different sizes expanded or shrunk by 50%. The results in F#37 show that a diamond 125 cells square is the mid point and larger diamonds are most likely to expand and smaller diamonds are more likely to shrink. F#38 and F#39 show examples of a diamond island shrinking and one expanding.
(a) |
(b) |
(c) |
F#37 Analysis of Shrinking or Expanding 50% by Universe Size |
(a) Generation 0 Population 3,890 |
(b) Generation 484 Population 3,059 |
(c) Generation 968 Population 2,760 |
(d) Generation 1,452 Population 2,272 |
(e) Generation 1,936 Population 1,898 |
F#38 H1D8^{RS} Random Diamond Island size 92 seed "10013" Shrinks by 50&percnt |
(a) Generation 0 Population 11,660 |
(b) Generation 1,104 Population 12,814 |
(c) Generation 2,207 Population 14,535 |
(d) Generation 3,311 Population 16,307 |
(e) Generation 4,415 Population 17,755 |
F#39 H1D8^{RS} Random Diamond Island size 160 seed "1113" Expands by 50&percnt |
F#40 shows H1D8^{RS} with a symmetric seed on a diagonal band in a universe 130 cells square. The symmetric flecks give the appearance of volcanoes. F#40 (d) shows the black state band breaking in two places leaving the chaos band. In this example the chaos band does not expand but shrinks and the band breaks.
(a) Generation 64 |
(b) Generation 7,188 |
(c) Generation 27,303 |
(d) Generation 44,954 |
(e) Generation 45,010 |
(f) Generation 90,069 |
(g) Generation 90,169 |
(h) Generation 93,432 Period 2 Oscillator |
F#40 H1D8^{RS} an Example of a Symmetrical Chaos Band with Complex Waves on Both Boundaries which Eventually Collapses |
Edge Behaviour top
Rules which show Edge Effects are mostly the Edge subcategory of Category Crystallising with H070, H0F0 and H170 from Category Minimal and H010 from Category Chaos. Initialised with a band the seed cause changes to oscillate round the boundary which otherwise remains stable. In addition is H1E8^{RS} from the Blobs subcategory of Category Crystallising which fills the universe with chaos from a band but then crystallizes into blobs with small period oscillators round the boundaries. All the other rules with Edge Behaviour do this when initialised with a random pattern except for H010 which does not crystallize. The oscillators on the boundaries act as 1D CAs with the rules from the Minimal category taking very few generations to arrive at this state.
These rules are divided into two according to the type of oscillations that form on boundaries. The short period rules form simple period two period oscillators on boundaries while the long period rules form complex oscillators. Initialised with a random pattern the long period rules of the Category Crystallising form islands that often do not stop shrinking until either the universe is all one state or contains bands of alternate state sometimes with Static Debris in a similar fashion to the Wave Category rules.
Short Period Rules
In rules with the binary codes X XX11 0000 (H030, H070, H0B0, H0F0, H130, H170, H1B0 and H1F0) an seed on an initial band boundary spreads along the boundary forming a short period oscillator typically period 2. The strobing boundary cells act as a one dimensional CA. Rule 51 in Wolfram's classification Wolfram S. 2002 is one example that is generated.
Initialised with a random pattern these rules quickly form large islands with fixed boundaries lined with strobing cells.
Long Period Rules
The rules with the binary codes X XX01 0000 (H010, H050, H090, H0D0, H110, H150, H190 and H1D0) produce a oscillations that spread along a seeded boundary forming a long period oscillator often too long to measure. These act as a one dimensional CA, rule 150 in Wolfram's classification. Rule 150 is one of the eight additive elementary cellular automata. F#54 some example patterns F#54 (b) and (c) show the period 14 oscillator produced by H010, H090, H110 and H190 and (d) and (e) show the period 12 oscillator produced by H050, H0D0, H150 and H1D0. The changed cells are shown in pink.
- With seeded bands the same pattern tends to be generated by the same seed for the pair of rules which differ only by whether a cell is born with 8 neighbours or not e.g. H0D0 and H1D0 produce the same pattern with most seeds as eight neighbours does not occur at the boundary.
- Rules H010, H050, H090, H110, H150 and H190 usually leave some fixed cells on the boundary while rules H0D0 and H1D0 do not often.
- On an orthogonal boundary the single cell oscillations develop in sections which are either above the original boundary or below it. Sometimes complex interactions develop where these sections meet. e.g. Rule H0D0 universe 20 cells square with seed '123' produces a rotationally symmetrical P12 oscillator.
(a) 20 × 20 Seed "000000000112" |
(b) H010 Generations 12 |
(c) H010 Generations 12-26 |
(d) H050 Generations 11 |
(e) H050 Generations 11-23 |
F#54 Long Period Edge Oscillators |
(a) Long Period Rules with Diagonal Bands |
(b) Long Period Rules with Orthogonal Bands |
F#56 Long Period Edge Oscillators Period with Universe Size |
F#56 shows that the oscillation period is rising sharply with the universe size with a pronounced difference in odd and even universe sizes. T#2 shows the oscillation periods which occurred 10 or more times in the last 3 sizes for which all the seed got results, 60 for each of the 8 rules. It is noticeable that a lot of the oscillation periods are close to 2^{n}.
Band Type | Universe Size |
No of Oscillation Periods |
Oscillation Period (Occurrences > 9) | |||||||||
Orthogonal | 30 | 16 | 30 (347) | 56 (23) | 126 (12) | 210 (30) | 1,022 (21) | 32,766 (10) | ||||
Orthogonal | 35 | 15 | 30 (20) | 32 (22) | 60 (37) | 62 (15) | 112 (7) | 120 (12) | 124 (7) | 240 (10) | 4,095 (327) | |
Orthogonal | 40 | 15 | 24 (346) | 60 (13) | 168 (32) | 1,022 (10) | 2,044 (22) | 8,190 (10) | 58,254 (23) | |||
Diagonal | 30 | 32 | 4 (12) | 28 (13) | 30 (173) | 31 (103) | 42 (11) | 56 (31) | 84 (22) | 210 (15) | 420 (19) | 1,022 (14) |
Diagonal | 35 | 35 | 28 (162) | 30 (23) | 32 (13) | 62 (36) | 112 (16) | 210 (11) | 420 (10) | 4,095 (121) | ||
Diagonal | 40 | 36 | 24 (259) | 60 (15) | 420 (12) | 1,022 (12) | 1,023 (13) | 2,044 (34) | 12,264 (31) | 58,254 (14) |
T#2 The Oscillation periods which occurred 10 or more times in.
The behaviour of these trapped 1D CA's is described further below.
Initialised with a random pattern these rules quickly form large islands with oscillations along the boundaries which sometimes become fixed or form bands. In rules H050,H0D0,H150 and H1D0 the islands usually shrink to nothing so , rules H090,H110 and H190 the island boundaries usually become fixed. These rules are in the Crystallising Category Rule H010 is an exception it is chaotic with Small Universe Crystallisation.
An example of forming islands whose boundaries become fixed is rule H090 from a random initial patten for width and height of 200 and seed "1232". The oscillation period of this pattern has not yet been determined. It remains an oscillator after 107 generations contains many trapped oscillators. Oscillators of periods 8, 14 and 36 have been seen. The actual oscillation period is 1,718,640 generations so there must also be oscillators with periods 5,11 and 31 or multiples of these.
(a) Generation 0 |
(b) Generation 10 |
(c) Generation 20 |
(d) Generation 30 |
(e) Generation 107 |
F#24 H090 from a random initial patten for width and height of 200 and seed "1232" Crystallized as Generation 107 as a period 1,718,640 generation oscillator
An example of forming a band is rule H150 from a random initial patten for width and height of 200 and seed "1232" stopped arbitrarily at generation 4,185,098 oscillation period is greater than 300,000. The general shape of the boundary is maintained but the oscillation along curved section is 3 cells deep but only one cell deep on the straight sections.
(a) Generation 0 |
(b) Generation 50 |
(c) Generation 2000 |
(d) Generation 4,185,098 |
(e) Generation 5,118,331 |
F#25 H150 from a random initial patten for width and height of 200 and seed "1232"
Trapped One Dimensional Cellular Automata
Trapped One Dimensional Cellular Automata occur in rules of the Edge category which exhibit long period oscillation. They also occur in maze patterns trapped in straight maze sections. Maize patterns produce two different One Dimensional Cellular Automata, one with each state as the CA and the other providing the background. An example is H08D(H172) shown in F#55. In a universe 24 cells square with a random seed of "112" it has a period of 84 generations after 1,367 generations. It has 6 trapped oscillators with periods of 6, 12, 14 and 28 generations. These act like Rule 178. T#3 lists the rules and the State Symmetric rules that generate them. Seeds that create trapped One Dimensional Cellular Automata on a boundary can be constructed that create sort sections of known patterns so that adding seeds together the result can be predicted.
An orthogonal boundary can support a classical 2 state one dimensional CA. A diagonal boundary has a more complex neighbourhood structure. H150 also supports 60 degree diagonal bands which have even more complex neighbourhood structures on their boundaries see F#49.
1D RULE (in Binary) | State Symmetric | State Symmetric Rules |
72 (0100 1000) | Not | H178 |
72 (0100 1000) | Not | H178 |
90 (0101 1010) | State Symmetric | H17A |
94 (0101 1110) | Not | H072, H07A |
126 (0111 1110) | Not | H07E |
129 (1000 0001) | Not | H07E |
133 (1000 0101) | Not | H072, H07A |
146 (1001 0010) | Not | H086, H182 |
150 (1001 0110) | State Symmetric | H010, H050, H082, H082, H090, H0D0, H110, H150, H190, H1D0 |
160 (1010 0000) | Not | H184, H18C |
164 (1010 0100) | Not | H084, H08C |
165 (1010 0101) | State Symmetric | H172, H17A |
178 (1011 0010) | Not | H070, H0B0, H0F0, H130, H170, H186, H186, H1B0 |
182 (1011 0110) | Not | H086, H182 |
218 (1101 1010) | Not | H084, H08C |
237 (1110 1101) | Not | H178 |
250 (1111 1010) | Not | H184, H18C |
T#3 One Dimensional Cellular Automita and the State Symetric Rules that Generate them
(a) Generation 0 |
(a) Generation 1 |
F#49 H150 with a 60 degree Diagonal Band Seed "0" a Period 2 Oscillator |
(a) Generation 1,367 |
(a) Plus Changes |
F#55 H08D(H172) A Reverse Strobing Maize Rule with long period trapped oscillators |
Small Universe Crystallisation top
The rules in T#4 all show crystallization in small universes and Crystal Reworking in larger ones. Crystal Reworking is the growing and shrinking of stable areas within a chaotic background. F#42 to F#46 show images of the universe with the changes over a small number of generations hi lighted. Small Universe Crystallisation is distinct from very small universes which do not have a very large number of possible patterns so the length of the sequence leading to repeating of a pattern is shorter. A universe 10 by 10 has been chosen as the minimum having 2^{100} possible patterns so that any repeating sequence must be a very small fraction of this number to be detected.
An analysis of the time to crystallise with respect to universe size shows that the time to crystallise grows exponentially with the universe size to the point where most patterns will fail to crystallise within the experiment time limit F#47 is an example graph showing this also giving the maximum oscillation period of 5 for the usable section of the data. By way of comparison F#48 shows the average data for all non chaos rules and gives a linear result. Subsection 12.1 Random Walk Drag shows that there is no point is comparing the figures for fitted exponential curves over different ranges as the exponent is likely to change with universe size. The FindEnd10-30Chaos Data Set used 60 seed results for each universe size over the range 10 - 30 cells square. It detects a crystallized universe in the first 1 million generations if it contains oscillators with a combined period of less then 200 generations. T#4 contains the results. The rules H08C and H172^{RS} crystallized to maze patterns with trapped oscillators that had very long periods.
The rules included in the FindEnd10-30Chaos Data Set are those that the FindEnd10-50 Data Set found more than 10 crystallization out of 60 seeds for the universe size 10 x 10
RULE | Chaos Type | Crystal Type | Universe Size Range 90% Solved | RULE | Chaos Type | Crystal Type | Universe Size Range 90% Solved | |
H010 | Network | Empty | 10-30 | H0A8 | Network | Empty | 10-15 Limited by number of generations | |
H01E^{RS} | Network | Diagonal Bands | 10-18 Limited by number of generations | H172^{RS} | Maze | Maze | 16 Limited by Oscillation period | |
H022 | Network | Gel | 10-15 Limited by number of generations | H174^{RS} | Maze | Maze | 10-24 Limited by number of generations | |
H05E^{RS} | Network | Diagonal Bands | 10-18 Limited by number of generations | H176^{RS} | Maze | Maze | 10-30 | |
H072^{RS} | Maze | Maze | 10-28 Limited by number of generations | H188 | Maze | Maze | 10-30 | |
H074^{RS} | Maze | Maze | 10-28 Limited by number of generations | H18A | Maze | Maze | 10-25 Limited by number of generations | |
H076^{RS} | Maze | Maze | 10-30 | H18C | Maze | Maze | 10-30 | |
H088 | Maze | Maze | 10-30 | H1AE^{RS} | Network | Gel | 10-27 Limited by number of generations | |
H08A | Maze | Maze | 10-26 Limited by number of generations | H1CE^{RS} | Network | Gel | 10-13 Limited by number of generations | |
H08C | Maze | Maze | 10-16 Limited by Oscillation Period | H1D8^{RS} | Network | Empty | 2 | |
H08E^{RS} | Network | Orthogonal Bands | 10-14 Limited by number of generations | H1DC^{RS} | Network | Gel | 10-14 Limited by number of generations | |
H09E^{RS} | Network | Islands | 10-25 Limited by number of generations |
T#4 Chaos Rules that Crystallize in Small Universes
Figures F#42 to F#46 below shows example patterns for the different types of chaos and the types of crystals that result. In the chaos phase both states have a connected network throughout the universe which interact with each other in a chaotic fashion. When the chaos phase forms parallel lines of alternate state with right angle bends we describe this as a Maze pattern. Different type of crystal form in different ways:
- Network Collapse. In the chaos phase both states have a connected network throughout the universe, if sufficient links break the networks becomes a number of isolated islands which can shrink (F#42 and F#43) to leave Static Debris unless the boundary stabilizes earlier (F#44). The GEL is a pattern of single cells which stabilises large areas of otherwise single state in rules with reverse strobing.
- Band Creation. A stable band forms round the universe limiting the chaos to two smaller areas which then become divided in turn (F#46).
- Chaos islands die off. Stable islands emerge from the chaos with areas of chaos between constantly reworking the edges. If sufficient stable boundaries appear and the areas of chaos become trapped as oscillators or die out completely (F#45). This is common in Maze patterns where different maze like tessellations meet at incompatible boundaries.
Rule H051(H1AE) shows the chaos pattern in a larger universe then the crystallization as crystallization only occurs after a very large number of generation in universes where the chaos pattern is interesting. This supports the theses that in Crystal Reworking the crystal size is similar to the size of universes where crystallization is seen.
(a) Generation 500 |
(b) Changes Generation 500-501 |
(c) Crystallized at Generation 2906 Period 2 Oscillator |
(d) Changes of the Oscillator |
F#42 H010 Network → EMPTY, Universe 24 x 24 (Cells that changed state are in red) |
(a) Universe 40 x 40 Generation 2000 |
(b) Changes Generation 2000-2001 |
(c) Crystallized at Generation 362 Period 4 Oscillator |
(d) Changes of the Oscillator |
F#43 H051(H1AE) Network → GEL, Universe 20 x 20 (Cells that changed state are in red) |
(a) Generation 2000 |
(b) Changes Generation 2000-2001 |
(c) Crystallized at Generation 6,163 Period 12 Oscillator |
(d) Changes of the Oscillator |
F#44 H161(H09E) Network → Islands, Universe 24 x 24 (Cells that changed state are in red) |
(a) Generation 500 |
(b) Changes Generation 500-501 |
(c) Crystallized at Generation 1011 Period 2 Oscillator |
(d) Changes of the Oscillator |
F#45 H18D(H072) Maze → Maze, Universe 24 x 24 (Cells that changed state are in red) |
(a) Generation 500 |
(b) Changes Generation 500-501 |
(c) Crystallized at Generation 3,681 Period 2 Oscillator |
(d) Changes of the Oscillator |
F#46 H1E1(H01E) Network → Bands, Universe 20 x 20 (Cells that changed state are in red) |
F#47 H18A Maze → Maze A good example of Crystal Reworking. Crystallizing when Chaos is trapped. |
F#48 Average Generations to Crystallization in non Chaos Rules. |
The rules of the Chaos subcategory Network show shadowy patches that to move about the universe. These are areas of chaos with just enough of a distinctive proportion of each state for the eye to pick up. If one thinks of the areas of different state proportion being different fluids then the equivalent to crystallisation in small universes would be the complete universe being one type of fluid.
Random_Walk_Drag top
The Random Walk Drag of a boundary wave varies with universe size as shown in the Category Wave subsection. Not only does the drag increase exponentially with size but the exponent also charges. This is unlike the exponential pattern of a single random walker see Drunkard's Walk. The Category Wave subsection shows the exponent getting smaller with universe size. In order to follow up this apparent trend an extension to the Wave Break data set was made (Wave Break H168) for rule H168 taking the data to a Universe size of 200. F#52(a) shows the fitted curve for the whole range, the equivalent to F#29. F#52(b) shows change in the exponent of a curves fitted to a rolling range of 6 data points. F#52(c) shows the fitted curve for the last section which is no longer falling in F#52(b). The reason for the fall in the value of the exponent with the length of the boundary is unknown but may be to do with ripples of change propagating along the boundary. Ripples are less likely to start on a short boundary leading to less movement.
(a) Random Walk Drag Fitted exponent over the full Range | (b) changes in b from a × e^{b × U} with U |
(b) Fitted Curve Over the Last Section |
F#52 Wave Break H168 Results
The motivation of this survey was to find rules that support checkerboard patterns first identified in H1E8 which is B35678/S4678 and has the name Holstein. These patterns show a random walk drag which is the square of the random walk drag of the waves described here. They are initialised as rectangles of alternate state filling a torus universe with seeds on one boundary which do not modify the boundary too close to a corner. They have the following properties:
- After a few generations both states have equal population.
- Blowoff occurs and after Blowoff the seeded boundary and boundaries parallel remain level with Blowoff like oscillation.
- The pattern is mirror symmetric about the seeded boundary, with opposite states.
- The boundaries perpendicular to the seeded boundary support complex waves.
- The corners make a random walk along the boundaries parallel to the seeded boundary.
- The checkerboard pattern collapses when two corners touch or more rarely two boundaries touch.
- The random walk drag of the corners is very high, about the square of the drag for diagonal boundaries.
The rules that support checkerboard patterns are: H068, H0E8, H168 and H1E8.
Summary top
The survey found five categories of behaviour, Chaos, Crystallizing, Minimal, Structural and Waves.
The Chaos Category has interesting rules which form islands of crystals or fluids of different proportions of the two states with boundaries that are continually changing. In some rules they touch each and in others they are embedded in chaos. In small universes some will crystallize.
The Crystallising Category rules produce crystals with different forms, Networks, maze patterns and blobs.
The Minimal Category rules do very little.
The Structural Category rules perform with mathematical precision.
The Wave Category rules showed that Random_Walk_Drag does not just increase exponentially with size but its exponent aso changes.
Boundary Waves in H1D8^{RS} where a surprise and showed that while the two states behave symmetrically a mixture of the two can have an asymmetrical relationship with both. It also demonstrates the effect of extra space on the random walk drag which tends to lead to small islands shrinking and large ones expanding.
This work has discovered that the Random Walk Drag of boundaries not only does the drag increase exponentially with size but the exponent also charges exponent getting smaller with universe size with the increment decreasing. The hypothesis is that ripples of change occasionally propagate along the boundary for some distance restarting more vigorous monument. With a short boundary Ripples are less likely to start. Further work is required to provide support for this hypothesis.
The emergence of asymmetry is shown in the fact that the One Dimensional Cellular Automata that occur spontaneously are not all themselves state symmetric. It is also shown in the Chaos created by H1D8 is not symmetric with either state.
The properties of the rules can be found here.
Appendix DataSets top
Description | Files |
FindEnd10-50 Data Set An End Rate Analysis performed on all rules using 60 non symmetrical seeds with a random initial pattern for square universes sizes 10 to 50 cells in steps of 5 run for up to 10,000 generations or ending with an oscillating pattern with a maximum oscillation period of 100 generations. | FindEnd10-50R_Script.txt FindEnd10-50ROut.zip FindendGen.r |
FindEnd10-50Edge Data Set This data set performs the same analysis as the FindEnd10-50 Data Set except that it uses diagonal and orthogonal bands with one seeded edge and cover rules with the Edge Behaviour that generate one dimensional CA's. The oscillation period is very dependent on the length of the any oscillating section of the seeded edge and can be very large. It collects the data for universe size 10 to 50 cells square in steps of 1. | FindEnd10-50EdgeScript.txt FindEnd10-50EdgeOut.zip FindEnd-OneDeeLP.r FindEnd-OneDeeSP.r |
FindEnd10-30Chaos Data Set This data set performs the same analysis as the FindEnd10-50 Data Set over the size range 10 to 30 in steps of 1. | FindEndchaosCrys_Script.txt FindEndchaosCrysOut1.zip FindEnd-chaos.r FindEnd-wave.r |
State Change Data The State Change Ratio is calculated as the proportion of the 256 different neighbourhood pattern that cause a state change for the a rule compared to the number that the complimentary rule would have caused. This was calculated by a Python program. |
ruleStateChangeRatio.py rule-StateChangeRatio.txt |
Strobe Ratio Data The Strobe Ratio measurement was made over 240 runs of 200 generations between each chaos CA and it's complementary CA counting the number of state changes. The 240 runs where made up of the combinations of 60 seeds and 4 widths. A strobe ratio of less than 1 indicates normal strobing and a ratio greater than 1 indicates reverse strobing. |
SymCAC_StrobeRatio__Script.txt SymCAC_StrobeRatio__C_Script.txt strobeRatio.r StrobeRatio.txt |
State Symmetrical Control Panel for Golly This ZIP file contains lua modules for the control panel and also a folder of Golly RuleLoader files for the odd complementary rules. Run the script controlPanel.lua contained in the folder. Golly's preferences must be modified to point to this file in order to run the odd rules. | SymCACP-1.zip |
Wave Break Generation to wave break for universes size 10-100 in steps of 5 for rules with Wave Behaviour. It measures the number of generations taken for a band boundary with complex waves to touch the neighbouring boundary and for a band to start to collapse. This information is used to calculate the average time for a band to collapse for each size of universe. It gives a measure of the drag created by the rule slowing down the random walk of the wave. The seeds used for the analysis where chosen to avoid generating symmetrical waves. |
SymCACPWave_B_Script.txt SymCACPWave_B_Out.zip FindEnd-wave.r |
Wave Break H168 Generation to wave break for universes size 10-200 in steps of 5 for rule H168. An extension of the Wave Break data set to show that the Random Walk Drag eventually becomes linear. |
SymCACPWave_Bh168_Script.txt SymCACPWave_Bh168_Out.zip SymCACPWave_Bh168.r |
H1D8^{RS} Random Diamond IslandThe number of generations it takes for an random island in H1D8^{RS} to either grow or shrink. Used to determine the island size for which both outcomes are equally likely. The initial pattern is a diamond shape filled with a seed based random pattern on cells to be 50% of each state. It was run until the population was 50% larger or 50% smaller. | SymCACPWave_ChaosIsle_Script.txt SymCACPWave_ChaosIsle_Out.zip SymCACPWave_ChaosIsle.r |
T#5 DataSets
References top
Day & Night |
Wikipedia entry https://en.wikipedia.org/wiki/Day_and_Night_(cellular_automaton) | Wikipedia the free encyclopedia. |
Drunkard's Walk |
Wikipedia entry https://en.wikipedia.org/wiki/The_Drunkard%27s_Walk | Wikipedia the free encyclopedia. |
Eppstein D. Glider Pattern data base | https://www.ics.uci.edu/~eppstein/ca/glider.db | |
Eppstein D. Glider Rule Classification | https://www.ics.uci.edu/~eppstein/ca/wolfram.html | |
Golly's RuleLoader | RuleLoader is Golly's system for defining complex rules for two dimensional cellular automata. | The Golly Team |
LUA | The Programing Language LUA. https://www.lua.org/. | Lua team at LabLua, a laboratory of the Department of Computer Science of PUC-Rio |
Moore Neighbourhood. |
Wikipedia entry https://en.wikipedia.org/wiki/Moore_neighborhood | Wikipedia the free encyclopedia. |
PEDRO JULIÁN and LEON O. CHUA (2002). | REPLICATION PROPERTIES OF PARITY CELLULAR AUTOMATA, | Int. J. Bifurcation Chaos 12, 477 (2002). |
Python. | The Python is a programming language https://www.python.org/ | The Python Software Foundation. |
R Core Team (2016). | R: A language and environment for statistical computing. | R Foundation for Statistical Computing, Vienna, Austria. |
Trevorrow A. and Rokicki T. | Golly is an open source, cross-platform application for exploring Conway's Game of Life and other cellular automata. | The Golly Team |
Wolfram S. | Universality and complexity in cellular automata. | Physica D: Nonlinear Phenomena, 1984 - Elsevier |
Wolfram S. 2002 | Wolfram, S. A New Kind of Science. | Champaign, IL: Wolfram Media, 2002. |
Site by Paul Rendell. | Last Update 15/January/2023 | Comments to Paul Rendell |