Smallest slowest spaceship?

For discussion of other cellular automata.
User avatar
ynotds
Posts: 31
Joined: August 23rd, 2010, 8:38 am
Location: Melbourne, Australia
Contact:

Smallest slowest spaceship?

Post by ynotds » December 20th, 2010, 2:09 am

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

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: Smallest slowest spaceship?

Post by calcyman » December 20th, 2010, 7:33 am

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!

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

Re: Smallest slowest spaceship?

Post by 137ben » April 4th, 2011, 10:05 pm

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
Posts: 14
Joined: April 4th, 2011, 3:08 pm

Re: Smallest slowest spaceship?

Post by quintopia » April 5th, 2011, 6:05 am

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

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: Smallest slowest spaceship?

Post by calcyman » April 5th, 2011, 11:48 am

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!

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

Re: Smallest slowest spaceship?

Post by 137ben » April 5th, 2011, 8:51 pm

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.

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: Smallest slowest spaceship?

Post by calcyman » April 6th, 2011, 2:07 am

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!

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

Re: Smallest slowest spaceship?

Post by 137ben » April 6th, 2011, 6:10 pm

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
Moderator
Posts: 2644
Joined: July 9th, 2009, 2:44 pm

Re: Smallest slowest spaceship?

Post by Sokwe » April 6th, 2011, 7:58 pm

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:

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

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

Re: Smallest slowest spaceship?

Post by 137ben » April 7th, 2011, 7:52 pm

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.

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

Re: Smallest slowest spaceship?

Post by Mats » April 8th, 2011, 2:15 am

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

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: Smallest slowest spaceship?

Post by calcyman » April 8th, 2011, 12:46 pm

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!

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

Re: Smallest slowest spaceship?

Post by 137ben » April 8th, 2011, 3:48 pm

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.

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

Re: Smallest slowest spaceship?

Post by Mats » April 8th, 2011, 4:17 pm

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
Posts: 14
Joined: April 4th, 2011, 3:08 pm

Re: Smallest slowest spaceship?

Post by quintopia » April 8th, 2011, 7:55 pm

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.

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

Re: Smallest slowest spaceship?

Post by Mats » April 9th, 2011, 2:35 am

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
Posts: 840
Joined: June 27th, 2009, 10:58 am
Location: Germany

Re: Smallest slowest spaceship?

Post by HartmutHolzwart » April 9th, 2011, 5:11 am

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
Posts: 14
Joined: April 4th, 2011, 3:08 pm

Re: Smallest slowest spaceship?

Post by quintopia » April 9th, 2011, 5:48 am

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.

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

Re: Smallest slowest spaceship?

Post by Mats » April 9th, 2011, 6:03 am

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.

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

Re: Smallest slowest spaceship?

Post by Mats » April 9th, 2011, 6:24 am

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?

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

Re: Smallest slowest spaceship?

Post by 137ben » April 9th, 2011, 9:08 am

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
Posts: 840
Joined: June 27th, 2009, 10:58 am
Location: Germany

Re: Smallest slowest spaceship?

Post by HartmutHolzwart » April 9th, 2011, 9:30 am

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.

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: Smallest slowest spaceship?

Post by calcyman » April 9th, 2011, 2:32 pm

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!

User avatar
ynotds
Posts: 31
Joined: August 23rd, 2010, 8:38 am
Location: Melbourne, Australia
Contact:

Re: Smallest slowest spaceship?

Post by ynotds » April 9th, 2011, 10:47 pm

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

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: Smallest slowest spaceship?

Post by calcyman » April 10th, 2011, 5:45 am

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!

Post Reply