Finding the smallest spaceship of given speed

[HartmutHolzwart]

Current search programs are optimized to find spaceships in a given array. In this way it is not possible to proof that a given spaceship is the smallest of its speed.

Is there a way to overcome these limitations and at least to be able to prove that there is no spaceship of given speed with fewer ON cells than n?

Any suggestions welcome!

For orthogonal speeds (upwards) one could e.g. list all possible left halves with less than n/2+1 ON cells and then try to combine the halves to a complete spaceship.

[calcyman]

Hmm, universal-constructor-based arguments show that there exists an integer, n, such that for every rational velocity (p,q)/r such that 2p+2q < r, there exists a spaceship of n live cells travelling at that velocity.

For example, I am convinced that min(n) < 10^6, and there is a spaceship much smaller than the Caterpillar (by live cell count) travelling at 17c/45. However, the estimated diameter of such a pattern is about 10^10^6, inconceivably larger than the Caterpillar.

[HartmutHolzwart]

I was thinking of small period ships, e.g. what is the smallest 2c/5, c/5 or c/6 ship?

For c/6, I'm pretty sure that smaller ships exist, but none have been found so far.

[Tropylium]

I was thinking of small period ships, e.g. what is the smallest 2c/5, c/5 or c/6 ship?

For c/6, I'm pretty sure that smaller ships exist, but none have been found so far.

c/4 is the one I really wonder about. By far most of these ships have a structure with a t-tetromino engine (there are two variations) + large tagalongs. Most of these tagalongs, however, require two engines. I'm willing to bet the smallest spaceship of this velocity would be no larger than 15×15. Probably this would involve a glide-reflectiv p8 tagalong.

Cf. c/2: most p2 ships have at least two engines and are way bigger than the p4 LWSS. (The current record-holder, if the wiki is up to date, is over 7 times bigger.)

I suspect the existence of a small glide-reflectiv 2c/5 spaceship based on a single pi engine as well, and stabilizations of a single Weekender engine and a single Lobster engine.

Shouldn't searching for glide-reflectiv spaceships of period 2N be just about as easy as searching for spaceships of period N?

[DivusIulius]

c/4 is the one I really wonder about. [...] I'm willing to bet the smallest spaceship of this velocity would be no larger than 15×15.

So smallest than both 37P4H1V0

Code: Select all

x = 19, y = 12
bo$bo8bo$obo5bo3bo$8bo3boo$5boboo5boo$b6obbo6bo$bboo6bo3b3o$10bo3boboo
$13bo$18bo$17bo$17bo!

and 46P4H1V0

Code: Select all

x = 19, y = 10, rule = b3/s23
3bo11bo3b$3bo11bo3b$2bobo9bobo2b2$bo3bo7bo3bob$bob6ob6obob$o7bobo7bo$o
7bobo7bo$o17bo$bob2ob2o3b2ob2obo!

...?

Hmmm... Interesting...

[velcrorex]

Previous thread about small c/4 orthogonal spaceships.

[ad_ca]

c/4 is the one I really wonder about. By far most of these ships have a structure with a t-tetromino engine (there are two variations) + large tagalongs. Most of these tagalongs, however, require two engines. I'm willing to bet the smallest spaceship of this velocity would be no larger than 15×15. Probably this would involve a glide-reflectiv p8 tagalong.

I can only confirm that gfind search for glide-reflective at width 15 doesn't seem to come up with anything significantly shorter than 20 cells long. An asymmetric search at width 15 takes longer (surprisingly), but seems quite do-able on current hardware.

[velcrorex]

I have previously preformed gfind searches for c/4 asymmetric ships at widths 10, 11, 12 and 13. The first (shortest) ships found in each with are as follows:

Code: Select all

x = 58, y = 43
4boo$5bo$bbo$3bobo$3bo$5bo$5bo$4boo$bb3o$bbobo$$3b3o$booboo$bbobo$boob
oo$boo4bo$5boo$6bo$bobboo12boo$bo3bo15bobo$bboobobo10bobboo$5bobo10bo
12boo$bboobbobo11bo$bboobo12bo12bo5bo$3bo4bo8boo13b3o3bo$4boobo9b3o15b
3o$7bo11bo12bo3bo9bo4b3obo$4b5o10bo12bo3boo8bo3b4obo$9bo23bob4o6bo3bob
ooboo$19boo11b4oboo10bo$3bo17bobo22boobobo4bo$3boboboo11bobbo12boo9bob
oboobb3o$ooboobbo13bo12b5obo6boobboo$bo5boo14boo9boo5bo5bo3b3o$4bo3bo
26bobbobo10bo$5bo3bo9bobboo8bobobboo6b3o3bo$5bobbo9bo6bo5bo3bobboo6boo
boo$5bobo10bo4boo10bobbo7b3o$bb3o17bobo7booboboo9bo$18boboo$3o12boobob
o9b3o14b3o$3o12b3o12b3o14b3o$bo14bo14bo16bo!

[HartmutHolzwart]

I.e., if there would be a smaller p4 c/4 spaceship, it would be definitely wider than 13 cells! Which already is rather close to the conujectured 15x15 box.

Is there any reasonable heuristic to guess the size of a space ship given the speed? It is clear that there is only a finite number of patterns in an nxm-box, so only a very finite number of different speeds possible. For me it seems reasonable that slower spaceships need higher periods and thus larger bounding boxes. Can we somehow quantify this?

[137ben]

Indeed, the width 13 already has a bounding box with an area of only 221.

An interesting question: what is the smallest orthogonal spaceship (by some definition of "smallest") with speed lower than c/2? So far, by bounding box area, the leading contender is

Code: Select all

x = 5, y = 16, rule = B3/S23
4bo$2b2o$2b2o$4bo$2bo$b3o$bo$2o$2bo$bobo$bobo$bo$3bo$b2o$b2o$3bo!

[DivusIulius]

So far, by bounding box area, the leading contender is...

... yes, it is. As far as I know, that's 25P3H1V0.2

[Tropylium]

I.e., if there would be a smaller p4 c/4 spaceship, it would be definitely wider than 13 cells! Which already is rather close to the conujectured 15x15 box.

Is there any reasonable heuristic to guess the size of a space ship given the speed? It is clear that there is only a finite number of patterns in an nxm-box, so only a very finite number of different speeds possible. For me it seems reasonable that slower spaceships need higher periods and thus larger bounding boxes. Can we somehow quantify this?

A very loose heuristic might look something like this:
1. Determine the density of "random Life-like" patterns out of all patterns. Clouds of activity in Life (as in most "ordered" rules) tend to have a certain size, density, connectedness and reticulatedness. Let's say, for the sake of argument, that among 15×15 patterns, we have "only" about 2^200 patterns to consider.
2. Approximately all of these 2^200 patterns evolve to one of the Life-like 17×17 patterns. Ergo this number includes approximately all spaceships, oscillators, still lifes and such fitting inside the box. Most will however be random "space dust".
3. Let's say these 2^200 patterns will evolve fairly randomly into one of the others. It seems this allows to calculate how many loops of N steps can be predicted to occur among them.
4. To sort out the spaceships from the oscillators, we'll also need to know how many of our patterns grow so as to shift their bounding box in exactly one direction (many will grow in several directions and cannot be spaceships of this size) while still staying at (or under) 15×15. (Spaceships that shrink in size over their period are not an issue; we're considering the bounding box of the largest phase.) Most clouds of activity in Life are not rectangular, so this number is probably not especially large. Let's say it is, for 15×15, about 1 in 1000. We'll also need to know the density of patterns that do not grow in any direction. Let's say about 50% do not.

So for a very approximate count of p2 (modulo symmetry) c/2 ships, start with all the 2^190 patterns that advance by one cell. We then have 1-in-2^201 odds that the resulting pattern is nongrowing and will return our original pattern.

Now OK, this spits out odds of (1 – 2^201)^(2^190) ≈ 1 – 2^11 that no p2 c/2 ships occur at all (when clearly several do) so the numbers used need some fine-tuning. One thing in particular that I think needs to be accounted for is that there is also a typical extent to which a typical Life pattern will change upon one iteration; survival is not particularly rare, so transitions aren't fully random. Edge effects might be particularly relevant (e.g. a pattern that just grew in direction Y is unlikely to do so a 2nd time immediately after, and probably also slightly unlikely to do so even after one nongrowing generation).

Anyway, considering c/3, c/4, c/5 etc. ships, the extra condition that non-growth transitions in the "middle" of the period do not lead to a previous phase is going to impose virtually no restriction. The main limiting factor seems to be that all the other phases have to be nongrowing. So if 50% of 15×15 patterns aren't, then the odds of randomly finding a c/N ship are going to be very approximately proportional to 0.5^N.

This line of argument also suggests that at a given size and period, there should be more slower spaceships than faster ones: fast ships need to incorporate several of the rarer advancement transitions. Also, given a speed, high-period ships (modulo symmetry) will also be rarer than low-period ships: these need to luck into several advancement transitions, as well as several non-growing transitions (although combinatorics in the ordering of these provides some overhang).

Given that we already know two 2c/5 ships that fit within 15×15, it seems there should be at least the same amount of c/5 and c/4 ships that do.

There's no immediate way to determine how small the smallest ship of a given speed will be though. For that we'd have to acquire exact numbers, then crunch them for several ship sizes and see at which point a particular ship's probability becomes significant…

[DivusIulius]

A very loose heuristic might look something like this…

Hmmm... a pretty good, insightful read... thanks!