Unproven conjectures

For general discussion about Conway's Game of Life.
User avatar
Hdjensofjfnen
Posts: 1338
Joined: March 15th, 2016, 6:41 pm
Location: r cis θ

Re: Unproven conjectures

Post by Hdjensofjfnen » March 19th, 2019, 10:46 pm

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:

Code: Select all

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).
"A man said to the universe:
'Sir, I exist!'
'However,' replied the universe,
'The fact has not created in me
A sense of obligation.'" -Stephen Crane

Code: Select all

x = 7, y = 5, rule = B3/S2-i3-y4i
4b3o$6bo$o3b3o$2o$bo!

User avatar
testitemqlstudop
Posts: 1197
Joined: July 21st, 2016, 11:45 am
Location: in catagolue
Contact:

Re: Unproven conjectures

Post by testitemqlstudop » March 19th, 2019, 11:11 pm

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?

Sarp
Posts: 203
Joined: March 1st, 2015, 1:28 pm

Re: Unproven conjectures

Post by Sarp » March 20th, 2019, 3:15 am

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.

Code: Select all

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!

Code: Select all

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
WADUFI

User avatar
Hdjensofjfnen
Posts: 1338
Joined: March 15th, 2016, 6:41 pm
Location: r cis θ

Re: Unproven conjectures

Post by Hdjensofjfnen » March 20th, 2019, 5:01 am

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.
"A man said to the universe:
'Sir, I exist!'
'However,' replied the universe,
'The fact has not created in me
A sense of obligation.'" -Stephen Crane

Code: Select all

x = 7, y = 5, rule = B3/S2-i3-y4i
4b3o$6bo$o3b3o$2o$bo!

User avatar
calcyman
Posts: 2096
Joined: June 1st, 2009, 4:32 pm

Re: Unproven conjectures

Post by calcyman » March 20th, 2019, 5:36 am

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!

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

Re: Unproven conjectures

Post by muzik » March 20th, 2019, 6:46 am

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!

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

Re: Unproven conjectures

Post by Hunting » March 21st, 2019, 12:08 am

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:

Code: Select all

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

Sarp
Posts: 203
Joined: March 1st, 2015, 1:28 pm

Re: Unproven conjectures

Post by Sarp » March 21st, 2019, 5:01 am

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.
WADUFI

User avatar
toroidalet
Posts: 1021
Joined: August 7th, 2016, 1:48 pm
Location: my computer
Contact:

Re: Unproven conjectures

Post by toroidalet » March 23rd, 2019, 3:01 pm

With infinite patterns B2a/S is probably TC; here is a p32 signal injector, (p32) signal track, and (p32) signal turner:

Code: Select all

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!
"Build a man a fire and he'll be warm for a day. Set a man on fire and he'll be warm for the rest of his life."

-Terry Pratchett

User avatar
Hdjensofjfnen
Posts: 1338
Joined: March 15th, 2016, 6:41 pm
Location: r cis θ

Re: Unproven conjectures

Post by Hdjensofjfnen » September 26th, 2019, 10:17 pm

If a pattern is a Garden of Eden, its inverse cannot be a Garden of Eden.
"A man said to the universe:
'Sir, I exist!'
'However,' replied the universe,
'The fact has not created in me
A sense of obligation.'" -Stephen Crane

Code: Select all

x = 7, y = 5, rule = B3/S2-i3-y4i
4b3o$6bo$o3b3o$2o$bo!

User avatar
dvgrn
Moderator
Posts: 5889
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Unproven conjectures

Post by dvgrn » September 26th, 2019, 11:08 pm

Hdjensofjfnen wrote:If a pattern is a Garden of Eden, its inverse cannot be a Garden of Eden.
This came up yesterday on Discord, and as Kazyan mentioned it's very easy to disprove this conjecture.

E.g., the following is a GoE whose inverse is trivially also a GoE:

Code: Select all

x = 12, y = 16, rule = B3/S23
o2b2obo2b3o$b2o2b2obobo$obobo2bobobo$b4o2b2o2bo$o3b3ob4o$2obobo2bob2o$
obo2b3obobo$b4obob4o$o4bobo$bob2o3bobo$2bobob2obo$b3o3bo$o4b2o2b2o$bob
ob2obobo$o2b2o2bobobo$b2o2bob2o!

User avatar
Hdjensofjfnen
Posts: 1338
Joined: March 15th, 2016, 6:41 pm
Location: r cis θ

Re: Unproven conjectures

Post by Hdjensofjfnen » September 26th, 2019, 11:20 pm

dvgrn wrote:
Hdjensofjfnen wrote:If a pattern is a Garden of Eden, its inverse cannot be a Garden of Eden.
This came up yesterday on Discord, and as Kazyan mentioned it's very easy to disprove this conjecture.

E.g., the following is a GoE whose inverse is trivially also a GoE:

Code: Select all

x = 12, y = 16, rule = B3/S23
o2b2obo2b3o$b2o2b2obobo$obobo2bobobo$b4o2b2o2bo$o3b3ob4o$2obobo2bob2o$
obo2b3obobo$b4obob4o$o4bobo$bob2o3bobo$2bobob2obo$b3o3bo$o4b2o2b2o$bob
ob2obobo$o2b2o2bobobo$b2o2bob2o!
Doh! I forget the questions I've asked and haven't asked.
EDIT: Anyway, another conjecture:
Call the set of Gardens of Eden S0. Then call the set of the grandfatherless patterns S1. Then call the set of the great-grandfatherless patterns S2, and so on.
Conjecture a) The number of elements in Sn for arbitrarily large n is smaller than the number of elements in S0. (In essence, there is not necessarily a bijection between the elements of Sn and the elements of Sn-1.)
Conjecture b) There is a nonzero and therefore infinite number of elements in each of S0, S1, S2, ... ad infinitum.
"A man said to the universe:
'Sir, I exist!'
'However,' replied the universe,
'The fact has not created in me
A sense of obligation.'" -Stephen Crane

Code: Select all

x = 7, y = 5, rule = B3/S2-i3-y4i
4b3o$6bo$o3b3o$2o$bo!

User avatar
testitemqlstudop
Posts: 1197
Joined: July 21st, 2016, 11:45 am
Location: in catagolue
Contact:

Re: Unproven conjectures

Post by testitemqlstudop » September 26th, 2019, 11:46 pm

The set of gardens of eden is infinite, so this is equivalent to asking whether or not there is a bijection between S0 and Z/R.

User avatar
Hdjensofjfnen
Posts: 1338
Joined: March 15th, 2016, 6:41 pm
Location: r cis θ

Re: Unproven conjectures

Post by Hdjensofjfnen » September 27th, 2019, 12:09 am

A question:
Call a soup complete if its every cell within its bounding box is contained within its resulting envelope when run. What is the density d so that a random soup with that density has a 50% chance of being complete?
"A man said to the universe:
'Sir, I exist!'
'However,' replied the universe,
'The fact has not created in me
A sense of obligation.'" -Stephen Crane

Code: Select all

x = 7, y = 5, rule = B3/S2-i3-y4i
4b3o$6bo$o3b3o$2o$bo!

User avatar
dvgrn
Moderator
Posts: 5889
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Unproven conjectures

Post by dvgrn » September 27th, 2019, 8:01 am

Hdjensofjfnen wrote:A question:
Call a soup complete if its every cell within its bounding box is contained within its resulting envelope when run. What is the density d so that a random soup with that density has a 50% chance of being complete?
This seems more like a Basic Question than an Unproven Conjecture. There's no well-defined answer as you've stated the question, because the required density will depend on the size and shape of the soup's bounding box. But above 2x2 d will be fairly low, since any soup with three consecutive ON cells along an edge of its bounding box will automatically be not-complete.

User avatar
Hdjensofjfnen
Posts: 1338
Joined: March 15th, 2016, 6:41 pm
Location: r cis θ

Re: Unproven conjectures

Post by Hdjensofjfnen » September 30th, 2019, 11:22 pm

dvgrn wrote:...any soup with three consecutive ON cells along an edge of its bounding box will automatically be not-complete.
Can you clarify what you mean? I'm not sure I understand your meaning exactly. Do you mean OFF cells?
"A man said to the universe:
'Sir, I exist!'
'However,' replied the universe,
'The fact has not created in me
A sense of obligation.'" -Stephen Crane

Code: Select all

x = 7, y = 5, rule = B3/S2-i3-y4i
4b3o$6bo$o3b3o$2o$bo!

wildmyron
Posts: 1274
Joined: August 9th, 2013, 12:45 am

Re: Unproven conjectures

Post by wildmyron » October 1st, 2019, 1:12 am

I believe there's some confusion here as dvgrn seems to have understood complete as meaning "all cells and only those cells within the bounding box of the soup have been On for at least one generation". With this definition any soup with three adjacent On cells on the boundary of the soup will be not-complete because of the birth outside the bbox on gen 1. With the less restrictive definition (as I believe was intended) this situation does not make the soup not-complete.
The latest version of the 5S Project contains over 221,000 spaceships. Tabulated pages up to period 160 are available on the LifeWiki.

Post Reply