In general, When are life like cellular automata turing complete and when do they have gliders?(In general)

[Colonizor48]

There are some interesting life rules which appear to have spaceships but are far less chaotic then Conway life(for example b35s238)
I conjecture that any life like rule with spaceship generators is Turing complete.(Though some ones without them might be as well)

Main questions:
In general, is there a way to determine if a lifelike cellular automata has gliders or not in all cases?
Is there a general way to determine if a lifelike cellular automata is Turing complete?
Does my conjecture hold?

EDIT: I only mean totalistic rules for now as the space of all possible non-totalistic rules is too large

[pipsqueek]

this is a good point, in most cases spaceships allow for the construction of basic logic circuits. plenty of life like rules have at least one spaceship.
but this does not always mean the rule is Turing complete, a rule could be explosive and have a simple spaceship. one could construct a basic XOR gate by making two spaceships collide, but in some cases there may not be a collision in which both spaceships are destroyed. so logic gates cannot be constructed. (or at least the rule may not be Turing complete) and sometimes a rule might seem too explosive to be Turing complete, but may be able to simulate Turing machines within its seemingly random explosions.

computers cannot assist in determining if a rule is Turing complete or not. as it is undecidable (I think)

[Colonizor48]

this is a good point, in most cases spaceships allow for the construction of basic logic circuits. plenty of life like rules have at least one spaceship.
but this does not always mean the rule is Turing complete, a rule could be explosive and have a simple spaceship. one could construct a basic XOR gate by making two spaceships collide, but in some cases there may not be a collision in which both spaceships are destroyed. so logic gates cannot be constructed. (or at least the rule may not be Turing complete) and sometimes a rule might seem too explosive to be Turing complete, but may be able to simulate Turing machines within its seemingly random explosions.

computers cannot assist in determining if a rule is Turing complete or not. as it is undecidable (I think)

While the problem of determining Turing completeness is in general undecidable, the problem can be decidable in specific cases. I suspect life like rules is one of these areas due to it's small search space and even smaller number of stable rules.

But with this, I revise my conjecture to every rule with spaceship guns that do not explode are Turing complete. But some rules without these properties may.

This raises the problem of searching every possible rule with a few soups and seeing which ones blow up and which ones dont(by that i mean every rule with b0 or b3).

Also I conjecture that no rule without b0 b1 b2 or b3 is turing complete(this can probably be proven trivially)

[FWKnightship]

Also I conjecture that no rule without b0 b1 b2 or b3 is turing complete(this can probably be proven trivially)

A W110 simulator in B5678/S0123456-ac78:

Code: Select all

x = 589, y = 378, rule = B5678/S0123456-ac78
589o$589o$589o$589o$589o$216ob291obob78o$138ob311ob138o$216ob294ob77o$
138ob311ob138o$589o$589o$589o$589o$509ob2ob76o$589o$589o$589o$589o$
589o$509ob2ob76o$589o$589o$589o$589o$589o$509ob2ob76o$589o$589o$589o$
589o$589o$214o2b294o2b77o$139o2b310o2b136o$214o2b373o$139o2b310o2b136o
$589o$589o$589o$589o$589o$218ob287obob80o$136ob311ob140o$218ob370o$
136ob311ob140o$589o$589o$589o$589o$57ob23ob23ob23ob23ob23ob23ob23ob23o
b23ob23ob23ob23ob23ob23ob23ob23ob23ob23ob99o$29ob5ob23ob23ob23ob23ob
23ob23ob23ob23ob23ob23ob23ob23ob23ob23ob23ob23ob23ob23ob23ob97o$29ob5o
b23ob23ob23ob23ob23ob23ob23ob23ob23ob23ob23ob23ob23ob23ob23ob23ob23ob
23ob23ob97o$5obob581o$589o$40obob546o$589o$589o$589o$589o$589o$589o$
423ob165o$589o$423ob165o$589o$130ob458o$589o$130ob458o$589o$421o2b166o
$589o$421o2b166o$589o$131o2b456o$589o$131o2b456o$589o$589o$425ob163o$
421ob167o$425ob163o$423ob165o$128ob460o$132ob288o2b166o$128ob460o$130o
b458o$589o$131o2b331ob124o$589o$134ob11ob3ob7obob240obob7ob3ob48ob16ob
107o$134ob11ob11obob240obob11ob173o$136ob11ob17obob224obob17ob43obob9o
bob3obob3ob107o$457ob11obob3obob111o$149obob258obob176o$589o$453o2b
134o$589o$453ob135o$589o$589o$589o$589o$449obob137o$589o$589o$589o$
589o$119obob331o2b134o$589o$102obob348o2b134o$108ob5ob11ob462o$108ob5o
b11ob462o$124ob97obob364o$453o2b134o$589o$130o2b321o2b134o$589o$129ob
459o$589o$451obob135o$134ob454o$589o$134ob454o$589o$589o$474obob112o$
589o$130o2b457o$589o$589o$589o$589o$589o$130o2b457o$589o$589o$589o$
132ob456o$589o$132ob343o2b111o$589o$589o$589o$589o$589o$475ob2ob110o$
589o$589o$589o$589o$589o$475ob2ob110o$589o$589o$589o$589o$589o$475ob2o
b110o$589o$476ob112o$472obob114o$476ob112o$589o$476o2b111o$589o$589o$
589o$589o$589o$589o$589o$589o$484ob104o$589o$390ob5ob87ob55obob46o$
388ob3obob3ob23ob23ob23ob118o$388ob3obob3ob23ob23ob23ob16ob23ob23ob23o
b5ob9obob11o$378obob9ob5ob23ob23ob23ob16ob23ob23ob23ob3obob3ob21o$485o
b23ob23ob23ob3obob3ob21o$413obob55ob87ob5ob23o$589o$471ob117o$589o$
589o$589o$476ob112o$589o$476o2b111o$589o$589o$589o$589o$589o$589o$589o
$589o$589o$265obob321o$589o$589o$589o$264o2b323o$589o$264o2b323o$589o$
589o$589o$264o2b323o$589o$264o2b210ob112o$589o$476o2b111o$589o$589o$
267obob319o$589o$589o$589o$589o$265ob323o$589o$264o2b323o$589o$483obob
103o$241obob3obob11ob327o$237ob3obob3obob9obob327o$589o$237ob16ob334o$
589o$254ob334o$589o$589o$589o$476ob112o$589o$476o2b111o$589o$589o$589o
$589o$589o$589o$589o$589o$589o$589o$589o$589o$589o$589o$202ob386o$589o
$185ob16ob386o$199ob76obob310o$185ob11ob3ob387o$197ob3ob91obob293o$
199ob67ob11obob307o$266ob12obob194ob112o$269ob319o$268ob207o2b111o$
589o$589o$589o$589o$589o$215obob371o$212o2b49ob325o$589o$211ob2ob48ob
325o$266o2b321o$212o2b375o$266o2b321o$589o$589o$589o$589o$589o$589o$
589o$589o$589o$476ob112o$213obob373o$265ob210o2b111o$589o$265ob323o$
589o$589o$589o$589o$589o$589o$589o$589o$589o$589o$589o$589o$589o$589o$
589o$589o$589o$589o$589o$476ob112o$589o$476o2b111o$589o$589o$589o$589o
$589o$589o$589o$589o$589o$589o$589o$589o$589o$589o$589o$589o$589o$589o
$589o$589o$589o$476ob112o$589o$476o2b111o$589o$589o$589o$589o$589o$85o
bob402ob5ob5ob86o$412ob71ob23ob80o$68obob341obob69obobob19ob13ob66o$
80ob5ob403ob5ob5ob86o$80ob5ob400ob34ob66o$589o$487ob101o$589o$589o$
589o$589o$589o$589o$100ob488o$96o2b491o$100ob488o$589o$589o$589o$589o$
96o2b491o$589o$589o$589o$589o$589o$589o$589o$589o$589o$98ob490o$589o$
98ob490o$589o$589o$589o$589o$589o$589o$589o$589o$589o!

[pipsqueek]

Also I conjecture that no rule without b0 b1 b2 or b3 is turing complete(this can probably be proven trivially)

A W110 simulator in B5678/S0123456-ac78:

this example is trivial due to not being a life like rule. (if "life like rule" implies it must be totalistic)

[yujh]

It’s a proof that a rule doesn’t need B0123 to be tc.

[Colonizor48]

Also I conjecture that no rule without b0 b1 b2 or b3 is turing complete(this can probably be proven trivially)

A W110 simulator in B5678/S0123456-ac78:

this example is trivial due to not being a life like rule. (if "life like rule" implies it must be totalistic)

Yes i met totalistic rules

[Colonizor48]

A W110 simulator in B5678/S0123456-ac78:

this example is trivial due to not being a life like rule. (if "life like rule" implies it must be totalistic)

Yes I met totalistic rules. None of what I have conjectured includes non-totalistic rules. By life like rules I just mean totalistic rules where cells have 2 states.

[toroidalet]

If you are allowed an infinite periodic grid, B57/S01234 is Turing-complete. Here is an OR gate:

Code: Select all

x = 190, y = 69, rule = B57/S01234
26bobo62bobo69bobo$26bobo62bobo69bobo$26bobo62bobo69bobo$26bobo62bobo
69bobo2$26bobo62bobo69bobo$24bobobobo58bobobobo65bobobobo$26bobo62bobo
69bobo$20bob5ob6obo49bob5ob6obo56bob5ob6obo2$20bob5ob6obo49bob5ob6obo
56bob5ob6obo$20bobo9b2obo49bobo9b2obo56bobo9b2obo$20bobo10bob2o48bobo
10bob2o55bobo10bob2o$16b5obo10bob4obo40b5obo10bob4obo47b5obo10bob4obo$
14bo64bo71bo$14bob5obo10bob4obo38bob5obo10bob4obo45bob5obo10bob4obo$
16bo20b2obo40bo20b2obo47bo20b2obo$14bo23bobo38bo23bobo45bo23bobo$14bob
o21bobo38bobo21bobo45bobo21bobo$16bo19bobobobo38bo19bobobobo45bo19bobo
bobo$14bo23bobo38bo23bobo45bo23bobo$7b2ob5ob5ob2o7b2ob5ob5ob2o24b2ob5o
b5ob2o7b2ob5ob5ob2o31b2ob5ob5ob2o7b2ob5ob5ob2o2$7b2ob5ob5ob2o7b2ob5ob
5ob2o24b2ob5ob5ob2o7b2ob5ob5ob2o31b2ob5ob5ob2o7b2ob5ob5ob2o$8bob2o7b2o
bo9bob2o7b2obo26bob2o7b2obo9bob2o7b2obo33bob2o7b2obo9bob2o7b2obo$8bobo
9bobo9bobo9bobo26bobo9bobo9bobo9bobo33bobo9bobo9bobo9bobo$8bobo9bobo9b
obo9bobo26bobo9bobo9bobo9bobo33bobo9bobo9bobo9bobo$8bobo9bobo9bobo9bob
o26bobo9bobo9bobo9bobo33bobo9bobo9bobo9bobo2$8bobo9bobo9bobo9bobo26bob
o9bobo9bobo9bobo33bobo9bobo9bobo9bobo$8bobo9bobo9bobo9bobo26bobo9bobo
9bobo9bobo33bobo9bobo9bobo9bobo$6bobobo7bobobobo5bobobobo7bobobo22bobo
bo7bobobobo5bobobobo7bobobo29bobobo7bobobobo5bobobobo7bobobo$8bobo9bob
o9bobo9bobo26bobo9bobo9bobo9bobo33bobo9bobo9bobo9bobo$3ob5obo3bob5ob5o
b5ob5obo3bob5ob3o10b3ob5obo3bob5ob5ob5ob5obo3bob5ob3o17b3ob5obo3bob5ob
5ob5ob5obo3bob5obo2$3ob5obo3bob5ob5ob5ob5obo3bob5ob3o10b3ob5obo3bob5ob
5ob5ob5obo3bob5ob3o17b3ob5obo3bob5ob5ob5ob5obo3bob5obo$b2ob2o8bobo9bob
o9bobo8b2ob2o12b2ob2o8bobo9bobo9bobo8b2ob2o19b2ob2o8bobo9bobo9bobo8b2o
bo$2bobo9bobobo5bobobobo5bobobo9bobo14bobo9bobobo5bobobobo5bobobo9bobo
21bobo9bobobo5bobobobo5bobobo9bobo$2bobo9bobo9bobo9bobo9bobo14bobo9bob
o9bobo9bobo9bobo21bobo9bobo9bobo9bobo9bobo$2bobo9bobo9bobo9bobo9bobo
14bobo9bobo9bobo9bobo9bobo21bobo9bobo9bobo9bobo9bobo$2bobobo7bobobo5bo
bobobo5bobobo7bobobo14bobobo7bobobo5bobobobo5bobobo7bobobo21bobobo7bob
obo5bobobobo5bobobo7bobobo$2bobo9bobo9bobo9bobo9bobo14bobo9bobo9bobo9b
obo9bobo21bobo9bobo9bobo9bobo9bobo$2bob5obo3bob5ob5ob5ob5obo3bob5obo
14bob5obo3bob5ob5ob5ob5obo3bob5obo21bob5obo3bob5ob5ob5ob5obo3bob5obo2$
2bob5obo3bob5ob5ob5ob5obo3bob5obo14bob5obo3bob5ob5ob5ob5obo3bob5obo21b
ob5obo3bob5ob5ob5ob5obo3bob5obo$2bobo3bobo3bobo3bobo3bobo3bobo3bobo3bo
bo3bobo14bobo3bobo3bobo3bobo3bobo3bobo3bobo3bobo3bobo21bobo3bobo3bobo
3bobo3bobo3bobo3bobo3bobo3bobo$2bobobobobo3bobobobobobobobobobobobobob
o3bobobobobo14bobobobobo3bobobobobobobobobobobobobobo3bobobobobo21bobo
bobobo3bobobobobobobobobobobobobobo3bobobobobo$8bobo9bobo9bobo9bobo26b
obo9bobo9bobo9bobo33bobo9bobo9bobo9bobo$8bobo9bobo9bobo9bobo26bobo9bob
o9bobo9bobo33bobo9bobo9bobo9bobo$8bobo9bobo9bobo9bobo26bobo9bobo9bobo
9bobo33bobo9bobo9bobo9bobo$8bobo9bobo9bobo9bobo26bobo9bobo9bobo9bobo
33bobo9bobo9bobo9bobo$8bobo9bobo9bobo9bobo26bobo9bobo9bobo9bobo33bobo
9bobo9bobo9bobo$8bobo9bobo9bobo9bobo26bobo9bobo9bobo9bobo33bobo9bobo9b
obo9bobo$8bob2o7b2obo9bob2o7b2obo26bob2o7b2obo9bob2o7b2obo33bob2o7b2ob
o9bob2o7b2obo$8bob5ob5obo9bob5ob5obo26bob5ob5obo9bob5ob5obo33bob5ob5ob
o9bob5ob5obo2$8bob5ob5obo9bob5ob5obo26bob5ob5obo9bob5ob5obo33bob5ob5ob
o9bob5ob5obo$8bob2o2bobo2b2obo9bob2o2bobo2b2obo26bob2o2bobo2b2obo9bob
2o2bobo2b2obo33bob2o2bobo2b2obo9bob2o2bobo2b2obo$8bobo3bobo3bobo9bobo
3bobo3bobo26bobo3bobo3bobo9bobo3bobo3bobo33bobo3bobo3bobo9bobo3bobo3bo
bo$14bobo21bobo38bobo21bobo45bobo21bobo$14bobo21bobo38bobo21bobo45bobo
21bobo$14bobo21bobo38bobo21bobo45bobo21bobo$14bobo21bobo38bobo21bobo
45bobo21bobo$14bobo21bobo38bobo21bobo45bobo21bobo$14bobo21bobo38bobo
21bobo45bobo21bobo$14bobo21bobo38bobo21bobo45bobo21bobo$14bobo21bobo
38bobo21bobo45bobo21bobo$14bobo21bobo38bobo21bobo45bobo21bobo$14b3o21b
3o38bobo21b3o45b3o21bobo!

This is constructed from AND and XOR gates, with which we can construct any Boolean function F if F(0,0,0,....0) = 0. In particular, we can use this to simulate rule 110 or a Turing machine. However, if you restrict it to finite patterns, it is in PSPACE.

[Colonizor48]

If you are allowed an infinite periodic grid, B57/S01234 is Turing-complete. Here is an OR gate:

Code: Select all

x = 190, y = 69, rule = B57/S01234
26bobo62bobo69bobo$26bobo62bobo69bobo$26bobo62bobo69bobo$26bobo62bobo
69bobo2$26bobo62bobo69bobo$24bobobobo58bobobobo65bobobobo$26bobo62bobo
69bobo$20bob5ob6obo49bob5ob6obo56bob5ob6obo2$20bob5ob6obo49bob5ob6obo
56bob5ob6obo$20bobo9b2obo49bobo9b2obo56bobo9b2obo$20bobo10bob2o48bobo
10bob2o55bobo10bob2o$16b5obo10bob4obo40b5obo10bob4obo47b5obo10bob4obo$
14bo64bo71bo$14bob5obo10bob4obo38bob5obo10bob4obo45bob5obo10bob4obo$
16bo20b2obo40bo20b2obo47bo20b2obo$14bo23bobo38bo23bobo45bo23bobo$14bob
o21bobo38bobo21bobo45bobo21bobo$16bo19bobobobo38bo19bobobobo45bo19bobo
bobo$14bo23bobo38bo23bobo45bo23bobo$7b2ob5ob5ob2o7b2ob5ob5ob2o24b2ob5o
b5ob2o7b2ob5ob5ob2o31b2ob5ob5ob2o7b2ob5ob5ob2o2$7b2ob5ob5ob2o7b2ob5ob
5ob2o24b2ob5ob5ob2o7b2ob5ob5ob2o31b2ob5ob5ob2o7b2ob5ob5ob2o$8bob2o7b2o
bo9bob2o7b2obo26bob2o7b2obo9bob2o7b2obo33bob2o7b2obo9bob2o7b2obo$8bobo
9bobo9bobo9bobo26bobo9bobo9bobo9bobo33bobo9bobo9bobo9bobo$8bobo9bobo9b
obo9bobo26bobo9bobo9bobo9bobo33bobo9bobo9bobo9bobo$8bobo9bobo9bobo9bob
o26bobo9bobo9bobo9bobo33bobo9bobo9bobo9bobo2$8bobo9bobo9bobo9bobo26bob
o9bobo9bobo9bobo33bobo9bobo9bobo9bobo$8bobo9bobo9bobo9bobo26bobo9bobo
9bobo9bobo33bobo9bobo9bobo9bobo$6bobobo7bobobobo5bobobobo7bobobo22bobo
bo7bobobobo5bobobobo7bobobo29bobobo7bobobobo5bobobobo7bobobo$8bobo9bob
o9bobo9bobo26bobo9bobo9bobo9bobo33bobo9bobo9bobo9bobo$3ob5obo3bob5ob5o
b5ob5obo3bob5ob3o10b3ob5obo3bob5ob5ob5ob5obo3bob5ob3o17b3ob5obo3bob5ob
5ob5ob5obo3bob5obo2$3ob5obo3bob5ob5ob5ob5obo3bob5ob3o10b3ob5obo3bob5ob
5ob5ob5obo3bob5ob3o17b3ob5obo3bob5ob5ob5ob5obo3bob5obo$b2ob2o8bobo9bob
o9bobo8b2ob2o12b2ob2o8bobo9bobo9bobo8b2ob2o19b2ob2o8bobo9bobo9bobo8b2o
bo$2bobo9bobobo5bobobobo5bobobo9bobo14bobo9bobobo5bobobobo5bobobo9bobo
21bobo9bobobo5bobobobo5bobobo9bobo$2bobo9bobo9bobo9bobo9bobo14bobo9bob
o9bobo9bobo9bobo21bobo9bobo9bobo9bobo9bobo$2bobo9bobo9bobo9bobo9bobo
14bobo9bobo9bobo9bobo9bobo21bobo9bobo9bobo9bobo9bobo$2bobobo7bobobo5bo
bobobo5bobobo7bobobo14bobobo7bobobo5bobobobo5bobobo7bobobo21bobobo7bob
obo5bobobobo5bobobo7bobobo$2bobo9bobo9bobo9bobo9bobo14bobo9bobo9bobo9b
obo9bobo21bobo9bobo9bobo9bobo9bobo$2bob5obo3bob5ob5ob5ob5obo3bob5obo
14bob5obo3bob5ob5ob5ob5obo3bob5obo21bob5obo3bob5ob5ob5ob5obo3bob5obo2$
2bob5obo3bob5ob5ob5ob5obo3bob5obo14bob5obo3bob5ob5ob5ob5obo3bob5obo21b
ob5obo3bob5ob5ob5ob5obo3bob5obo$2bobo3bobo3bobo3bobo3bobo3bobo3bobo3bo
bo3bobo14bobo3bobo3bobo3bobo3bobo3bobo3bobo3bobo3bobo21bobo3bobo3bobo
3bobo3bobo3bobo3bobo3bobo3bobo$2bobobobobo3bobobobobobobobobobobobobob
o3bobobobobo14bobobobobo3bobobobobobobobobobobobobobo3bobobobobo21bobo
bobobo3bobobobobobobobobobobobobobo3bobobobobo$8bobo9bobo9bobo9bobo26b
obo9bobo9bobo9bobo33bobo9bobo9bobo9bobo$8bobo9bobo9bobo9bobo26bobo9bob
o9bobo9bobo33bobo9bobo9bobo9bobo$8bobo9bobo9bobo9bobo26bobo9bobo9bobo
9bobo33bobo9bobo9bobo9bobo$8bobo9bobo9bobo9bobo26bobo9bobo9bobo9bobo
33bobo9bobo9bobo9bobo$8bobo9bobo9bobo9bobo26bobo9bobo9bobo9bobo33bobo
9bobo9bobo9bobo$8bobo9bobo9bobo9bobo26bobo9bobo9bobo9bobo33bobo9bobo9b
obo9bobo$8bob2o7b2obo9bob2o7b2obo26bob2o7b2obo9bob2o7b2obo33bob2o7b2ob
o9bob2o7b2obo$8bob5ob5obo9bob5ob5obo26bob5ob5obo9bob5ob5obo33bob5ob5ob
o9bob5ob5obo2$8bob5ob5obo9bob5ob5obo26bob5ob5obo9bob5ob5obo33bob5ob5ob
o9bob5ob5obo$8bob2o2bobo2b2obo9bob2o2bobo2b2obo26bob2o2bobo2b2obo9bob
2o2bobo2b2obo33bob2o2bobo2b2obo9bob2o2bobo2b2obo$8bobo3bobo3bobo9bobo
3bobo3bobo26bobo3bobo3bobo9bobo3bobo3bobo33bobo3bobo3bobo9bobo3bobo3bo
bo$14bobo21bobo38bobo21bobo45bobo21bobo$14bobo21bobo38bobo21bobo45bobo
21bobo$14bobo21bobo38bobo21bobo45bobo21bobo$14bobo21bobo38bobo21bobo
45bobo21bobo$14bobo21bobo38bobo21bobo45bobo21bobo$14bobo21bobo38bobo
21bobo45bobo21bobo$14bobo21bobo38bobo21bobo45bobo21bobo$14bobo21bobo
38bobo21bobo45bobo21bobo$14bobo21bobo38bobo21bobo45bobo21bobo$14b3o21b
3o38bobo21b3o45b3o21bobo!

This is constructed from AND and XOR gates, with which we can construct any Boolean function F if F(0,0,0,....0) = 0. In particular, we can use this to simulate rule 110 or a Turing machine. However, if you restrict it to finite patterns, it is in PSPACE.

I think this counts. As it is(weakly) universal. I think we could separate Turing completeness into strong and weak. Strongly Turing complete means it is universal with only finite(but arbitrarily large) patterns, where weakly Turing complete is only Turing complete with infinitely many cells in the initial state.(For more on strong/weak Turing completeness see(https://en.wikipedia.org/wiki/Universal ... t_machines).(I don't know if my definition is sound and if it is not then i will Revise it))
Good job irregardless.
This leaves the open question of is it possible for a rule without b0 b1 b2 or b3 is StronglyTuring complete. I suspect the answer of this is negative(it can never get larger then it's bounding box), but I very well could be wrong.

This means determining Turing completeness for Totalistic rules is harder then I thought. Is there a database of life rules known to be Turing complete and/or not Turing complete?

[Colonizor48]

I have thought of a potential angle of attack for determining if a given rule has Spaceships. Somehow converting the decision problem of "Given a life rule-string, does it have any spaceships?" into a SAT problem and solving that. SAT while worst case hard as far as we know, does have efficent solvers for most cases. Again i am only talking about Totalistic lifelike rules. The search space for those is far smaller then non-totalistic rules making this problem actually attack-able(maybe). So there is a reasonable chance of solving it by bruit force, as I imagine in most cases this problem will be trivial(It is already known that no rules without b0 b2 or b3 have any gliders.) This would basically be doing what logic life search does but making it from "Does a spaceship within this size in this rule satisfying these other constraints exist"? To "Does a spaceship exist in this rule?". This also might not be reducible to SAT. QBFSat may be needed. Which also has efficient solvers to my knowledge.

[yujh]

A rule has spaceships if it has B1, or B2a, or at least one of B3i or B2c and at least one of B3a or B2e. A rule does not have to have spaceships to be Turing complete. B0 is considered here, because it usually complicates things.

[hotdogPi]

A rule can only have spaceships if it has B1e, or B2a, or at least one of B3i or B2c and at least one of B3a or B2e. A rule does not have to have spaceships to be Turing complete. B0 is not considered here, because it usually complicates things.

Fixed.

1. It's a necessary condition, not a sufficient condition.

2. B1c explodes on all four corners. A spaceship is impossible with B1c.

3. I think you simply typoed this one.

[toroidalet]

This leaves the open question of is it possible for a rule without b0 b1 b2 or b3 is StronglyTuring complete. I suspect the answer of this is negative(it can never get larger then it's bounding box), but I very well could be wrong.

You were almost there! If a rule cannot expand beyond its bounding box, then after 2^(area) generations, it must have repeated itself at least once and therefore stabilized.

This means determining Turing completeness for Totalistic rules is harder then I thought. Is there a database of life rules known to be Turing complete and/or not Turing complete?

There is a list, but it is incomplete because there are a lot of rules, and the only way to prove Turing-completeness is to actually show a set of logic gates (or construct a universal machine, but that usually requires finding the logic gates). Additionally, it seems almost impossible to prove that a rule isn't Turing-complete if it's anything more complicated than B/S012345678. For arbitrary rules it is undecidable if a rule is (both strongly or weakly) Turing-complete even if you can solve the halting problem. The only thing that makes Life-like rules easier in this regard is because there are a relatively small number so we probably didn't get any horrible ones.

Somehow converting the decision problem of "Given a life rule-string, does it have any spaceships?" into a SAT problem and solving that.

It's a bit harder than that, because a rule could have only very large or very high-period spaceships (for example, if the smallest spaceship in a rule were 100*100 spaceship with period 1000, it would be very hard to find). In order to show that your SAT formula worked, you would need to show that every rule with a spaceship had a spaceship with a given bounding box and period or less, which is not an easy task (indeed, for arbitrary rules it is undecidable whether they even have a spaceship).

[Colonizor48]

This leaves the open question of is it possible for a rule without b0 b1 b2 or b3 is StronglyTuring complete. I suspect the answer of this is negative(it can never get larger then it's bounding box), but I very well could be wrong.

You were almost there! If a rule cannot expand beyond its bounding box, then after 2^(area) generations, it must have repeated itself at least once and therefore stabilized.

This means determining Turing completeness for Totalistic rules is harder then I thought. Is there a database of life rules known to be Turing complete and/or not Turing complete?

There is a list, but it is incomplete because there are a lot of rules, and the only way to prove Turing-completeness is to actually show a set of logic gates (or construct a universal machine, but that usually requires finding the logic gates). Additionally, it seems almost impossible to prove that a rule isn't Turing-complete if it's anything more complicated than B/S012345678. For arbitrary rules it is undecidable if a rule is (both strongly or weakly) Turing-complete even if you can solve the halting problem. The only thing that makes Life-like rules easier in this regard is because there are a relatively small number so we probably didn't get any horrible ones.

Somehow converting the decision problem of "Given a life rule-string, does it have any spaceships?" into a SAT problem and solving that.

It's a bit harder than that, because a rule could have only very large or very high-period spaceships (for example, if the smallest spaceship in a rule were 100*100 spaceship with period 1000, it would be very hard to find). In order to show that your SAT formula worked, you would need to show that every rule with a spaceship had a spaceship with a given bounding box and period or less, which is not an easy task (indeed, for arbitrary rules it is undecidable whether they even have a spaceship).

Can you give a Proof that determining if a (life like totalistic)rule has a spaceship is undecidable? Don't mean to be mean or anything I just want to verify that there is a proof. That feels the the kind of thing that could be reduced to SAT or QBF. Also to prove something isn't Turing complete you can show that it is Decidable, IE produce a general algorithm to determine if a given pattern will halt or not in a particular rule or prove one exists. I suspect that in rules where it is decidable the answer to if a given pattern ever stabilize will always be either yes or no for almost all initial conditions or all initial conditions.

[toroidalet]

What I meant was that for arbitrary cellular automata, it is undecidable whether there are spaceships{a}, and so we should expect this to be a Very Hard Problem. Because there are only finitely many life-like rules, it is decidable with the algorithm below.

Code: Select all

if rule is B/S:
    return no
else if rule is B1/S:
    return no
else if rule is B2/S:
    return yes
else if rule is B12/S:
    return yes
else if rule is B3/S:
    return no
and so on

"Decidable" is the wrong question here, because you have to solve the spaceship problem for all life-like rules to show that it is correct. Unfortunately, it is very hard to show that a rule doesn't have a very large or high-period spaceship. How would you rule out the possibility that a 1 million by 1 million blob of junk moves itself by 67 cells every 287 generations?

Even the halting problem is decidable if you restrict the size of the Turing machine, but that isn't a comfort if you have to show that the Turing machine that proves the Goldbach conjecture never halts (you have to prove the Goldbach conjecture to confirm that your decision algorithm is correct).

{a}: For example, the rule where a cell moves upward forever, leaving copies of a Turing machine in its wake. Obviously, has a spaceship iff the Turing clears its tape and halts, which is undecidable.
{b}: There is still the possibility that you could prove that if a rule has a spaceship, it has a spaceship of period <n, but