Smallest slowest spaceship?

[ynotds]

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

(1.24 KiB) Downloaded 290 times

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.)

[calcyman]

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

http://fano.ics.uci.edu/ca/rules/b3457s4568/g1.html

[137ben]

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".

[quintopia]

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

[calcyman]

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.

[137ben]

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.

[calcyman]

There's a smaller c/6 ship than the dragon, if I remember correctly. It should be somewhere on pentadecathlon.com.

[137ben]

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:

Code: Select all

x = 36, y = 36, rule = B3/S23
b2o$o$bo$2bo2bo$2bo2bo$4bo2$5b2o$5b4o2b2o$9b2o$8b2o$14bo$10bo3bob3o$
11bobo$12bo3bo$15bo$14b2o$13bo9bo$14b2o7bo$15b2o4bobo$16b2ob2o$17bobo
3b2o$18bo3bo$21bo5bo$22bo4bo$23bo2bo$25b2o$25bobo$27bo$27b2o$27b2o2b2o
$30bo2$31b2o2bo$33bobo$34bo!


[Sokwe]

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:

Code: Select all

x = 23, y = 23, rule = B3/S23
20b2o$20b2o$19bo2bo$16b2obo2bo$22bo$14b2o3bo2bo$14b2o5bo$15bob5o$16bo
3$13b3o$13bo$11b2o$5b2o4bo$5b3o3bo$3bo4bo$3bo3bo$7bo$2b2obobo$2o5bo$2o
4b2o$2b4o!

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

... 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?).

[137ben]

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.

[Mats]

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".

[calcyman]

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.

[137ben]

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.

[Mats]

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.

[quintopia]

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.

[Mats]

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.

[HartmutHolzwart]

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.

[quintopia]

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:

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.

[Mats]

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]

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.

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?

[137ben]

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.

[HartmutHolzwart]

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.

[calcyman]

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.

[ynotds]

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:

Code: Select all

x = 4, y = 3, rule = B3/S345
2o$2o$b3o!

with a circle superimposed, the circle generated by a simple enough Golly script:

Code: Select all

# 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');
}

[calcyman]

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.