Home  •  LifeWiki  •  Forums  •  Download Golly

## Unproven conjectures

For general discussion about Conway's Game of Life.

### Re: Unproven conjectures

Bullet51 wrote:
Hdjensofjfnen wrote:Maybe unrelated, but does anyone have a proof that any speed greater than c/4 diagonal is unachievable in Life? After all, there's a 2c/7 in a rule one transition from Life:
x = 5, y = 5, rule = B3/S234w
3o\$b2o\$2b3o\$3b2o\$4bo!

Here: http://www.njohnston.ca/2009/10/spacesh ... -automata/

Huh! Interesting. Never thought it was a matter of overpopulation (but it should be obvious given that the spaceship above requires S4w to survive).
Life is hard. Deal with it.
My favorite oscillator of all time:
x = 7, y = 5, rule = B3/S2-i3-y4i
4b3o\$6bo\$o3b3o\$2o\$bo!

Hdjensofjfnen

Posts: 1090
Joined: March 15th, 2016, 6:41 pm
Location: r cis θ

### Re: Unproven conjectures

OCA:

Is cellular automaton omnivelocital? (i.e. that 7,1c/8)
Are there spaceships in 1d B3/S23? (credits to hdjen)
What are the least transitions required for Turing-completeness in isotropic non-totalistic 2-dimensional CA? What about non-isotropic?

CA:

Can Life support all sub-c/2 orthogonal velocities? What about diagonal or oblique?

testitemqlstudop

Posts: 740
Joined: July 21st, 2016, 11:45 am
Location: very very very very boats

### Re: Unproven conjectures

testitemqlstudop wrote:What are the least transitions required for Turing-completeness in isotropic non-totalistic 2-dimensional CA?

We have proven B2ae/S and B2ac/S to be Turing complete in the discord.
x = 140, y = 120, rule = B2ae/S
13\$93bo\$94bo2\$69bo17bo12bo17bo\$70bo16bo12bo16bo\$121bo\$120bo4\$40bo\$41bo
2\$16bo17bo12bo17bo26bo2bo\$17bo16bo12bo16bo28b2o9\$39bo2bo77b2o\$40b2o2\$
104bo\$103bo\$111bo\$110bo12bo\$20bo89bo13bo\$21bo89bo\$21bo\$20bo3\$120b2o3\$
39bo2bo\$40b2o6\$97bo\$96bo\$8bo\$9bo4\$120bo\$121bo\$39bo2bo\$40b2o10\$8b2o5\$
18bo15bo4bo2bo\$6bo12bo15bo4b2o\$5bo13bo15bo\$18bo15bo2\$40bo\$39bo2\$8b2o
17\$9bo\$8bo!

x = 249, y = 163, rule = B2ac/S
49bobo\$54bo2\$52b2o2\$52b2o2\$51bo2bo2\$52b2o4\$43bo\$41bo3bo\$41bo3bo\$43bo\$
38b2o2\$37bo2bo10bo2\$38b2o12b2o3\$170bobo\$24bo2\$24bo6bo11bo\$27bobo3bo11b
o\$27bobo3bo11bo57bo71bo23bo23bo11bo5bo\$25bo5bo71bo65b2o4bo23bo23bo11bo
5bo\$105bo71bo23bo23bo22bo\$171bo\$233b2o13bo6\$232bo2bo3\$214b2o2\$216bo18b
obo7\$224bo\$218bo\$218bo\$169b2o43b2o8bo4bo2\$171bo57bo4\$214b2o7\$216bobo
11\$169b2o2\$171bo3\$97bobo5\$99bo2bo6\$86bo13b2o2\$86bo34bo23bo23bo\$93bo5bo
23bo23bo23bo\$93bo5bo23bo23bo23bobo11bo5bo\$173bo11bo5bo\$175bo22bo2\$30bo
bo136b2o12b2o13bo2\$171bo4\$182bo2bo\$33b2o\$183bo\$179bo\$173bo7bo\$19bo82b
2o69bo\$169b2o8bo\$19bo4bo8b2o66bo\$30bo\$30bo\$24bo2\$169b2o5\$11bobo18bo2\$
33b2o136bobo3\$13bo2bo6\$o13b2o\$102b2o\$o22bo23bo23bo23bo24bo23bo\$7bo5bo
11bo23bo23bo23bo3bo20bo23bo\$7bo5bo11bo23bo23bo23bo24bo23bo4bo2\$151bo4\$
93bo\$99bo\$99bo\$88bo4bo8b2o2\$88bo4\$102b2o2\$51bo2\$51bo3\$99bobo!

However I'm not sure if any 1 transition TC rules exist
Sarp

Posts: 192
Joined: March 1st, 2015, 1:28 pm

### Re: Unproven conjectures

testitemqlstudop wrote:Can Life support all sub-c/2 orthogonal velocities? What about diagonal or oblique?

Life is known to support all sub-c/4 orthogonal velocities. However, I'm not sure about the speeds between c/4 and c/2. As for diagonal and oblique, I'm not sure either.
Life is hard. Deal with it.
My favorite oscillator of all time:
x = 7, y = 5, rule = B3/S2-i3-y4i
4b3o\$6bo\$o3b3o\$2o\$bo!

Hdjensofjfnen

Posts: 1090
Joined: March 15th, 2016, 6:41 pm
Location: r cis θ

### Re: Unproven conjectures

Hdjensofjfnen wrote:
testitemqlstudop wrote:Can Life support all sub-c/2 orthogonal velocities? What about diagonal or oblique?

Life is known to support all sub-c/4 orthogonal velocities. However, I'm not sure about the speeds between c/4 and c/2. As for diagonal and oblique, I'm not sure either.

From a universal constructor argument (using blinker puffers), you can achieve any rational velocity *strictly* below the vacuum speed limit -- that is to say, you can attain any (a,b)c/d where 2(a + b) < d.

As a partial converse, it's impossible to attain (a,b)c/d where 2(a + b) > d (originally proved by Conway).

What remains are the velocities where 2(a + b) == d, where there's neither a proof of existence nor non-existence. Currently there are only three known examples: the velocities of the glider, the LWSS, and Sir Robin.
What do you do with ill crystallographers? Take them to the mono-clinic!

calcyman

Posts: 2026
Joined: June 1st, 2009, 4:32 pm

### Re: Unproven conjectures

Can there exist a rule where the speeds of spaceships cannot be a certain value, but are able to approach it infinitely closely?

Life's top (orthogonal) spaceship speed is c/2: I'm thinking of a rule where c/2 spaceships cannot be achieved, but speeds approaching c/2 such as 2c/5, 3c/7, 4c/9, 5c/11, ... nc/2n+1 all can.

Also, how far have we enumerated each possible different n-cell rotor in Life?
Bored of using the Moore neighbourhood for everything? Introducing the Range-2 von Neumann isotropic non-totalistic rulespace!
muzik

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

### Re: Unproven conjectures

Sarp wrote:
testitemqlstudop wrote:What are the least transitions required for Turing-completeness in isotropic non-totalistic 2-dimensional CA?

However I'm not sure if any 1 transition TC rules exist

It's not possible. Because rules with 1 transition cannot have spaceship.
This post was brought to you by the Element of Magic.

Plz correct my grammar mistakes. I'm still studying English.

Working on:

Nothing.

Favorite gun ever:
#C Favorite Gun. Found by me.
x = 4, y = 6, rule = B2e3i4at/S1c23cijn4a
o2bo\$4o3\$4o\$o2bo!
Hunting

Posts: 1038
Joined: September 11th, 2017, 2:54 am
Location: Ponyville, Equestria

### Re: Unproven conjectures

Hunting wrote:
Sarp wrote:
testitemqlstudop wrote:What are the least transitions required for Turing-completeness in isotropic non-totalistic 2-dimensional CA?

However I'm not sure if any 1 transition TC rules exist

It's not possible. Because rules with 1 transition cannot have spaceship.

You can have infinite but finitely describable universes which would also prove TC'ness without using spaceships. You can use b3i to simulate W22 and b3e for W68 but neither are TC. With finite starting patterns all rules except b2a are easily provable to be non-TC. Also banks and Wireworld are TC rules without spaceships.
Sarp

Posts: 192
Joined: March 1st, 2015, 1:28 pm

### Re: Unproven conjectures

With infinite patterns B2a/S is probably TC; here is a p32 signal injector, (p32) signal track, and (p32) signal turner:
x = 130, y = 197, rule = B2a/S
11\$71bo\$52bo3bo14bo\$56bo12b2o\$28bo3bo3bo3bo3bo3bo8b2o21bo\$32bo7bo7bo
25b2o4bo\$33b2o6b2o6b2o22bo4b2o\$52b2o19bo\$54bo28b2o\$28b2o6b2o6b2o8bo3bo
23bo\$30bo7bo7bo35bo\$30bo3bo3bo3bo3bo3bo2\$62bo\$62bo\$60b2o\$41b2o\$65b2o\$
64bo\$64bo5\$33b2o6b2o6\$57b2o2\$33b2o6b2o25b2o2\$65b2o4\$57b2o6b2o2\$41b2o6b
2o3\$77b2o3\$57b2o2\$49b2o17b2o5\$11bo110bo\$11bo45b2o63bo\$9b2o112b2o\$77bo
15bo\$14b2o61bo15bo24b2o\$13bo106bo\$13bo40bo3bo61bo\$54bo24bo\$30bo3bo3bo
3bo3bo3bob2o25bo\$30bo7bo7bo33b2o\$28b2o6b2o6b2o\$57b2o16b2o\$56bo11b2o7bo
\$33b2o6b2o6b2obo3bo20bo\$32bo7bo7bo\$28bo3bo3bo3bo3bo3bo9bo4bo\$63bo52bo
4bo\$64b2o50bo\$114b2o\$58b2o\$60bo59b2o\$60bo4bo7bo15bo29bo\$73bo15bo24bo4b
o2\$57bo4bo53bo4bo\$62bo53bo\$63b2o49b2o2\$57b2o61b2o\$59bo37bo21bo\$59bo4bo
32bo16bo4bo2\$57bo4bo53bo4bo\$62bo53bo\$63b2o49b2o2\$57b2o61b2o\$59bo29bo
15bo13bo\$59bo4bo24bo15bo8bo4bo2\$57bo4bo53bo4bo\$62bo53bo\$63b2o49b2o2\$
57b2o9b2o50b2o\$59bo21bo37bo\$59bo4bo16bo32bo4bo2\$57bo4bo53bo4bo\$62bo53b
o\$63b2o49b2o2\$57b2o61b2o\$59bo13bo15bo29bo\$59bo4bo8bo15bo24bo4bo2\$57bo
4bo53bo4bo\$62bo53bo\$63b2o49b2o2\$57b2o61b2o\$59bo37bo21bo\$59bo4bo32bo16b
o4bo2\$57bo4bo53bo4bo\$62bo53bo\$63b2o49b2o2\$57b2o61b2o\$59bo29bo15bo13bo\$
59bo4bo24bo15bo8bo4bo2\$57bo4bo53bo4bo\$62bo53bo\$63b2o49b2o2\$57b2o9b2o
50b2o\$59bo21bo37bo\$59bo4bo16bo32bo4bo2\$57bo4bo53bo4bo\$62bo53bo\$63b2o
49b2o2\$57b2o61b2o\$59bo13bo15bo29bo\$59bo4bo8bo15bo24bo4bo22\$68b2o17\$68b
o\$68bo\$66b2o2\$71b2o\$70bo\$70bo!
x = 11, y = 5, rule = B2ck3-ij5n78/S01e2ei3-k5ai
8b2o\$2o3b2o\$bo4bo3bo\$2bo2b2o\$o7bo!

(Check Gen 2)

toroidalet

Posts: 949
Joined: August 7th, 2016, 1:48 pm
Location: my computer

Previous