## Slowest one cell spaceships of each state count

For discussion of other cellular automata.

### Slowest one cell spaceships of each state count

This will be a challenge to find the slowest 1-cell spaceship in a non-symmetric rule of any number of states. For 2 states, it is obviously c, whether orthogonal or diagonal, as it cannot move in any direction without using a B1e or B1c transition, and so has to move at c:
x = 1, y = 1, rule = MAPGAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAo!

However, this is not true for higher state rules, as this preliminary example shows, with three states, acheiving C/16:
@RULE SlowestOneCell3StateCurrent@TABLEn_states:3neighborhood:Mooresymmetries:nonevar a={0,1,2}0,0,0,0,0,1,0,0,0,20,1,0,0,0,0,0,0,0,20,0,0,0,0,0,1,2,0,10,0,0,0,0,0,0,2,1,10,0,0,0,0,0,1,0,1,20,0,0,0,0,2,0,1,0,20,2,0,0,0,0,0,1,0,20,1,2,2,2,1,2,1,2,22,0,0,1,2,1,0,0,0,01,2,1,2,1,2,0,0,0,02,1,2,1,0,0,0,0,0,02,0,0,0,0,2,2,1,0,02,2,0,0,0,2,1,2,1,02,2,0,0,0,0,0,1,2,02,1,2,2,2,1,2,1,2,21,2,2,2,0,0,0,2,1,02,0,0,0,0,0,0,0,0,10,0,0,2,0,0,0,0,0,10,1,1,0,0,0,0,0,0,20,1,0,0,0,0,0,0,1,20,0,0,0,1,1,0,0,0,20,0,0,0,0,1,1,0,0,21,2,0,2,0,2,2,1,2,22,2,0,2,0,2,2,1,2,12,0,0,2,2,1,0,0,0,02,0,0,0,2,2,1,2,0,02,0,0,0,0,0,2,2,2,02,2,2,0,0,0,0,2,1,02,1,2,2,0,0,0,0,0,01,2,2,2,2,2,0,0,0,01,0,0,2,2,2,1,2,0,00,0,0,0,0,2,2,2,0,20,2,0,0,0,0,0,2,2,22,0,0,0,0,0,1,0,0,02,0,0,0,0,0,0,0,1,0

The slowest found of each state count will be held here. Entries should be submitted only with the condition that the spaceship the rule is designed for is one celled in one phase, and the state of the cell in that phase is state 1. The above two rules follow this condition, so when one state 1 cell is placed, it will follow the evolution of the entry spaceship. No direction is required, just a speed.

Records:

2-state: C
MAPGAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

3-state: C/36
@RULE slowshiptry@TABLEn_states: 3neighborhood:Mooresymmetries:none1,0,0,0,0,0,0,0,0,10,0,0,0,0,0,0,1,0,22,0,0,0,0,0,0,1,0,11,0,0,1,0,0,0,0,0,20,0,0,0,2,1,2,0,0,10,0,0,1,1,2,0,0,0,20,0,0,2,2,0,0,0,0,11,0,0,2,2,0,0,0,0,00,1,2,2,0,0,0,0,0,10,0,0,2,2,1,0,0,0,22,0,0,2,2,1,0,0,0,11,2,2,2,0,0,0,0,0,21,0,0,2,2,2,0,0,0,02,0,2,2,0,0,0,0,0,02,2,1,1,0,0,0,2,0,02,0,0,1,1,0,0,0,0,01,1,0,1,0,0,0,0,2,20,0,0,0,1,1,2,1,0,21,0,0,2,1,2,0,0,0,02,0,0,0,1,1,2,0,0,00,0,0,0,1,1,1,2,0,22,0,0,2,1,1,2,0,0,02,0,0,2,1,1,1,0,0,00,0,0,0,1,1,1,2,0,20,0,0,0,2,1,1,2,0,21,0,0,0,0,0,0,1,2,00,0,0,0,2,0,1,2,0,20,0,0,2,0,0,0,1,2,20,0,0,0,0,2,2,2,0,22,0,0,2,2,1,0,0,0,02,2,0,2,0,0,0,1,2,12,0,0,0,0,0,0,2,2,02,0,0,2,0,1,1,0,0,00,0,0,2,0,1,1,0,0,21,0,2,0,0,0,0,1,0,02,0,0,0,0,0,1,0,0,00,0,0,2,0,1,2,0,0,21,2,0,0,0,0,0,2,0,02,0,0,0,0,0,2,0,0,02,0,2,0,0,0,0,0,0,1

4-state: C/917636

@RULE MinSpeed4s-AFP-9-12-17@TABLEn_states:4neighborhood:Mooresymmetries:none010000000202000000030001000002000200000320012003033002000002210003002332000000022200000001310000000012000000002000000000300030000030000000300020030003230000300000300300033300000000030000030223000003033033000000031300002333130300200233000023022300002302230000330223000003032300000330023300011002330002100233320220023331013233000311200333310120011332033311000322231100032320032332033001123202200113330333110003323001123302231100033330011233023332000322231100033330023232022323000323200323330333320003322323000333300232330220032300000313030023331323002030320000003023000000200233300030011330001003313000113300030330110000003001333001100003310031000003103113000000020002000101000003030021330002202133000031000003201200033200
Last edited by AforAmpere on September 17th, 2017, 3:37 pm, edited 3 times in total.
Things to work on:
- Find a (7,1)c/8 ship in a Non-totalistic rule (someone please search the rules)
- Find a C/10 in JustFriends
- Find a C/10 in Day and Night
AforAmpere

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

### Re: Slowest one cell spaceships of each state count

Couldn't you just make a cell age as in Generations, but as it reaches its last stage, instead of just dying outright it births a state-1 cell to the right of it?
waiting for apgsearch to support one-dimensional rules
muzik

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

### Re: Slowest one cell spaceships of each state count

muzik wrote:Couldn't you just make a cell age as in Generations, but as it reaches its last stage, instead of just dying outright it births a state-1 cell to the right of it?

Yeah, but that's probably not optimal in most cases. See the example he actually posted, of a 3-state rule in which a single cell travels more slowly than the 3-state implementation of your idea.

Edit: Maybe your idea is still useful to establish an upper bound on the lowest possible speed for a given number of states.
succ

blah

Posts: 225
Joined: April 9th, 2016, 7:22 pm

### Re: Slowest one cell spaceships of each state count

This looks like a neat variation on the busy beaver problem.
EDIT: c/550 diagonal, 3 ON states:
@RULE BB3b@TABLEn_states:4neighborhood:Mooresymmetries:nonevar c1={1,3}var c2=c1var c3=c2var c4=c3var c5=c4var c6=c5var c7=c6var c8=c7var C1={0,1,3}var C2=C1var C3=C2var C4=C3var C5=C4var C6=C5var C7=C6var C8=C7#open up1,0,0,0,0,0,0,0,0,23,0,0,0,0,0,0,0,0,22,0,0,0,0,0,0,0,0,30,2,0,0,0,0,0,0,0,20,0,2,0,0,0,0,0,0,30,0,0,2,0,0,0,0,0,20,0,0,0,2,0,0,0,0,30,0,0,0,0,2,0,0,0,20,0,0,0,0,0,2,0,0,30,0,0,0,0,0,0,2,0,20,0,0,0,0,0,0,0,2,30,3,2,0,0,0,0,0,0,30,2,3,0,0,0,0,0,3,30,3,0,0,0,0,0,0,2,30,0,0,3,2,0,0,0,0,30,0,3,2,3,0,0,0,0,30,0,2,3,0,0,0,0,0,30,0,0,0,0,3,2,0,0,30,0,0,0,3,2,3,0,0,30,0,0,0,2,3,0,0,0,30,0,0,0,0,0,0,3,2,30,0,0,0,0,0,3,2,3,30,0,0,0,0,0,2,3,0,32,3,2,3,2,3,0,0,0,32,0,0,3,2,3,2,3,0,32,3,0,0,0,3,2,3,2,32,3,2,3,0,0,0,3,2,3#count or decay1,1,1,1,1,0,0,0,0,01,1,1,1,0,0,0,0,0,01,0,1,1,1,0,0,0,0,01,1,1,1,0,0,0,0,1,01,1,1,0,0,0,0,0,1,01,1,0,0,0,0,0,0,0,01,1,0,0,0,0,0,0,1,01,0,0,0,1,1,0,0,0,01,0,0,1,0,0,0,0,0,01,0,0,1,1,0,0,0,0,03,0,0,0,0,c1,c2,c3,c4,11,0,0,0,0,c1,c2,c3,c4,33,1,0,0,0,C1,C2,C3,C4,11,1,0,0,0,C1,C2,C3,C4,33,0,0,0,1,C1,C2,C3,C4,11,0,0,0,1,C1,C2,C3,C4,33,1,0,1,1,C1,C2,C3,C4,11,1,0,1,1,C1,C2,C3,C4,33,1,1,1,1,C1,C2,C3,C4,11,1,1,1,1,C1,C2,C3,C4,33,1,1,1,0,C1,C2,C3,C4,11,1,1,1,0,C1,C2,C3,C4,33,1,1,0,0,C1,C2,C3,C4,11,1,1,0,0,C1,C2,C3,C4,33,0,0,1,1,C1,C2,C3,C4,11,0,0,1,1,C1,C2,C3,C4,33,0,1,1,1,C1,C2,C3,C4,11,0,1,1,1,C1,C2,C3,C4,3#decay3,3,0,3,3,0,0,3,3,22,3,0,3,3,0,0,3,3,13,0,0,0,3,2,3,3,0,03,0,0,0,0,3,0,2,3,03,3,0,0,0,0,0,0,2,03,3,3,2,0,0,0,0,0,03,0,0,3,2,3,0,0,0,03,0,1,0,0,0,0,0,0,0

Extensible to higher state numbers as well, but would likely require non-trivial changes.
Last edited by BlinkerSpawn on September 12th, 2017, 10:30 pm, edited 1 time in total.
LifeWiki: Like Wikipedia but with more spaceships. [citation needed]

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

### Re: Slowest one cell spaceships of each state count

Yikes. No limit on the number of lines in the rule table, only on the number of states? The lower bound on the busy beaver Σ(N) function for increasing N goes like

4
6
13
4098
3.5×10^18267
10^10^10^10^18705352

I'm not sure the Single-Cell Spaceship Slowness function will take off quite as vertically as that, but when the exponents get big enough it can be kind of hard to tell the difference...! Come to think of it, rule tables would seem to have some resemblance to two-dimensional Turing machines -- for all I know, the function could even go up faster than Σ.

EDIT: Here's a problem that's probably about to show up: the rule table file for the slowest possible spaceship will start taking up terabytes of space, while the number of states is still in the single digits. Can I suggest a modification of the contest conditions? The rule table should fit in a [code] block in a forum post -- not an attached ZIP file or anything like that, just the plain quoted text in a single message.

dvgrn
Moderator

Posts: 4647
Joined: May 17th, 2009, 11:00 pm

### Re: Slowest one cell spaceships of each state count

c/36:
x = 1, y = 1, rule = slowshiptryA!

@RULE slowshiptry@TABLEn_states: 3neighborhood:Mooresymmetries:none1,0,0,0,0,0,0,0,0,10,0,0,0,0,0,0,1,0,22,0,0,0,0,0,0,1,0,11,0,0,1,0,0,0,0,0,20,0,0,0,2,1,2,0,0,10,0,0,1,1,2,0,0,0,20,0,0,2,2,0,0,0,0,11,0,0,2,2,0,0,0,0,00,1,2,2,0,0,0,0,0,10,0,0,2,2,1,0,0,0,22,0,0,2,2,1,0,0,0,11,2,2,2,0,0,0,0,0,21,0,0,2,2,2,0,0,0,02,0,2,2,0,0,0,0,0,02,2,1,1,0,0,0,2,0,02,0,0,1,1,0,0,0,0,01,1,0,1,0,0,0,0,2,20,0,0,0,1,1,2,1,0,21,0,0,2,1,2,0,0,0,02,0,0,0,1,1,2,0,0,00,0,0,0,1,1,1,2,0,22,0,0,2,1,1,2,0,0,02,0,0,2,1,1,1,0,0,00,0,0,0,1,1,1,2,0,20,0,0,0,2,1,1,2,0,21,0,0,0,0,0,0,1,2,00,0,0,0,2,0,1,2,0,20,0,0,2,0,0,0,1,2,20,0,0,0,0,2,2,2,0,22,0,0,2,2,1,0,0,0,02,2,0,2,0,0,0,1,2,12,0,0,0,0,0,0,2,2,02,0,0,2,0,1,1,0,0,00,0,0,2,0,1,1,0,0,21,0,2,0,0,0,0,1,0,02,0,0,0,0,0,1,0,0,00,0,0,2,0,1,2,0,0,21,2,0,0,0,0,0,2,0,02,0,0,0,0,0,2,0,0,02,0,2,0,0,0,0,0,0,1
I have the best signature ever.

toroidalet

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

### Re: Slowest one cell spaceships of each state count

Edited, what is the number of states where a computer that counts to any arbitrarily high number and then resets to one cell is possible? I feel like it is probably 50 states or less.
Things to work on:
- Find a (7,1)c/8 ship in a Non-totalistic rule (someone please search the rules)
- Find a C/10 in JustFriends
- Find a C/10 in Day and Night
AforAmpere

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

### Re: Slowest one cell spaceships of each state count

AforAmpere wrote:What is the number of states where a computer that counts to any arbitrarily high number and then resets to one cell is possible?

Should be possible in ≤15 states to make a ship with a period on the order of double or maybe triple exponential, based on the double-binary counter ship posted here (by me, shameless self-promo). I would make this, except that the vodka is good, but the meat is rotten.
I have the best signature ever.

toroidalet

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

### Re: Slowest one cell spaceships of each state count

@RULE MinSpeed4s-AFP-9-17-17@TABLEn_states:4neighborhood:Mooresymmetries:none010000000202000000030001000002000200000320012003033002000002210003002332000000022200000001310000000012000000002000000000300030000030000000300020030003230000300000300300033300000000030000030223000003033033000000031300002333130300200233000023022300002302230000330223000003032300000330023300011002330002100233320220023331013233000311200333310120011332033311000322231100032320032332033001123202200113330333110003323001123302231100033330011233023332000322231100033330023232022323000323200323330333320003322323000333300232330220032300000313030023331323002030320000003023000000200233300030011330001003313000113300030330110000003001333001100003310031000003103113000000020002000101000003030021330002202133000031000003201200033200

c/917636:
x = 1, y = 1, rule = MinSpeed4s-AFP-9-17-17A!

I'm sure there are plenty of trivial improvements that could be made, as well as nontrivial ones such as adding another binary counter.

EDIT: Fixed date.
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: 1616
Joined: September 13th, 2014, 5:36 pm
Location: 0x-1

### Re: Slowest one cell spaceships of each state count

Tried to make a 1-cell 2-state c/4 spaceship, and I got this:
@RULE MyEntry@TABLEn_states:2neighborhood:Mooresymmetries:none0,0,0,0,0,1,0,0,0,10,0,0,0,0,0,1,1,0,10,1,0,0,0,0,0,1,1,11,0,0,1,1,1,0,0,0,01,0,0,0,0,1,1,1,0,01,1,0,0,0,0,0,1,1,11,1,1,1,0,0,0,0,0,0

x = 1, y = 1, rule = MyEntryo!
One big dirty Oro. Yeeeeeeeeee...

gameoflifemaniac

Posts: 588
Joined: January 22nd, 2017, 11:17 am
Location: Poland