## Smallest slowest spaceship?

For discussion of other cellular automata.

### Smallest slowest spaceship?

When I grabbed it I thought it might be a new long period oscillator, but oscar.pl tells me it actually moves.
p3s782t.zip
Open in Golly 2.2

I've been excessive here and used Golly's maximum number of colours (256) for the demo zip, giving a speed of 3/782. the generic formula being 3/(3c+14) for any c>16. (I found it at c=20 which has become my starting level for exploring these rules.)

ynotds

Posts: 31
Joined: August 23rd, 2010, 8:38 am
Location: Melbourne, Australia

### Re: Smallest slowest spaceship?

No, *this* one is the slowest small spaceship, at c/5648:

http://fano.ics.uci.edu/ca/rules/b3457s4568/g1.html
What do you do with ill crystallographers? Take them to the mono-clinic!

calcyman

Posts: 2072
Joined: June 1st, 2009, 4:32 pm

### Re: Smallest slowest spaceship?

Me is confuzzled. What do you mean by the "slowest small spaceship"? Given that spaceships can be arbitrarily large, the gemini could be considered "small", and it is slower than c/5648. And because it can be modified to be arbitrarily slow, no single finite spaceship is the slowest (unless you consider oscillators to be spaceships with speed 0). So, to determine the "slowest small spaceship", we first need to define "small".
137ben

Posts: 343
Joined: June 18th, 2010, 8:18 pm

### Re: Smallest slowest spaceship?

We could speak of a /sequence/ of smallest slowest spaceships, however. Namely, the sequence of ships which are slower than all smaller ships.
quintopia

Posts: 14
Joined: April 4th, 2011, 3:08 pm

### Re: Smallest slowest spaceship?

Yes, I commend that! I suppose that is qualitatively similar to the sequence of best rational approximations to an irrational number, which are closer than any rationals with smaller coefficients.
What do you do with ill crystallographers? Take them to the mono-clinic!

calcyman

Posts: 2072
Joined: June 1st, 2009, 4:32 pm

### Re: Smallest slowest spaceship?

Interesting idea! Now comes the inevitable argument of how to define "smallest": bounding box, bounding polyomino, bounding polyplet, or population? Of course, there's no reason not to think about all of them, leading to a lot of potentially interesting spaceship sequences.

So, for B3/S23 by minimum population, we have the glider, the spider, the dragon, then the cordership.
137ben

Posts: 343
Joined: June 18th, 2010, 8:18 pm

### Re: Smallest slowest spaceship?

There's a smaller c/6 ship than the dragon, if I remember correctly. It should be somewhere on pentadecathlon.com.
What do you do with ill crystallographers? Take them to the mono-clinic!

calcyman

Posts: 2072
Joined: June 1st, 2009, 4:32 pm

### Re: Smallest slowest spaceship?

Ah, yes, it is 56P6H1V0.

By the way, the "smallest spaceships" page at PD is outdated--a smaller c/6 diagonal spaceship was posted on these forums earlier:
`x = 36, y = 36, rule = B3/S23b2o\$o\$bo\$2bo2bo\$2bo2bo\$4bo2\$5b2o\$5b4o2b2o\$9b2o\$8b2o\$14bo\$10bo3bob3o\$11bobo\$12bo3bo\$15bo\$14b2o\$13bo9bo\$14b2o7bo\$15b2o4bobo\$16b2ob2o\$17bobo3b2o\$18bo3bo\$21bo5bo\$22bo4bo\$23bo2bo\$25b2o\$25bobo\$27bo\$27b2o\$27b2o2b2o\$30bo2\$31b2o2bo\$33bobo\$34bo!`
137ben

Posts: 343
Joined: June 18th, 2010, 8:18 pm

### Re: Smallest slowest spaceship?

137ben wrote:the "smallest spaceships" page at PD is outdated--a smaller c/6 diagonal spaceship was posted on these forums earlier

There is also a smaller c/5 diagonal spaceship:
`x = 23, y = 23, rule = B3/S2320b2o\$20b2o\$19bo2bo\$16b2obo2bo\$22bo\$14b2o3bo2bo\$14b2o5bo\$15bob5o\$16bo3\$13b3o\$13bo\$11b2o\$5b2o4bo\$5b3o3bo\$3bo4bo\$3bo3bo\$7bo\$2b2obobo\$2o5bo\$2o4b2o\$2b4o!`

For a more up-to-date list of smallest spaceships for each speed, see the Lifewiki spaceship article.

quintopia wrote:... the sequence of ships which are slower than all smaller ships.

To considering this, one would need to order the spaceship velocities (is c/4 diagonal faster than c/4 orthogonal?).
-Matthias Merzenich
Sokwe
Moderator

Posts: 1479
Joined: July 9th, 2009, 2:44 pm

### Re: Smallest slowest spaceship?

To considering this, one would need to order the spaceship velocities (is c/4 diagonal faster than c/4 orthogonal?).

Normally, spaceship speed is measured with the L-infinity metric. However, you could consider both the sequences, one set of sequences uses the L-Infinity metric, and another set uses the Manhattan metric.
137ben

Posts: 343
Joined: June 18th, 2010, 8:18 pm

### Re: Smallest slowest spaceship?

I would like a sorting that is neither L-infinity nor Manhattan metric. Like this:
Place the spaceship so that Vx >= Vy. A speed (Vx1,Vy1) > (Vx2,Vy2) iff
- Vx1 > Vx2 or
- Vx1 = Vx2 and Vy1 > Vy2

This means that a LWSS is faster than a glider. In Manhattan metric they have the same speed. It also means that c/4 diagonal is faster than c/4 ortogonal. In L-infinity metric they have the same speed.

I guess this would be "L-very large but not infinity".

Mats

Posts: 42
Joined: August 10th, 2010, 7:40 am
Location: Stockholm, Sweden

### Re: Smallest slowest spaceship?

I would like a sorting that is neither L-infinity nor Manhattan metric.

What about the norm in the Euclidean metric, i.e. (dx²+dy²)/dt²? That possesses a certain elegance, which Manhattan and Chebyshev metrics do not.

The norm (squared magnitude) of the velocity is sufficient, rather than the magnitude of the velocity, as you are only considering the ordering, not the values themselves.
What do you do with ill crystallographers? Take them to the mono-clinic!

calcyman

Posts: 2072
Joined: June 1st, 2009, 4:32 pm

### Re: Smallest slowest spaceship?

Mats: that seems like a rather awkward and arbitrary sorting

Calcyman: Interesting idea. It does have an elegance to it, but the Euclidean metric doesn't really mean much in a Moore neighborhood.
137ben

Posts: 343
Joined: June 18th, 2010, 8:18 pm

### Re: Smallest slowest spaceship?

137ben: I can't see why my sorting is more awkward or more arbitrary than a sorting based on Manhattan metric in a Moore neighbourhood.

Mats

Posts: 42
Joined: August 10th, 2010, 7:40 am
Location: Stockholm, Sweden

### Re: Smallest slowest spaceship?

I think the only worthwhile choice is between L_inf and L_1. Which should it be?

Here is an argument for L_1: Suppose you want to see how long it takes a ship to get from (0,0) to (x,x). It will take a glider 2x generations, but it will take a LWSS 4x generations. How about from (0,0) to (x,0)? If you put a perfect instantaneous 90 degree glider reflector along the glider's path it will take it 2x generations, and it will also take the LWSS 2x generations. Thus, the glider's travel is always less than or equal to the LWSS's travel time.

Edit: this argument holds for knightships too. For three ships with the same L_inf speed, a straight diagonal one will beat a knightship will beat an orthogonal ship. This corresponds to the L_1 distance from the origin to all points the same L_inf distance away being maximized for those points on the lines y=x and y=-x (and being monotonically decreased towards the lines x=0 and y=0), which is to say, diagonal travel at a particular L_inf speed maximizes L_1 speed.
quintopia

Posts: 14
Joined: April 4th, 2011, 3:08 pm

### Re: Smallest slowest spaceship?

quintopia: I'm having trouble following your argument. Is it an argument for L_1 or for L_inf? Or is it a mixture of both? You wrote: "Thus, the glider's travel is always less than or equal to the LWSS's travel time." In L_inf it's "less than" and in L_1 it's "equal". Exactly what do you mean by "always less than or equal"?

My sorting order gives c/2_ort > c/4_dia > c/4_ort. I find that intuitively correct. L_1 gives c/2_ort = c/4_dia and L_inf gives c/4_dia = c/4_ort. That's why I think it's worthwhile to consider other choices than L_inf and L_1.

Mats

Posts: 42
Joined: August 10th, 2010, 7:40 am
Location: Stockholm, Sweden

### Re: Smallest slowest spaceship?

IMHO the matter is settled for CGoL:

The most appropriate metric is L_1! This is because the proof of the speed limit is based on the fastest possible advance of a diagonal line. Please look up the details in other forum threads.

In that sense the glider is as fast as an LWSS.
HartmutHolzwart

Posts: 421
Joined: June 27th, 2009, 10:58 am
Location: Germany

### Re: Smallest slowest spaceship?

Mats wrote:quintopia: I'm having trouble following your argument. Is it an argument for L_1 or for L_inf? Or is it a mixture of both? You wrote: "Thus, the glider's travel is always less than or equal to the LWSS's travel time." In L_inf it's "less than" and in L_1 it's "equal". Exactly what do you mean by "always less than or equal"?

My sorting order gives c/2_ort > c/4_dia > c/4_ort. I find that intuitively correct. L_1 gives c/2_ort = c/4_dia and L_inf gives c/4_dia = c/4_ort. That's why I think it's worthwhile to consider other choices than L_inf and L_1.

It's an argument for L_1 and your confusion is probably based on my mistake. Substitute "a c/4 orthogonal spaceship" for every occurrence of LWSS and it should make more sense.

Basically, I agree with what Hartmut just said.

I also want to point out that this:
Mats wrote:I guess this would be "L-very large but not infinity".

makes absolutely no sense. L_p is a set of normed spaces. There is no norm that satisfies your lexicographical ordering.
quintopia

Posts: 14
Joined: April 4th, 2011, 3:08 pm

### Re: Smallest slowest spaceship?

HartmutHolzwart wrote:IMHO the matter is settled for CGoL:

The most appropriate metric is L_1! This is because the proof of the speed limit is based on the fastest possible advance of a diagonal line. Please look up the details in other forum threads.

In that sense the glider is as fast as an LWSS.

This is simply wrong!

It's true for CGoL but there are other B3 rules in a Moore neighbourhhod where the fastest possible advance for a diagonal spaceship is c/3. Please look up the details in other forum threads.

Mats

Posts: 42
Joined: August 10th, 2010, 7:40 am
Location: Stockholm, Sweden

### Re: Smallest slowest spaceship?

quintopia wrote:Substitute "a c/4 orthogonal spaceship" for every occurrence of LWSS and it should make more sense.
I'm sorry but I'm still having problems understanding your argument. After substitution you get: "the glider's travel is always less than or equal to the c/4 ortogonal spaceship's travel time." In L_1 the glider is faster than a c/4 ortogonal spaceship.

quintopia wrote:makes absolutely no sense. L_p is a set of normed spaces. There is no norm that satisfies your lexicographical ordering.
Why would you need a normed space to sort spaceship speeds?

Mats

Posts: 42
Joined: August 10th, 2010, 7:40 am
Location: Stockholm, Sweden

### Re: Smallest slowest spaceship?

IMHO the matter is settled for CGoL:

The most appropriate metric is L_1! This is because the proof of the speed limit is based on the fastest possible advance of a diagonal line. Please look up the details in other forum threads.

In that sense the glider is as fast as an LWSS.

But that's not the fastest a signal can travel. We have orthogonal lightspeed signals, and 2c3 diagonal signals. Suppose you wanted to travel from (0,0) to (0,x). A glider (with a reflection in the middle) would take 4x generations, while an LWSS would take only 2x generations.
137ben

Posts: 343
Joined: June 18th, 2010, 8:18 pm

### Re: Smallest slowest spaceship?

it's the fastest velocity in empty space. Btw. a glider could not change its direction in empty space and would never get to (0,2x).

For every stable agar, one can define a specific convex polygon of maximum speed which would then define an appropriate metric for signals in that agar.

Likewise, the same thing could be defined for any cellular automaton.
HartmutHolzwart

Posts: 421
Joined: June 27th, 2009, 10:58 am
Location: Germany

### Re: Smallest slowest spaceship?

but the Euclidean metric doesn't really mean much in a Moore neighborhood.

Counter-example:

A king moves randomly for a while on a chessboard of infinite size. The eventual probability that a square is occupied is asymptotically proportional to a function of the Euclidean distance of that square from the initial location.
What do you do with ill crystallographers? Take them to the mono-clinic!

calcyman

Posts: 2072
Joined: June 1st, 2009, 4:32 pm

### Re: Smallest slowest spaceship?

but the Euclidean metric doesn't really mean much in a Moore neighborhood.
Another counter example (you might need to View Image to see the right hand section):
This shows B3/S345 run to 30,000 iterations from a small asymmetric seed:
`x = 4, y = 3, rule = B3/S3452o\$2o\$b3o!`
with a circle superimposed, the circle generated by a simple enough Golly script:
`# Draw a circle on the Golly plane# Author: Tony Smith (ts@meme.com.au), July 2009.# Single on state, all midline crossing cells on, assumes centred on ( -1/2, -1/2 )use strict;use warnings;use POSIX;my @line = ( 0, 0, 0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, 7, 0, 8, 0, 9 );my \$params = g_getstring("Enter the radius and thickness of the desired circle:",                      "100 10", "Draw circle");my ( \$r, \$t ) = split( /\s/, \$params );my \$outer = \$r + \$t/2;my \$inner = \$r - \$t/2;my \$outer2 = \$outer * \$outer;my \$inner2 = \$inner * \$inner;my ( @lines, \$long );for ( my \$y = 0; \$y < floor( \$inner ); \$y++ ) {  my \$y2 = \$y * \$y;  my \$xi = floor( sqrt( \$inner2 - \$y2 ) );  my \$xo = ceil(  sqrt( \$outer2 - \$y2 ) );  \$long = \$xo - \$xi;  push( @lines, -1-\$xo, \$y, \$long, \$xi, \$y, \$long, -1-\$xo, -1-\$y, \$long, \$xi, -1-\$y, \$long );}for ( my \$y = floor( \$inner ); \$y <= ceil( \$outer ); \$y++ ) {  my \$y2 = \$y * \$y;  my \$xo = ceil(  sqrt( \$outer2 - \$y2 ) );  my \$l = \$xo + \$xo + 1;  \$long = \$l if \$l > \$long;  push( @lines, -1-\$xo, \$y, \$l, -1-\$xo, -1-\$y, \$l );}my ( @long, \$this );while ( \$long-- ) { push( @long, \$this++, 0 ) }while ( @lines ) {  my \$x = shift @lines;  my \$y = shift @lines;  my \$l = shift @lines;  my @line = @long[ 0 .. 2*\$l + 1 ];  g_putcells( \@line, \$x, \$y, 1, 0, 0, 1, 'or');}`

ynotds

Posts: 31
Joined: August 23rd, 2010, 8:38 am
Location: Melbourne, Australia

### Re: Smallest slowest spaceship?

This shows B3/S345 run to 30,000 iterations from a small asymmetric seed:

I seem to recall that this doesn't actually asymptotically approximate a perfect circle, although it is indeed possible to engineer cellular automata which do. For example, the FHP lattice gas automaton has macroscopically circular waves.
What do you do with ill crystallographers? Take them to the mono-clinic!

calcyman

Posts: 2072
Joined: June 1st, 2009, 4:32 pm

Next