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