0. Contents

• Introduction
• Definitions
• Space Filling
• Category Chaos
• Category Crystallising
• Category Minimal
• Category Structural
• Category Wave
• Wave Behaviour in Rule H1D8
• Islands with a Special Size
• Edge Behaviour
• Small Universe Crystallisation
• Summary
• Appendix DataSets and Downloads
• 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 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 5 categories:

• Chaos. Patterns expand to full the universe and are chaotic. Subcategories: Flecks,Maze,Chaos Mix and Noise.
• Crystallising. Patterns expand to fill the universe and become primarily static sometimes trapping oscillators.Subcategories: Blobs, Edge, Maze, Minimal and Network.
• Minimal. Patterns stop changing after a few generations.Subcategories: Edge, Maze and Minimal.
• Structural. The universe size has a major impact on the evolution of random patterns. Subcategories: Noise and Replicator.
• 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₁ .. P_n each of which takes a value mapped on a 1:1 basis from the n states CA₁ .. CA_n. Of the CA. In a state symmetrical CA the outcome is the same for all 1:1 mappings. The term Self-complementary is sometimes used for State Symmetric.

This survey limits itself to 2 state 2D CAs with rules based on cell counts using a Moore Neighbourhood. This set of rules are sometimes refered to as Life like. 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. Rule names are found in the Life Life List.

Definitions       top

Ash

Ash is the collection of stable or oscillating objects left behind when a chaotic reaction stabilizes. Life Lexicon.

Blowoff

In a universe initialised with two bands of opposite state with straight boundaries some rules will generate lines of cells parallel to the band in sections which are not modified by the seed. This is termed Blowoff and differs for orthogonal and diagonal bands. Blowoff with seed "0" generates an agar in a finite universe even when there are complex reflections of the parallel lines.

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). The complementry rule is sometimes refered to as the Black/white reversa, On/Off reversal or Strobing Rule.

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.

Fate 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 Fate 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.

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

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 behave the same all else being equal. However the length of the boundary has an impact on the Random Walk Speed and causes the step size per generation to change.

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#58 Seeds on an Orthogonal band

F#59 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.

Speed of Light

Speed of Light The greatest speed at which any effect can propagate. A speed of one cell per generation. Wikipedia entry.

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.

Space Filling       top

Two types of space filling are considered.

In a universe initialised with two bands of opposite state with straight boundaries some rules will generate lines of cells parallel to the band in sections which are not modified by the seed. This is termed Blowoff and differs for orthogonal and diagonal bands. In a universe initialised with an island of a random pattern of cells of equal state in a universe otherwise of just one state some rules cause the island pattern to expand to fill the universe.

The following describe Blowoff behaviour with seed "0". Blowoff with seed "0" generates an agar in a finite universe even when there are complex relections.

Space Filling 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.

Space Filling from Diagonal bands

Types of Blowoff

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 a pair of diagonal lines with cells touching 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: The 1st generation is a single diagonal line which subsequently strobes.
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. They do not strobe.
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 with cells touching on 2 sides that subsequently strobe.
Rules with the binary patterns X XXX1 1X10 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 that then strobes, no other change in subsequent generations.
Rules with the binary patterns X XXX1 1X10. See F#1.

Space Filling from a Random Island

An island randomly filled with an equal mixture of both states will expand to fill the universe in Chaos, Structural and some Crystallising rules. The expanding island assumes an approximate Diamond, Square or Round shape.

Of the 256 pairs of rules only the 32 sets with pattern HXX0 and HXXF and the odd 9 from the set HXX8 do not exhibit space filling when initialised with a random filled round island.

• Square
  4 sets of 32 rules made up of:
  - rules with HXX2 i.e. X XXXX 0010 The boundary has small isolated patterns. See F#66 and F#67 Diagonal Blowoff is B-R2 or B-S2.
  - rules with HXX6 i.e. X XXXX 0110 The boundaries tend to show p2 and p4 patterns. See F#68 and F#69 Diagonal Blowoff is B-R2.
  - rules with HXXA i.e. X XXXX 1010 The boundaries tend to be like the centre with a few exceptions e.g. H00A, H10A and H11A^RS. See F#70. Diagonal Blowoff is B-R4 or B-S4.
  - rules with HXXE i.e. X XXXX 1110 The boundaries form a line round the pattern. See F#71, F#72 and F#73 Diagonal Blowoff is B-R4 or B-S4.
  
• Round
  Rules: H008, H078^RS, H088, H108 and H188. These are all Chaos: maze, Chaos: flecks or Crystallizing: maze. See F#74. Diagonal Blowoff is B-1.
• Diamond
  - rules with HXX4 i.e. X XXXX 0100. See F#77 and F#78. There is no diagonal Blowoff.
  - rules with HXXC i.e. X XXXX 1100. See F#79 and F#80. Diagonal Blowoff is B-R1 or B-S1.
  - rules H018 H028 H038^RS H048 H058^RS H098 H0A8 H0B8^RS H0D8^RS H118 H128 H138^RS H148 H158^RS H178^RS H198 H1B8^RS H1D8. These are all Chaos: maze, Chaos: flecks or Crystallizing: maze. See F#75. Diagonal Blowoff is B-1 or B-1S. Rule H1D8 is listed as space filling which it does in some cases as described below.

The nine rules in the HXX8 set which do not exhibit space filling are the seven Wave category rules, H0F8^RS and H1F8^RS. In the Wave Category rules Random Islands shrink. H0F8 and H1F8 are both Minimal Subcategory Maze. H0F8^RS occasionally shows partial space filling. F#76 shows a downward growth which continues round the universe to join up with the island again. Rule H1F8^RS typically becomes a period two oscillator in a few generations.

Category Chaos       top

Chaos patterns expand to full the universe and are chaotic, these CAs show four distinct visual patterns Maze, Chaos Mix, Flecks and Noise. Maze pattern show vertical and horizontal lines with right angle corners. Chaos Mix rules produce patterns from interleaved networks of two chaotic mixtures each with differing proportions of the two states. Flecks rules show small short lived islands of a single state that are appear and disappear quickly, some migrate as their boundaries change. Noise patterns occur when a large portion of the cells change state almost at random like white noise forming no visible structures.

Under Stephen Wolfram's 1983 classification scheme Chaos Rules are Class 3, most patterns tend towards chaotic, seemingly infinite growth.

Chaos rules subcategories:

• Maze: 12 rules
• Mix Large: 38 rules
• Mix Small: 31 rules
• Flecks: 16 Rules
• Noise: 59 rules

Subcategory Maze

Chaos Maze Rules:
H072^RS, H074^RS, H076^RS, H088, H08A, H08C, H172^RS, H174^RS, H176^RS, H188, H18A and H18C.

Maze Rules with Gliders:
H074(1).

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 rule with scattered small changes over one generation.

Subcategory Chaos Mix

The division into Large and Small sub categories was done arbitrarily by observation.

Chaos Mix Large Rules:
H016^RS, H01A, H01C^RS, H01E^RS, H022, H02E^RS, H04E^RS, H05C^RS, H05E^RS, H062, H06E^RS, H08E^RS, H09C^RS, H09E^RS, H0A2, H0AE, H0CE^RS, H0D2, H0DC^RS, H0E2, H0E4, H116^RS, H11A^RS, H11C^RS, H122, H12E^RS, H14E^RS, H15C^RS, H162, H16E^RS, H19C^RS, H1A2, H1AE^RS, H1CE^RS, H1D2, H1DC^RS, H1E2 and H1E4.

Mix Large Rules with Gliders:
H1E4(3).

Chaos Mix Small Rules:
H014, H02C^RS, H036^RS, H03A^RS, H04C, H052, H05A^RS, H064, H096, H09A^RS, H0A4, H0AC^RS, H0B2, H0C4, H0E6, H0EE^RS, H114, H118, H12C^RS, H136^RS, H13A^RS, H152, H15A^RS, H164, H196, H19A^RS, H1A4, H1B2, H1C4, H1E6 and H1EA^RS.

Mix Small Rules with Gliders:
H1A4(2).

The universe pattern consists of two interlaced chaotic mixtures of the two states with opposite proportions of the states. The boundries between the chaos mixtures are blured and continualy moving. The subdivision into Large and Medium was done visually. F#11 shows the reverse strobing rule H1E1(H016) as an example of a large Chaos Mix rule with considerable change over one generation.

(a) Generation 500	(b) Plus 1 Generation of Change	(a) Generation 500	(b) Plus 1 Generation of Change
F#10 H088 Maze		F#11 H1E1(H016) Large Chaos Mix

Subcategory Flecks

Chaos Flecks Rules:
H018, H028, H048, H04A, H06C, H0A8, H0D4, H0D6^RS, H0D8^RS, H128, H148, H156, H198, H1D6, H1D8 and H1EE^RS.

Chaos Flecks Rules with Gliders:
H028(2), H048(2), H0A8(8), H0D8(5), H128(4), H148(5) and H1D8(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, shown as in the (a) image of each Fig, but stand out from the background of change, shown as in the (b) image of each Fig.

(a) Genertion 5,760	(b) Plus 4 Generations of Change	(a) Genertion 5,764	(b) Plus 4 Generations of Change
F#12 H0A8 Flecks Generation 5,760		F#13 H0A8 Flecks Generation 5,764

(a) Genertion 5,768	(b) Plus 4 Generations of Change	(a) Genertion 5,772	(b) Plus 4 Generations of Change
F#14 H0A8 Flecks Generation 5,768		F#15 H0A8 Flecks Generation 5,772

Small Universe Crystallisation is discussed further below. Rule H1D8 has some wave behaviour which is described separately below.

Subcategory Noise

Chaos Noise Rules:
H012, H024, H026, H02A, H032, H034, H038^RS, H044, H046, H054, H056, H058, H066, H06A^RS, H092, H094, H098, H0A6, H0B4, H0B6^RS, H0B8, H0BA^RS, H0C6, H0CA, H0CC, H0DA, H0EA^RS, H0EC, H112, H124, H126, H12A, H132, H134^RS, H138, H144, H146, H14A, H14C,H154, H158^RS, H166, H16A, H16C, H192, H194, H1A6,H1AA, H1AC^RS, H1B4, H1B6^RS, H1B8, H1BA^RS, H1C6, H1CA, H1CC, H1D4, H1DA and H1EC^RS.

Noise Rules with Gliders:
H058(1), H0B4(1), H0B8(1), H134(1), H158(3), H1B8(3) and H1D4(1).

The universe changes chaotically with no structure. Rules H054 , H154 and H1AA are unusual in this category because they crystallize in an unusually way as described in Small Universe Crystallisation.

Category Crystallising       top

There are 79 rules 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.

Under Stephen Wolfram's 1983 classification scheme Crystallising Rules are Class 3, most patterns tend towards chaotic, seemingly infinite growth, albeit in a finite universe all inital patterns in these rule end up still life or oscillators.

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 H0BERS 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, H13C^RS, H142 and H1BC^RS and 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) and 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 "Vote".

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:
H002, H07C^RS, H07E^RS, H082, H0BE^RS, H0FC^RS, H0FE^RS,H102, H13E^RS, H17C^RS, H17E^RS, H182 and 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:
H010, 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.

Rule H010 is exceptional in that it does not crystallise when initialised with a universe full of a random pattern unless the random pattern contains an island of one state of sufficient size as described in H010 Islands. A random universe in rule H010 contains lots of irregular islands of one state with single cells of the other in them. These island emerge from the chaos, wriggle about, expand, contract and die out. See F#81.

Generation 200	Generation 200-203 Changed cells stained pink
F#81 H010 full universe Chaos mode

The types of pattern after crystallisation from a random pattern are :

F#18 H03CRS Network

F#19 H008 Maze

F#20 H18ERS Blobs

F#21 H07ERS Minimal

The type minimal initialised from an orthogonal band :

(a) Generation 20	(b) Generation 21
F#22 H07ERS Minimal

Category Minimal       top

Minimal Rules:
H000, H070, H080, H0C0, H0F0, H0F8^RS, H100, H120, H140 H170, H180, H1F0 "Majority" and H1F8^RS.

Minimal Rules with Gliders:
None.

The behaviour of these rules can be defined as rules where the evolution stops in less generations than it would take to space fill the universe at the speed of light. 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.

Under Stephen Wolfram's 1983 classification scheme Minimal rules are Class 1 or Class 2 depending on whether ash is left or not.

Sub Category- No change: H000 and H100.

Sub Category- Still Life after a few generations: H080, H0C0, H0F8^RS, H120, H140, H180, H1F0 and H1F8^RS

Sub Category- Edge: H070, H0F0 and H170.

Category Structural       top

Structural Rules:
H0AA "Fredkin"

Structural Rules with Gliders:
None.

The rule H0AA has special symmetry. The rule is called Fredkin after Edward 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 n < 2^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.

Under Stephen Wolfram's 1983 classification scheme Fredkin is Class 3.

In a torus universe the result is dependent on the universe size. In a universe size 2ⁿ × 2ⁿ 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 results from the FindEnd10-30Chaos Data Set listed in T#1 show that all seeds for each width with results found the same oscillation period after the same number of generations.

Width	Period	Generation		Width	Period	Generation		Width	Period	Generation		Width	Period	Generation
10	6	0		14	14	0		18	14	2		24	4	8
11	31	0		15	15	1		20	12	0		26	42	0
12	2	4		16	8	0		21	63	1		28	28	0
13	21	0		17	15	0		22	62	0		30	30	2

T#1 Rule Fredkin results from the FindEnd10-30Chaos Data Set. All seeds for each width with results found the same oscillation period after the same number of generations.

Rule Fredkin has a State Change Ratio of 1 and the Strobe Ratio was measured as 0.98.

(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 "000000000000000103"

Category Wave       top

Wave Rules with Gliders:
H068, H0C8, H0E8, H168, H1A8 "Geology", H1C8 "Day & Night" and H1E8 "Holstein"

Wave Rules with Gliders:
H068(3), H0C8(11), H0E8(5), H168(3), H1A8(14), H1C8(20) and H1E8(3).

Rule H1D8 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 Ash. 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.

Under Stephen Wolfram's 1983 classification scheme Wave rules are Class 1 or Class 2 depending on whether ash is left or not.

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 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 Ash. 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 6,529	(a) Generation 6,538
F#50 H0E8 Universe 50 cells square seed "2223" Breaking at Generation 6,518

The (b)'s in F#26 to F#32 below show the statistical fit for the random walk step size = a × U ^b where U is the size of the universe. The data for these charts is from the Wave Step Size data set using the average change in population over one generation to calculate the step size. The (c)'s show the fitted line from the (b)'s over the initial part of the range. The vertical line indicate the start of the fitted section. Many of the wave rules exhibit a marked divination from the a × U ^b trend with boundary lengths less than 50 cells long. One reason for this is that five samples are taken between the generation 10 time the universe width and the generation 26 times the universe width for each seed. In small universes the diagonal band collapses within this range leading to spurious results. Another reason might be that this is due to the boundary being too short for specific classes of patterns and that the a × U ^b relationship only appears in universes large enough that longer boundaries add no new classes of patterns.

H068 F#26 (a) 50 cells square seed "0103" generation 200

F#26 (b)

F#26 (c)

H0C8 F#27 (a) 50 cells square seed "0103" generation 200

F#27 (b)

F#27 (c)

In rule H0C8 with initial diagonal band the band sometimes stabilises with a trapped oscillator e.g. Seed "2132" in a universe 60 cells square stabilised with oscillators of period 6 after 763 generations.

H0E8 F#28 (a) 50 cells square seed "0103" generation 200

F#28 (b)

F#28 (c)

H168 F#29 (a) 50 cells square seed "0103" generation 200

F#29 (b)

F#29 (c)

H1A8 F#30 (a) 50 cells square seed "0103" generation 200

F#30 (b)

F#30 (c)

H1A8 has some similarities to H1D8 in that a layer of chaos develops between areas of different state however in this case the layer never extends into the solid state areas. It is does generate its own activity rather than be just a part of the wavy boundary.

The deep waves generated by H1A8 fill up most of small universe creating a universe full of chaos resulting in a distortion of the results for universes smaller than 45 cells square.

H1C8 F#31 (a) 50 cells square seed "0103" generation 200

F#31 (b)

F#31 (c)

H1E8 F#32 (a) 50 cells square seed "0103" generation 200

F#32 (b)

F#32 (c)

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 567 generations with a period of 18.

Diagonal Bands with Symmetrical Seeds

When the seed on an initial diagonal boundary has mirror symmetry the wave generated performs the usual random walk with the boundary maintaining the mirror symetry. If the seed has rotational symmetry 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 and . 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 bands or in smaller universes a mixture island patches. An example in rule H068 is shown in F#85.

(a) Generation 0	(b) Generation 700	(c) Generation 7153	(c) Generation 9000	(c) Generation 150,000
F#85 H068 48 × 48 cell universe Seed "01002" centered.

Waves on Orthogonal Bands with Asymmetrical

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. Some seeds which are not mirror symmetric generate mirror symmetric patterns in wave rules except H0C8 and H1C8. Mirror symmetric patterns often form checkerboard patterns. Rule H1A8 has very thick boundary layers and requires universes that are larger than about 150 cells square to form checkerboard patterns.

• 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

Orthogonal Bands with Symmetrical Seeded

When the seed on an initial orthogonal boundary has mirror symmetry the wave generated performs the usual random walk with the boundary maintaining the mirror symetry. If the seed has rotational symmetry 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. An example is rule H0C8 shown in F#33 this rule usually forms stable orthogonal boundaries which stops the switching.

(a) Generation 0	(b) Generation 397	(c) Generation 5490 Period 6 Oscillator
F#33 H0C8 28 × 28 cell universe Seed "000000000000012"

Wave Behaviour in Rule H1D8       top

Rule H1D8 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 Ash in H1D8 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 Ash in an otherwise empty universe.

H1D8 (a) Universe 50 × 50 seed "2003" Generation 200	(b) Generations to a Universe full of Chaos	(c) Proportion of results that ended in Chaos	(d) 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 (c) is caused by small universe crystallization shown in the Fate Analysis of F#51 (d) using the FindEnd10-30Chaos Data Set .

F#40 shows H1D8 with a symmetric seed "101" centred with leading zeros 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 an Example of a Symmetrical Chaos Band with Complex Waves on Both Boundaries which Eventually Collapses

Islands with a Special Size       top

Two rules have been found which show islands that tend to expand if they are larger that a particular size and shrink if they are smaller. These are H010 and H1D8.

H010 is categorized as crystallising with Edge Behaviour as islands of chaos shrink leaving Ash. A universe full of chaos however remains chaotic making the classification a little shaky. The interesting thing is that islands of one state within this chaos exhibit this expanding or shrinking tenancy depending on size.

H1D8 shows this behaviour with islands of chaos in an otherwise single state universe. The islands of chaos adopt an approximate diamond shape.

H010 Islands

The H010 Island in Chaos data set analysed whether an island of a single state in a universe otherwise full of chaos either grow or shrink by 25%. The results in F#52 show that a island with an area of about 2280 cells is the mid point and larger islands are more likely to expand and smaller islands are more likely to shrink. F#53 and F#57 show examples of a island shrinking and one expanding.

H010 was included in the FindEnd10-30Chaos Data Set and found to crystallize is small universes as described in Small Universe Crystallisation. Tiny island open up and close continually in H010 chaotic patterns so it is possible that there exist patterns that do crystallize in large universes and this may be more likely in larger ones with an increase in the number of tiny islands that occur. It is highly unlikely that such a pattern could be found.

(a)	(b)	(c)
F#52 Analysis of H010 Islands Shrinking or Expanding by 25% by Universe Size

(a) Gen. 0 Population 3,599	(b) Gen. 1,400 Population 3,595	(c) Gen. 2,750 Population 3,816	(d) Gen. 4,100 Population 3,790	(e) Gen. 5,500 Population 4,190
F#53 H010 Island size 35 seed "13" Shrinks in a Chaos Universe 90 cells square

(a) Gen. 0 Population 5,790	(b) Gen. 8,250 Population 5,319	(c) Gen. 16,500 Population 4,917	(d) Gen. 24,750 Population 4,323	(e) Gen. 33,000 Population 3,670
F#57 H010 Island size 60 seed "103" Expands in a Chaos Universe 120 cells square

H1D8 Islands

The H1D8 Random Diamond Island data set analysed whether diamond shaped random patterns of different sizes expanded or shrank by 25%. The results in F#37 show that a diamond with about 7400 cells is the mid point and larger diamonds are most likely to expand and smaller diamonds are more likely to shrink. This would cover an area of 120 cells square or a diamond shape 86 cells each side. F#38 and F#39 show examples of a diamond island shrinking and one expanding.

(a)	(b)	(c)
F#37 Analysis of H1D8 islands Shrinking or Expanding by 25% in Population Size

(a) Gen. 0 Population 6,320	(b) Gen. 3,150 Population 5,859	(c) Gen. 6,300 Population 4,769	(d) Gen. 9,450 Population 2,527	(e) Gen. 12,600 Population 54
F#38 H1D8 Random Diamond Island size 80 seed "13" Shrinks

(a) Gen. 0 Population 8,011	(b) Gen. 4,550 Population 8,589	(c) Gen. 9,100 Population 10,331	(d) Gen. 13,650 Population 10,340	(e) Gen. 18,200 Population 19,961
F#39 H1D8 Random Diamond Island size 90 seed "13" Expands

Edge Behaviour       top

Rules which show Edge Effects are mostly the Edge subcategory of Category Crystallising with H070, H0F0 and H170 from Category Minimal. 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 except for H010 do this when initialised with a random pattern. Random patten islands in Rule H010 crystallize to Ash but a universe completely full of a random pattern does not Crystallize however small islands of one state in a universe if Chaos tend to shrink while large ones expand. 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 Ash 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 "Vote 4/5") 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 shows 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 by Universe Size. The line "mean × 15" is added to show the increase with size.

The FindEnd10-50Edge Data Set was used to generate the charts in F#56 which show 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 out of the 480 results of the largest 3 universe sizes for which all 60 seeds got results for all 8 rules. It is noticeable that a lot of the oscillation periods are close to 2ⁿ.

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 out of the 480. The number in brackets is the number of occurrences.

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.

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". 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 One Dimensional Cellular Automata with cells changing state in a row or column. They also have more complex oscillators at right angle junctions. An example is H08D(H172) shown in F#55. In a universe 24 cells square with a random seed of "113" it has a period of 1,260 generations after 1,657 generations. It has 7 trapped oscillators with periods of 2, 6, 14, 20 and 126 generations. The row or column oscillators 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	H178RS
72 (0100 1000)	Not	H178RS
90 (0101 1010)	State Symmetric	H17A
94 (0101 1110)	Not	H072 and H07A
126 (0111 1110)	Not	H07E
129 (1000 0001)	Not	H07E
133 (1000 0101)	Not	H072 and H07A
146 (1001 0010)	Not	H086 and H182
150 (1001 0110)	State Symmetric	H010, H050, H082, H082, H090, H0D0, H110, H150, H190 and H1D0
160 (1010 0000)	Not	H184 and H18C
164 (1010 0100)	Not	H084 and H08C
165 (1010 0101)	State Symmetric	H172 and H17A
178 (1011 0010)	Not	H070, H0B0, H0F0, H130, H170, H186, H186 and H1B0
182 (1011 0110)	Not	H086 and H182
218 (1101 1010)	Not	H084 and H08C
237 (1110 1101)	Not	H178RS
250 (1111 1010)	Not	H184 and H18C

T#3 One Dimensional Cellular Automata and the State Symmetric 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 (1260) 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. This ranges for constantly moving boundaries between chaos mixtures to trails of chaos spreading through crystal structures, branching to maintaining a chain reaction as other trails die out. 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¹⁰⁰ possible patterns so that any repeating sequence must be a very small fraction of this number to be detected.

Rule H010 is included in this analysis although it has been classified as Crystallising because when initialised with a random universe it remains chaotic. In most other respects it behaves like other crystallizing rules.

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 Crystal Reworking Rules gives a linear result. 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 column "Universe Size Range 90% Solved" shows the universe size range for which 90% of the seeds resulted in crystallisation in the maximum number of generations set in the experiment.

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 × 10. None of the other Chaos category rules recorded crystallization in larger universes.

RULE	Chaos Type	Crystal Type	Spacefill Type	Universe Size Range 90% Solved		RULE	Chaos Type	Crystal Type	Spacefill Type	Universe Size Range 90% Solved
H010	Chaos Mix	Empty	None	10-30		H0A8	Chaos Mix	Empty	Diamond	10-15 Generations Limited
H01ERS	Chaos Mix	Diagonal Bands	Square	10-18 Generations Limited		H172RS	Maze	Maze	Square	16 Oscillations Limited
H022	Chaos Mix	Gel	Square	10-15 Generations Limited		H174RS	Maze	Maze	Diamond	10-24 Generations Limited
H05ERS	Chaos Mix	Diagonal Bands	Square	10-18 Generations Limited		H176RS	Maze	Maze	Square	10-30
H072RS	Maze	Maze	Square	10-28 Generations Limited		H188	Maze	Maze	Round	10-30
H074RS	Maze	Maze	Diamond	10-28 Generations Limited		H18A	Maze	Maze	Square	10-25 Generations Limited
H076RS	Maze	Maze	Square	10-30		H18C	Maze	Maze	Diamond	10-30
H088	Maze	Maze	Round	10-30		H1AERS	Chaos Mix	Gel	Square	10-27 Generations Limited
H08A	Maze	Maze	Square	10-26 Generations Limited		H1CERS	Chaos Mix	Gel	Square	10-13 Generations Limited
H08C	Maze	Maze	Diamond	10-16 Oscillations Limited		H1D8	Flecks	Empty	Diamond	10-13 Generations Limited
H08ERS	Chaos Mix	Orthogonal Bands	Square	10-14 Generations Limited		H1DCRS	Chaos Mix	Gel	Diamond	10-14 Generations Limited
H09ERS	Chaos Mix	Islands	Square	10-25 Generations Limited

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 Ash 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 Chaos Mix → EMPTY, Universe 24 × 24 seed "10011" (Cells that changed state are in red)

(a) Universe 24 × c 24 Generation 400	(b) Changes Generation 400-401	(c) Crystallized at Generation 662 Period 4 Oscillator	(d) Changes of the Oscillator
F#43 H051(H1AE) Chaos Mix → GEL, Universe 24 × 24 seed "1011" (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) Chaos Mix → Islands, Universe 24 × 24 seed "1103" (Cells that changed state are in red)

(a) Generation 500	(b) Changes Generation 500-501	(c) Crystallized at Generation 1011 Period 10 Oscillator	(d) Changes of the Oscillator
F#45 H18D(H072) Maze → Maze, Universe 24 × 24 seed "10122" (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) Chaos Mix → Bands, Universe 20 × 20 seed "113" (Cells that changed state are in red)

F#47 H18A Maze → Maze. A good example of Crystallizing in small universes and Crystal Reworking.

F#48 Average Generations to Crystallization in non Crystal Reworking Rules.

The rules of the Chaos subcategory Chaos Mix show shadowy patches that 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.

Rules H054, H0AA (Fredkin), H154 and H1AA stand out from all the others in this analysis as the time to crystalize does not show an expnetial relatiobship with universe size. See F#41 to F#84. Fredkin is already noted as perticular having its own clisification and the others where concidered to join it but fail to have sufficient similarities.

F#41 H054 A Chaos Noise rule with unusual results.	F#82 H0AA Rule Fredkin.
F#83 H154 A Chaos Noise rule with unusual results.	F#84 H1AA A Chaos Noise rule with unusual results.

Summary       top

The survey found five categories of behaviour, Chaos, Crystallizing, Minimal, Structural and Waves. The Space Filling Survey found that the rules with the same settings for neighbourhood counts 0 to 3 behave in a similar way except for the HXX8 group. This group contains all 7 Wave category rules and two other rule that do not space fill. It also contains H1D8 which only space fills with larger islands.

Analysis of the glider information comes from David Eppstein's glider pattern data base shows that Group of rules HXX8 has 100 of the gliders with group HXX4 having the other 12. Once again indicating that the HXX8 group has particularly interesting rules.

The gliders from the HXX4 group:
  - 9 gliders from 6 Chaos category rules
  - 3 gliders from 2 Crystallising category rules

The gliders from the HXX8 group:
  - 36 gliders from 11 Chaos category rules
  - 5 gliders from 2 Crystallising category rules
  - 59 gliders from 7 Wave category rules

The Chaos Category has interesting rules which form islands of crystals or mixtures 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 the mean step size of the random walk changes according to a × U ^b where U is the size of the universe and b is close to -0.5. It remains to be shown if this relationship can be explained mathematically. Many of the wave rules exhibit a marked divination from this trend with boundary lengths less than 50 cells long. It is suggested that this is due to the boundary being too short for specific classes of patterns and that the a × U ^-5 relationship only appears after such additions have stopped.

Wave Behaviour in Rule H1D8 (B34678/S3678) was a surprise and showed that while the two states behave symmetrically a mixture of the two can have an asymmetrical relationship with both. It has the unique property that leads to the tendency for small islands to shrink and large ones expand. The population size for a diamond shaped random filled island of around 7,500 cells gives a 50 50 change of shrinking or expanding. The other rule showing Islands with a Special Size is H010 (B4/S01235678) and involves islands of a single state in a universe full of chaos. Islands with an area of 2240 cells are this special size. Rule H010 is crystallising except when there are no island boundaries large enough to stop the chain reaction of chaos. This opens the question of whether the tiny islands that open up in the chaos ever grow to crystallize the universe or whether their boundaries always have some property that prevents this.

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 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 oscillations.
• 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.

All seven wave rules support checkerboard patterns to some degree. Rules H0E8 (B3567/S04678), H1A8 (B3578/S24678) and H1E8 (B35678/S4678) generate checkerboard patterns easily the others are less predictable. The boundaries in H0E8 stabilize quickly. H1A8 requires large universes to form checkerboards patterns which have deep complex waves on the boundaries in contrast to H1E8 where in larger universes large sections of the boundaries are stable but disturbed by oscillations emanating from the corners. Rule H168 (B3568/S14678) creates large complex patterns in the unseeded rectangles after Blowoff. These patterns are large and many reliable transform into the solid rectangles required unlike the other rules which have a more random outcome. More details can be found on the checkerboard page.

Chaos rules that show crystallization in small universes also show crystal reworking. These crystal fragments have indistinct boundaries which is a feature that occurs in the natural world. The repeatability of Cellular Automata could be helpful in building tools that work with indistinct boundaries. Statistical tools that can say where a boundary was with more accuracy than they can determine where it is. Rules H054, H0AA (Fredkin), H154 and H1AA stand out from all the others in the Fate Analysis of Sec. 12.

A lot of the interesting things uncovered by this survey are to do with the behaviour of boundaries. Boundaries that make random walks, boundaries that support one dimensional CA's, boundaries between crystals and chaos and boundaries between areas different of chaos mix proportions. Some of these have been covered in some detail here but others are more complex. In particular boundaries between areas different of chaos mix proportions. These boundaries are indistinct and continuously moving. The concept of a chaos mix with a specific proportion of each state is something of an ideal that the constraints of tessellating the universe force to be dynamic. Untangling two or more such proportions competing both with themselves and with the others to achieve an impossible tessellation will be a challenge.

The properties of all the rules including translation from hexadecimal notation to B/S notation can be found under Downloads.

Appendix DataSets and Downloads       top

Description	Files
Rule Attributes Attributes of each rule. The csv version is used by someof the R files to add information to charts.	RuleDesc.csv RuleDesc.PDF
FindEnd10-50 Data Set A Fate 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 and a maximum oscillation period of 100 generations.	FindEnd10-50R_Script.txt FindEnd10-50ROut.zip FindendGen-Chaos.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 for the rules 16 with Edge Behaviour. These rules 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 5 run for up to 8,000 generations or ending with an oscillating pattern with a maximum oscillation period of 50,000 generations.	FindEnd10-50EdgeScript.txt FindEnd10-50EdgeOut.zip FindEnd-OneDeeLP.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 for up to 10,000 generations a maximum oscillation period of 100 generations.	FindEndchaosCrys_Script.txt FindEndchaosCrysOut1.zip SymCACPWave_B_H1D8chaos__Out.zip Findend-Chaos-H18A.r FindEnd-wave-H1D8.r FindEnd-chaos.r FindEnd-wave.r
State Change Data Set 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 the Python program ruleStateChangeRatio.py run in Golly.	ruleStateChangeRatio.py rule-StateChangeRatio.txt
Strobe Ratio Data Set 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
SYMCACP 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
Wave Break Data Set 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-H1D8.r FindEnd-wave.r
Wave Step Size Data Set Measurements of the change is population over one generation of a diagonal band. Five samples for each of 60 seed at different generations to give 300 independent measurements for each universe size from 10 to 500 cells square. This number divided by the universe size gives the random walk step size.	RWstepSize10-500_Script.txt RWstepSize10-500__Out.zip RWstepSize.r
H010 Island in Chaos Data Set The number of generations it takes for an island of a single state in a universe otherwise full of chaos to either grow or shrink by 25%. Used to determine the island size for which both outcomes are equally likely. The initial pattern is a circle of state zero cleared from a random pattern of 50% of each state filling the universe. This was then run for the number of generations equal to 10 times the island diameter so that it assumed a more natural state. It was then run until the population was 25% larger or smaller. A simple binary search algorithm was used which assumes incorrectly that island size changed monotonically.	SymCACPCrys_isleInChaos_Script_3.txt SymCACPCrys_isleInChaos_3_Out.zip SymCACP_ChaosIsle.r
H1D8 Random Diamond Island Data Set The number of generations it takes for an random island in H1D8 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. This was then run for the number of generations equal to 10 times the isle size so that it assumed a more natural state. It was then run until the population was 25% larger or smaller. A simple binary search algorithm was used which assumes incorrectly that island size changed monotonically.	SymCACPWave_ChaosIsle_3_Script.txt SymCACPWave_ChaosIsle_3_Out.zip

T#5 Data Sets and Downloads

References       top

Agar(2009)	Conway Life wiki Black/white reversal https://a.com/wiki/Agar.	Conwaylife.com wiki
Ash(2020)	Conway Life wiki Black/white reversal https://conwaylife.com/wiki/Soup#Ash".	Conwaylife.com wiki
Black/white reversal(2016)	Conway Life wiki Black/white reversal https://conwaylife.com/wiki/Black/white_reversal.	Conwaylife.com wiki
Day & Night(2019)	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.	Wolfram's Classification of Cellular Automata 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
Life Lexicon(2018)	Stephen Silver's Life Lexicon, an explanation of over 1,350 terms used in Conway's Life. https://conwaylife.com/ref/lexicon/lex_home.htm.	Maintained by Dave Greene
List of Life Like Rules(2023)	Conway Life wiki List of Life Like Rules https://conwaylife.com/wiki/List_of_Life-like_rules.	Conwaylife.com wiki
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.(2022)	Wikipedia entry https://en.wikipedia.org/wiki/Moore_neighborhood	Wikipedia the free encyclopedia.
PEDRO JULIÁN and LEON O. CHUA (2002).(2002)	REPLICATION PROPERTIES OF PARITY CELLULAR AUTOMATA,	Int. J. Bifurcation Chaos 12, 477 .
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. https://www.R-project.org/	R Foundation for Statistical Computing, Vienna, Austria.
Self-complementary(2016)	Conway Life wiki Self-complementary https://conwaylife.com/wiki/Self-complementary"	Conwaylife.com wiki
Speed of Light(2022)	Wikipedia entry https://en.wikipedia.org/wiki/Speed_of_light_(cellular_automaton)	Wikipedia the free encyclopedia.
Still Life(2017)	Conway Life wiki Still Life https://conwaylife.com/wiki/Still_life.	Conwaylife.com wiki
Strobing Rule(2017)	Conway Life wiki List of Life Like Rules https://conwaylife.com/wiki/Strobing_rule".	Conwaylife.com wiki
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.(1984)	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 23/January/2024

Comments to Paul Rendell

---