Single Rotation Spaceships (205 of them)

TL;DR: 205 Single rotation spaceships.

The “Single Rotation” rule (it's my personal naming, it could be already known under the different name) is a very simple reversible cellular automaton, acting on a field with Margolus neighborhood. In this rule, each 2x2 block is rotated by 90° if it has exactly one alive cell. All other blocks remain unchanged. Despite its simplicity, this rule supports a multitude of different pattern types, and is especially interesting for me because of its spaceships. There are hundreds of spaceships with different periods.

Some spaceships of the Single Rotation rule. All spaceships on this animation are different.

Live version of this animation can be seen in the online simulator.

Even simple observations showed that random reactions in this rule naturally produce more than ten different spaceships. Of course, ten was not enough so I tried to find more of them. This post is a digest of what I have found.

Spaceship search method

Random initial block produces multiple spaceships. Motion blur added to emphasize moving patterns.

The method to search for spaceships was simple: take an empty field and put a random initial block in its center. During evolution, random reaction would produce multiple spaceships, which are then removed from the field and automatically classified. Typical parameters, used for search:

• Field size: 128x128.
• Initial random block size: 80x80.
• Initial pattern density: 40%.
• Simulation time: 30000 generations.

Several days of search brought a list of 205 different spaceships. To identify them, 108'720'436 moving patterns were analyzed. Here are the top 10 most frequent spaceships from this list:

Image	RLE	Size	Period	Δx	Δy	Velocity	Type	Probability
	b2o2$b2o	4	12	2	0	1/6	orthogonal	0.264
	bo$2b2o$3bo	4	28	2	2	1/14	diagonal	0.311
	2bobo$b2o	4	44	2	2	1/22	diagonal	0.179
	b2o2$2o	4	48	2	2	1/24	diagonal	0.141
	bo$bo$2o	4	61	1	1	1/61	diagonal	0.038
	o$o2$o$o	4	368	2	2	1/184	diagonal	0.0435
	3o$o$bo	5	15	1	1	1/15	diagonal	0.00985
	b2o$2b2o$2bo	5	149	3	3	3/149	diagonal	0.00675
	o$bo$o$2o	5	158	2	0	1/79	orthogonal	0.000988
	3o$o3bo	5	178	2	0	1/89	orthogonal	0.0012

First 10 spaceships, ordered by the natural production rate. See the whole list.

Posting the whole list of 205 spaceships here would blow up the post, so I've uploaded it to a separate page. You can download the data for this list in different formats:

• JSON library for the online simulator. To use it in the simulator, copy-paste it to the bottom text area on the “Library” pane of the simulator, and click “Import from JSON”
• CSV file.
• Google documents spreadsheet.

Digesting the data

Size distribution

All discovered spaceships have 4 to 9 cells. The distribution of their sizes shows good agreement with power law:

Probability of the natural production plotted against spaceship weight. Dashed line is a best-fit power law distribution.

Power law approximation (dashed line on the plot) gives the following distribution: $$P_n \approx \frac{0.679} {{17.55}^{n-4}},$$ where P_n is a probability of a randomly produced spaceship having weight n. For 10-cell spaceships, this formula gives expected probability P₁₀=2.33·10^-8. Thus, the expected number of 10-cellers is 2 or 3, while none were discovered. Either I have bad luck, or the actual probability is lower, or maybe these spaceships have too large periods, and were not detected.

4-cell spaceships

Lightest spaceships have 4 cells and there are exactly 6 different spaceships of such size (I don't have a proof, but it should be easily provable by enumeration). Lightest spaceships have some interesting properties, mentioned in the previous post.

5-cell spaceships

Only 6 spaceships made of 5 cells were discovered during the search, all with significant hit counts. This suggests that there are no other 5-cell spaceships. From them, 2 are diagonal, and 4 are orthogonal. Curious coincidence: the most common diagonal 5-celler have a phase, that looks exactly as the Conway's Life glider.

The most common diagonal 5-cell spaceship, suspiciously resembling a phase of the Conway's glider

It moves by 1 cell every 15 generations, and its intermediate steps don't resemble glider at all, so this resemblance is nothing more than a coincidence. The other diagonal 5-celler is the R-pentomino.

Heavier spaceships

Number of different spaceships increases with weight, the experiment discovered 57 different 6-cell spaceships and 69 spaceships of 7 cells. Some of them are extremely rare, having probability less than 3.31e-07, which suggests that there are more spaceships, too rare to be discovered. The heaviest spaceships discovered are 10 different 9-cellers. Of them the most common one, detected 26 times, is $b2o$b3o$3bo$obo$2bo, fast diagonal spaceship with period 31 and velocity c/31.

The most common 9-cell spaceship and its evolution. Try it in the simulator.

No heavier spaceships were detected.

Periods

Smalest periods

Among the discovered spaceships, the smallest period are:

• orthogonal: 12 generatons, achieved by the 4-cell spaceship b2o2$b2o,
• diagonal: 11 generations, 6-cell spaceship obo$obo$b2o.

Two spaceships with smallest periods: p12 orthogonal (left) and p11 diagonal (right)

Interestingly, record for the diagonal spaceships is achieved by the relatively heavy (6 cells) and rare (probability 0.08%) pattern. Are there any heavier moving patterns with smaller periods? I don't know (though intuition says no).

Highest period

While in the Conway's Game of Life naturally produced spaceships and oscillators commonly have small periods, in the "Single Rotation" rule there are numerous patterns taking extremely long time to start repeating.

Obviously, there is no upper limit for the spaceship period. But among known (to me) patterns the one with highest period is orthogonal 8-cell spaceship b3o$o3b2o2$bo$2bo. It takes whopping 9046 generations to move horizontally by 2 cells (thus its speed is c/4523).

Spaceship with the highest known period 9046.

Velocities

Fastest spaceships

As one may expect, the pair of the spaceships with the smallest periods also hold the speed record. Their movement speeds are:

• Orthogonal: c/6. Spaceship: b2o2$b2o
• Diagonal c/11. Spaceship: obo$obo$b2o

Two fastest spaceships (same pair that has smallest periods).

Whether there are any faster patterns is an open question. It is easy to prove that in the "Single Rotation" rule spaceship velocity can not exceed c/2, but this estimation is very rough.

Slowest spaceships

The slowest spaceship found is the 8-cell pattern 2bo$b2o$2bo4$bo$bo$2b2o. Its speed is c/4755.

The slowest known (to me) spaceship, c/4755.

The period of this spaceship is not the largest, but it moves only by 1 cell, where the P9046 moves by 2 cells.

Open questions

• Smallest period. Current record is 11 generations, held by the 6-cell pattern: obo$obo$b2o. Are there spaceships with faster period?
• Fastest spaceship. It is easy to prove that spaceship velocity can't be more than c/2. Currently, the speed record is c/6 for orthogonal and c/11 for diagonal spaceships. Are there any faster ones?
• Oblique spaceships (knightships). So far, no oblique (neither diagonal nor orthogonal) spaceships were found. Are there any?
• Spaceship families. Some spaceships are clearly forming families. For example, family of period 31 spaceships with 7, 8 and 9 cells. How to find them? Are there infinite families?
• 10-cellspaceships. None found yet.