ConwayLife.com - A community for Conway's Game of Life and related cellular automata
Home  •  LifeWiki  •  Forums  •  Download Golly

Slowest one cell spaceships of each state count

For discussion of other cellular automata.

Slowest one cell spaceships of each state count

Postby AforAmpere » September 12th, 2017, 7:52 pm

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 = MAPGAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
o!


However, this is not true for higher state rules, as this preliminary example shows, with three states, acheiving C/16:
@RULE SlowestOneCell3StateCurrent

@TABLE

n_states:3
neighborhood:Moore
symmetries:none

var a={0,1,2}

0,0,0,0,0,1,0,0,0,2
0,1,0,0,0,0,0,0,0,2
0,0,0,0,0,0,1,2,0,1
0,0,0,0,0,0,0,2,1,1
0,0,0,0,0,0,1,0,1,2
0,0,0,0,0,2,0,1,0,2
0,2,0,0,0,0,0,1,0,2
0,1,2,2,2,1,2,1,2,2
2,0,0,1,2,1,0,0,0,0
1,2,1,2,1,2,0,0,0,0
2,1,2,1,0,0,0,0,0,0
2,0,0,0,0,2,2,1,0,0
2,2,0,0,0,2,1,2,1,0
2,2,0,0,0,0,0,1,2,0
2,1,2,2,2,1,2,1,2,2
1,2,2,2,0,0,0,2,1,0
2,0,0,0,0,0,0,0,0,1
0,0,0,2,0,0,0,0,0,1
0,1,1,0,0,0,0,0,0,2
0,1,0,0,0,0,0,0,1,2
0,0,0,0,1,1,0,0,0,2
0,0,0,0,0,1,1,0,0,2
1,2,0,2,0,2,2,1,2,2
2,2,0,2,0,2,2,1,2,1
2,0,0,2,2,1,0,0,0,0
2,0,0,0,2,2,1,2,0,0
2,0,0,0,0,0,2,2,2,0
2,2,2,0,0,0,0,2,1,0
2,1,2,2,0,0,0,0,0,0
1,2,2,2,2,2,0,0,0,0
1,0,0,2,2,2,1,2,0,0
0,0,0,0,0,2,2,2,0,2
0,2,0,0,0,0,0,2,2,2
2,0,0,0,0,0,1,0,0,0
2,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
@TABLE
n_states: 3
neighborhood:Moore
symmetries:none
1,0,0,0,0,0,0,0,0,1
0,0,0,0,0,0,0,1,0,2
2,0,0,0,0,0,0,1,0,1
1,0,0,1,0,0,0,0,0,2
0,0,0,0,2,1,2,0,0,1
0,0,0,1,1,2,0,0,0,2
0,0,0,2,2,0,0,0,0,1
1,0,0,2,2,0,0,0,0,0
0,1,2,2,0,0,0,0,0,1
0,0,0,2,2,1,0,0,0,2
2,0,0,2,2,1,0,0,0,1
1,2,2,2,0,0,0,0,0,2
1,0,0,2,2,2,0,0,0,0
2,0,2,2,0,0,0,0,0,0
2,2,1,1,0,0,0,2,0,0
2,0,0,1,1,0,0,0,0,0
1,1,0,1,0,0,0,0,2,2
0,0,0,0,1,1,2,1,0,2
1,0,0,2,1,2,0,0,0,0
2,0,0,0,1,1,2,0,0,0
0,0,0,0,1,1,1,2,0,2
2,0,0,2,1,1,2,0,0,0
2,0,0,2,1,1,1,0,0,0
0,0,0,0,1,1,1,2,0,2
0,0,0,0,2,1,1,2,0,2
1,0,0,0,0,0,0,1,2,0
0,0,0,0,2,0,1,2,0,2
0,0,0,2,0,0,0,1,2,2
0,0,0,0,0,2,2,2,0,2
2,0,0,2,2,1,0,0,0,0
2,2,0,2,0,0,0,1,2,1
2,0,0,0,0,0,0,2,2,0
2,0,0,2,0,1,1,0,0,0
0,0,0,2,0,1,1,0,0,2
1,0,2,0,0,0,0,1,0,0
2,0,0,0,0,0,1,0,0,0
0,0,0,2,0,1,2,0,0,2
1,2,0,0,0,0,0,2,0,0
2,0,0,0,0,0,2,0,0,0
2,0,2,0,0,0,0,0,0,1


4-state: C/917636

@RULE MinSpeed4s-AFP-9-12-17
@TABLE
n_states:4
neighborhood:Moore
symmetries:none
0100000002
0200000003
0001000002
0002000003
2001200303
3002000002
2100030023
3200000002
2200000001
3100000000
1200000000
2000000000
3000300000
3000000030
0020030003
2300003000
0030030003
3300000000
0300000302
2300000303
3033000000
0313000023
3313030020
0233000023
0223000023
0223000033
0223000003
0323000003
3002330001
1002330002
1002333202
2002333101
3233000311
2003333101
2001133203
3311000322
2311000323
2003233203
3001123202
2001133303
3311000332
3001123302
2311000333
3001123302
3332000322
2311000333
3002323202
2323000323
2003233303
3332000332
2323000333
3002323302
2003230000
0313030023
3313230020
3032000000
3023000000
2002333000
3001133000
1003313000
1133000303
3011000000
3001333001
1000033100
3100000310
3113000000
0200020001
0100000303
0021330002
2021330000
3100000320
1200033200
Last edited by AforAmpere on September 17th, 2017, 3:37 pm, edited 3 times 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: 210
Joined: July 1st, 2016, 3:58 pm

Re: Slowest one cell spaceships of each state count

Postby muzik » September 12th, 2017, 8:04 pm

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?
2c/n spaceships project

Current priorities: see here
muzik
 
Posts: 2462
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Slowest one cell spaceships of each state count

Postby blah » September 12th, 2017, 8:06 pm

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
User avatar
blah
 
Posts: 171
Joined: April 9th, 2016, 7:22 pm

Re: Slowest one cell spaceships of each state count

Postby BlinkerSpawn » September 12th, 2017, 8:37 pm

This looks like a neat variation on the busy beaver problem.
EDIT: c/550 diagonal, 3 ON states:
@RULE BB3b

@TABLE
n_states:4
neighborhood:Moore
symmetries:none
var c1={1,3}
var c2=c1
var c3=c2
var c4=c3
var c5=c4
var c6=c5
var c7=c6
var c8=c7
var C1={0,1,3}
var C2=C1
var C3=C2
var C4=C3
var C5=C4
var C6=C5
var C7=C6
var C8=C7
#open up
1,0,0,0,0,0,0,0,0,2
3,0,0,0,0,0,0,0,0,2
2,0,0,0,0,0,0,0,0,3
0,2,0,0,0,0,0,0,0,2
0,0,2,0,0,0,0,0,0,3
0,0,0,2,0,0,0,0,0,2
0,0,0,0,2,0,0,0,0,3
0,0,0,0,0,2,0,0,0,2
0,0,0,0,0,0,2,0,0,3
0,0,0,0,0,0,0,2,0,2
0,0,0,0,0,0,0,0,2,3
0,3,2,0,0,0,0,0,0,3
0,2,3,0,0,0,0,0,3,3
0,3,0,0,0,0,0,0,2,3
0,0,0,3,2,0,0,0,0,3
0,0,3,2,3,0,0,0,0,3
0,0,2,3,0,0,0,0,0,3
0,0,0,0,0,3,2,0,0,3
0,0,0,0,3,2,3,0,0,3
0,0,0,0,2,3,0,0,0,3
0,0,0,0,0,0,0,3,2,3
0,0,0,0,0,0,3,2,3,3
0,0,0,0,0,0,2,3,0,3
2,3,2,3,2,3,0,0,0,3
2,0,0,3,2,3,2,3,0,3
2,3,0,0,0,3,2,3,2,3
2,3,2,3,0,0,0,3,2,3
#count or decay
1,1,1,1,1,0,0,0,0,0
1,1,1,1,0,0,0,0,0,0
1,0,1,1,1,0,0,0,0,0
1,1,1,1,0,0,0,0,1,0
1,1,1,0,0,0,0,0,1,0
1,1,0,0,0,0,0,0,0,0
1,1,0,0,0,0,0,0,1,0
1,0,0,0,1,1,0,0,0,0
1,0,0,1,0,0,0,0,0,0
1,0,0,1,1,0,0,0,0,0
3,0,0,0,0,c1,c2,c3,c4,1
1,0,0,0,0,c1,c2,c3,c4,3
3,1,0,0,0,C1,C2,C3,C4,1
1,1,0,0,0,C1,C2,C3,C4,3
3,0,0,0,1,C1,C2,C3,C4,1
1,0,0,0,1,C1,C2,C3,C4,3
3,1,0,1,1,C1,C2,C3,C4,1
1,1,0,1,1,C1,C2,C3,C4,3
3,1,1,1,1,C1,C2,C3,C4,1
1,1,1,1,1,C1,C2,C3,C4,3
3,1,1,1,0,C1,C2,C3,C4,1
1,1,1,1,0,C1,C2,C3,C4,3
3,1,1,0,0,C1,C2,C3,C4,1
1,1,1,0,0,C1,C2,C3,C4,3
3,0,0,1,1,C1,C2,C3,C4,1
1,0,0,1,1,C1,C2,C3,C4,3
3,0,1,1,1,C1,C2,C3,C4,1
1,0,1,1,1,C1,C2,C3,C4,3
#decay
3,3,0,3,3,0,0,3,3,2
2,3,0,3,3,0,0,3,3,1
3,0,0,0,3,2,3,3,0,0
3,0,0,0,0,3,0,2,3,0
3,3,0,0,0,0,0,0,2,0
3,3,3,2,0,0,0,0,0,0
3,0,0,3,2,3,0,0,0,0
3,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]
User avatar
BlinkerSpawn
 
Posts: 1426
Joined: November 8th, 2014, 8:48 pm
Location: Getting a snacker from R-Bee's

Re: Slowest one cell spaceships of each state count

Postby dvgrn » September 12th, 2017, 10:07 pm

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: 3861
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Slowest one cell spaceships of each state count

Postby toroidalet » September 14th, 2017, 10:36 am

c/36:
x = 1, y = 1, rule = slowshiptry
A!

@RULE slowshiptry
@TABLE
n_states: 3
neighborhood:Moore
symmetries:none
1,0,0,0,0,0,0,0,0,1
0,0,0,0,0,0,0,1,0,2
2,0,0,0,0,0,0,1,0,1
1,0,0,1,0,0,0,0,0,2
0,0,0,0,2,1,2,0,0,1
0,0,0,1,1,2,0,0,0,2
0,0,0,2,2,0,0,0,0,1
1,0,0,2,2,0,0,0,0,0
0,1,2,2,0,0,0,0,0,1
0,0,0,2,2,1,0,0,0,2
2,0,0,2,2,1,0,0,0,1
1,2,2,2,0,0,0,0,0,2
1,0,0,2,2,2,0,0,0,0
2,0,2,2,0,0,0,0,0,0
2,2,1,1,0,0,0,2,0,0
2,0,0,1,1,0,0,0,0,0
1,1,0,1,0,0,0,0,2,2
0,0,0,0,1,1,2,1,0,2
1,0,0,2,1,2,0,0,0,0
2,0,0,0,1,1,2,0,0,0
0,0,0,0,1,1,1,2,0,2
2,0,0,2,1,1,2,0,0,0
2,0,0,2,1,1,1,0,0,0
0,0,0,0,1,1,1,2,0,2
0,0,0,0,2,1,1,2,0,2
1,0,0,0,0,0,0,1,2,0
0,0,0,0,2,0,1,2,0,2
0,0,0,2,0,0,0,1,2,2
0,0,0,0,0,2,2,2,0,2
2,0,0,2,2,1,0,0,0,0
2,2,0,2,0,0,0,1,2,1
2,0,0,0,0,0,0,2,2,0
2,0,0,2,0,1,1,0,0,0
0,0,0,2,0,1,1,0,0,2
1,0,2,0,0,0,0,1,0,0
2,0,0,0,0,0,1,0,0,0
0,0,0,2,0,1,2,0,0,2
1,2,0,0,0,0,0,2,0,0
2,0,0,0,0,0,2,0,0,0
2,0,2,0,0,0,0,0,0,1
I have the best signature ever.
User avatar
toroidalet
 
Posts: 676
Joined: August 7th, 2016, 1:48 pm
Location: Somewhere on a planet called "Earth"

Re: Slowest one cell spaceships of each state count

Postby AforAmpere » September 16th, 2017, 2:12 pm

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:
- 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: 210
Joined: July 1st, 2016, 3:58 pm

Re: Slowest one cell spaceships of each state count

Postby toroidalet » September 16th, 2017, 8:28 pm

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.
User avatar
toroidalet
 
Posts: 676
Joined: August 7th, 2016, 1:48 pm
Location: Somewhere on a planet called "Earth"

Re: Slowest one cell spaceships of each state count

Postby A for awesome » September 17th, 2017, 3:29 pm

@RULE MinSpeed4s-AFP-9-17-17
@TABLE
n_states:4
neighborhood:Moore
symmetries:none
0100000002
0200000003
0001000002
0002000003
2001200303
3002000002
2100030023
3200000002
2200000001
3100000000
1200000000
2000000000
3000300000
3000000030
0020030003
2300003000
0030030003
3300000000
0300000302
2300000303
3033000000
0313000023
3313030020
0233000023
0223000023
0223000033
0223000003
0323000003
3002330001
1002330002
1002333202
2002333101
3233000311
2003333101
2001133203
3311000322
2311000323
2003233203
3001123202
2001133303
3311000332
3001123302
2311000333
3001123302
3332000322
2311000333
3002323202
2323000323
2003233303
3332000332
2323000333
3002323302
2003230000
0313030023
3313230020
3032000000
3023000000
2002333000
3001133000
1003313000
1133000303
3011000000
3001333001
1000033100
3100000310
3113000000
0200020001
0100000303
0021330002
2021330000
3100000320
1200033200

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

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
User avatar
A for awesome
 
Posts: 1354
Joined: September 13th, 2014, 5:36 pm
Location: 0x-1

Re: Slowest one cell spaceships of each state count

Postby gameoflifemaniac » Yesterday, 1:30 pm

Tried to make a 1-cell 2-state c/4 state, and I got this:
@RULE MyEntry
@TABLE
n_states:2
neighborhood:Moore
symmetries:none

0,0,0,0,0,1,0,0,0,1
0,0,0,0,0,0,1,1,0,1
0,1,0,0,0,0,0,1,1,1
1,0,0,1,1,1,0,0,0,0
1,0,0,0,0,1,1,1,0,0
1,1,0,0,0,0,0,1,1,1
1,1,1,1,0,0,0,0,0,0

x = 1, y = 1, rule = MyEntry
o!
User avatar
gameoflifemaniac
 
Posts: 306
Joined: January 22nd, 2017, 11:17 am
Location: 54°00'39.4"N 21°43'50.5"E


Return to Other Cellular Automata

Who is online

Users browsing this forum: No registered users and 5 guests