ConwayLife.com

Based on various projects relating to creating spaceships with new forms of movement, I had the thought that maybe it'd be useful to form a method of categorizing CA rules based on the limitations on possible velocities within any given rule. I should clarify that velocity here refers to slope and speed, ignoring period. Period is important in some class definitions but it is important that it is separated from velocity. Spaceships are defined as normal, as patterns within a vacuum that reappear after a number of generations unchanged, translated some number of cells (oscillators/still lives are degenerate spaceships and will be excluded below except when otherwise specified). Thus puffers and the like do not count.

With that in mind, here's a proposal for some fairly simple (in concept) but rigorous classes which cellular automata can be filtered into:

• Unbounded Omnikinetic (Class 1): Spaceships exist for all rational velocities ≤ c. No 'Life-like' rule that is not "B0 without S8" is able to qualify for this title as all B1 rules explode and B2 rules have an upper limit of c/2 diagonal for any expansion. I don't know if any CA exist in this class. Technically not unbounded as lightspeed is the boundary.
• Class 2: Not sure what to call this one. Like Class 1, except spaceships do not exist for all rational velocities with at least 1 of the orthogonal components equal to c.
• Bounded Omnikinetic or Omnikinetic (Class 3): Infinitely many velocities exist, and if each velocity (h,k)c/p (with at least one of h,k co-prime with p) is plotted at the coordinate (h/p, k/p), then spaceships exist at all rational velocities on or within the convex hull of all extant velocities.
• Limit Omnikinetic (Class 4): Like Class 3, but not all rational velocities on the convex hull are possible. CGoL is probably Class 4 (unless by some miraculous feat it turns out it is Class 3).
• Class 5: Not all velocities within the velocity limit are possible, but infinitely many do still exist.
• Finite (Class 6): Only a finite number of velocities are possible.

There's other features that can be analyzed too, like strict class members (which support spaceships at every possible velocity/period combination) versus weak ones; whether parametric solutions exist (Parametric solutions basically cover things like 'every possible type of xWSS flotilla', 'UC ship able to reach any velocity matching some criterion', the HBKs, Caterloopillars... which is very handy. Also would likely be an excellent sort of thing on which to base the distinction between elementary ships and adjustable-velocity ships) and about the nature of these parametric solutions, etc...
For example, it's possible that there is some CA rule that is class 3 but has no parametric solutions for finding velocities at all... Such a rule would extremely likely be impossible to prove as being class 3...

TL;DR: This post discusses possible spaceship-based analogues of omniperiodicity and ways to describe rules based on allowed velocities.

I think it is an interesting concept which explains thise variable velocity ships better, but I highly doubt that any rule would be classified in the near future. CGoL is the most studied rule in the CA land and we still don't know if it is class 3 or 4 or 5. Basically in order to classify we should "prove" that spaceships of all velocities (in a certain condition) exist and I think this makes classifying so hard. (Disproving seems easier. One need only prove that no spaceships exist at a certain velocity.)
However, I think some alternative way to explain these variable velocity spaceships would be nice... But I cannot think of a good way. Perhaps mark the possible (dx, dy, p) values and connect them?

Scorbie wrote:I think it is an interesting concept which explains thise variable velocity ships better, but I highly doubt that any rule would be classified in the near future. CGoL is the most studied rule in the CA land and we still don't know if it is class 3 or 4 or 5.

It's either 3 or 4: we can achieve any velocity (a, b)c/d provided a + b < 2d (by universal constructors and c/2 blinker-fuse puffers).

calcyman wrote:

Scorbie wrote:I think it is an interesting concept which explains thise variable velocity ships better, but I highly doubt that any rule would be classified in the near future. CGoL is the most studied rule in the CA land and we still don't know if it is class 3 or 4 or 5.

It's either 3 or 4: we can achieve any velocity (a, b)c/d provided a + b < 2d (by universal constructors and c/2 blinker-fuse puffers).

Did you mean 2(a+b) < d? Anyway, good to know.