Friday, October 3, 2014

Cellular automata on hyperbolic {5,4} tiling, strobing rules

In the previous post on hyperbolic cellular automata I presented a program for simulating them (Pentagrid). One of the slightly disappointing discoveries I made using this tool was the fact that totalistic binary automata on the {5;4} hyperbolic tiling are either "explosive" (almost every initial configuration grows with time, that's class 3 by the Wolfram's classification), or "limited", unable to support spaceships (classes 1 or 2).

That's because if the minimal number of alive neighbors required to the cell birth is 3 or more, then due to the geometry of the {5;4} tiling, a compact pattern can't grow "outside". This prohibits spaceships and possibility of infinite growth in such rules. However, if 2 alive neighbors are enough to create a new alive cell, then 2-cell pattern will grow infinitely, and the rule becomes "explosive". (However, some of the explosive rules support spaceships!)

Strobing rules

There is one exception though: "strobing" rules, where a cell spontaneously becomes alive if it has 0 alive neighbors, and dies, if all its neighbors are alive.

In the standard B/S notation, strobing rules on the {5,4} tiling have B0 and don't have Sa (where "a" stands for 10 neighbors). Under such rules, empty field becomes completely filled in the next generation, and then it completely dies out one generation later.

In these rules, if a pattern starts with finitely many live cells on a background of dead cells, it will continue to have finitely many live cells on a background of dead cells in every even step, but in the odd steps the pattern is reversed: there are finitely many dead cells on a background of infinitely many live cells
(From the Growth and Decay in Life-Like Cellular Automata).

Naive simulation of such rules would either require making field finite or consume infinite amount of memory, but a simple trick could be used for effective simulation: consider evolution of the difference between the "flashing" background and the cells. This can be done by replacing one strobing rules with a pair of complementary stable rules without B0 part; where first rule is applied on even generations, and the second is on odd. For example rule B0157/S01 is replaced by the pair: B234689a/S23456789a, B59a/S359a.

It is possible to find such strobing rule, that the first rule of its non-strobing representation is "explosive", and the second is "stable". Careful choice of these rules allows to find that "edge of chaos" between stability and chaotic explosion, where interesting things could occur.

Below are some results of my small exploration of such rules. I used brute-force search in the rule space, searching for the rules that do not grow exponentially fast, but produce patterns away from the original random seed.

Rules with spaceships

Rule B0157/S01

The rule is stable, random initial patterns evolves into spaceships and few very rare oscillators. This is the first rule where I discovered a spaceship. The spaceship has 7 cells in one of its configuration. It has period 4 and velocity c/2.

The 332 spaceship, moving along the hyperbolic plane.

The spaceship virtually the only common pattern in this rule, but there are some rare oscillators too. One of them is 5-star:

Rule B0157A/S01

This rule is very similar to the previous. The same spaceship is present, but the 5-star oscillator has different period

5-star and its oscillator evolution in the B0157A/S01 rule.

Rule B01357/S01

This rule has a slightly different spaceship, made of 5 cells. Also, this rule is on the "explosive" side of the "edge of chaos". Though most small patterns are not growing infinitely, most big random patterns show gradual population growth. I has not identified a smallest pattern, that causes this behavior, probably, there are some natural replicators, puffers or rakes.

The 32 spaceship in the rule B01357/S01, period is 4, velocity is c/2.

5-star is stable in this rule, but there are different oscillators.

Rule B01357A/S01

This rule has the same 32-spaceship and several rare oscillators. Same as the previous, B01357/S01 shows slow infinite growth for large initial patterns. No minimal pattern with infinite growth identified.

Rule B01347/S013

The spaceship in this rule has different configuration, I dubbed it L-ship. It has period 8 and velocity c/2, same as the rest spaceships. This rule is stable, random initial pattern quickly evolves into some spaceships and very rare oscillators.

L-ship with period 8 and velocity c/2, in the rule B01347/S013.

Oscilators are rarely produced

One of the rare oscillators, 4-bar.

Rule B01367A/S013

This rule is stable, with c/2 spaceship which is the same as L-ship above, but because of the different intermediate steps, this spaceship does not coincides with its own mirror image.

L-ship in the rule B01367A/S013, same velocity c/2 and period 8.

Rules without spaceships

There also are some rules exhibiting slow growth, but without apparent spaceships or puffers. I haven't identified the mechanism of growth in them.

Rule B01568A/S013

No spaceships visible, but random initial patterns tends to grow slowly. Some oscillators are present.

Relatively common period-6 oscillator.

Rule B01568/S01

Same as above. No spaceships found, slow but steady growth, oscillators.

Rule B01478A/S01

Same as above. No spaceships found, slow but steady growth. Has 2 common oscillator patterns: 3-celled corner and 5-star.

Conclusion

Some properties are common for all of the explored strobing rules (that are the small part of the whole rule space).

  1. "Static" patterns are rare. This is natural, because the patterns that appear static in the simulation (hence quotes), are actually inverting on each step, together with background.
  2. The set of naturally occurring patterns is very limited. Usually, there is one or no spaceship with velocity c/2, and a few significantly rare oscillators. Some oscillators can be constructed manually, but almost never form naturally.
  3. Discovered spaceships have clear resemblance. The same velocity c/2 regardless the period, the same method of moving by growing a block of 2 cells on each even generation.

Open questions

Some questions I don't have an answer:

  1. Are there any other spaceship in these rules? Geometry of the hyperbolic plane seems to complicate formation of the "wide" spaceships, but "long" ones should be possible.
  2. What pattern causes very slow but infinite growth in some of the rules? Some patterns are visible, but they are relatively big and hard to grasp.
  3. Are there any significantly different rules with spaceships?

Software

To produce images and animations, self-written Pentagrid simulator was used. It is open source, and runs on every desktop platform supported by Java (Linux and Windows are tested). To run the program, download the pentagrid-0.x.jar file and run it with java -jar (usually double-click in Windows). Install Java runtime, if not installed (it is safe if you don't enable java plug-in in the browser). The program has very basic GUI and controlled by the hot keys, so read the readme first.