## Perfect Orthogonal Speeds in Life-like CA

For discussion of other cellular automata.

### Minimum size for a speed

I've had this idea for a while that the smallest possible spaceship for speed c/x has a maximum bounding box area of log2(x). More specifically, (less sure of this) running the pattern in b12345678/s012345678 for one generation will give you a minimum of log2(x) cells. The idea is this: the cells involved in the spaceship can be regarded as information, and the densest way to store information with a bunch of things with two states is in binary. So for an oscillator or spaceship, the maximum number of phases is 2^[number of cells on in at least one phase]. And a spaceship has to move by at least one cell over the course of those phases, giving it a minimum speed of c/[number of phases]. Anyways, a more refined and accurate conjecture would be:

In a semi-totalistic rule with two states, the minimum size of a spaceship of speed c/x is log2(x), size being defined by the number of cells that are on at some point through the spaceship's cycle.

PS: the absolute minimum cell count of a spaceship* is 3. That's when the spaceship's asymmetrical enough to travel in just one direction.
*In a semi-totalistic rule with two states.
There is life on Mars. We put it there with not-completely-sterilized rovers.
And, for that matter, the Moon, Jupiter, Titan, and 67P/Churyumov–Gerasimenko.

Mr. Missed Her

Posts: 90
Joined: December 7th, 2016, 12:27 pm
Location: Somewhere within [time in years since this was entered] light-years of you.

### Re: Perfect Orthogonal Speeds in Life-like CA

drc wrote:Throwing a curveball. (c/15d. Yes, I read the title. #rebel):
x = 3, y = 6, rule = B2ce3a/S12obo$obo$bo2$2bo$2bo!

I mean, you could start a diagonal type thread if you wanted? I was planning on doing that but I'm disgustingly lazy.
2c/n spaceships project

Current priorities: see here
muzik

Posts: 2474
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

### Re: Perfect Orthogonal Speeds in Life-like CA

drc wrote:#rebel

gcc wrote:foo.c:1:2: error: invalid preprocessing directive #rebel
#rebel
^~~~~
x₁=ηx
V ⃰_η=c²√(Λη)
K=(Λu²)/2
Pₐ=1−1/(∫^∞_t₀(p(t)ˡ⁽ᵗ⁾)dt)

$$x_1=\eta x$$
$$V^*_\eta=c^2\sqrt{\Lambda\eta}$$
$$K=\frac{\Lambda u^2}2$$
$$P_a=1-\frac1{\int^\infty_{t_0}p(t)^{l(t)}dt}$$

http://conwaylife.com/wiki/A_for_all

Aidan F. Pierce

A for awesome

Posts: 1354
Joined: September 13th, 2014, 5:36 pm
Location: 0x-1

### Re: Perfect Orthogonal Speeds in Life-like CA

toroidalet wrote:c:
x = 2, y = 3, rule = B2ace/S2o2$o! This can be improved upon to make its period 1. I don't quite understand rule syntax, but the rule in which the same ship is period 1: a rule with no survival conditions, a two neighbor on birth condition, and a two cells on opposite sides of the cell birth condition. There is life on Mars. We put it there with not-completely-sterilized rovers. And, for that matter, the Moon, Jupiter, Titan, and 67P/Churyumov–Gerasimenko. Mr. Missed Her Posts: 90 Joined: December 7th, 2016, 12:27 pm Location: Somewhere within [time in years since this was entered] light-years of you. ### Re: Perfect Orthogonal Speeds in Life-like CA Mr. Missed Her wrote: toroidalet wrote:c: x = 2, y = 3, rule = B2ace/S2o2$o!

This can be improved upon to make its period 1. I don't quite understand rule syntax, but the rule in which the same ship is period 1: a rule with no survival conditions, a two neighbor on birth condition, and a two cells on opposite sides of the cell birth condition.

x = 2, y = 3, rule = B2a3r/S2o2$o! This post was brought to you by the letter D, for dishes that Andrew J. Wade won't do. (Also Daniel, which happens to be me.) B2-ac3i4a/S12 drc Posts: 1598 Joined: December 3rd, 2015, 4:11 pm Location: creating useless things in OCA ### Re: Perfect Orthogonal Speeds in Life-like CA improvements: c: x = 2, y = 3, rule = B2a3r/S2o2$o!

c/2:
x = 3, y = 2, rule = B2a3e/S1c2c3ebo$obo! or: x = 3, y = 2, rule = B2e3i/S1c2cebo$obo!

c/3:
x = 4, y = 1, rule = B2cin3aiy6c/S02ac3iob2o!

c/4:
x = 4, y = 1, rule = B2cin3aiy/S02-ikn3iob2o!

c/5:
x = 4, y = 1, rule = B2cin3aijy4i6c/S02ace3iob2o!

c/6:
x = 4, y = 1, rule = B2cin3aijy6c/S02acek3iob2o!

c/12:
x = 2, y = 3, rule = B2-a3-ai5a6ai/S1e23-aibo$o$bo!

c/17:
x = 10, y = 5, rule = B34n7/S238b2o$b2o4b2o$o2bo2bo2bo$b2o4b2o$8b2o!

c/18:
x = 6, y = 7, rule = B0234/S01245bo4$5bo2$o4bo!

c/26:
x = 8, y = 10, rule = B02345/S01247bo$6b2o$5b3o$6o$6o$6o$6o$5b3o$6b2o$7bo! c/60: x = 17, y = 8, rule = B36/S03567812bo$4b9obo$b14o$17o$17o$b14o$4b9obo$12bo!
I have the best signature ever.

toroidalet

Posts: 679
Joined: August 7th, 2016, 1:48 pm
Location: Somewhere on a planet called "Earth"

### Re: Minimum size for a speed

Mr. Missed Her wrote:The idea is this: the cells involved in the spaceship can be regarded as information, and the densest way to store information with a bunch of things with two states is in binary. So for an oscillator or spaceship, the maximum number of phases is 2^[number of cells on in at least one phase].

The problem with this is that information is stored both in ON and OFF cells, so the "size" isn't minimum population but bounding box area, specifically envelope area.
Take a look at the c/5648 in B3457/S4568.
x = 12, y = 14, rule = B3457/S45684bo2bo$4b4o$2b8o$2b2ob2ob2o$obobo2bobobo$2ob6ob2o$ob3o2b3obo$3ob4ob3o$2ob6ob2o$b3o4b3o$b3o4b3o$3b2o2b2o$3bo4bo$5b2o! The cells in the pattern change pseudorandomly and changes gradually shift the shape forward. If we let A be the total number of cells that are ON at least once in a single period, then each of the A cells can be either on or off, giving 2^A, which is greater than 2^P, considering that some cells are OFF at any given time. In this case, the minimum speed would be c/2^162 (~1.7e-49 cells/gen). BUT WAIT! The total number of unknown cells can't be 182 in this case, because the ship is even-bilateral symmetric, so the actual minimum speed is 2^-81 (~4.1e-25 cells/gen). This is still slower than your bound of at least 2^-78. Similar modification is required for odd symmetric (with variation to prevent half-counting middle cells) and glide symmetry (A = total number of cells ON at any point in a half-period). LifeWiki: Like Wikipedia but with more spaceships. [citation needed] BlinkerSpawn Posts: 1429 Joined: November 8th, 2014, 8:48 pm Location: Getting a snacker from R-Bee's ### Re: Minimum size for a speed BlinkerSpawn wrote: Mr. Missed Her wrote:The idea is this: the cells involved in the spaceship can be regarded as information, and the densest way to store information with a bunch of things with two states is in binary. So for an oscillator or spaceship, the maximum number of phases is 2^[number of cells on in at least one phase]. The problem with this is that information is stored both in ON and OFF cells, so the "size" isn't minimum population but bounding box area, specifically envelope area. Take a look at the c/5648 in B3457/S4568. x = 12, y = 14, rule = B3457/S45684bo2bo$4b4o$2b8o$2b2ob2ob2o$obobo2bobobo$2ob6ob2o$ob3o2b3obo$3ob4ob3o$2ob6ob2o$b3o4b3o$b3o4b3o$3b2o2b2o$3bo4bo$5b2o!

The cells in the pattern change pseudorandomly and changes gradually shift the shape forward. If we let A be the total number of cells that are ON at least once in a single period, then each of the A cells can be either on or off, giving 2^A, which is greater than 2^P, considering that some cells are OFF at any given time. In this case, the minimum speed would be c/2^162 (~1.7e-49 cells/gen).
BUT WAIT! The total number of unknown cells can't be 182 in this case, because the ship is even-bilateral symmetric, so the actual minimum speed is 2^-81 (~4.1e-25 cells/gen).
This is still slower than your bound of at least 2^-78.
Similar modification is required for odd symmetric (with variation to prevent half-counting middle cells) and glide symmetry (A = total number of cells ON at any point in a half-period).

Your totally right. Only thing was, I meant the number of cells you'd get if you overlapped all the phases on top of each other and then counted.
x = 67, y = 18, rule = LifeHistory33.2B$31.6B$29.10B$27.4BA4BA4B$26.3B2AB4AB2A3B$27.4BA4BA4B$29.10B$31.6B$33.2B5$2D2.3D.D.D.3D2.D2.2D2.3D2.2D2.D2.3D.D.D.D4.D2.D.D6.D3.D$D.D.D3.3D2.D2.D.D.D.D.D3.D3.D.D2.D2.D.D.D3.D.D.3D.3D.D.D.D.D$2D2.2D2.3D2.D2.3D.D.D.2D2.D3.3D2.D2.3D.D3.D.D.3D6.D2.D.D$D3.D3.D.D2.D2.D.D.D.D.D3.D3.D.D2.D2.D.D.D3.D.D.D.D.3D.D.D.D.D$D3.3D.D.D2.D2.D.D.2D2.3D2.2D.D.D2.D2.D.D.3D2.D2.D.D6.D3.D! It should be true that we need only to count half of a symmetrical ship, because if the ship's symmetrical, both halves are doing the exact same thing. (Count the cells on the axis of symmetry, because they don't have a matching row of cells.) Same general thing for glide-symmetric. Now, I was going for "what would the minimum size for a certain speed spaceship be" and not "what would the minimum speed for a certain spaceship be," but your post does point out that the smallest spaceships for a certain speed should be asymmetrical. There is life on Mars. We put it there with not-completely-sterilized rovers. And, for that matter, the Moon, Jupiter, Titan, and 67P/Churyumov–Gerasimenko. Mr. Missed Her Posts: 90 Joined: December 7th, 2016, 12:27 pm Location: Somewhere within [time in years since this was entered] light-years of you. ### Re: Perfect Orthogonal Speeds in Life-like CA Back on topic, a small c/10 from 83bismuth38: x = 3, y = 4, rule = B34aenrw5c/S12-n3e4cobo$o$o$bo!
LifeWiki: Like Wikipedia but with more spaceships. [citation needed]

Posts: 1429
Joined: November 8th, 2014, 8:48 pm
Location: Getting a snacker from R-Bee's

### Re: Perfect Orthogonal Speeds in Life-like CA

BlinkerSpawn wrote:Back on topic, a small c/10 from 83bismuth38:

c/29:
x = 7, y = 4, rule = B345/S04782b3o$ob3obo$b5o$o5bo! c/30: x = 9, y = 5, rule = B346/S3578bo5bo$b2obob2o$3o3b3o$4bo$bo5bo! Things to work on: - An Isotropic version of All_Speeds - Find more ships in B2ek3-ajny4ajqr5a/S02ack3ackny4aq5y - Find a p4 knightship in a Non-totalistic rule (someone please search the rules) AforAmpere Posts: 213 Joined: July 1st, 2016, 3:58 pm ### Re: Perfect Orthogonal Speeds in Life-like CA ...how are you finding these so fast? Is there some secret database I don't know about? 2c/n spaceships project Current priorities: see here muzik Posts: 2474 Joined: January 28th, 2016, 2:47 pm Location: Scotland ### Re: Perfect Orthogonal Speeds in Life-like CA I have a huge list of spaceships, most from the glider database. Things to work on: - An Isotropic version of All_Speeds - Find more ships in B2ek3-ajny4ajqr5a/S02ack3ackny4aq5y - Find a p4 knightship in a Non-totalistic rule (someone please search the rules) AforAmpere Posts: 213 Joined: July 1st, 2016, 3:58 pm ### Re: Perfect Orthogonal Speeds in Life-like CA right then Is there a script or search engine trick that can let you look up any period and speed on the glider database? 2c/n spaceships project Current priorities: see here muzik Posts: 2474 Joined: January 28th, 2016, 2:47 pm Location: Scotland ### Re: Perfect Orthogonal Speeds in Life-like CA No, I just looked through thousands of rules, because I had a lot of time. It is kind of ridiculous, but I have like 200 speeds, with many at 5 cell ships. A script could be written for it, David Eppstein has a raw data file, that with a simple python program, it could probably read. I tried to write the script on an IPad, but it couldn't process that much (go figure). EDIT: Actually, you can use the search on page stuff on the file to find certain speeds, you just have to know the notation. Things to work on: - An Isotropic version of All_Speeds - Find more ships in B2ek3-ajny4ajqr5a/S02ack3ackny4aq5y - Find a p4 knightship in a Non-totalistic rule (someone please search the rules) AforAmpere Posts: 213 Joined: July 1st, 2016, 3:58 pm ### Re: Perfect Orthogonal Speeds in Life-like CA 2c/n spaceships project Current priorities: see here muzik Posts: 2474 Joined: January 28th, 2016, 2:47 pm Location: Scotland ### Re: Perfect Orthogonal Speeds in Life-like CA c/20 orthogonal: x = 3, y = 5, rule = B35678/S1247b2o$2o$3o$2o$b2o! c/23 orthogonal: x = 4, y = 7, rule = B3/S0145678bo$bo2$2obo2$bo$bo! c/26 orthogonal: x = 7, y = 6, rule = B3457/S045782bobo$4ob2o$o5bo$o5bo$4ob2o$2bobo!
Things to work on:
- An Isotropic version of All_Speeds
- Find more ships in B2ek3-ajny4ajqr5a/S02ack3ackny4aq5y
- Find a p4 knightship in a Non-totalistic rule (someone please search the rules)
AforAmpere

Posts: 213
Joined: July 1st, 2016, 3:58 pm

### Re: Perfect Orthogonal Speeds in Life-like CA

Thanks for the help, I do appreciate it you know.

A list of every speed up to c/100 not yet covered correctly, I would not be surprised if some of these speeds have not yet been found:

c/51c/57c/61c/65c/69c/71c/75c/77c/79c/85c/91c/93c/95c/97c/99--<FOUND> c/27 - current example is p54<FOUND> c/28 - current example is p56<FOUND> c/31<FOUND> c/32<FOUND> c/33 - current example is p264 and in a B0 rule<FOUND> c/35 - current example is p70<FOUND> c/36<FOUND> c/37<FOUND> c/38<FOUND> c/39<FOUND> c/41<FOUND> c/43<FOUND> c/45<FOUND> c/46<FOUND> c/47 - current example is p94 and in a B0 rule<FOUND> c/48<FOUND> c/49<FOUND> c/50<FOUND> c/53<FOUND> c/54<FOUND> c/55 - current example is p110<FOUND> c/56<FOUND> c/59<FOUND> c/63<FOUND> c/66<FOUND> c/67<FOUND> c/70<FOUND> c/81<FOUND> c/83<FOUND> c/86<FOUND> c/87<FOUND> c/89<FOUND> c/92<ADJUSTABLE RULE> c/52<ADJUSTABLE RULE> c/58<ADJUSTABLE RULE> c/72<ADJUSTABLE RULE> c/78<ADJUSTABLE RULE> c/82<ADJUSTABLE RULE> c/84<ADJUSTABLE RULE> c/88<ADJUSTABLE RULE> c/90<ADJUSTABLE RULE> c/94<ADJUSTABLE RULE> c/96<REPLACED BY ADJUSTABLE RULE> c/42 - current example is p84<REPLACED BY ADJUSTABLE RULE> c/62 - current example is in a B0 rule<REPLACED BY ADJUSTABLE RULE> c/68 - current example is in a B0 rule<REPLACED BY ADJUSTABLE RULE> c/74 - current example is in a B0 rule<REPLACED BY ADJUSTABLE RULE> c/76 - current example is in a B0 rule<REPLACED BY ADJUSTABLE RULE> c/80 - current example is in a B0 rule
Last edited by muzik on July 4th, 2017, 3:51 pm, edited 6 times in total.
2c/n spaceships project

Current priorities: see here
muzik

Posts: 2474
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

### Re: Perfect Orthogonal Speeds in Life-like CA

Thanks for that Muzik. Here's speeds up to c/40.

c/27 orthogonal:
x = 5, y = 5, rule = B34568/S3678bo$ob3o$o$ob3o$bo!

c/28 orthogonal:
x = 5, y = 5, rule = B35678/S2467obobo$3b2o$bo2bo$3b2o$obobo!

c/31 orthogonal:
x = 6, y = 7, rule = B34678/S0263bo$bo$4b2o$o3bo$4b2o$bo$3bo!

c/32 orthogonal:
x = 7, y = 6, rule = B3678/S2378o3b2o$o3b3o$o$o$o3b3o$o3b2o! c/33 orthogonal: x = 7, y = 4, rule = B37/S024578o2b2obo$ob2o2bo$ob2o2bo$o2b2obo!

c/35 orthogonal:
x = 4, y = 13, rule = B36/S2372o$2o4$bobo$o2bo$bobo4$2o$2o!

c/36 orthogonal:
x = 5, y = 6, rule = B35/S34673b2o$o2b2o$2obo$2obo$o2b2o$3b2o! c/37 orthogonal: x = 6, y = 6, rule = B346/S3563b2o$2o2b2o$2obobo$2obobo$2o2b2o$3b2o!

c/38 orthogonal:
x = 10, y = 5, rule = B3467/S015672bo2bo2$3o6bo2$2bo2bo!

c/39 orthogonal:
x = 5, y = 17, rule = B378/S24568o$2o$2o$obo2$bo$2b3o4$2b3o$bo2$obo$2o$2o$o! Things to work on: - An Isotropic version of All_Speeds - Find more ships in B2ek3-ajny4ajqr5a/S02ack3ackny4aq5y - Find a p4 knightship in a Non-totalistic rule (someone please search the rules) AforAmpere Posts: 213 Joined: July 1st, 2016, 3:58 pm ### Re: Perfect Orthogonal Speeds in Life-like CA So you have all speeds up to c/40? That's a pretty insanely expansive glider collection. Not bad. I also managed to find a c/55 while raking through the threads here in OCA since i took a massive break and want to see what went on. It's p110 though, so will need a reduced period version. 2c/n spaceships project Current priorities: see here muzik Posts: 2474 Joined: January 28th, 2016, 2:47 pm Location: Scotland ### Re: Perfect Orthogonal Speeds in Life-like CA Actually, I was missing a c/39, but I did a search on the raw data and found one, it is fast, and I am planning to add more to my list. EDIT, a c/55, only one on the database that is not higher period: x = 8, y = 9, rule = B3457/S1583bo$bo3bo$2bobo$2bo$3o4bo$2bo$2bobo$bo3bo\$3bo!
Last edited by AforAmpere on June 17th, 2017, 5:26 pm, edited 1 time in total.
Things to work on:
- An Isotropic version of All_Speeds
- Find more ships in B2ek3-ajny4ajqr5a/S02ack3ackny4aq5y
- Find a p4 knightship in a Non-totalistic rule (someone please search the rules)
AforAmpere

Posts: 213
Joined: July 1st, 2016, 3:58 pm

PreviousNext