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.

Comments

won3d said…
Margouls should be spelled "Margolus" throughout
Unknown said…
Have you considered this slight variation: rotate blocks with exactly 3 alive cells *counter*clockwise 90°.

Why would such a rule be interesting? The reason is that we can use *local orientations* as cell states. Then the two rules can be seen as one rule as follows:

Rule: In a block, if there is exactly one cell of a given orientation in that block, rotate the block 90 degrees clockwise, using that orientation's definition of clockwise.

If we are on an orientable surface (like the plane or torus) this is not particularly interesting, but if we are on a *non*orientable surface (like a mobius strip or a klein bottle), it is pretty neat. When a surface is nonorientable, there is no globally consistent orientation. That means that if a spaceship, for example, loops around the space, it will actually be in the opposite state of what it started as.
@Unknown, I think, I understand your idea.
Here is a link to the simulator with this rule (I also initialized half of the field with alive cells):

http://dmishin.github.io/js-revca/?rule=0,2,8,3,1,5,6,13,4,9,10,7,12,14,11,15&rle_x0=30&rle_y0=0&rle=33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o$33o&step=8&frame_delay=100&size=64x64&cell_size=4,1&phase=0

On the first glance, it is not much different. There are no indestructible still lifes though.
Henning said…
Could this rule be turing complete?
@Henning: Call this a conjecture rather than a proof... I think the conservation of living cells implies a maximum finite memory for any given population of cells, and hence no truly Turing complete structures.
Henning said…
@jennifer I thought this too at first, but there could be infinite many configurations from a given population as particles can travel arbitrary distances. You could encode information by distances.
Stephen Jones said…
@jennifer is right. With finite population there's no way that a reversable-CA could do the equivalent of writing to the Turing machine's infinite tape. @Henning's idea of encoding information by distance doesn't help because you'd run out of cells to encode those distances in addition to ever-increasing time needed to "read" those distances.
Anonymous said…
@Dmitry Shintyakov How hard would it be to add Klein bottle fields to the simulation?
Elstel said…
Thank you - Just shared this post with a colleague who would benefit from reading this, really enjoyed it. Compiler and Automaton Network Simulator
Mason L. Green said…
There is a hexagonal version (actually two of them) which uses the Q*Bert neighborhood. (If you’re not familiar with the Q*Bert neighborhood, see here: http://cell-auto.com/neighbourhood/qbert/index.html). In this version, if a single cell in a block is on, rotate it by 120 degrees clockwise. In the “Klein bottle invertible” version, you also rotate blocks with two on cells 120 degrees counterclockwise. The former example has inconstructible/indestructible still lifes (such as a star of six ON rhombi meeting at a point), the latter does not.

For the regular Margolus neighborhood, one could also consider a rule in which every block is rotated by 90 degrees times the number of ON cells. Thus, blocks with 0 or 4 cells are unchanged, blocks with 1 on cell are rotated 90, blocks with 3 on cells are rotated 270, and (here’s where new behavior appears!) blocks with 2 cells of each type are rotated by 180. This rule is bound to give very different behavior from the ordinary single rotation rule, due to the frequency with which two-on, two-off blocks appear in most would-be spaceships.

Finally, higher-dimensional versions could be worth considering. Using the four-dimensional version of the Margolus neighborhood, for example, you could have a rule with two different types of ON cell corresponding to rotations about two orthogonal planes (planes oriented so that rotations through them commute). Thus if a block has 1 red cell and 1 blue cell, it’s rotated 90 degrees in the “red” plane and 90 degrees in the orthogonal (“blue”) plane. A “purple” cell would count towards both planes, etc. The number of variations on this rule is practically endless. 4D works much better than 3D for these types of rules because in 3D there is no way to make rotations in different planes commute.
Mason L. Green said…
Also, any of the above rules that don’t contain indestructible still lifes are candidates for physical universality. See https://www.scottaaronson.com/blog/?p=1896.
Mason L. Green said…
Finally, most definitions of Turing completeness that I have seen allow for initial configurations with infinitely many live cells, as long as they have a short, finite description. For example, you could consider a starting configuration where all except a finite number of cells follow a periodic pattern. Such a configuration would avoid the problem Jennifer mentioned, but would still provide for Turing completeness under some definitions.
John smith said…
This comment has been removed by a blog administrator.
Malcolm Sharpe said…
The "Double Rotate" rule is wonderful and deserves to be better known. Basically any reasonable low-entropy initialization spawns an incredible variety of spaceships (especially compared with the single common spaceship of Critters) until eventually settling into high-entropy generic configurations.

Until trying Double Rotate, I thought that Critters was the most pleasing known reversible cellular automaton, what with it being one of the few that has a Wikipedia page, but now Double Rotate seems to me the clear champion.
Anonymous said…
There were comments above that said you can't build a Turing Machine with a finite number of live cells. But that's not true.

A Turing machine is a finite state machine plus a tape, where the tape can be finite length at each moment, but grow arbitrarily long as it is written to. But that's equivalent to a FSM plus two stacks (if you cut the tape at the head, and tilt each half up). And if you think of the stack as encoding a binary number, then that's equivalent to a FSM plus 4 counters, where a counter is a nonnegative integer that can grow arbitrarily large, and the FSM can increment, decrement, and check if it's zero. And that, in turn (by encoding as the product of powers of 4 primes) is equivalent to a FSM plus just 2 counters.

So all you need is the ability to create two counters. There could be a main blob that is the FSM. Then a non-moving cycler that is far to the north, and another that is far to the east. If the FSM could shoot a spaceship at a blob that has the effect of moving it slightly farther away, or shoot a different spaceship that moves it slightly closer, and have a third interaction that detects whether it has retracted all the way back to the main blob, then this is equivalent to a FSM plus two counters. Which, in turn, is equivalent to a Turing machine.

In other words, you don't need infinite live cells. You just need infinite space into which your two finite patterns can move.

So the first step in building a Turing machine in this CA is to discover whether it is possible to have some pattern that oscillates in place, but when hit by some type of spaceship from a given direction, will interact with it and move slightly toward the direction the spaceship came from. And if there's another spaceship that would make it move slightly further away. Is this possible?

I'm now very curious: is this CA Turing complete?
Anonymous said…
So if you actually built a universal Turing machine this way, you'd start out with a standard pattern in a small area that is the FSM blob and the east blob close by. And the north blob would be a standard, finite pattern that is placed 2^n cells north of the main blob. This would then act like a Turing machine that started with an infinite tape that is mostly blank except the head is at the left end of a finite region of 1s and 0s, which are the binary representation of n. So the distance of 2^n cells encodes the integer n which encodes the initial bits on the tape. And it could then act exactly like that universal Turing machine running on that tape, so it could run arbitrarily long and write an arbitrary number of bits, possibly halting, or possibly never halting, depending on the chosen n.

This is exactly the proof of the Turing completness of the Game of Life that I read in the 1980s. It assumed an infinite empty universe, with a number of active cells that is always below a fixed constant, but used the distances to two remote blobs to encode an arbitrary, growing tape.

It would be very cool if that could be proved for this CA, too.
Malcolm Sharpe said…
@Anonymous, Morita recently constructed a reversible Turing machine in Double Rotate. (He formulates it as a partitioned cellular automaton, but I'm fairly sure that it's equivalent.) I think there though he handles the live cell conservation problem by initializing with infinitely many live cells (though in practice you just use as many as the amount of memory you need).

Morita, Kenichi. "Making reversible computing machines in a reversible cellular space." Bulletin of EATCS 140, no. 2 (2023).

(I would link it since the PDF is available online, but sometimes links run into trouble with spam detection.)