Monday, November 4, 2013

The Single Rotation rule: remarkably simple and rich reversible cellular automaton

See also other posts tagged Single Rotation.

In the previous post I have presented the Reversible Cellular Automata simulator, along with some explanations about the reversible computations and block cellular automata. This post is dedicated to the specific reversible cellular automaton, I have stumbled upon while playing with the Simulator: the “Single Rotation” rule. Here is what it looks like:

Animated example of the “Single Rotation” rule: reversible cellular automaton with Margouls neighborhood.

Your browser must support SVG and JavaScript to show the animation above. In case your browser does not support it, see the GIF animation:

Animated example of the Single Rotation rule: reversible cellular automaton with Margouls neighborhood.

This automaton is an example of the binary block cellular automaton with Margouls neighborhood. It can be described by the only one simple block transition rule:

Rotate clockwise by 90° every block with exactly 1 alive cell.
And that's all: other blocks remain unchanged. The numeric code for this rule is: [0,2,8,3,1,5,6,7,4,9,10,11,12,13,14,15], which corresponds to the following substitution table:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 2 8 3 1 5 6 7 4 9 10 11 12 13 14 15
Table of the block transition function for the “Single Rotation” rule.

Time-reversibility of this rule is obvious: previous state can be obtained by reversing the direction of the rotation. Just like the famous “Game of Life”, this rule is very simple, but the automaton it defines has a remarkably complex behavior, arguably more rich than that of the “Critters” rule ([1], [2]), better covered in the net. I doubt that I am the first one to discover this rule (the rule is too simple), but I haven't seen it mentioned anywhere, so - who knows?

Properties of the “Single Rotation” rule

Conservation of population

The rule has a simple conservation law: evolution of the field never changes the total number of the alive cells. This immediately follows from the transfer function, since rotation obviously never changes total number of alive cells.

No mirror symmetry

Unlike the irreversible “Game of Life” and reversible rule “Critters”, “Single Rotation” rule has no mirror symmetry. Mirrored patterns will evolve absolutely differently from the original. The symmetries “Single Rotation” universe is invariant to are:

  • Rotation by 90°, and, consequently, rotations by 180° and 270°.
  • Translation by 2n cells along coordinate axes. Note that translation by 1 cell will also change the evolution of a pattern.

Patterns

As a consequence of the time-reversibility, no pattern can completely disappear (die out) in the reversible CA. Moreover, population invariance prohibits patterns that grow infinitely: guns, puffers and breeders. Reactions, that consume spaceships are also impossible.

By the above reasons, pattern types in the “Single Rotation” rule are limited to spaceships and oscillators (including static lifes as a special kind). Boring? Not at all, because their variety is extremely rich.

Spaceships!

For me, spaceships always were the most interesting kind of the patterns. And “Single Rotation” universe has a whole zoo of them, with different velocities, periods and directions. I've discovered 90 different spaceships, naturally produced by a random reaction. For comparison: in the “Game of Life” there are 2 spaceships that appear naturally in the random reactions: the Glider and the LWSS, with the latter being rare. In the “Critters” rule, there is one common light spaceship (“brace”, RLE: $2bo$bo$bo$2bo ) and few rare spaceships. See the collection of the “Critters” spaceships in the Simulator.

Diagonal spaceships
Several orthogonal spaceships of the Single Rotation universe, ordered by the velocity. Try them in the Simulator.
Orthogonal spaceships
Several diagonal spaceships of the Single Rotation universe, ordered by the velocity. Try them in the Simulator.

Lightest spaceships

Spaceships of the minimal possible “weight” (number of alive cells) play special role in the reversible CAs with conservation. In the “Single Rotation” rule every pattern with 1,2,or 3 cells is an oscillator. A spaceship must have at least 4 alive cells. (This should be easily provable by enumeration) There are 6 different 4-cell spaceships, 1 orthogonal and 5 diagonal ones:

Lightest spaceships
Lightest spaceships in the “Single Rotation” rule. Arrow shows movement direction.

Spaceship “A” is the only 4-cell spaceship that moves in the orthogonal direction. It has period 12 and velocity c/6. I am conjecturing that it is also the fastest spaceship possible. However, this is only a hypothesis, I don't have a proof. Big spaceships can sometimes be unexpectedly fast, for example, the second fastest known to me orthogonal spaceship has 9 cells.

A B C D E F
Type Orthogonal Diagonal Diagonal Diagonal Diagonal Diagonal
Period 12 28 44 48 61 368
Translation 2 2 2 2 1 2
Velocity c/6 c/14 c/22 c/24 c/61 c/184
Natural abundance 0.242 0.308 0.191 0.159 0.041 0.036
Parameters of the lightest spaceships A-F.

The spaceship “F”, resembling a vertical stroke has unexpectedly large period: 368 generations, which makes it one of the slowest spaceships.

Lightest spaceships has several special properties. One of them can be formulated as a theorem:

Theorem:
Collision of a lightest spaceship with a single cell always produces single cell and another lightest spaceship.
See demonstration below. Note that the interaction can move the single cell, and the type of the spaceship can change.

Lightest spaceship and cell collision
Collision of the lightest spaceship “A” with a single cell produces spaceship “B”. Try it in the Simulator.

Conway's Glider

I believe that it is nothing more than a curious coincidence, but the iconic Conway's GOL Glider is also a spaceship in the “Single Rotation” universe. It has period 15, translating diagonally by 2 cells every period. It is rather common spaceship, its natural abundance is 0.009 that means that roughly every 100'th spaceship produced by the random reaction is a Conway's Glider.

Conway's glider
Conway's glider in the “Single Rotation” universe. Gray arrow shows the movement direction. Try in the Simulator.

Important note here: since “Single Rotation” universe is not invariant under mirror flips and translations by an odd amount, it is important to correctly align the pattern to the blocks.

Oscillators

In the Reversible Cellular Automata, every non-growing pattern that is not a spaceship is an oscillator. It is easy to prove that under the rule with population conservation, every pattern is either an oscillator, a spaceship or will eventually evolve in the combination of the first two.

The smallest oscillator is a single cell, which have period 4 and rotates clockwise or counter-clockwise depending on the initial position. There are 2 possible 2-cell oscillators and several 3-cell ones.

Small oscillators
Several small oscillators in the “Single Rotation” rule.

Indestructible Still lifes (period-1 oscillators)

Still lifes are easy to construct in the “Single Rotation” rule: construct a pattern that have 2 or more alive cells in every block, regardless of the subdivision phase.

Indestructible still lifes
Indestructible still lifes in the “Single Rotation” rule. 4-cell block is the smallest possible still life. Try in the Simulator.

Interestingly, such patterns are indestructible: no interaction could ever change them. Since the rule is time-reversible, indestructibility leads to inconstructibility: such patterns could never arise during interaction.

Static lifes can be used to construct impenetrable walls, enclosing parts of the field. When a spaceship collides with such indestructible object, it gets “smashed” into a cloud of chaotically moving cells that are orbiting the obstacle's indestructible core, but then this cloud inevitably produces another spaceship. See example:

Collision of a spaceship with still life
Indestructibility of the still life: collision with a spaceship leaves it intact. See it in the Simulator.

In this experiment, lightest orthogonal spaceship collides with a static life and “bounces” from it. It is not a coincidence, there is a general property that can be formulated as a theorem, similar to the previous one:

Theorem:
In the “Single Rotation” cellular automaton, collision of a lightest spaceship with a static life always produces another lightest spaceship and the same static life.
Note that the kind of the spaceship can change during the interaction (in the animation above it does not change though). There is one difference with a previous theorem regarding the single-cell collision: position of the single cell can change, but position of the still life would be exactly the same.

There are several other theorems about the “Single Rotation” universe. I'll write about them later. Maybe.

Code and Programs

Animated SVG demo

The animation at the top of the post was made with SVG image, animated by the means of JavaScript. The sources are available in the same GitHub repository: dmishin/js-revca.

It does not simply plays the animation, it actually simulates the automaton, and the initial pattern as well as other animation parameters can be specified via URL arguments. See some examples:

SVG demo should work in the most of the modern browsers, desktop and mobile.