Finding the smallest spaceship of given speed

 Posts: 427
 Joined: June 27th, 2009, 10:58 am
 Location: Germany
Finding the smallest spaceship of given speed
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.
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.
Re: Finding the smallest spaceship of given speed
Hmm, universalconstructorbased 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.
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.
What do you do with ill crystallographers? Take them to the monoclinic!

 Posts: 427
 Joined: June 27th, 2009, 10:58 am
 Location: Germany
Re: Finding the smallest spaceship of given speed
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.
For c/6, I'm pretty sure that smaller ships exist, but none have been found so far.
Re: Finding the smallest spaceship of given speed
c/4 is the one I really wonder about. By far most of these ships have a structure with a ttetromino 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 glidereflectiv p8 tagalong.HartmutHolzwart wrote: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.
Cf. c/2: most p2 ships have at least two engines and are way bigger than the p4 LWSS. (The current recordholder, if the wiki is up to date, is over 7 times bigger.)
I suspect the existence of a small glidereflectiv 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 glidereflectiv spaceships of period 2N be just about as easy as searching for spaceships of period N?
 DivusIulius
 Posts: 89
 Joined: April 1st, 2009, 11:23 am
 Contact:
Re: Finding the smallest spaceship of given speed
So smallest than both 37P4H1V0Tropylium wrote: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.
Code: Select all
x = 19, y = 12
bo$bo8bo$obo5bo3bo$8bo3boo$5boboo5boo$b6obbo6bo$bboo6bo3b3o$10bo3boboo
$13bo$18bo$17bo$17bo!
Code: Select all
x = 19, y = 10, rule = b3/s23
3bo11bo3b$3bo11bo3b$2bobo9bobo2b2$bo3bo7bo3bob$bob6ob6obob$o7bobo7bo$o
7bobo7bo$o17bo$bob2ob2o3b2ob2obo!
Hmmm... Interesting...
Re: Finding the smallest spaceship of given speed
Previous thread about small c/4 orthogonal spaceships.
Josh Ball.
Re: Finding the smallest spaceship of given speed
I can only confirm that gfind search for glidereflective 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 doable on current hardware.Tropylium wrote:c/4 is the one I really wonder about. By far most of these ships have a structure with a ttetromino 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 glidereflectiv p8 tagalong.
Re: Finding the smallest spaceship of given speed
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!
Josh Ball.

 Posts: 427
 Joined: June 27th, 2009, 10:58 am
 Location: Germany
Re: Finding the smallest spaceship of given speed
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 nxmbox, 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?
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 nxmbox, 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?
Re: Finding the smallest spaceship of given speed
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
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
 Posts: 89
 Joined: April 1st, 2009, 11:23 am
 Contact:
Re: Finding the smallest spaceship of given speed
... yes, it is. As far as I know, that's 25P3H1V0.2137ben wrote:So far, by bounding box area, the leading contender is...
Re: Finding the smallest spaceship of given speed
A very loose heuristic might look something like this:HartmutHolzwart wrote: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 nxmbox, 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?
1. Determine the density of "random Lifelike" 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 Lifelike 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 1in2^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 finetuning. 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 nongrowth 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, highperiod ships (modulo symmetry) will also be rarer than lowperiod ships: these need to luck into several advancement transitions, as well as several nongrowing 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
 Posts: 89
 Joined: April 1st, 2009, 11:23 am
 Contact:
Re: Finding the smallest spaceship of given speed
Hmmm... a pretty good, insightful read... thanks!Tropylium wrote:A very loose heuristic might look something like this…