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

List of the Turing-complete totalistic life-like CA

For discussion of other cellular automata.

List of the Turing-complete totalistic life-like CA

Postby Naszvadi » December 4th, 2016, 4:00 pm

This topic is for collecting all 2D life-like totalistic cellular automata that are proven to be Turing-complete, with link to/summary of the first AND the simplest proof of its Turing-completeness.

Game of Life (citation needed, with oldest existence and simplest constructed UTM) Others?

What I prefer:
  • Would be handy including constructions of unit cells that emulates GoL, Rule-110 or other relevant rules, and wonder if there are such unit cells that work in other rules
  • If there is at least one $SUBJECT CA that is TC, then it can be embedded into Life using OTCA-metapixel
  • An up-to-date wiki entry with the corresponding rules

Currently known universal rules that support the Glider (total 256 rules, and 64 without S0 and S5):
  1. B3/S23
  2. B3/S236
  3. B3/S2367
  4. B3/S23678
  5. B3/S2368
  6. B3/S237
  7. B3/S2378
  8. B3/S238
  9. B36/S23
  10. B36/S237
  11. B36/S2378
  12. B36/S238
  13. B368/S23
  14. B368/S238
  15. B37/S23
  16. B37/S236
  17. B37/S237
  18. B37/S238
  19. B378/S237
  20. B378/S2378
  21. B378/S238
  22. B38/S23
  23. B38/S236
  24. B38/S2367
  25. B38/S23678
  26. B38/S2368
  27. B38/S237
  28. B38/S2378
  29. B38/S238
Last edited by Naszvadi on January 3rd, 2017, 10:58 am, edited 3 times in total.
Naszvadi
 
Posts: 150
Joined: May 7th, 2016, 8:53 am

Re: List of the Turing-complete totalistic life-like CA

Postby Naszvadi » December 8th, 2016, 6:04 pm

B3/S23 (Game of Life): A unit cell of Rule-110 automaton was created, visit for more: http://pentadecathlon.com/lifenews/2005 ... _cell.html
Naszvadi
 
Posts: 150
Joined: May 7th, 2016, 8:53 am

Re: List of the Turing-complete totalistic life-like CA

Postby Naszvadi » December 9th, 2016, 6:51 pm

Naszvadi wrote:B3/S23 (Game of Life): A unit cell of Rule-110 automaton was created, visit for more: http://pentadecathlon.com/lifenews/2005 ... _cell.html


The above unit cell works in B3/S238, too, and in the non-totalistic B3/S234c and B3/S236e rules.

So, EightLife is Turing-complete - proven since 2016.12.09

http://www.conwaylife.com/wiki/EightLife is B3/S238, so a pattern with 000001 Rule-110 initial configuration is here:

#C Unit cell for Wolfram's "Rule 110".
#C Place multiple copies of this pattern in a horizontal
#C row, overlapping the decorative still-lifes at the corners.
#C The state of the cell is determined by the presence (OFF)
#C or absence (ON) of a glider between the tubs at generation
#C 1200N. Note the negative logic. For generation 0, the
#C state of the cell is forced ON by the block in front of the
#C glider. Delete the block to set the state to OFF.
#C Jason Summers, 19 Dec '05
#C NASZVADI P.: this Unit cell also works in rules
#C between B3/S23 and B3/S234c6e8, so corollary:
#C B3/S238 is Turing-complete! (and the others are, too)
#C Unit cell rotated 90 degrees
x = 1535, y = 1536, rule = B3/S238:T0,1536
33b2o$34bo$34bobo6b2o$35b3o5bobo$37b3o6bo$37bo2bo2bo2bo7b2o$38b2o6bo7b
2o$43bobo$43b2o12$4b2o$4b2o11$2b2o3b2o$4b3o$3bo3bo$4bobo$5bo$16b3o$6b
3o7bo$6b3o8bo4$4b2o3b2o$5b5o14b2o$6b3o15bobo$7bo16bo6$31b3o62bo$31bo
62bobo$7b2o23bo53bo5b2o12b2o$7b2o76bobo4b2o12b2o$84bo3bo3b2o$84b5o5bob
o$83b2o3b2o6bo$39b2o43b5o$39bobo43b3o$39bo46bo14b2o$102bo$102bobo9bo$
103b2o9bobo$115bobo$115bo2bo3b2o$46b3o66bobo4b2o$46bo67bobo$47bo66bo$
85b2o$85b2o3$54b2o$54bobo$54bo6$61b3o$61bo$62bo4$61bo$61b3o5b2o$64bo4b
obo$63b2o4bo5$66bo8bo$65b3o7b2o$64b5o7b2o2b2o$63bobobobo10b2o$63b2o3b
2o5bobo$75bobo$76bo6b2o$68b2o14bo$68b2o14bobo6bo$70bo14b2o4bobo$55b2o
11b3o18b2o18b2o$55b2o9bo22b2o17bo3bo$66b5o12b2o4b2o16bo5bo3b2o$67b2o
13b2o7bobo4bo8bo3bob2o2b2o$84bo8bo3bo9bo5bo$97b3o2bo5bo3bo19b2o$65b2o
3b2o37b2o21bo$66b5o53bo5bobo$66b2ob2o52bobo4b2o$66b2ob2o20bo31b2obo$
55b3o9b3o20b2o19b2o10b2ob2o$54bo3bo31bobo18b2o10b2obo$53bo5bo45bo17bob
o$53bo5bo38b2b4bobo17bo$56bo41b2b5bo$54bo3bo34b2o$55b3o9b2o24b2o6b3o$
56bo10b2o32bo$102bo12bo$33b2o64bo13b3o$33b2o22b3o38bobo11bo$57b3o39bo
12b2o11b2o$56bo3bo64b2o$50bobo56b2o$50b2o3b2o3b2o28b2o17bobo49b2o$51bo
38b2o17bo51b2o2$133b2o$133b2o2$44bo$31b5o6b2o72b3o$30bob3obo6b2o71bo7b
3o15b2o$31bo3bo81bo5bo3bo15bo$32b3o23b2o31bo30bo5bo4b3o4b3o15b2obob2o$
33bo24b2o30b3o30bo3bo12bo$89b5o30b3o6bobo10b2o10bo5bo$88b2o3b2o28bo2bo
5b5o9b2o$89b5o29b3o5b2o3b2o21b2ob2o$31bo10b2o45b5o28bob2o5b2o3b2o23bo$
31bo11bo46bo2bo28bobo$30bobo10bobo7bo36bo3bo28bo$29b2ob2o2bobo5b2o4b4o
40bo7b2o29b2o$28bo5bo2bo11b4o38b2obo6b2o29b2ob2o8b3o15b2o$31bo17bo2bo
40bo9bo16b2o3b2o6bo2bo7b2ob2o14bo$28b2o3b2o14b4o67bobobobo6bo10b2ob2o
15b3o$50b4o7b2o58b5o10bo7b5o17bo$53bo7bobo26b2o3b2o25b3o9b2o7b2o3b2o$
32bo30bo26bo5bo26bo$32bo30b2o45bo$33bo57bo3bo13b2o18b2o3b2o$92b3o14bob
o18b5o5bo5bo$131b3o7b2o2bobo77b2o$30b2o100bo7b2o3bobo77b2o$30b2o114bo$
122b2o$122b2o101bo$117b2o105b3o$93b2o21b2o25bo79bo3bo$93b2o23bo10b2o
10b2ob2o79bo$130bo91bo5bo$127b3o10bo5bo75bo5bo$127bo95bo3bo$140b2obob
2o77b3o$125bo$124b2o$124bobo2$223bo3$223bo$132b2o9b2o78bobo$131b2o10b
2o78b2o$133bo2$145b2o65b2o$145bo2bo63b2o10b2o3b2o$135bo3b3o7bo6b2o58bo
$134b5o3bo6bo6b2o57bo9bo3bo$133b2ob2o3bo7bo65b3o8b3o$122b2o8b3ob2o3bo
3bo2bo77b3o$122b2o9b2ob4o5b2o$134b4o$135bo93b2o$229bo$146b2o60bo21b3o$
146b2o60bobo21bo$208b2o27bo$235b3o$234bo$234b2o2$147bo53bo$146b3o51bo$
146b3o51b3o2$144b2o3b2o80b3o$144b2o3b2o79bo3bo$156bo56b2o$156b2o55bo
15bo5bo$147bo3b2o4b2o43b2o7bobo15b2o3b2o$146bobo2b2o4b3o7b2o33bobo6b2o
$146bobo2b2o4b2o8b2o23bo4b2o6bo$147bo8b2o33bobo2bo2bo2bo2bo26bo$156bo
34b2obob3o6bo25bobo$179b2o10b2ob2o6bobo26bobo$179b2o10b2obo7b2o29bo$
191bobo39bo$192bo37bo2bo$231b2o3$68bo2bob2obo2bo$68b4ob2ob4o119bobo$
68bo2bob2obo2bo119bo2bo$92bo4bo92b2o10b2o$90b2ob4ob2o90b2o8bo3b2o$92bo
4bo97b2o5b2o$194bo4bo2bo$199bobo5$128b2o76bo$128bobo74b3o$123b2o6bo7b
2o63b5o$122bo2bo2bo2bo7b2o62bobobobo$122b3o6bo71b2o3b2o$120b3o5bobo$
119bobo6b2o$119bo86bo$118b2o85bobo$205bobo$206bo$206b2o$206b2o$206b2o
11$o$33b2o$34bo$34bobo6b2o$35b3o5bobo$37b3o6bo$37bo2bo2bo2bo7b2o$38b2o6bo7b
2o$43bobo$43b2o12$4b2o$4b2o11$2b2o3b2o$4b3o$3bo3bo$4bobo$5bo$16b3o$6b
3o7bo$6b3o8bo4$4b2o3b2o$5b5o14b2o$6b3o15bobo$7bo16bo6$31b3o62bo$31bo
62bobo$7b2o23bo53bo5b2o12b2o$7b2o76bobo4b2o12b2o$84bo3bo3b2o$84b5o5bob
o$83b2o3b2o6bo$39b2o43b5o$39bobo43b3o$39bo46bo14b2o$102bo$102bobo9bo$
103b2o9bobo$115bobo$115bo2bo3b2o$46b3o66bobo4b2o$46bo67bobo$47bo66bo$
85b2o$85b2o3$54b2o$54bobo$54bo6$61b3o$61bo$62bo4$61bo$61b3o5b2o$64bo4b
obo$63b2o4bo5$66bo8bo$65b3o7b2o$64b5o7b2o2b2o$63bobobobo10b2o$63b2o3b
2o5bobo$75bobo$76bo6b2o$68b2o14bo$68b2o14bobo6bo$70bo14b2o4bobo$55b2o
11b3o18b2o18b2o$55b2o9bo22b2o17bo3bo$66b5o12b2o4b2o16bo5bo3b2o$67b2o
13b2o7bobo4bo8bo3bob2o2b2o$84bo8bo3bo9bo5bo$97b3o2bo5bo3bo19b2o$65b2o
3b2o37b2o21bo$66b5o53bo5bobo$66b2ob2o52bobo4b2o$66b2ob2o20bo31b2obo$
55b3o9b3o20b2o19b2o10b2ob2o$54bo3bo31bobo18b2o10b2obo$53bo5bo45bo17bob
o$53bo5bo38b2b4bobo17bo$56bo41b2b5bo$54bo3bo34b2o$55b3o9b2o24b2o6b3o$
56bo10b2o32bo$102bo12bo$33b2o64bo13b3o$33b2o22b3o38bobo11bo$57b3o39bo
12b2o11b2o$56bo3bo64b2o$50bobo56b2o$50b2o3b2o3b2o28b2o17bobo49b2o$51bo
38b2o17bo51b2o2$133b2o$133b2o2$44bo$31b5o6b2o72b3o$30bob3obo6b2o71bo7b
3o15b2o$31bo3bo81bo5bo3bo15bo$32b3o23b2o31bo30bo5bo4b3o4b3o15b2obob2o$
33bo24b2o30b3o30bo3bo12bo$89b5o30b3o6bobo10b2o10bo5bo$88b2o3b2o28bo2bo
5b5o9b2o$89b5o29b3o5b2o3b2o21b2ob2o$31bo10b2o45b5o28bob2o5b2o3b2o23bo$
31bo11bo46bo2bo28bobo$30bobo10bobo7bo36bo3bo28bo$29b2ob2o2bobo5b2o4b4o
40bo7b2o29b2o$28bo5bo2bo11b4o38b2obo6b2o29b2ob2o8b3o15b2o$31bo17bo2bo
40bo9bo16b2o3b2o6bo2bo7b2ob2o14bo$28b2o3b2o14b4o67bobobobo6bo10b2ob2o
15b3o$50b4o7b2o58b5o10bo7b5o17bo$53bo7bobo26b2o3b2o25b3o9b2o7b2o3b2o$
32bo30bo26bo5bo26bo$32bo30b2o45bo$33bo57bo3bo13b2o18b2o3b2o$92b3o14bob
o18b5o5bo5bo$131b3o7b2o2bobo77b2o$30b2o100bo7b2o3bobo77b2o$30b2o114bo$
122b2o$122b2o101bo$117b2o105b3o$93b2o21b2o25bo79bo3bo$93b2o23bo10b2o
10b2ob2o79bo$130bo91bo5bo$127b3o10bo5bo75bo5bo$127bo95bo3bo$140b2obob
2o77b3o$125bo$124b2o$124bobo2$223bo3$223bo$132b2o9b2o78bobo$131b2o10b
2o78b2o$133bo2$145b2o65b2o$145bo2bo63b2o10b2o3b2o$135bo3b3o7bo6b2o58bo
$134b5o3bo6bo6b2o57bo9bo3bo$133b2ob2o3bo7bo65b3o8b3o$122b2o8b3ob2o3bo
3bo2bo77b3o$122b2o9b2ob4o5b2o$134b4o$135bo93b2o$229bo$146b2o60bo21b3o$
146b2o60bobo21bo$208b2o27bo$235b3o$234bo$234b2o2$147bo53bo$146b3o51bo$
146b3o51b3o2$144b2o3b2o80b3o$144b2o3b2o79bo3bo$156bo56b2o$156b2o55bo
15bo5bo$147bo3b2o4b2o43b2o7bobo15b2o3b2o$146bobo2b2o4b3o7b2o33bobo6b2o
$146bobo2b2o4b2o8b2o23bo4b2o6bo$147bo8b2o33bobo2bo2bo2bo2bo26bo$156bo
34b2obob3o6bo25bobo$179b2o10b2ob2o6bobo26bobo$179b2o10b2obo7b2o29bo$
191bobo39bo$192bo37bo2bo$231b2o3$68bo2bob2obo2bo$68b4ob2ob4o119bobo$
68bo2bob2obo2bo119bo2bo$92bo4bo92b2o10b2o$90b2ob4ob2o90b2o8bo3b2o$92bo
4bo97b2o5b2o$194bo4bo2bo$199bobo5$128b2o76bo$128bobo74b3o$123b2o6bo7b
2o63b5o$122bo2bo2bo2bo7b2o62bobobobo$122b3o6bo71b2o3b2o$120b3o5bobo$
119bobo6b2o$119bo86bo$118b2o85bobo$205bobo$206bo$206b2o$206b2o$206b2o
11$o$33b2o$34bo$34bobo6b2o$35b3o5bobo$37b3o6bo$37bo2bo2bo2bo7b2o$38b2o6bo7b
2o$43bobo$43b2o12$4b2o$4b2o11$2b2o3b2o$4b3o$3bo3bo$4bobo$5bo$16b3o$6b
3o7bo$6b3o8bo4$4b2o3b2o$5b5o14b2o$6b3o15bobo$7bo16bo6$31b3o62bo$31bo
62bobo$7b2o23bo53bo5b2o12b2o$7b2o76bobo4b2o12b2o$84bo3bo3b2o$84b5o5bob
o$83b2o3b2o6bo$39b2o43b5o$39bobo43b3o$39bo46bo14b2o$102bo$102bobo9bo$
103b2o9bobo$115bobo$115bo2bo3b2o$46b3o66bobo4b2o$46bo67bobo$47bo66bo$
85b2o$85b2o3$54b2o$54bobo$54bo6$61b3o$61bo$62bo4$61bo$61b3o5b2o$64bo4b
obo$63b2o4bo5$66bo8bo$65b3o7b2o$64b5o7b2o2b2o$63bobobobo10b2o$63b2o3b
2o5bobo$75bobo$76bo6b2o$68b2o14bo$68b2o14bobo6bo$70bo14b2o4bobo$55b2o
11b3o18b2o18b2o$55b2o9bo22b2o17bo3bo$66b5o12b2o4b2o16bo5bo3b2o$67b2o
13b2o7bobo4bo8bo3bob2o2b2o$84bo8bo3bo9bo5bo$97b3o2bo5bo3bo19b2o$65b2o
3b2o37b2o21bo$66b5o53bo5bobo$66b2ob2o52bobo4b2o$66b2ob2o20bo31b2obo$
55b3o9b3o20b2o19b2o10b2ob2o$54bo3bo31bobo18b2o10b2obo$53bo5bo45bo17bob
o$53bo5bo38b2b4bobo17bo$56bo41b2b5bo$54bo3bo34b2o$55b3o9b2o24b2o6b3o$
56bo10b2o32bo$102bo12bo$33b2o64bo13b3o$33b2o22b3o38bobo11bo$57b3o39bo
12b2o11b2o$56bo3bo64b2o$50bobo56b2o$50b2o3b2o3b2o28b2o17bobo49b2o$51bo
38b2o17bo51b2o2$133b2o$133b2o2$44bo$31b5o6b2o72b3o$30bob3obo6b2o71bo7b
3o15b2o$31bo3bo81bo5bo3bo15bo$32b3o23b2o31bo30bo5bo4b3o4b3o15b2obob2o$
33bo24b2o30b3o30bo3bo12bo$89b5o30b3o6bobo10b2o10bo5bo$88b2o3b2o28bo2bo
5b5o9b2o$89b5o29b3o5b2o3b2o21b2ob2o$31bo10b2o45b5o28bob2o5b2o3b2o23bo$
31bo11bo46bo2bo28bobo$30bobo10bobo7bo36bo3bo28bo$29b2ob2o2bobo5b2o4b4o
40bo7b2o29b2o$28bo5bo2bo11b4o38b2obo6b2o29b2ob2o8b3o15b2o$31bo17bo2bo
40bo9bo16b2o3b2o6bo2bo7b2ob2o14bo$28b2o3b2o14b4o67bobobobo6bo10b2ob2o
15b3o$50b4o7b2o58b5o10bo7b5o17bo$53bo7bobo26b2o3b2o25b3o9b2o7b2o3b2o$
32bo30bo26bo5bo26bo$32bo30b2o45bo$33bo57bo3bo13b2o18b2o3b2o$92b3o14bob
o18b5o5bo5bo$131b3o7b2o2bobo77b2o$30b2o100bo7b2o3bobo77b2o$30b2o114bo$
122b2o$122b2o101bo$117b2o105b3o$93b2o21b2o25bo79bo3bo$93b2o23bo10b2o
10b2ob2o79bo$130bo91bo5bo$127b3o10bo5bo75bo5bo$127bo95bo3bo$140b2obob
2o77b3o$125bo$124b2o$124bobo2$223bo3$223bo$132b2o9b2o78bobo$131b2o10b
2o78b2o$133bo2$145b2o65b2o$145bo2bo63b2o10b2o3b2o$135bo3b3o7bo6b2o58bo
$134b5o3bo6bo6b2o57bo9bo3bo$133b2ob2o3bo7bo65b3o8b3o$122b2o8b3ob2o3bo
3bo2bo77b3o$122b2o9b2ob4o5b2o$134b4o$135bo93b2o$229bo$146b2o60bo21b3o$
146b2o60bobo21bo$208b2o27bo$235b3o$234bo$234b2o2$147bo53bo$146b3o51bo$
146b3o51b3o2$144b2o3b2o80b3o$144b2o3b2o79bo3bo$156bo56b2o$156b2o55bo
15bo5bo$147bo3b2o4b2o43b2o7bobo15b2o3b2o$146bobo2b2o4b3o7b2o33bobo6b2o
$146bobo2b2o4b2o8b2o23bo4b2o6bo$147bo8b2o33bobo2bo2bo2bo2bo26bo$156bo
34b2obob3o6bo25bobo$179b2o10b2ob2o6bobo26bobo$179b2o10b2obo7b2o29bo$
191bobo39bo$192bo37bo2bo$231b2o3$68bo2bob2obo2bo$68b4ob2ob4o119bobo$
68bo2bob2obo2bo119bo2bo$92bo4bo92b2o10b2o$90b2ob4ob2o90b2o8bo3b2o$92bo
4bo97b2o5b2o$194bo4bo2bo$199bobo5$128b2o76bo$128bobo74b3o$123b2o6bo7b
2o63b5o$122bo2bo2bo2bo7b2o62bobobobo$122b3o6bo71b2o3b2o$120b3o5bobo$
119bobo6b2o$119bo86bo$118b2o85bobo$205bobo$206bo$206b2o$206b2o$206b2o
11$o$33b2o$34bo$34bobo6b2o$35b3o5bobo$37b3o6bo$37bo2bo2bo2bo7b2o$38b2o6bo7b
2o$43bobo$43b2o12$4b2o$4b2o11$2b2o3b2o$4b3o$3bo3bo$4bobo$5bo$16b3o$6b
3o7bo$6b3o8bo4$4b2o3b2o$5b5o14b2o$6b3o15bobo$7bo16bo6$31b3o62bo$31bo
62bobo$7b2o23bo53bo5b2o12b2o$7b2o76bobo4b2o12b2o$84bo3bo3b2o$84b5o5bob
o$83b2o3b2o6bo$39b2o43b5o$39bobo43b3o$39bo46bo14b2o$102bo$102bobo9bo$
103b2o9bobo$115bobo$115bo2bo3b2o$46b3o66bobo4b2o$46bo67bobo$47bo66bo$
85b2o$85b2o3$54b2o$54bobo$54bo6$61b3o$61bo$62bo4$61bo$61b3o5b2o$64bo4b
obo$63b2o4bo5$66bo8bo$65b3o7b2o$64b5o7b2o2b2o$63bobobobo10b2o$63b2o3b
2o5bobo$75bobo$76bo6b2o$68b2o14bo$68b2o14bobo6bo$70bo14b2o4bobo$55b2o
11b3o18b2o18b2o$55b2o9bo22b2o17bo3bo$66b5o12b2o4b2o16bo5bo3b2o$67b2o
13b2o7bobo4bo8bo3bob2o2b2o$84bo8bo3bo9bo5bo$97b3o2bo5bo3bo19b2o$65b2o
3b2o37b2o21bo$66b5o53bo5bobo$66b2ob2o52bobo4b2o$66b2ob2o20bo31b2obo$
55b3o9b3o20b2o19b2o10b2ob2o$54bo3bo31bobo18b2o10b2obo$53bo5bo45bo17bob
o$53bo5bo38b2b4bobo17bo$56bo41b2b5bo$54bo3bo34b2o$55b3o9b2o24b2o6b3o$
56bo10b2o32bo$102bo12bo$33b2o64bo13b3o$33b2o22b3o38bobo11bo$57b3o39bo
12b2o11b2o$56bo3bo64b2o$50bobo56b2o$50b2o3b2o3b2o28b2o17bobo49b2o$51bo
38b2o17bo51b2o2$133b2o$133b2o2$44bo$31b5o6b2o72b3o$30bob3obo6b2o71bo7b
3o15b2o$31bo3bo81bo5bo3bo15bo$32b3o23b2o31bo30bo5bo4b3o4b3o15b2obob2o$
33bo24b2o30b3o30bo3bo12bo$89b5o30b3o6bobo10b2o10bo5bo$88b2o3b2o28bo2bo
5b5o9b2o$89b5o29b3o5b2o3b2o21b2ob2o$31bo10b2o45b5o28bob2o5b2o3b2o23bo$
31bo11bo46bo2bo28bobo$30bobo10bobo7bo36bo3bo28bo$29b2ob2o2bobo5b2o4b4o
40bo7b2o29b2o$28bo5bo2bo11b4o38b2obo6b2o29b2ob2o8b3o15b2o$31bo17bo2bo
40bo9bo16b2o3b2o6bo2bo7b2ob2o14bo$28b2o3b2o14b4o67bobobobo6bo10b2ob2o
15b3o$50b4o7b2o58b5o10bo7b5o17bo$53bo7bobo26b2o3b2o25b3o9b2o7b2o3b2o$
32bo30bo26bo5bo26bo$32bo30b2o45bo$33bo57bo3bo13b2o18b2o3b2o$92b3o14bob
o18b5o5bo5bo$131b3o7b2o2bobo77b2o$30b2o100bo7b2o3bobo77b2o$30b2o114bo$
122b2o$122b2o101bo$117b2o105b3o$93b2o21b2o25bo79bo3bo$93b2o23bo10b2o
10b2ob2o79bo$130bo91bo5bo$127b3o10bo5bo75bo5bo$127bo95bo3bo$140b2obob
2o77b3o$125bo$124b2o$124bobo2$223bo3$223bo$132b2o9b2o78bobo$131b2o10b
2o78b2o$133bo2$145b2o65b2o$145bo2bo63b2o10b2o3b2o$135bo3b3o7bo6b2o58bo
$134b5o3bo6bo6b2o57bo9bo3bo$133b2ob2o3bo7bo65b3o8b3o$122b2o8b3ob2o3bo
3bo2bo77b3o$122b2o9b2ob4o5b2o$134b4o$135bo93b2o$229bo$146b2o60bo21b3o$
146b2o60bobo21bo$208b2o27bo$235b3o$234bo$234b2o2$147bo53bo$146b3o51bo$
146b3o51b3o2$144b2o3b2o80b3o$144b2o3b2o79bo3bo$156bo56b2o$156b2o55bo
15bo5bo$147bo3b2o4b2o43b2o7bobo15b2o3b2o$146bobo2b2o4b3o7b2o33bobo6b2o
$146bobo2b2o4b2o8b2o23bo4b2o6bo$147bo8b2o33bobo2bo2bo2bo2bo26bo$156bo
34b2obob3o6bo25bobo$179b2o10b2ob2o6bobo26bobo$179b2o10b2obo7b2o29bo$
191bobo39bo$192bo37bo2bo$231b2o3$68bo2bob2obo2bo$68b4ob2ob4o119bobo$
68bo2bob2obo2bo119bo2bo$92bo4bo92b2o10b2o$90b2ob4ob2o90b2o8bo3b2o$92bo
4bo97b2o5b2o$194bo4bo2bo$199bobo5$128b2o76bo$128bobo74b3o$123b2o6bo7b
2o63b5o$122bo2bo2bo2bo7b2o62bobobobo$122b3o6bo71b2o3b2o$120b3o5bobo$
119bobo6b2o$119bo86bo$118b2o85bobo$205bobo$206bo$206b2o$206b2o$206b2o
11$o$33b2o$34bo$34bobo6b2o$35b3o5bobo$37b3o6bo$37bo2bo2bo2bo7b2o$38b2o6bo7b
2o$43bobo$43b2o12$4b2o$4b2o11$2b2o3b2o$4b3o$3bo3bo$4bobo$5bo$16b3o$6b
3o7bo$6b3o8bo4$4b2o3b2o$5b5o14b2o$6b3o15bobo$7bo16bo6$31b3o62bo$31bo
62bobo$7b2o23bo53bo5b2o12b2o$7b2o76bobo4b2o12b2o$84bo3bo3b2o$84b5o5bob
o$83b2o3b2o6bo$39b2o43b5o$39bobo43b3o$39bo46bo14b2o$102bo$102bobo9bo$
103b2o9bobo$115bobo$115bo2bo3b2o$46b3o66bobo4b2o$46bo67bobo$47bo66bo$
85b2o$85b2o3$54b2o$54bobo$54bo6$61b3o$61bo$62bo4$61bo$61b3o5b2o$64bo4b
obo$63b2o4bo5$66bo8bo$65b3o7b2o$64b5o7b2o2b2o$63bobobobo10b2o$63b2o3b
2o5bobo$75bobo$76bo6b2o$68b2o14bo$68b2o14bobo6bo$70bo14b2o4bobo$55b2o
11b3o18b2o18b2o$55b2o9bo22b2o17bo3bo$66b5o12b2o4b2o16bo5bo3b2o$67b2o
13b2o7bobo4bo8bo3bob2o2b2o$84bo8bo3bo9bo5bo$97b3o2bo5bo3bo19b2o$65b2o
3b2o37b2o21bo$66b5o53bo5bobo$66b2ob2o52bobo4b2o$66b2ob2o20bo31b2obo$
55b3o9b3o20b2o19b2o10b2ob2o$54bo3bo31bobo18b2o10b2obo$53bo5bo45bo17bob
o$53bo5bo38b2b4bobo17bo$56bo41b2b5bo$54bo3bo34b2o$55b3o9b2o24b2o6b3o$
56bo10b2o32bo$102bo12bo$33b2o64bo13b3o$33b2o22b3o38bobo11bo$57b3o39bo
12b2o11b2o$56bo3bo64b2o$50bobo56b2o$50b2o3b2o3b2o28b2o17bobo49b2o$51bo
38b2o17bo51b2o2$133b2o$133b2o2$44bo$31b5o6b2o72b3o$30bob3obo6b2o71bo7b
3o15b2o$31bo3bo81bo5bo3bo15bo$32b3o23b2o31bo30bo5bo4b3o4b3o15b2obob2o$
33bo24b2o30b3o30bo3bo12bo$89b5o30b3o6bobo10b2o10bo5bo$88b2o3b2o28bo2bo
5b5o9b2o$89b5o29b3o5b2o3b2o21b2ob2o$31bo10b2o45b5o28bob2o5b2o3b2o23bo$
31bo11bo46bo2bo28bobo$30bobo10bobo7bo36bo3bo28bo$29b2ob2o2bobo5b2o4b4o
40bo7b2o29b2o$28bo5bo2bo11b4o38b2obo6b2o29b2ob2o8b3o15b2o$31bo17bo2bo
40bo9bo16b2o3b2o6bo2bo7b2ob2o14bo$28b2o3b2o14b4o67bobobobo6bo10b2ob2o
15b3o$50b4o7b2o58b5o10bo7b5o17bo$53bo7bobo26b2o3b2o25b3o9b2o7b2o3b2o$
32bo30bo26bo5bo26bo$32bo30b2o45bo$33bo57bo3bo13b2o18b2o3b2o$92b3o14bob
o18b5o5bo5bo$131b3o7b2o2bobo77b2o$30b2o100bo7b2o3bobo77b2o$30b2o114bo$
122b2o$122b2o101bo$117b2o105b3o$93b2o21b2o25bo79bo3bo$93b2o23bo10b2o
10b2ob2o79bo$130bo91bo5bo$127b3o10bo5bo75bo5bo$127bo95bo3bo$140b2obob
2o77b3o$125bo$124b2o$124bobo2$223bo3$223bo$132b2o9b2o78bobo$131b2o10b
2o78b2o$133bo2$145b2o65b2o$145bo2bo63b2o10b2o3b2o$135bo3b3o7bo6b2o58bo
$134b5o3bo6bo6b2o57bo9bo3bo$133b2ob2o3bo7bo65b3o8b3o$122b2o8b3ob2o3bo
3bo2bo77b3o$122b2o9b2ob4o5b2o$134b4o$135bo93b2o$229bo$146b2o60bo21b3o$
146b2o60bobo21bo$208b2o27bo$235b3o$234bo$234b2o2$147bo53bo$146b3o51bo$
146b3o51b3o2$144b2o3b2o80b3o$144b2o3b2o79bo3bo$156bo56b2o$156b2o55bo
15bo5bo$147bo3b2o4b2o43b2o7bobo15b2o3b2o$146bobo2b2o4b3o7b2o33bobo6b2o
$146bobo2b2o4b2o8b2o23bo4b2o6bo$147bo8b2o33bobo2bo2bo2bo2bo26bo$156bo
34b2obob3o6bo25bobo$179b2o10b2ob2o6bobo26bobo$179b2o10b2obo7b2o29bo$
191bobo39bo$192bo37bo2bo$231b2o3$68bo2bob2obo2bo$68b4ob2ob4o119bobo$
68bo2bob2obo2bo119bo2bo$92bo4bo92b2o10b2o$90b2ob4ob2o90b2o8bo3b2o$92bo
4bo97b2o5b2o$194bo4bo2bo$199bobo5$128b2o76bo$128bobo74b3o$123b2o6bo7b
2o63b5o$122bo2bo2bo2bo7b2o62bobobobo$122b3o6bo71b2o3b2o$120b3o5bobo$
119bobo6b2o$119bo86bo$118b2o85bobo$205bobo$206bo$206b2o$206b2o$206b2o
11$o$33b2o$34bo$34bobo6b2o$35b3o5bobo$37b3o6bo$37bo2bo2bo2bo7b2o$38b2o6bo7b
2o$43bobo$43b2o12$4b2o$4b2o11$2b2o3b2o$4b3o$3bo3bo$4bobo$5bo$16b3o$6b
3o7bo$6b3o8bo4$4b2o3b2o$5b5o14b2o$6b3o15bobo$7bo16bo6$31b3o62bo$31bo
62bobo$7b2o23bo53bo5b2o12b2o$7b2o76bobo4b2o12b2o$84bo3bo3b2o$84b5o5bob
o$83b2o3b2o6bo$39b2o43b5o$39bobo43b3o$39bo46bo14b2o$102bo$102bobo9bo$
103b2o9bobo$115bobo$115bo2bo3b2o$46b3o66bobo4b2o$46bo67bobo$47bo66bo$
85b2o$85b2o3$54b2o$54bobo$54bo6$61b3o$61bo$62bo4$61bo$61b3o5b2o$64bo4b
obo$63b2o4bo5$66bo8bo$65b3o7b2o$64b5o7b2o2b2o$63bobobobo10b2o$63b2o3b
2o5bobo$75bobo$76bo6b2o$68b2o14bo$68b2o14bobo6bo$70bo14b2o4bobo$55b2o
11b3o18b2o18b2o$55b2o9bo22b2o17bo3bo$66b5o12b2o4b2o16bo5bo3b2o$67b2o
13b2o7bobo4bo8bo3bob2o2b2o$84bo8bo3bo9bo5bo$97b3o2bo5bo3bo19b2o$65b2o
3b2o37b2o21bo$66b5o53bo5bobo$66b2ob2o52bobo4b2o$66b2ob2o20bo31b2obo$
55b3o9b3o20b2o19b2o10b2ob2o$54bo3bo31bobo18b2o10b2obo$53bo5bo45bo17bob
o$53bo5bo38b2o4bobo17bo$56bo41b2o5bo$54bo3bo34b2o$55b3o9b2o24b2o6b3o$
56bo10b2o32bo$102bo12bo$33b2o64bo13b3o$33b2o22b3o38bobo11bo$57b3o39bo
12b2o11b2o$56bo3bo64b2o$50bobo56b2o$50b2o3b2o3b2o28b2o17bobo49b2o$51bo
38b2o17bo51b2o2$133b2o$133b2o2$44bo$31b5o6b2o72b3o$30bob3obo6b2o71bo7b
3o15b2o$31bo3bo81bo5bo3bo15bo$32b3o23b2o31bo30bo5bo4b3o4b3o15b2obob2o$
33bo24b2o30b3o30bo3bo12bo$89b5o30b3o6bobo10b2o10bo5bo$88b2o3b2o28bo2bo
5b5o9b2o$89b5o29b3o5b2o3b2o21b2ob2o$31bo10b2o45b5o28bob2o5b2o3b2o23bo$
31bo11bo46bo2bo28bobo$30bobo10bobo7bo36bo3bo28bo$29b2ob2o2bobo5b2o4b4o
40bo7b2o29b2o$28bo5bo2bo11b4o38b2obo6b2o29b2ob2o8b3o15b2o$31bo17bo2bo
40bo9bo16b2o3b2o6bo2bo7b2ob2o14bo$28b2o3b2o14b4o67bobobobo6bo10b2ob2o
15b3o$50b4o7b2o58b5o10bo7b5o17bo$53bo7bobo26b2o3b2o25b3o9b2o7b2o3b2o$
32bo30bo26bo5bo26bo$32bo30b2o45bo$33bo57bo3bo13b2o18b2o3b2o$92b3o14bob
o18b5o5bo5bo$131b3o7b2o2bobo77b2o$30b2o100bo7b2o3bobo77b2o$30b2o114bo$
122b2o$122b2o101bo$117b2o105b3o$93b2o21b2o25bo79bo3bo$93b2o23bo10b2o
10b2ob2o79bo$130bo91bo5bo$127b3o10bo5bo75bo5bo$127bo95bo3bo$140b2obob
2o77b3o$125bo$124b2o$124bobo2$223bo3$223bo$132b2o9b2o78bobo$131b2o10b
2o78b2o$133bo2$145b2o65b2o$145bo2bo63b2o10b2o3b2o$135bo3b3o7bo6b2o58bo
$134b5o3bo6bo6b2o57bo9bo3bo$133b2ob2o3bo7bo65b3o8b3o$122b2o8b3ob2o3bo
3bo2bo77b3o$122b2o9b2ob4o5b2o$134b4o$135bo93b2o$229bo$146b2o60bo21b3o$
146b2o60bobo21bo$208b2o27bo$235b3o$234bo$234b2o2$147bo53bo$146b3o51bo$
146b3o51b3o2$144b2o3b2o80b3o$144b2o3b2o79bo3bo$156bo56b2o$156b2o55bo
15bo5bo$147bo3b2o4b2o43b2o7bobo15b2o3b2o$146bobo2b2o4b3o7b2o33bobo6b2o
$146bobo2b2o4b2o8b2o23bo4b2o6bo$147bo8b2o33bobo2bo2bo2bo2bo26bo$156bo
34b2obob3o6bo25bobo$179b2o10b2ob2o6bobo26bobo$179b2o10b2obo7b2o29bo$
191bobo39bo$192bo37bo2bo$231b2o3$68bo2bob2obo2bo$68b4ob2ob4o119bobo$
68bo2bob2obo2bo119bo2bo$92bo4bo92b2o10b2o$90b2ob4ob2o90b2o8bo3b2o$92bo
4bo97b2o5b2o$194bo4bo2bo$199bobo5$128b2o76bo$128bobo74b3o$123b2o6bo7b
2o63b5o$122bo2bo2bo2bo7b2o62bobobobo$122b3o6bo71b2o3b2o$120b3o5bobo$
119bobo6b2o$119bo86bo$118b2o85bobo$205bobo$206bo$206b2o$206b2o$206b2o
11$!


The following configurations should occur in LWSS columns (tested until 6th):
  1. 000001
  2. 000011
  3. 000111
  4. 001101
  5. 011111
  6. 110001 - tested till this
  7. 010011
  8. 110111
  9. 011100
  10. 110100
  11. 111101
  12. 000111 - loop

The Unit Cell grid generator for Rule-110 what I made will be published here soon:
viewtopic.php?f=9&t=2604

EDITED 2016.12.10: cut an obsolete cell, so pattern can fit into its bounding box. (It works in golly in its original form)
Naszvadi
 
Posts: 150
Joined: May 7th, 2016, 8:53 am

Re: List of the Turing-complete totalistic life-like CA

Postby Naszvadi » December 10th, 2016, 7:01 am

All of the following rules support the above Rule-110 simulation, so they are all Turing-complete:
  • B3/S234c
  • B3/S236e
  • B3/S234c6e
  • B3/S234c8
  • B3/S236e8
  • B3/S234c6e8

Another idea: a script, that inspects a pattern between two given generations, and determines the minimal and maximal rulestrings that support it. I know there is a topic for such "wishlists", feel free to announce this idea - or warn me if there is already a script for the wanted purpose :)
Naszvadi
 
Posts: 150
Joined: May 7th, 2016, 8:53 am

Re: List of the Turing-complete totalistic life-like CA

Postby Naszvadi » December 12th, 2016, 2:29 pm

Naszvadi wrote:Another idea: a script, that inspects a pattern between two given generations, and determines the minimal and maximal rulestrings that support it. I know there is a topic for such "wishlists", feel free to announce this idea - or warn me if there is already a script for the wanted purpose :)


Done.

Now, bad news, good news.

First of all: http://repositorio.uam.es/bitstream/han ... sequence=2
in the above pdf published that also B38/S23 and B38/S238 is universal, with checking the inherited logic gate elements from GoL. So, B3/S238 had an existence proof until Jason Summers' unit cell hadn't been verified in it :roll:

Now let's prove that rules between B3/S23 and B3678/S23678 are all universal - if they have a glider gun with period n, where n is at least 30.

I made a tiny pattern collection here, scroll down for explanations:
#CXRLE Pos=-96,4 Gen=4
#CNASZVADI, Peter's small collection
#CSmall pattern collection for proving the Turing-completeness of
#Call the life-like cellular automata from B3/S23 to B3678/S23678
#COnly one type of glider gun is needed to complete the proof for
#Ceach rule, the gun's period must be at least 30
#CContents in rows:
#C1. right angle pairwise glider death collisions
#C... - this is necessary for glider phase synchronisation!
#C2. opposite pairwise glider death collisions 1
#C3. opposite pairwise glider death collisions 2
#C4. eater1 and two block removal by glider
#C5. turnback kickback reaction, beehive creator, block creator
#C6. gun period doubling mechanism, needs gun with period 30 or higher
#C... - this temporary block creation is needed for signal splitting
#C... - it is also handy for timing, delay, etc.
#C7. right angle turn, needs a constructed gun with period 40 or higher
#C8. AND gate, NOT gate (the negated signal usually needs a
#C... high period gun in a unit cell)
x = 98, y = 292, rule = B3678/S23678
o19bo19bobo$b2o18b2o18b2o$2o18b2o19bo4$7bo19bo20bo$8bo19bo17bobo$6b3o
17b3o18b2o2$8bo20b2o18b2o$8b2o20b2o16bobo$7bobo19bo20bo4$23b2o18bo$b3o
18bobo18b2o$3bo20bo17bobo$2bo5$2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob
2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2o$2ob2ob2ob
2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob
2ob2ob2ob2ob2ob2ob2o5$bobo16bo19bo19bobo17bobo$2b2o17b2o18b2o18b2o18b
2o$2bo17b2o18b2o19bo19bo4$9bo17bo19bo20bo19bo$7bobo18bo19bo17bobo17bob
o$8b2o16b3o17b3o18b2o18b2o2$6b2o61b2o18b2o$6bobo17b3o18b3o19bobo16b2o$
6bo19bo20bo21bo20bo$27bo20bo3$13bo62bo18b2o$12b2o19b2o19b2o19b2o18bobo
$12bobo17b2o19b2o20bobo17bo$34bo20bo5$2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2o
b2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2o$2ob
2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob
2ob2ob2ob2ob2ob2ob2ob2ob2o4$bo19bo$2bo19bo17bo19bo$3o17b3o18b2o18b2o$
40b2o18b2o4$6bobo17bobo18bo19bo$7b2o18b2o19bo19bo$7bo19bo18b3o17b3o$
29bo40bo$8b3o17b2o19b3o17b2o$8bo19bobo18bo19bobo$9bo40bo4$15b2o17b3o
19b2o17b3o$14b2o18bo20b2o18bo$16bo18bo21bo18bo6$2ob2ob2ob2ob2ob2ob2ob
2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob
2ob2ob2o$2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob
2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2o8$2bobo$3b2o$3bo$7bo19bo19bo$8bo
19bo19bo$6b3o17b3o17b3o$30b2o$9b2o19b2o17b2o$9bo39b2o$10b3o$12bo11$2ob
2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob
2ob2ob2ob2ob2ob2ob2ob2ob2o$2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob
2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2o6$b2o$b2o4$6bo
bo3b2o13bo29bo$7b2o2b2o15bo29bo$7bo5bo12b3o12bo14b3o$40bobo$29b3o8bobo
16b2o9b2o$31bo9bo16bobo9b2o$30bo29bo12$2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob
2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2o$
2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob
2ob2ob2ob2ob2ob2ob2ob2ob2ob2o4$o2$2bo$3bo$b3o6$10bo$8bobo$9b2o5$17bo$
18bo$16b3o2$19b2o$18bobo$20bo6$11b3o$13bo14b2o$12bo15bo$29b3o$31bo3$4b
2o$3bobo$5bo2$2bo5$2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob
2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2o$2ob2ob2ob2ob2ob2ob2ob
2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob
2ob2ob2o4$o2$2bo$3bo$b3o8$12bo$13bo$11b3o2$35b2o$35bo$33bobo$33b2o3$
22bo$23bo$21b3o2$24b2o$25b2o$24bo3$28b2o$27b2o$29bo3$14b2o$15b2o$14bo
3$38b2o$37b2o$39bo3$4b2o$5b2o$4bo2$2bo5$2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob
2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2o$
2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob2ob
2ob2ob2ob2ob2ob2ob2ob2ob2ob2o3$45b2o$o44b2o3bo2$2bo42b2o5bo$3bo41b2o6b
o$b3o47b3o$45b2o$45b2o2$45b2o$45b2o$10bo49bo$8bobo34b2o11bobo$9b2o34b
2o12b2o$28b2o$7b2o19b2o27b2o$6bobo36b2o9bobo$8bo36b2o11bo$17bo49bo$18b
o49bo$16b3o26b2o19b3o$45b2o2$45b2o$45b2o2$25bo19b2o28bo$23bobo19b2o26b
obo$24b2o48b2o$45b2o$11b3o13b2o16b2o30b2o$13bo13bo49bo$12bo15b3o14b2o
31b3o$30bo14b2o33bo!

Pattern contents in rows:
  1. right angle pairwise glider death collisions - this is necessary for glider phase synchronisation!
  2. opposite pairwise glider death collisions 1
  3. opposite pairwise glider death collisions 2
  4. eater1 and two block removal by glider
  5. turnback kickback reaction, beehive creator, block creator
  6. gun period doubling mechanism, needs gun with period 30 or higher
    • this temporary block creation is needed for signal splitting
    • it is also handy for timing, delay, etc.
  7. right angle turn, needs a constructed gun with period 40 or higher
  8. AND gate, NOT gate (the negated signal usually needs a high period gun in a unit cell)

The first block vanisher and the beehive creation is not used, they are just fit in the rule interval.

And for the proof it must be used for example, that Rule-110 cellular automaton is universal. So it can be embedded easily via implementing its ternary transition function (ternary = it has 3 arguments, all of them are boolean)

Some of the transition function's form of Rule-110 automaton:
NextState(Left, Middle, Right)

((NOT Left) AND Middle AND Right) OR (Middle XOR Right)

((NOT Left) AND Middle AND Right) XOR (Middle XOR Right)

(Middle OR Right) XOR (Left AND Middle AND Right)


There is no need for create a unit cell. An infinite 2-dimensional grid of synchronized logic gates is enough.

Now, feel free to post alien guns with PERIOD NOT SMALLER than 30, in order to cover some of the above rule interval, visit this for hint: http://conwaylife.com/w/index.php?title ... r_automata
Naszvadi
 
Posts: 150
Joined: May 7th, 2016, 8:53 am

Re: List of the Turing-complete totalistic life-like CA

Postby Naszvadi » December 12th, 2016, 3:18 pm

x = 37, y = 27, rule = B36/S23
2o$2o$14bo$13b3o$12b2ob2o$11b2ob2o$10b2ob2o$11b3o$12bo10$25b2o6b2o$24b
obo6b2o$26bo2$35bo$33bobo$34bobo$25b2o7bo$25b2o!


The above gun was stolen from: "HighLife - An Interesting Variant of Life (part 1/3)" by David I. Bell, 7 May 1994

Works in rules:
  • B36/S23
  • B368/S23
  • B36/S238
  • B368/S238

Its period is 96. Corollary: the above 4 rules - including HighLife - are universal.
Naszvadi
 
Posts: 150
Joined: May 7th, 2016, 8:53 am

Re: List of the Turing-complete totalistic life-like CA

Postby calcyman » December 12th, 2016, 5:13 pm

You have to be subtle about universality.

A cellular automaton such as Wireworld can perform arbitrary bounded computations, but cannot emulate a Turing machine from a finite initial configuration (i.e. any pattern has limited memory).

By comparison, a register machine in Life, or Paul Chapman's 'full UTM' (which has fleets of rakes to extend the tape infinitely in both directions) is universal as it can perform arbitrary computations on an unbounded memory store.

I believe you have only proved those other rules to be bounded-universal, rather than fully universal.
What do you do with ill crystallographers? Take them to the mono-clinic!
User avatar
calcyman
 
Posts: 1304
Joined: June 1st, 2009, 4:32 pm

Re: List of the Turing-complete totalistic life-like CA

Postby Naszvadi » December 12th, 2016, 6:19 pm

calcyman wrote:You have to be subtle about universality.

A cellular automaton such as Wireworld can perform arbitrary bounded computations, but cannot emulate a Turing machine from a finite initial configuration (i.e. any pattern has limited memory).

By comparison, a register machine in Life, or Paul Chapman's 'full UTM' (which has fleets of rakes to extend the tape infinitely in both directions) is universal as it can perform arbitrary computations on an unbounded memory store.

I believe you have only proved those other rules to be bounded-universal, rather than fully universal.


Well, according to the terminology you mentioned, Rule-110 is bounded-universal only, too. Because it needs a background tiling pattern.

If Rule-110 is fully universal (because I really might be wrong), then consider as an analogon a 2D (infinite) tiling of Rule-110 unit cells or just Rule-110 transition logic gates on a 2D ca, like in the list of my previous post.

Hmmm, see more: https://en.wikipedia.org/wiki/Rule_110# ... n_Rule_110
"The function of the universal machine in Rule 110 requires an infinite number of localized patterns to be embedded within an infinitely repeating background pattern."

GOTO10
Naszvadi wrote:B3/S23 (Game of Life): A unit cell of Rule-110 automaton was created, visit for more: http://pentadecathlon.com/lifenews/2005 ... _cell.html


RUN

*EDIT -- many guns appear in the publicly available alien guns list. Here you are:

#Cp62 and p98 glider guns
#CBy Jason Summers, 13 Aug 2000
x = 135, y = 38, rule = B378/S237
134bo$132b3o$131bo$131boo6$17boo$16bobo105bo$16bobbo103bobo$17b3o102b
ooboo$19bo106bo$125boo$$23bo$23b3o$23bobbo$24bobo$24boo3$boo$obbo$oo$b
4o112boo$3bo16bo95boo$21bo95bobo$8bo10b3o96boo$7b4o$10boo$8bobbo103bo$
9boo104bo$107boo$106bobo$106bo$105boo!


And p50:
#Cp50 glider gun
#CJason Summers, Oct 2001
x = 22, y = 33, rule = B37/S237
12bo$10bo3bo$12bo$10bo3bo3$10bo3bo$9b3ob3o$9bo5bo$11b3o$11b3o10$6bo$6b
oo$3obo3bo$6boo12bo$6bo14bo$12bo6b3o$10booboo$10booboo$11b3o4$11b3o!


And a p60:
#Cp60 glider gun (B37/S23)
x = 66, y = 60, rule = B37/S23
29bo5bo$29boo3boo$29boo3boo$22boo6bo3bo$23bo$23bobo5b3o$24boo4bo3bo9bo
$30bo3bo7bobbo$30bo3bo7bobbo$31b3o9bo$$10boo3boo14b3o9bo$9bo7bo12bo3bo
7bobbo$12bobo15bo3bo7bobbo$10boo3boo13bo3bo9bo$31b3o$41boo$10bo7boo20b
obbo$3o7bo8boo18bobobo$b3o6bo7bo19b3obo$7bo5bo24b3o$7bobobobo$7bo5bo
40bo$b3o29bo18b3o$3o7bo20bobo17bo$16bo15boo17boo$13bo3bobo$3boo6b3obb
oobbo38bobo$bbobbo7boobo3bo28bo8bo$bbobobo12bo27b3o9bobbo$3bobbo9b3o
27bo12bobobo$7bo8bo28bo3boboo7bobbo$4bobo38bobboobb3o6boo$46bobo3bo$
13boo17boo15bo$14bo17bobo20bo7b3o$11b3o18bo29b3o$11bo40bo5bo$52bobobob
o$25b3o24bo5bo$23bob3o19bo7bo6b3o$22bobobo18boo8bo7b3o$22bobbo20boo7bo
$23boo$32b3o$21bo9bo3bo13boo3boo$20bobbo7bo3bo15bobo$20bobbo7bo3bo12bo
7bo$22bo9b3o14boo3boo$$22bo9b3o$20bobbo7bo3bo$20bobbo7bo3bo$21bo9bo3bo
$32b3o$$31bo3bo$30boo3boo8bo$30boo3boo9bo$30bo5bo7b3o!


Two p30:
#CB3/S2378 p30 glider gun
#CDavid Eppstein 10 Feb 01
x = 43, y = 25, rule = B3/S2378
7boo$8bo$8bobo$9boo8bo$15bo3bobboo$14bobobo5bo$19bobobboo$19bo3boo16b
oo$21b3o17bo$39bobo$25boo6boo4boo$oo23bo6bobbo$bo30bobboo$bobo27bobboo
$bboo4boo6boo6bo6b4o$7bobbo4b3o7bo$7bobbo12b3o$7booboo$9boo7bobo$18b3o
3$32bo$30bobo$31boo!


...and:

#CB3/S237 p30 glider gun
#CDavid Eppstein 10 Feb 01
x = 43, y = 25, rule = B3/S237
7boo$8bo$8bobo$9boo8bo$15bo3bobboo$14bobobo5bo$19bobobboo$19bo3boo16b
oo$21b3o17bo$39bobo$25boo6boo4boo$oo23bo6bobbo$bo30bobboo$bobo27bobboo
$bboo4boo6boo6bo6b4o$7bobbo4b3o7bo$7bobbo12b3o$7booboo$9boo4$32bo$30bo
bo$31boo!


so, included in the Turing-complete list:
  • B37/S23
  • B37/S237
  • B37/S238
  • B378/S237
  • B378/S2378
  • B3/S2378
  • B38/S2378
  • B3/S237
  • B38/S237
Naszvadi
 
Posts: 150
Joined: May 7th, 2016, 8:53 am

Re: List of the Turing-complete totalistic life-like CA

Postby Naszvadi » December 14th, 2016, 7:33 am

There was given a p24 glider gun in B36/S23, by Dean Hickerson, 1994.
This gun works in B36/S23[78] too.
But if the rule has S7, it was a hell to find a capable collision of three p24 series of gliders that produces a period higher than 24.

So constructed by me, a p96 gun, this is more than period 30, enough to give evidence about another two rules' TC property. Sorry if I invented wheel:

x = 130, y = 112, rule = B36/S237
7$34bo56bo$32b3o54b3o$31bo56bo$31b2o55b2o4$28b3o54b3o$28bobo54bobo$27b
o3bo52bo3bo$28bobo54bobo$29bo56bo3$98b2o$48b2o47b4o$13b2o33bo37bo9b2o
3bo$14bo31bobo35b2o11b4o$14bobo29b2o37b2o11b2o4b2o$15b2o23b2o62bobo$
21b3o5bo5bobobobo64bo$20b2obo7bo8b2o64b2o$21b3o5b3o48bo$78b2o$79b2o2$
36bo50bo$37bo48b3o$35b3o36bo11bobo$72b2o13bo$73b2o2$42bo$43bo45b2o$41b
3o24bo20bo$66b2o22b3o$67b2o23bo2$48bo$49bo$47b3o4$54bo$55bo$53b3o10$
43bo$43b2o$42bobo4$37bo$37b2o$36bobo4$23bo7bo46bo$21b2obo6b2o46bo$21bo
3bo4bobo8b2o34b3o$21b2obo15b2obo$16b2o5bo17b2o$15bobo29b2o$15bo31bobo$
14b2o33bo$49b2o4$30bo$29b3o$28b2ob2o$28b2ob2o$29bobo$30bo3$32b2o$32bo$
33b3o$35bo$102bo$103bo$101b3o!


So 2 rules are appended to Turing-complete list:
  • B36/S237
  • B36/S2378

I'd rather create a lifewiki entry - if allowed - about listing Turing-complete, bounded Turing-complete etc. rules, introducing both ancient and novel technics about embedding universal gates, unit cells, Turing machines, and referring to interesting patterns like prime/twin/fermat-prime search patterns etc.

Batlogo is shining on the night sky!

Misc: I created a bash script that creates a huge tile .lif pattern of 3 gliders' collisions. This helped me to find a fitting interaction and period increment for the gun. Visit here: http://www.conwaylife.com/forums/viewto ... f=9&t=2615
Naszvadi
 
Posts: 150
Joined: May 7th, 2016, 8:53 am

Re: List of the Turing-complete totalistic life-like CA

Postby Naszvadi » December 20th, 2016, 7:55 pm

Another glider gun is here:

viewtopic.php?f=11&t=575

Works in B3[8]/S236[8]. Unfortunately, its period is so low, only 26. And still looking up for a 30+period gun in these 4 rules.

My 3 glider stream collision tiler script I mentioned in the previous post works only with 4*n period streams, but as usual: no warranty, no liabl*.* no responsibility etc. :mrgreen:
Naszvadi
 
Posts: 150
Joined: May 7th, 2016, 8:53 am

Re: List of the Turing-complete totalistic life-like CA

Postby Naszvadi » December 21st, 2016, 7:49 am

Naszvadi wrote:Another glider gun is here:

viewtopic.php?f=11&t=575

Works in B3[8]/S236[8]. Unfortunately, its period is so low, only 26. And still looking up for a 30+period gun in these 4 rules.

My 3 glider stream collision tiler script I mentioned in the previous post works only with 4*n period streams, but as usual: no warranty, no liabl*.* no responsibility etc. :mrgreen:


Successfully doubled the period of the above gun using right angle kickback reaction, which remained working in all 4 rules. See pattern:

x = 72, y = 82, rule = B3/S236
11b2o20b2o$12bo20bo$12bobo16bobo$13b2o8bo2bo4b2o$23bo3bo$22bo4bo$23bo
3bo$23bo2bo$2o40b2o$bo40bo$bobo36bobo$2b2o24bo2bo8b2o$13b3o11bo3bo$11b
2ob2o11bo4bo$6bo6b3o5bo5bo3bo$5bo14b3o5bo2bo$6bo12b2ob2o$19b2ob2o$20bo
bo$21bo9bo$29bobo$30b2o4$37bo$38bo$23b2o11b3o$23bo$24b3o$9b2o15bo$10bo
$10bobo31bo$11b2o29bobo$14b2o27b2o$14bobo$14bo$26bo$24b2o$25b2o2$20b3o
$20bo$21bo2$57bo$55bobo$27b2o27b2o$27bobo$27bo$39bo$37b2o6bo$38b2o5b3o
$48bo$33b3o11b2o$33bo$34bo2$70bo$68bobo$40b2o27b2o$40bobo$40bo9bo$49bo
bo$48b2ob2o$48b2ob2o12bo$40bo2bo5b3o14bo$40bo3bo5bo5b3o6bo$39bo4bo11b
2ob2o$40bo3bo11b3o$30b2o8bo2bo24b2o$29bobo36bobo$29bo40bo$28b2o40b2o$
45bo2bo$44bo3bo$44bo4bo$44bo3bo$39b2o4bo2bo8b2o$38bobo16bobo$38bo20bo$
37b2o20b2o!


So 4 rules are appended to the Turing-complete list:
  • B3/S236
  • B3/S2368
  • B38/S236
  • B38/S2368
Naszvadi
 
Posts: 150
Joined: May 7th, 2016, 8:53 am

Re: List of the Turing-complete totalistic life-like CA

Postby Naszvadi » January 2nd, 2017, 10:53 am

B37/S236 p30 gun is here, thanks to Sokwe:
viewtopic.php?f=11&t=1071#p7732

So B37/S236 is added to universal rules list in the OP.
Naszvadi
 
Posts: 150
Joined: May 7th, 2016, 8:53 am

Re: List of the Turing-complete totalistic life-like CA

Postby Naszvadi » January 3rd, 2017, 10:58 am

There are additional guns for rules here viewtopic.php?f=11&t=1071 :
  • P44 for B378/S238
  • P44 for B3/S2367 - B38/S23678
Totally 5 new universal rules.
Naszvadi
 
Posts: 150
Joined: May 7th, 2016, 8:53 am

Re: List of the Turing-complete totalistic life-like CA

Postby Naszvadi » January 7th, 2017, 2:33 pm

Now, read carefully:

In B3/S23-B3678/S023678, the following advanced eaters work: Eater_5

Note that 0 survival is added to the supported rules, and these patterns can swallow gliders from two angles - in the other hand, need more recovery time.
Naszvadi
 
Posts: 150
Joined: May 7th, 2016, 8:53 am

Re: List of the Turing-complete totalistic life-like CA

Postby Naszvadi » September 6th, 2017, 3:38 pm

Breaking silence:

A p120 gun were constructed in B36/S23[8], based on p24 glider stream removal with fitting replicators.
See here: ../forums/viewtopic.php?f=11&t=2332&p=50630#p50630

So from now, rule list that support p120-compatible technologies are extended. Of course it was known about Highlife before, but this is a relatively compact construction, so it is worth to use in later W110 rule emulators.
Naszvadi
 
Posts: 150
Joined: May 7th, 2016, 8:53 am

Re: List of the Turing-complete totalistic life-like CA

Postby Naszvadi » September 7th, 2017, 10:56 am

Naszvadi wrote:Breaking silence:

A p120 gun were constructed in B36/S23[8], based on p24 glider stream removal with fitting replicators.
See here: ../forums/viewtopic.php?f=11&t=2332&p=50630#p50630

So from now, rule list that support p120-compatible technologies are extended. Of course it was known about Highlife before, but this is a relatively compact construction, so it is worth to use in later W110 rule emulators.


Update here with one of the best p120 _versatile_ Highlife guns: ../forums/viewtopic.php?f=11&t=2332&p=50652#p50652

The following minimal margolus XOR automaton series had been generated with the corresponding width that fits for certain constraints when they are emulated via Highlife replicators:

(period : width : initial cells)
3 : 7 : 0011101
5 : 8 : 00110010
31 : 15 : 000000111010000
31 : 16 : 0000001100100000
3 : 22 : 0011101010111000011101
15 : 25 : 0000011110011101101101010
5 : 25 : 0000111110010101101100010
5 : 25 : 0011001000100110000110010
Naszvadi
 
Posts: 150
Joined: May 7th, 2016, 8:53 am


Return to Other Cellular Automata

Who is online

Users browsing this forum: No registered users and 2 guests