Huh! Interesting. Never thought it was a matter of overpopulation (but it should be obvious given that the spaceship above requires S4w to survive).Bullet51 wrote:Here: http://www.njohnston.ca/2009/10/spacesh ... -automata/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!`

## Unproven conjectures

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

### Re: Unproven conjectures

"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

'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!
```

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

### 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?

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?

### Re: Unproven conjectures

We have proven B2ae/S and B2ac/S to be Turing complete in the discord.testitemqlstudop wrote: What are the least transitions required for Turing-completeness in isotropic non-totalistic 2-dimensional CA?

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!
```

WADUFI

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

### Re: Unproven conjectures

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.testitemqlstudop wrote: Can Life support all sub-c/2 orthogonal velocities? What about diagonal or oblique?

"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

'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!
```

### Re: Unproven conjectures

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.Hdjensofjfnen wrote: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.testitemqlstudop wrote: Can Life support all sub-c/2 orthogonal velocities? What about diagonal or oblique?

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### 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?

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!

### Re: Unproven conjectures

It's not possible. Because rules with 1 transition cannot have spaceship.Sarp wrote:However I'm not sure if any 1 transition TC rules existtestitemqlstudop wrote: What are the least transitions required for Turing-completeness in isotropic non-totalistic 2-dimensional CA?

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:

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!
```

### Re: Unproven conjectures

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.Hunting wrote:It's not possible. Because rules with 1 transition cannot have spaceship.Sarp wrote:However I'm not sure if any 1 transition TC rules existtestitemqlstudop wrote: What are the least transitions required for Turing-completeness in isotropic non-totalistic 2-dimensional CA?

WADUFI

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

### Re: Unproven conjectures

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

-Terry Pratchett

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

### Re: Unproven conjectures

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

'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!
```

### Re: Unproven conjectures

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

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!
```

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

### Re: Unproven conjectures

Doh! I forget the questions I've asked and haven't asked.dvgrn wrote:This came up yesterday on Discord, and as Kazyan mentioned it's very easy to disprove this conjecture.Hdjensofjfnen wrote:If a pattern is a Garden of Eden, its inverse cannot be a Garden of Eden.

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!`

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.

'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!
```

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

### Re: Unproven conjectures

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.

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

### Re: Unproven conjectures

A question:

Call a soup

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?'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!
```

### Re: Unproven conjectures

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 2x2Hdjensofjfnen wrote:A question:

Call a soupcompleteif its every cell within its bounding box is contained within its resulting envelope when run. What is the densitydso that a random soup with that density has a 50% chance of being complete?

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

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

### Re: Unproven conjectures

Can you clarify what you mean? I'm not sure I understand your meaning exactly. Do you mean OFF cells?dvgrn wrote:...any soup with three consecutive ON cells along an edge of its bounding box will automatically be not-complete.

'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!
```

### Re: Unproven conjectures

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.