List of the Turing-complete totalistic life-like CA

For discussion of other cellular automata.
Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

List of the Turing-complete totalistic life-like CA

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

...or with embedding a Wolfram 110 automata, showing at least that the automata is capable to perform all finite computations - the purpose is: mostly all logic element implementations usually lack precisity, e.g. correct timing, discussing correctly the connectivity of elements etc.

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 list of rules that supports Glider and cirtuitry that trivially allows construction of W110 Unit Cell:
  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/S23 (2020.09.21.)
  20. B378/S237
  21. B378/S2378
  22. B378/S238
  23. B38/S23
  24. B38/S236
  25. B38/S2367
  26. B38/S23678
  27. B38/S2368
  28. B38/S237
  29. B38/S2378
  30. B38/S238
Other life-like rules inspected by David Eppstein, Dean Hickerson et al having at least one constructed W110 (or CGoL) Unit Cell:
  1. B35/S236
  2. B368/S12578 (2020.07.11.)
  3. B3678/S34678 a.k.a. Day and Night (2020.08.14.)
  4. B36/S245 a.k.a. Logarithmic replicator rule (2020.08.19.)
  5. B368/S245 as Move by Layz Boi (2020.08.20.)
  6. B3/S012345678 Life without death rule (2020.10.13.)
  7. B2/S0 a.k.a. Live free or die by FWKnightship (2020.10.20.) - first B2 life-like rule proven to be Turing-complete
  8. B2/S a.k.a. Seeds (2020.10.30.) works in three other life-like rules between B2/S and B27/S78, first polyglot pattern in a B2* OT rule
  9. B358/S236 (2020.11.07.) by FWKnightship - works in another OT rule B35/S236
  10. B3/S023 a.k.a. DotLife (2020.12.30.) by FWKnightship
  11. B36/S125 a.k.a. 2×2 (2021.02.04.) by FWKnightship
  12. B3678/S01456 (2021.03.06.) by Layz Boi
  13. B3678/S235678 a.k.a. Stains (2021.08.07.)
Selected list of blinking life-like rules having at least one constructed W110 (or CGoL) Unit Cell/rake/stripe etc:
  1. B01346/S02 (2020.09.06.) by FWKnightship
  2. B017/S01 (2020.09.19.) by FWKnightship
  3. B01368/S03 (2020.10.08.) by GUYTU6J
  4. B0235/S1234 (2020.10.11.) by FWKnightship
  5. B012/S017 and B0128/S017 (2020.11.07.) by FWKnightship
  6. B0234/S0124 (2020.11.07.) by FWKnightship
Selected list of rules having von Neumann neighbourhood and 2 states per cell with at least one constructed W110 (or CGoL) Unit Cell/rake/stripe etc:
  1. Banks-I or as an INT-rule B3c4c/S01c2n3c4c (2017.11.02.)
  2. B03/S0V and its dual rule B0123/S023V (2021.04.11.)
L̶a̶s̶t̶ ̶u̶p̶d̶a̶t̶e̶d̶ ̶o̶n̶:̶ ̶2̶0̶2̶0̶.̶0̶9̶.̶2̶4̶.̶
L̶a̶s̶t̶ ̶u̶p̶d̶a̶t̶e̶d̶ ̶o̶n̶:̶ ̶2̶0̶2̶0̶.̶1̶0̶.̶1̶9̶.̶
L̶a̶s̶t̶ ̶u̶p̶d̶a̶t̶e̶d̶ ̶o̶n̶:̶ ̶2̶0̶2̶0̶.̶1̶0̶.̶2̶1̶.̶
L̶a̶s̶t̶ ̶u̶p̶d̶a̶t̶e̶d̶ ̶o̶n̶:̶ ̶2̶0̶2̶0̶.̶1̶1̶.̶1̶1̶.̶
L̶a̶s̶t̶ ̶u̶p̶d̶a̶t̶e̶d̶ ̶o̶n̶:̶ ̶2̶0̶2̶0̶.̶1̶2̶.̶3̶1̶.̶
L̶a̶s̶t̶ ̶u̶p̶d̶a̶t̶e̶d̶ ̶o̶n̶:̶ ̶2̶0̶2̶1̶.̶0̶3̶.̶1̶5̶.̶
Last updated on: 2022.08.04.
Last edited by Naszvadi on August 4th, 2022, 6:41 am, edited 13 times in total.

Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

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

Post by 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: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

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

Post by 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:

Code: Select all

#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):
  • 000001
  • 000011
  • 000111
  • 001101
  • 011111
  • 110001 - tested till this
  • 010011
  • 110111
  • 011100
  • 110100
  • 111101
  • 000111 - loop
The Unit Cell grid generator for Rule-110 what I made will be published here soon:
http://conwaylife.com/forums/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: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

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

Post by 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: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

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

Post by 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:

Code: Select all

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

Code: Select all

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: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

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

Post by Naszvadi » December 12th, 2016, 3:18 pm

Code: Select all

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.

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

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

Post by 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!

Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

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

Post by 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:

Code: Select all

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

Code: Select all

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

Code: Select all

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

Code: Select all

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

Code: Select all

#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: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

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

Post by 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:

Code: Select all

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: viewtopic.php?f=9&t=2615

Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

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

Post by Naszvadi » December 20th, 2016, 7:55 pm

Another glider gun is here:

http://conwaylife.com/forums/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: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

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

Post by Naszvadi » December 21st, 2016, 7:49 am

Naszvadi wrote:Another glider gun is here:

http://conwaylife.com/forums/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:

Code: Select all

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: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

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

Post by Naszvadi » January 2nd, 2017, 10:53 am

B37/S236 p30 gun is here, thanks to Sokwe:
http://conwaylife.com/forums/viewtopic. ... 1071#p7732

So B37/S236 is added to universal rules list in the OP.

Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

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

Post by Naszvadi » January 3rd, 2017, 10:58 am

There are additional guns for rules here http://conwaylife.com/forums/viewtopic.php?f=11&t=1071 :
  • P44 for B378/S238
  • P44 for B3/S2367 - B38/S23678
Totally 5 new universal rules.

Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

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

Post by 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: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

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

Post by 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: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

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

Post by 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: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

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

Post by Naszvadi » October 4th, 2017, 10:59 am

Now, a cuckoo-egg (this rule is nontotalistic) - a unit cell implementing Wolfram Rule 110 and pattern 100000:

Code: Select all

x = 227, y = 1086, rule = B2ce3ai/S1c23-a:T0,1086
o225bo36$103b2o$103bo$105bo$104bo2bo$106b2o$32b2o$32bo2bo$34bo34b2o$
36bo33bo$35b2o31bo$66bo2bo123b2o$66b2o125bo$195bo$194bo2bo$196b2o10$
75b2o$75bo79bo$77bo10bo64b2ob2o60bo$76b2o8b2ob2o60bo2bobo59b2ob2o$84bo
2bobo62bobo3bo55bo2bobo$85bobo3bo60bo2bob2obo54bobo3bo$85bo2bob2obo57b
obo2bo2b2ob2o51bo2bob2obo$84bobo2bo2b2ob2o54b2obo8bo50bobo2bo2b2ob2o$
84b2obo8bo57bo6bo52b2obo8bo$86bo7bo58bobo5b2o53bo7bo$94b2o56b2ob2o67b
2o$153bobo$5b2o79b3o65bo61b3o$5bo2bo77bobo127bobo$7b2o77b3o127b3o$4b2o
$5bo$3b2o$bo2bo5b2o$b2o2bo4bo$o3bo3bobo$b3o2b2o6bo175b3o$bo3bo184bobo$
3b2o2bo30b2o63b2o30b2o31b2o20bobo7b2o$2bo2bo3bobo24bo2bo61bo2bo32bo28b
o2bo20b3o9bo$10bo27b2o63b2o30b2o31b2o20bobo7b2o21b2o$190b3o30bo2bo$
100b3o87bobo32b2o$100bobo87b3o2$101bo$21b2o$22bo$20bo$18bo2bo48b2o$18b
2o50bo$42b2o28bo47b2o$40bo2bo27b2o47bo$41bo55bo2bob2o18bo75bo$39bo62bo
2b2o14b2o74bobo$39b2o59bo2bo92b2ob2o$74b2o23bobobo3bo89bob2o$75bo27bo
7b2o80b2o4bo$73bo30bo6bo81bo5bob2o$71bo2bo26b2obo8bo80bo6bo$71b2o28bob
o2bo2b2ob2o77b2obo2bo5bo$89b2o11bo2bob2obo80bobo2bo2b2ob2o$87bo2bo11bo
bo3bo83bo2bob2obo$88bo12bo2bobo85bobo3bo$86bo16b2ob2o83bo2bobo$86b2o
17bo87b2ob2o$195bo2$156b2o50b2o$154bo2bo50bo2bo$155bo54bo$21b2o130bo
58bo$21bo2bo128b2o56b2o$23bo$25bo$24b2o10$119b2o$119bo$121bo$120bo2bo$
122b2o$68b2o$68bo2bo$70bo$72bo$71b2o3$74b2o$75bo$73bo$71bo2bo$71b2o$
125b2o$123bo2bo$124bo$122bo$122b2o29$o225bo$o225bo36$103b2o$103bo$105b
o$104bo2bo$106b2o$32b2o$32bo2bo$34bo34b2o$36bo33bo$35b2o31bo$66bo2bo
123b2o$66b2o125bo$195bo$194bo2bo$196b2o10$75b2o$75bo79bo$77bo10bo64b2o
b2o60bo$76b2o8b2ob2o60bo2bobo59b2ob2o$84bo2bobo62bobo3bo55bo2bobo$85bo
bo3bo60bo2bob2obo54bobo3bo$85bo2bob2obo57bobo2bo2b2ob2o51bo2bob2obo$
84bobo2bo2b2ob2o54b2obo8bo50bobo2bo2b2ob2o$84b2obo8bo57bo6bo52b2obo8bo
$86bo7bo58bobo5b2o53bo7bo$94b2o56b2ob2o67b2o$153bobo$5b2o79b3o65bo61b
3o$5bo2bo77bobo127bobo$7b2o77b3o127b3o$4b2o$5bo$3b2o$bo2bo5b2o$b2o2bo
4bo$o3bo3bobo$b3o2b2o6bo175b3o$bo3bo184bobo$3b2o2bo30b2o30b2o31b2o30b
2o31b2o20bobo7b2o$2bo2bo3bobo24bo2bo32bo28bo2bo32bo28bo2bo20b3o9bo$10b
o27b2o30b2o31b2o30b2o31b2o20bobo7b2o21b2o$190b3o30bo2bo$100b3o87bobo
32b2o$100bobo87b3o2$101bo$21b2o$22bo$20bo$18bo2bo48b2o$18b2o50bo$42b2o
28bo47b2o$40bo2bo27b2o47bo$41bo55bo2bob2o18bo75bo$39bo62bo2b2o14b2o74b
obo$39b2o59bo2bo92b2ob2o$74b2o23bobobo3bo89bob2o$75bo27bo7b2o80b2o4bo$
73bo30bo6bo81bo5bob2o$71bo2bo26b2obo8bo80bo6bo$71b2o28bobo2bo2b2ob2o
77b2obo2bo5bo$89b2o11bo2bob2obo80bobo2bo2b2ob2o$87bo2bo11bobo3bo83bo2b
ob2obo$88bo12bo2bobo85bobo3bo$86bo16b2ob2o83bo2bobo$86b2o17bo87b2ob2o$
195bo2$156b2o50b2o$154bo2bo50bo2bo$155bo54bo$21b2o130bo58bo$21bo2bo
128b2o56b2o$23bo$25bo$24b2o10$119b2o$119bo$121bo$120bo2bo$122b2o$68b2o
$68bo2bo$70bo$72bo$71b2o3$74b2o$75bo$73bo$71bo2bo$71b2o$125b2o$123bo2b
o$124bo$122bo$122b2o29$o225bo$o225bo36$103b2o$103bo$105bo$104bo2bo$
106b2o$32b2o$32bo2bo$34bo34b2o$36bo33bo$35b2o31bo$66bo2bo123b2o$66b2o
125bo$195bo$194bo2bo$196b2o10$75b2o$75bo79bo$77bo10bo64b2ob2o60bo$76b
2o8b2ob2o60bo2bobo59b2ob2o$84bo2bobo62bobo3bo55bo2bobo$85bobo3bo60bo2b
ob2obo54bobo3bo$85bo2bob2obo57bobo2bo2b2ob2o51bo2bob2obo$84bobo2bo2b2o
b2o54b2obo8bo50bobo2bo2b2ob2o$84b2obo8bo57bo6bo52b2obo8bo$86bo7bo58bob
o5b2o53bo7bo$94b2o56b2ob2o67b2o$153bobo$5b2o79b3o65bo61b3o$5bo2bo77bob
o127bobo$7b2o77b3o127b3o$4b2o$5bo$3b2o$bo2bo5b2o$b2o2bo4bo$o3bo3bobo$b
3o2b2o6bo175b3o$bo3bo184bobo$3b2o2bo30b2o30b2o31b2o30b2o31b2o20bobo7b
2o$2bo2bo3bobo24bo2bo32bo28bo2bo32bo28bo2bo20b3o9bo$10bo27b2o30b2o31b
2o30b2o31b2o20bobo7b2o21b2o$190b3o30bo2bo$100b3o87bobo32b2o$100bobo87b
3o2$101bo$21b2o$22bo$20bo$18bo2bo48b2o$18b2o50bo$42b2o28bo47b2o$40bo2b
o27b2o47bo$41bo55bo2bob2o18bo75bo$39bo62bo2b2o14b2o74bobo$39b2o59bo2bo
92b2ob2o$74b2o23bobobo3bo89bob2o$75bo27bo7b2o80b2o4bo$73bo30bo6bo81bo
5bob2o$71bo2bo26b2obo8bo80bo6bo$71b2o28bobo2bo2b2ob2o77b2obo2bo5bo$89b
2o11bo2bob2obo80bobo2bo2b2ob2o$87bo2bo11bobo3bo83bo2bob2obo$88bo12bo2b
obo85bobo3bo$86bo16b2ob2o83bo2bobo$86b2o17bo87b2ob2o$195bo2$156b2o50b
2o$154bo2bo50bo2bo$155bo54bo$21b2o130bo58bo$21bo2bo128b2o56b2o$23bo$
25bo$24b2o10$119b2o$119bo$121bo$120bo2bo$122b2o$68b2o$68bo2bo$70bo$72b
o$71b2o3$74b2o$75bo$73bo$71bo2bo$71b2o$125b2o$123bo2bo$124bo$122bo$
122b2o29$o225bo$o225bo36$103b2o$103bo$105bo$104bo2bo$106b2o$32b2o$32bo
2bo$34bo34b2o$36bo33bo$35b2o31bo$66bo2bo123b2o$66b2o125bo$195bo$194bo
2bo$196b2o10$75b2o$75bo79bo$77bo10bo64b2ob2o60bo$76b2o8b2ob2o60bo2bobo
59b2ob2o$84bo2bobo62bobo3bo55bo2bobo$85bobo3bo60bo2bob2obo54bobo3bo$
85bo2bob2obo57bobo2bo2b2ob2o51bo2bob2obo$84bobo2bo2b2ob2o54b2obo8bo50b
obo2bo2b2ob2o$84b2obo8bo57bo6bo52b2obo8bo$86bo7bo58bobo5b2o53bo7bo$94b
2o56b2ob2o67b2o$153bobo$5b2o79b3o65bo61b3o$5bo2bo77bobo127bobo$7b2o77b
3o127b3o$4b2o$5bo$3b2o$bo2bo5b2o$b2o2bo4bo$o3bo3bobo$b3o2b2o6bo175b3o$
bo3bo184bobo$3b2o2bo30b2o30b2o31b2o30b2o31b2o20bobo7b2o$2bo2bo3bobo24b
o2bo32bo28bo2bo32bo28bo2bo20b3o9bo$10bo27b2o30b2o31b2o30b2o31b2o20bobo
7b2o21b2o$190b3o30bo2bo$100b3o87bobo32b2o$100bobo87b3o2$101bo$21b2o$
22bo$20bo$18bo2bo48b2o$18b2o50bo$42b2o28bo47b2o$40bo2bo27b2o47bo$41bo
55bo2bob2o18bo75bo$39bo62bo2b2o14b2o74bobo$39b2o59bo2bo92b2ob2o$74b2o
23bobobo3bo89bob2o$75bo27bo7b2o80b2o4bo$73bo30bo6bo81bo5bob2o$71bo2bo
26b2obo8bo80bo6bo$71b2o28bobo2bo2b2ob2o77b2obo2bo5bo$89b2o11bo2bob2obo
80bobo2bo2b2ob2o$87bo2bo11bobo3bo83bo2bob2obo$88bo12bo2bobo85bobo3bo$
86bo16b2ob2o83bo2bobo$86b2o17bo87b2ob2o$195bo2$156b2o50b2o$154bo2bo50b
o2bo$155bo54bo$21b2o130bo58bo$21bo2bo128b2o56b2o$23bo$25bo$24b2o10$
119b2o$119bo$121bo$120bo2bo$122b2o$68b2o$68bo2bo$70bo$72bo$71b2o3$74b
2o$75bo$73bo$71bo2bo$71b2o$125b2o$123bo2bo$124bo$122bo$122b2o29$o225bo
$o225bo36$103b2o$103bo$105bo$104bo2bo$106b2o$32b2o$32bo2bo$34bo34b2o$
36bo33bo$35b2o31bo$66bo2bo123b2o$66b2o125bo$195bo$194bo2bo$196b2o10$
75b2o$75bo79bo$77bo10bo64b2ob2o60bo$76b2o8b2ob2o60bo2bobo59b2ob2o$84bo
2bobo62bobo3bo55bo2bobo$85bobo3bo60bo2bob2obo54bobo3bo$85bo2bob2obo57b
obo2bo2b2ob2o51bo2bob2obo$84bobo2bo2b2ob2o54b2obo8bo50bobo2bo2b2ob2o$
84b2obo8bo57bo6bo52b2obo8bo$86bo7bo58bobo5b2o53bo7bo$94b2o56b2ob2o67b
2o$153bobo$5b2o79b3o65bo61b3o$5bo2bo77bobo127bobo$7b2o77b3o127b3o$4b2o
$5bo$3b2o$bo2bo5b2o$b2o2bo4bo$o3bo3bobo$b3o2b2o6bo175b3o$bo3bo184bobo$
3b2o2bo30b2o30b2o31b2o30b2o31b2o20bobo7b2o$2bo2bo3bobo24bo2bo32bo28bo
2bo32bo28bo2bo20b3o9bo$10bo27b2o30b2o31b2o30b2o31b2o20bobo7b2o21b2o$
190b3o30bo2bo$100b3o87bobo32b2o$100bobo87b3o2$101bo$21b2o$22bo$20bo$
18bo2bo48b2o$18b2o50bo$42b2o28bo47b2o$40bo2bo27b2o47bo$41bo55bo2bob2o
18bo75bo$39bo62bo2b2o14b2o74bobo$39b2o59bo2bo92b2ob2o$74b2o23bobobo3bo
89bob2o$75bo27bo7b2o80b2o4bo$73bo30bo6bo81bo5bob2o$71bo2bo26b2obo8bo
80bo6bo$71b2o28bobo2bo2b2ob2o77b2obo2bo5bo$89b2o11bo2bob2obo80bobo2bo
2b2ob2o$87bo2bo11bobo3bo83bo2bob2obo$88bo12bo2bobo85bobo3bo$86bo16b2ob
2o83bo2bobo$86b2o17bo87b2ob2o$195bo2$156b2o50b2o$154bo2bo50bo2bo$155bo
54bo$21b2o130bo58bo$21bo2bo128b2o56b2o$23bo$25bo$24b2o10$119b2o$119bo$
121bo$120bo2bo$122b2o$68b2o$68bo2bo$70bo$72bo$71b2o3$74b2o$75bo$73bo$
71bo2bo$71b2o$125b2o$123bo2bo$124bo$122bo$122b2o29$o225bo$o225bo36$
103b2o$103bo$105bo$104bo2bo$106b2o$32b2o$32bo2bo$34bo34b2o$36bo33bo$
35b2o31bo$66bo2bo123b2o$66b2o125bo$195bo$194bo2bo$196b2o10$75b2o$75bo
79bo$77bo10bo64b2ob2o60bo$76b2o8b2ob2o60bo2bobo59b2ob2o$84bo2bobo62bob
o3bo55bo2bobo$85bobo3bo60bo2bob2obo54bobo3bo$85bo2bob2obo57bobo2bo2b2o
b2o51bo2bob2obo$84bobo2bo2b2ob2o54b2obo8bo50bobo2bo2b2ob2o$84b2obo8bo
57bo6bo52b2obo8bo$86bo7bo58bobo5b2o53bo7bo$94b2o56b2ob2o67b2o$153bobo$
5b2o79b3o65bo61b3o$5bo2bo77bobo127bobo$7b2o77b3o127b3o$4b2o$5bo$3b2o$b
o2bo5b2o$b2o2bo4bo$o3bo3bobo$b3o2b2o6bo175b3o$bo3bo184bobo$3b2o2bo30b
2o30b2o31b2o30b2o31b2o20bobo7b2o$2bo2bo3bobo24bo2bo32bo28bo2bo32bo28bo
2bo20b3o9bo$10bo27b2o30b2o31b2o30b2o31b2o20bobo7b2o21b2o$190b3o30bo2bo
$100b3o87bobo32b2o$100bobo87b3o2$101bo$21b2o$22bo$20bo$18bo2bo48b2o$
18b2o50bo$42b2o28bo47b2o$40bo2bo27b2o47bo$41bo55bo2bob2o18bo75bo$39bo
62bo2b2o14b2o74bobo$39b2o59bo2bo92b2ob2o$74b2o23bobobo3bo89bob2o$75bo
27bo7b2o80b2o4bo$73bo30bo6bo81bo5bob2o$71bo2bo26b2obo8bo80bo6bo$71b2o
28bobo2bo2b2ob2o77b2obo2bo5bo$89b2o11bo2bob2obo80bobo2bo2b2ob2o$87bo2b
o11bobo3bo83bo2bob2obo$88bo12bo2bobo85bobo3bo$86bo16b2ob2o83bo2bobo$
86b2o17bo87b2ob2o$195bo2$156b2o50b2o$154bo2bo50bo2bo$155bo54bo$21b2o
130bo58bo$21bo2bo128b2o56b2o$23bo$25bo$24b2o10$119b2o$119bo$121bo$120b
o2bo$122b2o$68b2o$68bo2bo$70bo$72bo$71b2o3$74b2o$75bo$73bo$71bo2bo$71b
2o$125b2o$123bo2bo$124bo$122bo$122b2o29$o225bo!
So, rule B2ce3ai/S1c23-a is Turing-comlete.

Period is 650. Cell width is 181. Used only a stable right angle reflector, some 2G collisions, a p65 gun, and an eater.

This is extraordinary: with some tweaks and with a p65-stream-backrake, a gunless W110 unit cell could be created.

The 3 implemented logical gates are:
  1. AND(NOT(p),q)
  2. XOR(q,r)
  3. IOR(*1,*2)

Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

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

Post by Naszvadi » October 14th, 2017, 5:55 pm

Constructed a W110 unit cell in rule B35/S236 (Hello Eppstein!) - so it is Turing-complete!

Here you are:

Code: Select all

x = 366, y = 1647, rule = B35/S236:T0,1704
#C Naszvadi Peter, 2015-2017
6b2o$5b2o$6bo2bo$7b3o$8bo63b4o$71bo3bo$23bobo25b2o19bo4bo$22bo2b2o24b
3o19bo2b2o$23bobo25b2o2$2b3o$2bobo$2o2bo$o$3o2$76bo$76b2o$77bo$76bo$
79b2o$69b2o7bob2o$69b2o$69bo2$65b3o274b3o$65b2o275bo$187b2o153b2o2bo$
187b3o154bobo$344b3o$191bo$191b2o$191b2o2$340bo$339bobo$43bo295bob2o$
42bo294b2obo$41b2o293bo2bo$41b2o294b2o$47bo290bo$44b3o$44b2o10$334bobo
$334bo$333b2o20bo$333bo5bo14b3o2$75b3o259b3o14bobo$76bo259b2o17bo$77bo
$72bo3bo$72b2obo$72bobo5$198b2o$197b2o2bo$197bo3bo$197b4o$198bo4b2o70b
3o$112b2o88bo10b2o60b2o$111bo90bo2bo5b3obo60bo2bo$111b3o87b2ob2o5b2obo
62b3o$111bo90b3o8b2o63b2o4bo8bo$108b3o97b2o5bo67bobo6bo$107bobo98b2o
74bo6b2o$107bobo97b2obo72b3o4bobo$207bob2o78b3o$38bobo167bo2bo76bo$38b
2obo313bo$38bo3bo311bobo$43bo309bo3bo$42bo312bo$41b3o$62bo135bo135bo$
63bo24bobo25b2o25b3o24bobo26bo24bobo25b2o25b3o24bobo26bo29bo$61bo2bo
22bo2b2o24b3o22b5o23bob2o24bo2bo22bo2b2o24b3o22b5o23bob2o24bo2bo27b2o$
63bo24bobo25b2o25b3o24bobo26bo24bobo25b2o25b3o24bobo26bo28bo$37bo24bo
135bo135bo30bo$36b3o322b2o$36bo323b2obo$37b2o$33b2o2bo$32b2ob2o299bo$
33bobo299b3o$192bo148b3o$85b2o104bobo141bobo4bobo$86b2o248bo6b2o$83bo
2bo104b2o2bo148bo$83b3o107bo2bo133bo$84bo99bo8bobo133b3o$184bo143bo2bo
$185bo141b2o$184bo143b2o$180b2obo$182bo2$250bobo$249bo2bo$250bo2b2o2$
252bobo$253bo9b2o$262b3o$261bo2bo$260b2o$260b3o11$257bo$256bobo$257bo$
256b3o3$287b2o$287b2o$287bo$284b3o$284b2o7$299b2o$300b2o$297bo2bo$297b
3o$258b2o5b2o31bo$257b4o3b4o$256b3ob2ob2ob3o7bobo$54b2o201b4o3b4o8b2ob
o$53b2o203b2o5b2o9bobo$54bo2bo$55b3o$56bo235b3o$293bobo$294b2o$295bo
15$166b2o$168bo$166b3o$168bo$99b2o68b3o$100b3o67bobo$170bobo$96bo5bo$
96b2o$97bo$97bobo3$251bo$250bob2o$249bo$248bo$247bo4bo$246bo5bo$247bo
2b2o$247bo2$191b3o25b2o23b2o$191b5o22b3o23b2o$191b3o25b2o24bo$241bo2$
242b2o2bo$242b4obo$242b3obo$245b2o3b2o$245b3o$245b3o$249bo8$173b2o$
172b3o$173b2o$175b3o$175b3o$164bobo9bo$163bob2o$162bo3bo$161bo$162bo$
161b3o58$6b2o$5b2o$6bo2bo$7b3o$8bo63b4o$71bo3bo$23bobo25b2o19bo4bo$22b
o2b2o24b3o19bo2b2o$23bobo25b2o2$2b3o$2bobo$2o2bo$o$3o2$76bo$76b2o$77bo
$76bo$79b2o$69b2o7bob2o$69b2o$69bo2$65b3o274b3o$65b2o275bo$187b2o153b
2o2bo$187b3o154bobo$344b3o$191bo$191b2o$191b2o2$340bo$339bobo$43bo295b
ob2o$42bo294b2obo$41b2o293bo2bo$41b2o294b2o$47bo290bo$44b3o$44b2o10$
334bobo$334bo$333b2o20bo$333bo5bo14b3o2$75b3o259b3o14bobo$76bo259b2o
17bo$77bo$72bo3bo$72b2obo$72bobo5$198b2o$197b2o2bo$197bo3bo$197b4o$
198bo4b2o70b3o$112b2o88bo10b2o60b2o$111bo90bo2bo5b3obo60bo2bo$111b3o
87b2ob2o5b2obo62b3o$111bo90b3o8b2o63b2o4bo8bo$108b3o97b2o5bo67bobo6bo$
107bobo98b2o74bo6b2o$107bobo97b2obo72b3o4bobo$207bob2o78b3o$38bobo167b
o2bo76bo$38b2obo313bo$38bo3bo311bobo$43bo309bo3bo$42bo312bo$41b3o$62bo
135bo135bo$63bo24bobo25b2o25b3o24bobo26bo24bobo25b2o25b3o24bobo26bo29b
o$61bo2bo22bo2b2o24b3o22b5o23bob2o24bo2bo22bo2b2o24b3o22b5o23bob2o24bo
2bo27b2o$63bo24bobo25b2o25b3o24bobo26bo24bobo25b2o25b3o24bobo26bo28bo$
37bo24bo135bo135bo30bo$36b3o322b2o$36bo323b2obo$37b2o$33b2o2bo$32b2ob
2o299bo$33bobo299b3o$192bo148b3o$85b2o104bobo141bobo4bobo$86b2o248bo6b
2o$83bo2bo104b2o2bo148bo$83b3o107bo2bo133bo$84bo99bo8bobo133b3o$184bo
143bo2bo$185bo141b2o$184bo143b2o$180b2obo$182bo2$250bobo$249bo2bo$250b
o2b2o2$252bobo$253bo9b2o$262b3o$261bo2bo$260b2o$260b3o11$257bo$256bobo
$257bo$256b3o3$287b2o$287b2o$287bo$284b3o$284b2o7$299b2o$300b2o$297bo
2bo$297b3o$258b2o5b2o31bo$257b4o3b4o$256b3ob2ob2ob3o7bobo$54b2o201b4o
3b4o8b2obo$53b2o203b2o5b2o9bobo$54bo2bo$55b3o$56bo235b3o$293bobo$294b
2o$295bo15$166b2o$168bo$166b3o$168bo$99b2o68b3o$100b3o67bobo$170bobo$
96bo5bo$96b2o$97bo$97bobo3$251bo$250bob2o$249bo$248bo$247bo4bo$246bo5b
o$247bo2b2o$247bo2$191b3o25b2o23b2o$191b5o22b3o23b2o$191b3o25b2o24bo$
241bo2$242b2o2bo$242b4obo$242b3obo$245b2o3b2o$245b3o$245b3o$249bo8$
173b2o$172b3o$173b2o$175b3o$175b3o$164bobo9bo$163bob2o$162bo3bo$161bo$
162bo$161b3o58$6b2o$5b2o$6bo2bo$7b3o$8bo63b4o$71bo3bo$23bobo25b2o19bo
4bo$22bo2b2o24b3o19bo2b2o$23bobo25b2o2$2b3o$2bobo$2o2bo$o$3o2$76bo$76b
2o$77bo$76bo$79b2o$69b2o7bob2o$69b2o$69bo2$65b3o274b3o$65b2o275bo$187b
2o153b2o2bo$187b3o154bobo$344b3o$191bo$191b2o$191b2o2$340bo$339bobo$
43bo295bob2o$42bo294b2obo$41b2o293bo2bo$41b2o294b2o$47bo290bo$44b3o$
44b2o10$334bobo$334bo$333b2o20bo$333bo5bo14b3o2$75b3o259b3o14bobo$76bo
259b2o17bo$77bo$72bo3bo$72b2obo$72bobo5$198b2o$197b2o2bo$197bo3bo$197b
4o$198bo4b2o70b3o$112b2o88bo10b2o60b2o$111bo90bo2bo5b3obo60bo2bo$111b
3o87b2ob2o5b2obo62b3o$111bo90b3o8b2o63b2o4bo8bo$108b3o97b2o5bo67bobo6b
o$107bobo98b2o74bo6b2o$107bobo97b2obo72b3o4bobo$207bob2o78b3o$38bobo
167bo2bo76bo$38b2obo313bo$38bo3bo311bobo$43bo309bo3bo$42bo312bo$41b3o$
62bo135bo135bo$63bo24bobo25b2o25b3o24bobo26bo24bobo25b2o25b3o24bobo26b
o29bo$61bo2bo22bo2b2o24b3o22b5o23bob2o24bo2bo22bo2b2o24b3o22b5o23bob2o
24bo2bo27b2o$63bo24bobo25b2o25b3o24bobo26bo24bobo25b2o25b3o24bobo26bo
28bo$37bo24bo135bo135bo30bo$36b3o322b2o$36bo323b2obo$37b2o$33b2o2bo$
32b2ob2o299bo$33bobo299b3o$192bo148b3o$85b2o104bobo141bobo4bobo$86b2o
248bo6b2o$83bo2bo104b2o2bo148bo$83b3o107bo2bo133bo$84bo99bo8bobo133b3o
$184bo143bo2bo$185bo141b2o$184bo143b2o$180b2obo$182bo2$250bobo$249bo2b
o$250bo2b2o2$252bobo$253bo9b2o$262b3o$261bo2bo$260b2o$260b3o11$257bo$
256bobo$257bo$256b3o3$287b2o$287b2o$287bo$284b3o$284b2o7$299b2o$300b2o
$297bo2bo$297b3o$258b2o5b2o31bo$257b4o3b4o$256b3ob2ob2ob3o7bobo$54b2o
201b4o3b4o8b2obo$53b2o203b2o5b2o9bobo$54bo2bo$55b3o$56bo235b3o$293bobo
$294b2o$295bo15$166b2o$168bo$166b3o$168bo$99b2o68b3o$100b3o67bobo$170b
obo$96bo5bo$96b2o$97bo$97bobo3$251bo$250bob2o$249bo$248bo$247bo4bo$
246bo5bo$247bo2b2o$247bo2$191b3o25b2o23b2o$191b5o22b3o23b2o$191b3o25b
2o24bo$241bo2$242b2o2bo$242b4obo$242b3obo$245b2o3b2o$245b3o$245b3o$
249bo8$173b2o$172b3o$173b2o$175b3o$175b3o$164bobo9bo$163bob2o$162bo3bo
$161bo$162bo$161b3o58$6b2o$5b2o$6bo2bo$7b3o$8bo63b4o$71bo3bo$23bobo25b
2o19bo4bo$22bo2b2o24b3o19bo2b2o$23bobo25b2o2$2b3o$2bobo$2o2bo$o$3o2$
76bo$76b2o$77bo$76bo$79b2o$69b2o7bob2o$69b2o$69bo2$65b3o274b3o$65b2o
275bo$187b2o153b2o2bo$187b3o154bobo$344b3o$191bo$191b2o$191b2o2$340bo$
339bobo$43bo295bob2o$42bo294b2obo$41b2o293bo2bo$41b2o294b2o$47bo290bo$
44b3o$44b2o10$334bobo$334bo$333b2o20bo$333bo5bo14b3o2$75b3o259b3o14bob
o$76bo259b2o17bo$77bo$72bo3bo$72b2obo$72bobo5$198b2o$197b2o2bo$197bo3b
o$197b4o$198bo4b2o70b3o$112b2o88bo10b2o60b2o$111bo90bo2bo5b3obo60bo2bo
$111b3o87b2ob2o5b2obo62b3o$111bo90b3o8b2o63b2o4bo8bo$108b3o97b2o5bo67b
obo6bo$107bobo98b2o74bo6b2o$107bobo97b2obo72b3o4bobo$207bob2o78b3o$38b
obo167bo2bo76bo$38b2obo313bo$38bo3bo311bobo$43bo309bo3bo$42bo312bo$41b
3o$62bo135bo135bo$63bo24bobo52b3o24bobo26bo24bobo25b2o25b3o24bobo26bo
29bo$61bo2bo22bo2b2o49b5o23bob2o24bo2bo22bo2b2o24b3o22b5o23bob2o24bo2b
o27b2o$63bo24bobo52b3o24bobo26bo24bobo25b2o25b3o24bobo26bo28bo$37bo24b
o135bo135bo30bo$36b3o322b2o$36bo323b2obo$37b2o$33b2o2bo$32b2ob2o299bo$
33bobo299b3o$192bo148b3o$85b2o104bobo141bobo4bobo$86b2o248bo6b2o$83bo
2bo104b2o2bo148bo$83b3o107bo2bo133bo$84bo99bo8bobo133b3o$184bo143bo2bo
$185bo141b2o$184bo143b2o$180b2obo$182bo2$250bobo$249bo2bo$250bo2b2o2$
252bobo$253bo9b2o$262b3o$261bo2bo$260b2o$260b3o11$257bo$256bobo$257bo$
256b3o3$287b2o$287b2o$287bo$284b3o$284b2o7$299b2o$300b2o$297bo2bo$297b
3o$258b2o5b2o31bo$257b4o3b4o$256b3ob2ob2ob3o7bobo$54b2o201b4o3b4o8b2ob
o$53b2o203b2o5b2o9bobo$54bo2bo$55b3o$56bo235b3o$293bobo$294b2o$295bo
15$166b2o$168bo$166b3o$168bo$99b2o68b3o$100b3o67bobo$170bobo$96bo5bo$
96b2o$97bo$97bobo3$251bo$250bob2o$249bo$248bo$247bo4bo$246bo5bo$247bo
2b2o$247bo2$191b3o25b2o23b2o$191b5o22b3o23b2o$191b3o25b2o24bo$241bo2$
242b2o2bo$242b4obo$242b3obo$245b2o3b2o$245b3o$245b3o$249bo8$173b2o$
172b3o$173b2o$175b3o$175b3o$164bobo9bo$163bob2o$162bo3bo$161bo$162bo$
161b3o58$6b2o$5b2o$6bo2bo$7b3o$8bo63b4o$71bo3bo$23bobo25b2o19bo4bo$22b
o2b2o24b3o19bo2b2o$23bobo25b2o2$2b3o$2bobo$2o2bo$o$3o2$76bo$76b2o$77bo
$76bo$79b2o$69b2o7bob2o$69b2o$69bo2$65b3o274b3o$65b2o275bo$187b2o153b
2o2bo$187b3o154bobo$344b3o$191bo$191b2o$191b2o2$340bo$339bobo$43bo295b
ob2o$42bo294b2obo$41b2o293bo2bo$41b2o294b2o$47bo290bo$44b3o$44b2o10$
334bobo$334bo$333b2o20bo$333bo5bo14b3o2$75b3o259b3o14bobo$76bo259b2o
17bo$77bo$72bo3bo$72b2obo$72bobo5$198b2o$197b2o2bo$197bo3bo$197b4o$
198bo4b2o70b3o$112b2o88bo10b2o60b2o$111bo90bo2bo5b3obo60bo2bo$111b3o
87b2ob2o5b2obo62b3o$111bo90b3o8b2o63b2o4bo8bo$108b3o97b2o5bo67bobo6bo$
107bobo98b2o74bo6b2o$107bobo97b2obo72b3o4bobo$207bob2o78b3o$38bobo167b
o2bo76bo$38b2obo313bo$38bo3bo311bobo$43bo309bo3bo$42bo312bo$41b3o$62bo
135bo135bo$63bo24bobo25b2o25b3o24bobo26bo24bobo25b2o25b3o24bobo26bo29b
o$61bo2bo22bo2b2o24b3o22b5o23bob2o24bo2bo22bo2b2o24b3o22b5o23bob2o24bo
2bo27b2o$63bo24bobo25b2o25b3o24bobo26bo24bobo25b2o25b3o24bobo26bo28bo$
37bo24bo135bo135bo30bo$36b3o322b2o$36bo323b2obo$37b2o$33b2o2bo$32b2ob
2o299bo$33bobo299b3o$192bo148b3o$85b2o104bobo141bobo4bobo$86b2o248bo6b
2o$83bo2bo104b2o2bo148bo$83b3o107bo2bo133bo$84bo99bo8bobo133b3o$184bo
143bo2bo$185bo141b2o$184bo143b2o$180b2obo$182bo2$250bobo$249bo2bo$250b
o2b2o2$252bobo$253bo9b2o$262b3o$261bo2bo$260b2o$260b3o11$257bo$256bobo
$257bo$256b3o3$287b2o$287b2o$287bo$284b3o$284b2o7$299b2o$300b2o$297bo
2bo$297b3o$258b2o5b2o31bo$257b4o3b4o$256b3ob2ob2ob3o7bobo$54b2o201b4o
3b4o8b2obo$53b2o203b2o5b2o9bobo$54bo2bo$55b3o$56bo235b3o$293bobo$294b
2o$295bo15$166b2o$168bo$166b3o$168bo$99b2o68b3o$100b3o67bobo$170bobo$
96bo5bo$96b2o$97bo$97bobo3$251bo$250bob2o$249bo$248bo$247bo4bo$246bo5b
o$247bo2b2o$247bo2$191b3o25b2o23b2o$191b5o22b3o23b2o$191b3o25b2o24bo$
241bo2$242b2o2bo$242b4obo$242b3obo$245b2o3b2o$245b3o$245b3o$249bo8$
173b2o$172b3o$173b2o$175b3o$175b3o$164bobo9bo$163bob2o$162bo3bo$161bo$
162bo$161b3o58$6b2o$5b2o$6bo2bo$7b3o$8bo63b4o$71bo3bo$23bobo25b2o19bo
4bo$22bo2b2o24b3o19bo2b2o$23bobo25b2o2$2b3o$2bobo$2o2bo$o$3o2$76bo$76b
2o$77bo$76bo$79b2o$69b2o7bob2o$69b2o$69bo2$65b3o274b3o$65b2o275bo$187b
2o153b2o2bo$187b3o154bobo$344b3o$191bo$191b2o$191b2o2$340bo$339bobo$
43bo295bob2o$42bo294b2obo$41b2o293bo2bo$41b2o294b2o$47bo290bo$44b3o$
44b2o10$334bobo$334bo$333b2o20bo$333bo5bo14b3o2$75b3o259b3o14bobo$76bo
259b2o17bo$77bo$72bo3bo$72b2obo$72bobo5$198b2o$197b2o2bo$197bo3bo$197b
4o$198bo4b2o70b3o$112b2o88bo10b2o60b2o$111bo90bo2bo5b3obo60bo2bo$111b
3o87b2ob2o5b2obo62b3o$111bo90b3o8b2o63b2o4bo8bo$108b3o97b2o5bo67bobo6b
o$107bobo98b2o74bo6b2o$107bobo97b2obo72b3o4bobo$207bob2o78b3o$38bobo
167bo2bo76bo$38b2obo313bo$38bo3bo311bobo$43bo309bo3bo$42bo312bo$41b3o$
62bo135bo135bo$63bo24bobo25b2o25b3o24bobo26bo24bobo25b2o25b3o24bobo26b
o29bo$61bo2bo22bo2b2o24b3o22b5o23bob2o24bo2bo22bo2b2o24b3o22b5o23bob2o
24bo2bo27b2o$63bo24bobo25b2o25b3o24bobo26bo24bobo25b2o25b3o24bobo26bo
28bo$37bo24bo135bo135bo30bo$36b3o322b2o$36bo323b2obo$37b2o$33b2o2bo$
32b2ob2o299bo$33bobo299b3o$192bo148b3o$85b2o104bobo141bobo4bobo$86b2o
248bo6b2o$83bo2bo104b2o2bo148bo$83b3o107bo2bo133bo$84bo99bo8bobo133b3o
$184bo143bo2bo$185bo141b2o$184bo143b2o$180b2obo$182bo2$250bobo$249bo2b
o$250bo2b2o2$252bobo$253bo9b2o$262b3o$261bo2bo$260b2o$260b3o11$257bo$
256bobo$257bo$256b3o3$287b2o$287b2o$287bo$284b3o$284b2o7$299b2o$300b2o
$297bo2bo$297b3o$258b2o5b2o31bo$257b4o3b4o$256b3ob2ob2ob3o7bobo$54b2o
201b4o3b4o8b2obo$53b2o203b2o5b2o9bobo$54bo2bo$55b3o$56bo235b3o$293bobo
$294b2o$295bo15$166b2o$168bo$166b3o$168bo$99b2o68b3o$100b3o67bobo$170b
obo$96bo5bo$96b2o$97bo$97bobo3$251bo$250bob2o$249bo$248bo$247bo4bo$
246bo5bo$247bo2b2o$247bo2$191b3o25b2o23b2o$191b5o22b3o23b2o$191b3o25b
2o24bo$241bo2$242b2o2bo$242b4obo$242b3obo$245b2o3b2o$245b3o$245b3o$
249bo8$173b2o$172b3o$173b2o$175b3o$175b3o$164bobo9bo$163bob2o$162bo3bo
$161bo$162bo$161b3o!
[[ AUTOSTART STOP 14280 STEP 34 ]]
Fancy stuff, explanations, weird XOR gate with negated output etc. will be described later. Only used p68 technology (right angle turn, eater, gun) and 2-0/2-1 glider collisions.

Is this the first outer-totalistic life-like rule with a unit cell for a Turing-complete rule other than CGoL/p30 compatible rules?

Post here later: ../forums/viewtopic.php?f=11&t=1921

Also lifewiki guns/rules section would worth an update IMHO.

Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

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

Post by Naszvadi » October 27th, 2017, 2:23 pm

Opening post is updated.

p30 technology can be used from B3/S23 to B38/S2378 efficiently, all'em have small p60 guns via period doubling, eaters and this p6 right angle reflector at bottom work well:

Code: Select all

x = 71, y = 65, rule = B38/S2378
55bo$53b3o$52bo$52b2o3$7b2o$8bo40b3o14bo$8bobo38bo2bo11b3o$9b2o8bo28bo
3bo10bo$15bo3bo2b2o24b4o11b2o$14bobobo5bo24bo$19bobo2b2o$19bo3b2o16b2o
$21b3o17bo19bo$39bobo9bo10bo$25b2o6b2o4b2o10b2o8bo$2o23bo6bo2bo15b2o$b
o30bo2b2o10b2o12bo$bobo27bo2b2o11bo11b2ob2o$2b2o4b2o6b2o6bo6b4o12b2o$
7bo2bo4b3o7bo32bobo$7bo2bo12b3o32bo3bo$7b2ob2o38bo7b2o2bo$9b2o7bobo29b
obo6b3o$18b3o29b2o3b2o3bo$56bo2$32bo$30bobo$31b2o10bo$42bo9b2o$42b3o7b
ob2o$52bo3bo$52b2o2bo$53b3o$38b2o14bo$38b2o2$56b2o$56bo$57b3o$59bo9b2o
$47bo21bo$45bobo19bobo$46b2o19b2o7$56bo$54bobo$55b2o2$57b2o$56bo2bo4b
2o$56bobo5b2o$57bo2$52b2o9b3o$53bo9b2obo2b2o$50b3o12b2o2b2o$50bo14b2o!
Reflector ripped from: Bumper

Unfortunately, stable Life reflectors are not versatile, they usually support at most 4 outer-totalistic rules between B3/S23 and B38/S238.

fluffykitty
Posts: 1175
Joined: June 14th, 2014, 5:03 pm
Contact:

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

Post by fluffykitty » October 29th, 2017, 11:54 am

What about the rules which are TC with finite initial patterns? You'd need a highly configurable puffer to generate the tag system sequences.

Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

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

Post by Naszvadi » November 1st, 2017, 6:46 pm

fluffykitty wrote:What about the rules which are TC with finite initial patterns? You'd need a highly configurable puffer to generate the tag system sequences.
It is impossible in Bank-I, for example. It is Turing-complete, if tiling is allowed as an initial configuration.

Here is a P256 unit cell in Banks-I emulating Rule-110 and pattern "000100" some P256*generations later:

Code: Select all

x = 1225, y = 804, rule = B3e4ejr5cinqy6-ei78/S012-e3-ajk4-akqw5-ajk6-e78:T1225,804
600b3o38b3o$600b2o39b3o$600b2o39b3o$600b2o39b3o$600b2o19bo19b3o$600b
22o19b3o$599b23o19b3o$602b20o3bo15b3o$602bo2bo14b6o15b3o$620b6o15b3o$
620b3o2bo15b3o$620b3o18b3o$620b4o17b3o$618b3o20b3o$619b2o20b3o$619b2o
20b3o$619b2o20b3o$609bo9b2o20b3o$609b12o20b3o$609b13o19b3o$605bo3b10o
22b3o$605b6o4bo2bo22b3o$605b6o30b3o$605bo2b3o30b3o$605bo2b3o30b3o$605b
6o19b5o6b3o$605b6o20b3o7b3o$605b6o20b3o7b3o$605bo4b24o7b3o$610b28o3b3o
$606bo3b21o3b3o4b3o$606b6o17b2o3b3o4b3o$606b6o17b2o3b3o4b3o$606bo2b3o
16b4o2b3o4b3o$609b3o22b3o4b3o$609b3o22b3o4b3o$608b4o22b3o4b3o$611b3o
20b3o4b3o$611b2o21b3o4b3o$611b2o21b3o4b3o$611b2o21b3o4b3o$611b2o8bo12b
3o4b3o$611b11o12b3o4b3o$610b12o12b3o4b3o$613b9o3bo8b3o4b3o$613bo6b6o8b
3o4b3o$620b6o8b3o4b3o$620b3o2bo8b3o4b3o$620b3o11b3o4b3o$620b4o10b3o4b
3o$618b3o13b3o4b3o$619b2o13b3o4b3o$619b2o13b3o4b3o$619b2o13b3o4b3o$
610bo8b2o13b3o4b3o$610b11o13b3o4b3o$610b12o12b3o4b3o$606bo3b9o15b3o2bo
b3o$606b6o6bo15b6ob3o$606b6o9bo2bo9b6ob3o$606bo2b3o9b15o3bob3o$609b3o
6b18o5b3o$609b3o7b17o5b3o$609b3o7b2o14bo5b3o$609b3o7b2o20b3o$609b3o7b
2o20b3o$609b3o7b2o20b3o$609b3o7b3o19b3o$609b3o4b4o21b3o$609b3o5b3o21b
3o$609b3o2bo2b3o3b4o14b3o$609b3o2b6o4b2o15b3o$609b3o2b6o4b2o15b3o$609b
3o2bo3b8o15b3o$609b3o6b12o11b3o$609b3o6b11o12b3o$609b3o6bo7b3o12b3o2bo
$609b3o11bo2b3o3b4o5b6o$609b3o11b6o4b2o3bo2b6o$609b3o11b6o4b2o3b5o3bo$
609b3o2b4o5bo3b8o3b5o$609b3o3b2o10b16o$609b3o3b2o3bo6b11o4bo$609b3o3b
6o6bo7b3o$608b13o6bo7b3o$612b11ob4o7b3o$612b3o6b7o7b3o$612b3o6bo4b4o2b
o2b3o$612b3o2bo8b3o3b6o$612b6o8b3o3b6o3bo$570bo2bo38b6o8b4o2bo3b6o$
570b44o3bo8b3o7b6o$567b47o12b3o7b6o3bo$568b46o6bo5b11o3b6o$568b2o43bo
6b17o3b6o$568b2o50b6o3b8o3b3o2bo$568b2o46bo3b6o3b2o5bo3b3o2bo$568b2o
46b6o3bo3b2o9b6o$568b3o45b6o6b4o8b6o$565b4o47bo2b3o14bo3b6o$566b3o50b
3o14b5o4bo$563bo2b3o40b4o6b3o14b5o$563b6o41b2o7b3o14b5o3bo$139bo255bo
167b6o41b2o7b3o14bo2b6o$140bo255bo166bo3b45o7b3o17b6o$567b49o3b3o17b3o
2bo$o566b48o4b3o17b3o2bo$139ob255ob172o44b3o4b3o17b6o$140ob255ob171o
44b3o4b3o17b6o$568o44b3o4b3o13bo3b6o$o564b3o44b3o4b3o13b5o4bo$565b3o
44b3o4b3o13b5o$565b3o44b3o3b4o13b5o3bo$562bo2b3o10b4o30b3o6b3o11bo2b6o
$562b6o11b2o31b3o6b2o15b6o$562b6o11b2o31b3o6b2o15b3o2bo$562bo3b15o31b
3o6b2o15b3o$566b19o27b3o6b2o15b4o$566b18o28b3o6b18o$566bo14b3o28b3o5b
19o$581b3o28b3o8b16o3bo$581b3o28b3o8bo3bo9b6o$581b3o28b3o22b6o$581b3o
28b3o11b9o2b3o2bo$581b3o25bo2b3o6b4o2b3o2b2o3b3o$581b3o25b6o7b2o3b3o2b
2o3b3o$581b3o25b6o7b2o3b7o3b3o$581b3o25bo3b11o3b14o$581b3o29b24o$581b
3o29b14o7b3o$581b3o29bo10b3o7b3o$581b3o40b3o6b5o$581b3o40b3o$581b3o40b
4o$581b3o38b3o$581b3o39b2o$581b3o39b2o$581b3o39b2o$581b3o19bo19b2o$
581b3o19b22o$581b3o19b23o$581b3o15bo3b20o$581b3o15b6o14bo2bo$581b3o15b
6o$581b3o15bo2b3o$581b3o18b3o$581b3o17b4o$581b3o20b3o$581b3o20b2o$581b
3o20b2o$581b3o20b2o$581b3o20b2o9bo$581b3o20b12o$581b3o19b13o$581b3o22b
10o3bo$581b3o22bo2bo4b6o$581b3o30b6o$581b3o30b3o2bo$581b3o30b3o2bo$
581b3o6b5o19b6o$581b3o7b3o20b6o$581b3o7b3o20b6o$581b3o7b24o4bo$581b3o
3b28o$581b3o4b3o3b21o3bo$581b3o4b3o3b2o17b6o$581b3o4b3o3b2o17b6o$581b
3o4b3o2b4o16b3o2bo$581b3o4b3o22b3o$581b3o4b3o22b3o$581b3o4b3o22b4o$
581b3o4b3o20b3o$581b3o4b3o21b2o$581b3o4b3o21b2o$581b3o4b3o21b2o$581b3o
4b3o12bo8b2o$581b3o4b3o12b11o$581b3o4b3o12b12o$581b3o4b3o8bo3b9o$581b
3o4b3o8b6o6bo$581b3o4b3o8b6o$581b3o4b3o8bo2b3o$581b3o4b3o11b3o$581b3o
4b3o10b4o$581b3o4b3o13b3o$581b3o4b3o13b2o$581b3o4b3o13b2o$581b3o4b3o
13b2o$581b3o4b3o13b2o8bo$581b3o4b3o13b11o$581b3o4b3o12b12o$581b3obo2b
3o15b9o3bo$581b3ob6o15bo6b6o$581b3ob6o9bo2bo9b6o$581b3obo3b15o9b3o2bo$
581b3o5b18o6b3o$581b3o5b17o7b3o$581b3o5bo14b2o7b3o$581b3o20b2o7b3o$
581b3o20b2o7b3o$581b3o20b2o7b3o$581b3o19b3o7b3o$581b3o21b4o4b3o$581b3o
21b3o5b3o$581b3o14b4o3b3o2bo2b3o$581b3o15b2o4b6o2b3o$581b3o15b2o4b6o2b
3o$581b3o15b8o3bo2b3o$581b3o11b12o6b3o$581b3o12b11o6b3o$578bo2b3o12b3o
7bo6b3o$578b6o5b4o3b3o2bo11b3o$578b6o2bo3b2o4b6o11b3o$578bo3b5o3b2o4b
6o11b3o$582b5o3b8o3bo5b4o2b3o$582b16o10b2o3b3o$582bo4b11o6bo3b2o3b3o$
587b3o7bo6b6o3b3o$587b3o7bo6b13o$587b3o7b16o$587b3o7b7o6b3o$587b3o2bo
2b4o4bo6b3o$587b6o3b3o8bo2b3o$583bo3b6o3b3o8b6o$583b6o3bo2b4o8b6o38bo
2bo$583b6o7b3o8bo3b44o$579bo3b6o7b3o12b47o$579b6o3b11o5bo6b46o$579b6o
3b17o6bo43b2o$579bo2b3o3b8o3b6o50b2o$579bo2b3o3bo5b2o3b6o3bo46b2o$579b
6o9b2o3bo3b6o46b2o$579b6o8b4o6b6o45b3o$579b6o3bo14b3o2bo47b4o$579bo4b
5o14b3o50b3o$584b5o14b3o6b4o40b3o2bo$580bo3b5o14b3o7b2o41b6o$580b6o2bo
14b3o7b2o41b6o167bo255bo$580b6o17b3o7b45o3bo166bo255bo$580bo2b3o17b3o
3b49o$580bo2b3o17b3o4b48o566bo$580b6o17b3o4b3o44b172ob395o$580b6o17b3o
4b3o44b171ob396o$580b6o3bo13b3o4b3o44b568o$580bo4b5o13b3o4b3o44b3o564b
o$585b5o13b3o4b3o44b3o$581bo3b5o13b4o3b3o44b3o$581b6o2bo11b3o6b3o30b4o
10b3o2bo$581b6o15b2o6b3o31b2o11b6o$581bo2b3o15b2o6b3o31b2o11b6o$584b3o
15b2o6b3o31b15o3bo$583b4o15b2o6b3o27b19o$586b18o6b3o28b18o$586b19o5b3o
28b3o14bo$582bo3b16o8b3o28b3o$582b6o9bo3bo8b3o28b3o$582b6o22b3o28b3o$
582bo2b3o2b9o11b3o28b3o$585b3o3b2o2b3o2b4o6b3o2bo25b3o$585b3o3b2o2b3o
3b2o7b6o25b3o$585b3o3b7o3b2o7b6o25b3o$584b14o3b11o3bo25b3o$588b24o29b
3o$588b3o7b14o29b3o$588b3o7b3o10bo29b3o$587b5o6b3o40b3o$598b3o40b3o$
597b4o40b3o$600b3o38b3o$600b2o39b3o$600b2o39b3o$600b2o39b3o$600b2o19bo
19b3o$600b22o19b3o$599b23o19b3o$602b20o3bo15b3o$602bo2bo14b6o15b3o$
620b6o15b3o$620b3o2bo15b3o$620b3o18b3o$620b4o17b3o$618b3o20b3o$619b2o
20b3o$619b2o20b3o$619b2o20b3o$609bo9b2o20b3o$609b12o20b3o$609b13o19b3o
$605bo3b10o22b3o$605b6o4bo2bo22b3o$605b6o30b3o$605bo2b3o30b3o$605bo2b
3o30b3o$605b6o19b5o6b3o$605b6o20b3o7b3o$605b6o20b3o7b3o$605bo4b24o7b3o
$610b28o3b3o$606bo3b21o3b3o4b3o$606b6o17b2o3b3o4b3o$606b6o17b2o3b3o4b
3o$606bo2b3o16b4o2b3o4b3o$609b3o22b3o4b3o$609b3o22b3o4b3o$608b4o22b3o
4b3o$611b3o20b3o4b3o$611b2o21b3o4b3o$611b2o21b3o4b3o$611b2o21b3o4b3o$
611b2o8bo12b3o4b3o$611b11o12b3o4b3o$610b12o12b3o4b3o$613b9o3bo8b3o4b3o
$613bo6b6o8b3o4b3o$620b6o8b3o4b3o$620b3o2bo8b3o4b3o$620b3o11b3o4b3o$
620b4o10b3o4b3o$618b3o13b3o4b3o$619b2o13b3o4b3o$619b2o13b3o4b3o$619b2o
13b3o4b3o$610bo8b2o13b3o4b3o$610b11o13b3o4b3o$610b12o12b3o4b3o$606bo3b
9o15b3o2bob3o$606b6o6bo15b6ob3o$606b6o9bo2bo9b6ob3o$606bo2b3o9b15o3bob
3o$609b3o6b18o5b3o$609b3o7b17o5b3o$609b3o7b2o14bo5b3o$609b3o7b2o20b3o$
609b3o7b2o20b3o$609b3o7b2o20b3o$609b3o7b3o19b3o$609b3o4b4o21b3o$609b3o
5b3o21b3o$609b3o2bo2b3o3b4o14b3o$609b3o2b6o4b2o15b3o$609b3o2b6o4b2o15b
3o$609b3o2bo3b8o15b3o$609b3o6b12o11b3o$609b3o6b11o12b3o$609b3o6bo7b3o
12b3o2bo$609b3o11bo2b3o3b4o5b6o$609b3o11b6o4b2o3bo2b6o$609b3o11b6o4b2o
3b5o3bo$609b3o2b4o5bo3b8o3b5o$609b3o3b2o10b16o$609b3o3b2o3bo6b11o4bo$
609b3o3b6o6bo7b3o$608b13o6bo7b3o$612b16o7b3o$612b3o6b7o7b3o$612b3o6bo
4b4o2bo2b3o$612b3o2bo8b3o3b6o$612b6o8b3o3b6o3bo$570bo2bo38b6o8b4o2bo3b
6o$570b44o3bo8b3o7b6o$567b47o12b3o7b6o3bo$568b46o6bo5b11o3b6o$568b2o
43bo6b17o3b6o$568b2o50b6o3b8o3b3o2bo$568b2o46bo3b6o3b2o5bo3b3o2bo$568b
2o46b6o3bo3b2o9b6o$568b3o45b6o6b4o8b6o$565b4o47bo2b3o14bo3b6o$566b3o
50b3o14b5o4bo$563bo2b3o40b4o6b3o14b5o$563b6o41b2o7b3o14b5o3bo$139bo
255bo167b6o41b2o7b3o14bo2b6o$140bo255bo166bo3b45o7b3o17b6o$567b49o3b3o
17b3o2bo$o566b48o4b3o17b3o2bo$139ob255ob172o44b3o4b3o17b6o$140ob255ob
171o44b3o4b3o17b6o$568o44b3o4b3o13bo3b6o$o564b3o44b3o4b3o13b5o4bo$565b
3o44b3o4b3o13b5o$565b3o44b3o3b4o13b5o3bo$562bo2b3o10b4o30b3o6b3o11bo2b
6o$562b6o11b2o31b3o6b2o15b6o$562b6o11b2o31b3o6b2o15b3o2bo$562bo3b15o
31b3o6b2o15b3o$566b19o27b3o6b2o15b4o$566b18o28b3o6b18o$566bo14b3o28b3o
5b19o$581b3o28b3o8b16o3bo$581b3o28b3o8bo3bo9b6o$581b3o28b3o22b6o$581b
3o28b3o11b9o2b3o2bo$581b3o25bo2b3o6b4o2b3o2b2o3b3o$581b3o25b6o7b2o3b3o
2b2o3b3o$581b3o25b6o7b2o3b7o3b3o$581b3o25bo3b11o3b14o$581b3o29b24o$
581b3o29b14o7b3o$581b3o29bo10b3o7b3o$581b3o40b3o6b5o$581b3o40b3o$581b
3o40b4o$581b3o38b3o$581b3o39b2o$581b3o39b2o$581b3o39b2o$581b3o19bo19b
2o$581b3o19b22o$581b3o19b23o$581b3o15bo3b20o$581b3o15b6o14bo2bo$581b3o
15b6o$581b3o15bo2b3o$581b3o18b3o$581b3o17b4o$581b3o20b3o$581b3o20b2o$
581b3o20b2o$581b3o20b2o$581b3o20b2o9bo$581b3o20b12o$581b3o19b13o$581b
3o22b10o3bo$581b3o22bo2bo4b6o$581b3o30b6o$581b3o30b3o2bo$581b3o30b3o2b
o$581b3o6b5o19b6o$581b3o7b3o20b6o$581b3o7b3o20b6o$581b3o7b24o4bo$581b
3o3b28o$581b3o4b3o3b21o3bo$581b3o4b3o3b2o17b6o$581b3o4b3o3b2o17b6o$
581b3o4b3o2b4o16b3o2bo$581b3o4b3o22b3o$581b3o4b3o22b3o$581b3o4b3o22b4o
$581b3o4b3o20b3o$581b3o4b3o21b2o$581b3o4b3o21b2o$581b3o4b3o21b2o$581b
3o4b3o12bo8b2o$581b3o4b3o12b11o$581b3o4b3o12b12o$581b3o4b3o8bo3b9o$
581b3o4b3o8b6o6bo$581b3o4b3o8b6o$581b3o4b3o8bo2b3o$581b3o4b3o11b3o$
581b3o4b3o10b4o$581b3o4b3o13b3o$581b3o4b3o13b2o$581b3o4b3o13b2o$581b3o
4b3o13b2o$581b3o4b3o13b2o8bo$581b3o4b3o13b11o$581b3o4b3o12b12o$581b3ob
o2b3o15b9o3bo$581b3ob6o15bo6b6o$581b3ob6o9bo2bo9b6o$581b3obo3b15o9b3o
2bo$581b3o5b18o6b3o$581b3o5b17o7b3o$581b3o5bo14b2o7b3o$581b3o20b2o7b3o
$581b3o20b2o7b3o$581b3o20b2o7b3o$581b3o19b3o7b3o$581b3o21b4o4b3o$581b
3o21b3o5b3o$581b3o14b4o3b3o2bo2b3o$581b3o15b2o4b6o2b3o$581b3o15b2o4b6o
2b3o$581b3o15b8o3bo2b3o$581b3o11b12o6b3o$581b3o12b11o6b3o$578bo2b3o12b
3o7bo6b3o$578b6o5b4o3b3o2bo11b3o$578b6o2bo3b2o4b6o11b3o$578bo3b5o3b2o
4b6o11b3o$582b5o3b8o3bo5b4o2b3o$582b16o10b2o3b3o$582bo4b11o6bo3b2o3b3o
$587b3o7bo6b6o3b3o$587b3o7bo6b13o$587b3o7b16o$587b3o7b7o6b3o$587b3o2bo
2b4o4bo6b3o$587b6o3b3o8bo2b3o$583bo3b6o3b3o8b6o$583b6o3bo2b4o8b6o38bo
2bo$583b6o7b3o8bo3b44o$579bo3b6o7b3o12b47o$579b6o3b11o5bo6b46o$579b6o
3b17o6bo43b2o$579bo2b3o3b8o3b6o50b2o$579bo2b3o3bo5b2o3b6o3bo46b2o$579b
6o9b2o3bo3b6o46b2o$579b6o8b4o6b6o45b3o$579b6o3bo14b3o2bo47b4o$579bo4b
5o14b3o50b3o$584b5o14b3o6b4o40b3o2bo$580bo3b5o14b3o7b2o41b6o$580b6o2bo
14b3o7b2o41b6o167bo255bo$580b6o17b3o7b45o3bo166bo255bo$580bo2b3o17b3o
3b49o$580bo2b3o17b3o4b48o566bo$580b6o17b3o4b3o44b172ob255ob139o$580b6o
17b3o4b3o44b171ob255ob140o$580b6o3bo13b3o4b3o44b568o$580bo4b5o13b3o4b
3o44b3o564bo$585b5o13b3o4b3o44b3o$581bo3b5o13b4o3b3o44b3o$581b6o2bo11b
3o6b3o30b4o10b3o2bo$581b6o15b2o6b3o31b2o11b6o$581bo2b3o15b2o6b3o31b2o
11b6o$584b3o15b2o6b3o31b15o3bo$583b4o15b2o6b3o27b19o$586b18o6b3o28b18o
$586b19o5b3o28b3o14bo$582bo3b16o8b3o28b3o$582b6o9bo3bo8b3o28b3o$582b6o
22b3o28b3o$582bo2b3o2b9o11b3o28b3o$585b3o3b2o2b3o2b4o6b3o2bo25b3o$585b
3o3b2o2b3o3b2o7b6o25b3o$585b3o3b7o3b2o7b6o25b3o$584b14o3b11o3bo25b3o$
588b24o29b3o$588b3o7b14o29b3o$588b3o7b3o10bo29b3o$587b5o6b3o40b3o$598b
3o40b3o$597b4o40b3o$600b3o38b3o$600b2o39b3o$600b2o39b3o$600b2o39b3o$
600b2o19bo19b3o$600b22o19b3o$599b23o19b3o$602b20o3bo15b3o$602bo2bo14b
6o15b3o$620b6o15b3o$620b3o2bo15b3o$620b3o18b3o$620b4o17b3o$618b3o20b3o
$619b2o20b3o$619b2o20b3o$619b2o20b3o$609bo9b2o20b3o$609b12o20b3o$609b
13o19b3o$605bo3b10o22b3o$605b6o4bo2bo22b3o$605b6o30b3o$605bo2b3o30b3o$
605bo2b3o30b3o$605b6o19b5o6b3o$605b6o20b3o7b3o$605b6o20b3o7b3o$605bo4b
24o7b3o$610b28o3b3o$606bo3b21o3b3o4b3o$606b6o17b2o3b3o4b3o$606b6o17b2o
3b3o4b3o$606bo2b3o16b4o2b3o4b3o$609b3o22b3o4b3o$609b3o22b3o4b3o$608b4o
22b3o4b3o$611b3o20b3o4b3o$611b2o21b3o4b3o$611b2o21b3o4b3o$611b2o21b3o
4b3o$611b2o8bo12b3o4b3o$611b11o12b3o4b3o$610b12o12b3o4b3o$613b9o3bo8b
3o4b3o$613bo6b6o8b3o4b3o$620b6o8b3o4b3o$620b3o2bo8b3o4b3o$620b3o11b3o
4b3o$620b4o10b3o4b3o$618b3o13b3o4b3o$619b2o13b3o4b3o$619b2o13b3o4b3o$
619b2o13b3o4b3o$610bo8b2o13b3o4b3o$610b11o13b3o4b3o$610b12o12b3o4b3o$
606bo3b9o15b3o2bob3o$606b6o6bo15b6ob3o$606b6o9bo2bo9b6ob3o$606bo2b3o9b
15o3bob3o$609b3o6b18o5b3o$609b3o7b17o5b3o$609b3o7b2o14bo5b3o$609b3o7b
2o20b3o$609b3o7b2o20b3o$609b3o7b2o20b3o$609b3o7b3o19b3o$609b3o4b4o21b
3o$609b3o5b3o21b3o$609b3o2bo2b3o3b4o14b3o$609b3o2b6o4b2o15b3o$609b3o2b
6o4b2o15b3o$609b3o2bo3b8o15b3o$609b3o6b12o11b3o$609b3o6b11o12b3o$609b
3o6bo7b3o12b3o2bo$609b3o11bo2b3o3b4o5b6o$609b3o11b6o4b2o3bo2b6o$609b3o
11b6o4b2o3b5o3bo$609b3o2b4o5bo3b8o3b5o$609b3o3b2o10b16o$609b3o3b2o3bo
6b11o4bo$609b3o3b6o6bo7b3o$608b13o6bo7b3o$612b11ob4o7b3o$612b3o6b7o7b
3o$612b3o6bo4b4o2bo2b3o$612b3o2bo8b3o3b6o$612b6o8b3o3b6o3bo$570bo2bo
38b6o8b4o2bo3b6o$570b44o3bo8b3o7b6o$567b47o12b3o7b6o3bo$568b46o6bo5b
11o3b6o$568b2o43bo6b17o3b6o$568b2o50b6o3b8o3b3o2bo$568b2o46bo3b6o3b2o
5bo3b3o2bo$568b2o46b6o3bo3b2o9b6o$568b3o45b6o6b4o8b6o$565b4o47bo2b3o
14bo3b6o$566b3o50b3o14b5o4bo$563bo2b3o40b4o6b3o14b5o$563b6o41b2o7b3o
14b5o3bo$139bo255bo167b6o41b2o7b3o14bo2b6o$140bo255bo166bo3b45o7b3o17b
6o$567b49o3b3o17b3o2bo$o566b48o4b3o17b3o2bo$395ob172o44b3o4b3o17b6o$
396ob171o44b3o4b3o17b6o$568o44b3o4b3o13bo3b6o$o564b3o44b3o4b3o13b5o4bo
$565b3o44b3o4b3o13b5o$565b3o44b3o3b4o13b5o3bo$562bo2b3o10b4o30b3o6b3o
11bo2b6o$562b6o11b2o31b3o6b2o15b6o$562b6o11b2o31b3o6b2o15b3o2bo$562bo
3b15o31b3o6b2o15b3o$566b19o27b3o6b2o15b4o$566b18o28b3o6b18o$566bo14b3o
28b3o5b19o$581b3o28b3o8b16o3bo$581b3o28b3o8bo3bo9b6o$581b3o28b3o22b6o$
581b3o28b3o11b9o2b3o2bo$581b3o25bo2b3o6b4o2b3o2b2o3b3o$581b3o25b6o7b2o
3b3o2b2o3b3o$581b3o25b6o7b2o3b7o3b3o$581b3o25bo3b11o3b14o$581b3o29b24o
$581b3o29b14o7b3o$581b3o29bo10b3o7b3o$581b3o40b3o6b5o$581b3o40b3o$581b
3o40b4o$581b3o38b3o$581b3o39b2o$581b3o39b2o$581b3o39b2o$581b3o19bo19b
2o$581b3o19b22o$581b3o19b23o$581b3o15bo3b20o$581b3o15b6o14bo2bo$581b3o
15b6o$581b3o15bo2b3o$581b3o18b3o$581b3o17b4o$581b3o20b3o$581b3o20b2o$
581b3o20b2o$581b3o20b2o$581b3o20b2o9bo$581b3o20b12o$581b3o19b13o$581b
3o22b10o3bo$581b3o22bo2bo4b6o$581b3o30b6o$581b3o30b3o2bo$581b3o30b3o2b
o$581b3o6b5o19b6o$581b3o7b3o20b6o$581b3o7b3o20b6o$581b3o7b24o4bo$581b
3o3b28o$581b3o4b3o3b21o3bo$581b3o4b3o3b2o17b6o$581b3o4b3o3b2o17b6o$
581b3o4b3o2b4o16b3o2bo$581b3o4b3o22b3o$581b3o4b3o22b3o$581b3o4b3o22b4o
$581b3o4b3o20b3o$581b3o4b3o21b2o$581b3o4b3o21b2o$581b3o4b3o21b2o$581b
3o4b3o12bo8b2o$581b3o4b3o12b11o$581b3o4b3o12b12o$581b3o4b3o8bo3b9o$
581b3o4b3o8b6o6bo$581b3o4b3o8b6o$581b3o4b3o8bo2b3o$581b3o4b3o11b3o$
581b3o4b3o10b4o$581b3o4b3o13b3o$581b3o4b3o13b2o$581b3o4b3o13b2o$581b3o
4b3o13b2o$581b3o4b3o13b2o8bo$581b3o4b3o13b11o$581b3o4b3o12b12o$581b3ob
o2b3o15b9o3bo$581b3ob6o15bo6b6o$581b3ob6o9bo2bo9b6o$581b3obo3b15o9b3o
2bo$581b3o5b18o6b3o$581b3o5b17o7b3o$581b3o5bo14b2o7b3o$581b3o20b2o7b3o
$581b3o20b2o7b3o$581b3o20b2o7b3o$581b3o19b3o7b3o$581b3o21b4o4b3o$581b
3o21b3o5b3o$581b3o14b4o3b3o2bo2b3o$581b3o15b2o4b6o2b3o$581b3o15b2o4b6o
2b3o$581b3o15b8o3bo2b3o$581b3o11b12o6b3o$581b3o12b11o6b3o$578bo2b3o12b
3o7bo6b3o$578b6o5b4o3b3o2bo11b3o$578b6o2bo3b2o4b6o11b3o$578bo3b5o3b2o
4b6o11b3o$582b5o3b8o3bo5b4o2b3o$582b16o10b2o3b3o$582bo4b11o6bo3b2o3b3o
$587b3o7bo6b6o3b3o$587b3o7bo6b13o$560bo2bo2bo2bo2bo14b3o7b4ob11o10bo2b
o2bo2bo2bo$587b3o7b7o6b3o$587b3o2bo2b4o4bo6b3o$587b6o3b3o8bo2b3o$583bo
3b6o3b3o2bo5b6o$583b6o3bo2b4o8b6o38bo2bo$583b6o7b3o2bo5bo3b44o$579bo3b
6o7b3o12b47o$579b6o3b11o5bo6b46o$579b6o3b17o6bo43b2o$579bo2b3o3b8o3b6o
50b2o$579bo2b3o3bo5b2o3b6o3bo46b2o$579b6o9b2o3bo3b6o46b2o$579b6o8b4o6b
6o45b3o$579b6o3bo14b3o2bo47b4o$579bo4b5o14b3o50b3o$584b5o14b3o6b4o40b
3o2bo$580bo3b5o14b3o7b2o41b6o$580b6o2bo14b3o7b2o41b6o167bo255bo$580b6o
17b3o7b45o3bo166bo255bo$580bo2b3o17b3o3b49o$580bo2b3o17b3o4b48o566bo$
580b6o17b3o4b3o44b568o$580b6o17b3o4b3o44b568o$580b6o3bo13b3o4b3o44b
568o$580bo4b5o13b3o4b3o44b3o564bo$585b5o13b3o4b3o44b3o$581bo3b5o13b4o
3b3o44b3o$581b6o2bo11b3o6b3o30b4o10b3o2bo$581b6o15b2o6b3o31b2o11b6o$
581bo2b3o15b2o6b3o31b2o11b6o$584b3o15b2o6b3o31b15o3bo$583b4o15b2o6b3o
27b19o$586b18o6b3o28b18o$586b19o5b3o28b3o14bo$582bo3b16o8b3o28b3o$582b
6o9bo3bo8b3o28b3o$582b6o22b3o28b3o$582bo2b3o2b9o11b3o28b3o$585b3o3b2o
2b3o2b4o6b3o2bo25b3o$585b3o3b2o2b3o3b2o7b6o25b3o$585b3o3b7o3b2o7b6o25b
3o$584b14o3b11o3bo25b3o$588b24o29b3o$588b3o7b14o29b3o$588b3o7b3o10bo
29b3o$587b5o6b3o40b3o$598b3o40b3o$597b4o40b3o!
Usual printer tape on the sides. Unit cell connected alternately depending the parity of their positions in the 1D cellspace. An empty cell is a still life. ~134 is the cell width.

Hensel isotropic rulestring: B3e4ejr5cinqy6-ei78/S012-e3-ajk4-akqw5-ajk6-e78 (published here earlier by a conwaylife forum member)
More on this rule in the examples delivered with golly and the rule is defined there is a built-in.
More on this rule on the internet: http://www.bottomlayer.com/bottom/banks ... entary.htm

Thanks to Edwin Roger Banks for his PhD thesis (1971) and to the golly stuff!

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

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

Post by dvgrn » November 1st, 2017, 8:32 pm

Naszvadi wrote:Hensel isotropic rulestring: B3e4ejr5cinqy6-ei78/S012-e3-ajk4-akqw5-ajk6-e78 (published here earlier by a conwaylife forum member)
More on this rule in the examples delivered with golly and the rule is defined there is a built-in.
It's kind of funny that the rule is so much simpler than the isotropic rulestring makes it out to be -- it's just

Code: Select all

neighborhood:vonNeumann
symmetries:rotate4reflect
111000
011101
011111
... but the isotropic rulestring has to mention not only those birth and survival conditions based on orthogonal neighbors, but also all the combinations of ways that corner-neighbor cells can happen to be ON or OFF, even though we don't really care about them.

Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

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

Post by Naszvadi » November 19th, 2017, 1:12 pm

dvgrn wrote:
Naszvadi wrote:Hensel isotropic rulestring: B3e4ejr5cinqy6-ei78/S012-e3-ajk4-akqw5-ajk6-e78 (published here earlier by a conwaylife forum member)
More on this rule in the examples delivered with golly and the rule is defined there is a built-in.
It's kind of funny that the rule is so much simpler than the isotropic rulestring makes it out to be -- it's just

Code: Select all

neighborhood:vonNeumann
symmetries:rotate4reflect
111000
011101
011111
... but the isotropic rulestring has to mention not only those birth and survival conditions based on orthogonal neighbors, but also all the combinations of ways that corner-neighbor cells can happen to be ON or OFF, even though we don't really care about them.
Yes, this was the bait :)

So, basically Banks-I rule is a (von)Neumann isotropic rule, but as a ruletable, with so little number of transitions.

Just a reminder: it would be nice if Golly could support nontotalistic isotropic Neumann rules e.g. with rulestrings B34/S012n34V , where n in 2n strands for "near", and "o" for "opposite" in other cases.

Well, the (rather) incomplete background story of creating the W110 unit cell in Banks-I:

First of all, tried to create an XOR-gate in several weeks, and constructed this working instance:

Code: Select all

x = 119, y = 353, rule = B3e4ejr5cinqy6-ei78/S012-e3-ajk4-akqw5-ajk6-e78
68bo$66b3o$67b2o$67b2o$67b2o$67b2o$67b2o$67b2o$67bobo$64b3o$65b3o$65b
3o$65b3o$65b3o8bo$65b3o8b3o$65b3o8bo2bo$65b3o8bo2bo$65b3o9b2o$65b3o$
65b3o$65b3o$65b3o$65b3o$65b3o$65bobo$65b2o$65b3o$65b3o$65b3o$65b3o$65b
3o$65b3o$65b3o$65b3o$65b3o$65b3o$65b3o$62bo2b3o$62b6o$62b3ob2o2bo31b2o
$54b5o3bo4b4o30bo2bo$55b3o8b5o30bo2bo$55b3o8b5o31b4o$47bo8b11o3bo$45b
3o3b3obob10o$46b2o4b3o3b9o$46b2o4b3o4bo4b3o$46b2o4b3o3b2o4b3o$46b2o4b
3o2b4o3b3o16b5o$46b2o4b3o6bo2b3o17b3o23bo$46b2o4b3o6b6o17b3o24b8o$46bo
bo3b3o6b6o17b9ob15ob8o$43b3o3bo2b3o6bo3b13ob15ob15o7bo$44b3o2b6o10b14o
b4o4b22o$44b3o2bobob2o10b19o3b2o20bo$41bo2b3o2bo4b12o3bo11b3o4bo$41b6o
6bob11o15bobo2b4o$41b6o6b2ob10o15b2o$41bo3b7obo3bo5b3o15b3o$45b8o10b3o
15b3o$45b9o9b3o15b3o$42b4o3bo3bo8b4o15b3o$43b3o17bobo5bo9b3o$43b3o17b
3o5b9ob3o$43b3o17bob9ob4o2b3o$43b3o13b12o7bo2b3o$31bo11b3o14b3o4b4o10b
3o$21b2o2bo2bob3o10b3o14bobo3b2o2bo7bo2b3o$20bo2bobo2bo2bo11b3o14b2o4b
2o10b6o$20bo2bobo2bo2bo11b3o14b3o2b4o9bob4o2bo$21b2o3b2o4bo10b3o11bo2b
3o15bo3b5o$43b3o11b6o19b5o$43b3o11b6o20b4o$40bo2b3o11bo3b6ob15o3bo$40b
6o15b7ob14o$40b6o15b22o$40bo3b18o3bo16bo$44b18o$o43b18o$45o3bo12bo$45o
$45o$o43bo8$68bo$66b3o$67b2o$67b2o$67b2o$67b2o$67b2o$67b2o$67bobo$64b
3o$65b3o$65b3o$65b3o$65b3o$65b3o$65b3o$65b3o$65b3o$65b3o$65b3o$65b4o$
65b3o$65b3o$65b3o$65b3o$65b3o$65b3o$65b3o$65b3o$65b3o$65b3o$65b3o$65b
3o$65b3o$65b3o$65b3o$65b3o$62bo2b3o$62b6o$62b6o2bo31b2o$54b5o3bo3b5o
30bo2bo$55b3o8b5o30bo2bo$55b3o8b5o31b4o$47bo7b12o3bo$45b3o3b16o$46b2o
4b3o3b9o$46b2o4b3o3b2o4b3o$46b2o4b3o3b2o4b3o$46b2o4b3o2b4o3b3o16b5o$
46b2o4b3o6bo2b3o17b3o23bo$46b2o4b3o6b6o17b3o24b8o$46bobo3b3o6b6o17b9ob
15ob8o$43b3o3bo2b3o6bo3b13ob15ob15o7bo$44b3o2b6o10b14ob4o4b22o$44b3o2b
6o10b19o3b2o20bo$41bo2b3o2bo3b13o3bo11b3o4bo$41b6o6b13o15bobo2b4o$41b
6o6b13o15b2o$41bo3b9o3bo5b3o15b3o$45b9o9b3o15b3o$45b9o9b3o15b3o$42b4o
3bo3bo8b4o15b3o$43b3o17bobo5bo9b3o$43b3o17b3o5b9ob3o$43b3o17bob9ob4o2b
3o$43b3o13b12o7bo2b3o$31bo11bobo14b3o4b4o10b3o$21b2o2bo2bob3o10b2o15bo
bo3b2o2bo7bo2b3o$20bo2bobo2bo2bo11b3o14b2o4b2o10b6o$20bo2bobo2bo2bo11b
3o14b3o2b4o9bob4o2bo$21b2o3b2o4bo10b3o11bo2b3o15bo3b5o$43b3o11b6o19b5o
$43b3o11b6o20b4o$40bo2b3o11bo3b6ob15o3bo$40b6o15b7ob14o$40b3ob2o15b22o
$40bo3b18o3bo16bo$44bobob14o$o43b18o$9ob15ob15ob3o3bo12bo$10ob15ob15ob
2o$45o$o43bo8$68bo$66b3o$67b2o$67b2o$67b2o$67b2o$67b2o$67b2o$67bobo$
64b3o$65b3o$65b3o$65b3o$65b3o8bo$65b3o8b3o$65b3o8bo2bo$65b3o8bo2bo$65b
3o9b2o$65b3o$65b3o$65b3o$65b3o$65b3o$65b3o$65bobo$65b2o$65b3o$65b3o$
65b3o$65b3o$65b3o$65b3o$65b3o$65b3o$65b3o$65b3o$65b3o$62bo2b3o$62b6o$
62b3ob2o2bo$54b5o3bo4b4o$55b3o8b5o$55b3o8b5o$47bo8b11o3bo$45b3o3b3obob
10o$46b2o4b3o3b9o$46b2o4b3o4bo4b3o$46b2o4b3o3b2o4b3o$46b2o4b3o2b4o3b3o
16b5o$46b2o4b3o6bo2b3o17b3o23bo$46b2o4b3o6b6o17b3o7bo16b8o$46bobo3b3o
6b2ob3o17b25ob8o$43b3o3bo2b3o6bo3b45o7bo$44b3o2b6o11b18o3b23o$44b3o2b
6o10bob17o3b2o20bo$41bo2b3o2bo3b12o4bo11b3o3b2o$41b6o6b13o15b3o2b4o$
41b6o6b13o15b3o$41bo3b9o3bo5b3o15b3o$45b9o9b3o15b3o$45b9o9b3o15b3o$42b
4o3bo3bo8b4o15b3o$43b3o17b3o5bo9b3o$43b3o17b3o5b9ob3o$43b3o17b11ob4o2b
3o$43b3o13b12o7bo2b3o$31bo11bobo14b3o3b5o10b3o$21b2o2bo2bob3o10b2o15b
3o3b2o2bo7bo2b3o$20bo2bobo2bo2bo11b3o14b3o3b2o10b6o$20bo2bobo2bo2bo11b
3o14b3o2b4o9b6o2bo$21b2o3b2o4bo10b3o11bo2b3o15bo3b5o$43b3o11b6o19b5o$
43b3o11b6o19b5o$40bo2b3o11bo3b22o3bo$40b6o15b22o$40b3ob2o15b22o$40bo3b
18o3bo16bo$44bobob14o$o43b18o$9ob15ob15ob3o3bo12bo$10ob15ob15ob2o$45o$
o43bo8$68bo$66b3o$67b2o$67b2o$67b2o$67b2o$67b2o$67b2o$67bobo$64b3o$65b
3o$65b3o$65b3o$65b3o$65b3o$65b3o$65b3o$65b3o$65b3o$65b3o$65b4o$65b3o$
65b3o$65b3o$65b3o$65b3o$65b3o$65b3o$65b3o$65b3o$65b3o$65b3o$65b3o$65b
3o$65b3o$65b3o$65b3o$62bo2b3o$62b6o$62b6o2bo$54b5o3bo3b5o$55b3o8b5o$
55b3o8b5o$47bo7b12o3bo$45b3o3b16o$46b2o4b3o3b9o$46b2o4b3o3b2o4b3o$46b
2o4b3o3b2o4b3o$46b2o4b3o2b4o3b3o16b5o$46b2o4b3o6bo2b3o17b3o23bo$46b2o
4b3o6b6o17b3o7bo16b8o$46bobo3b3o6b6o17b25ob8o$43b3o3bo2b3o6bo3b45o7bo$
44b3o2b6o10b19o3b23o$44b3o2b6o10b19o3b2o20bo$41bo2b3o2bo3b13o3bo11b3o
3b2o$41b6o6b13o15b3o2b4o$41b6o6b13o15b3o$41bo3b9o3bo5b3o15b3o$45b9o9b
3o15b3o$45b9o9b3o15b3o$42b4o3bo3bo8b4o15b3o$43b3o17bobo5bo9b3o$43b3o
17b3o5b9ob3o$43b3o17bob9ob4o2b3o$43b3o13b12o7bo2b3o$31bo11bobo14b3o4b
4o10b3o$21b2o2bo2bob3o10b2o15bobo3b2o2bo7bo2b3o$20bo2bobo2bo2bo11b3o
14b2o4b2o10b6o$20bo2bobo2bo2bo11b3o14b3o2b4o9b6o2bo$21b2o3b2o4bo10b3o
11bo2b3o15bo3b5o$43b3o11b6o19b5o$43b3o11b6o19b5o$40bo2b3o11bo3b22o3bo$
40b6o15b22o$40b6o15b22o$40bo3b10ob7o3bo16bo$44b11ob6o$o43b18o$45o3bo
12bo$45o$45o$o43bo!
After finishing the above gate, in 4-5 minutes constructed this much more smaller and stable XOR gate:

Code: Select all

x = 27, y = 59, rule = B3e4ejr5cinqy6-ei78/S012-e3-ajk4-akqw5-ajk6-e78
11b5o$12b3o5b5o$2b5o5b3o6b3o$3b3o6b3o6b3o$3b3o6b3o6b3o$3b3o6b3o6b3o$3b
3o6b3o6b3o$3b3o6b3o6b3o$3b3o6b3o6b3o$3b3o6b3o6b3o$3bobo6b3o6b3o$4b2o6b
3o6b3o$3b3o6b3o6b3o$3b3o6b3o6b3o$3b3o6b3o6b3o$3b3o6b3o6b3o$3b3o6b3o6b
3o$3b3o6b3o6b3o$3b3o6b3o6b3o$3b3o6b3o6b3o$3b3o6b3o6b3o$3b3o6b3o6b3o$3b
3o6b3o6b3o$3b3o6b3o6b3o$3b3o6b3o6b3o$3b3o6b3o6b3o$3b3o6b3o6b3o$3b3o6b
3o6b3o$3b3o6b3o6b3o$3b3o6b3o6b3o$3b3o6b3o6bobo$3b3o6b3o6b2o$3b3o6b3o6b
3o$3b3o6b3o6b3o$3b3o6b3o6b3o$3b3o6b3o6b3o$3b3o6b3o6b3o$3b3o6b3o6b3o$3b
3o6b3o6b3o$3b3o6b3o6b3o$3b3o6b3o6b3o$3b3o6b3o6b3o$3b3o6b3o6b3o$3b3o6b
3o6b3o$3bobo6b3o6b3o$4b2o6b3o6b3o$3b3o6b3o6bobo$3b3o6b3o3bo2b2o$3b3o2b
o3b3o3b6o$3b6o3b3o3b6o2bo$o2b6o3b3o3bo3b5o$5o3bo3b3o7b5o$5o7b3o7b5o$5o
7b11o3bo$o3b19o$4b8o3b8o$4b8o3b2o5bo$4bo6bo3b2o$14b4o!
After that, combining with signal splitters from Banks and the (x)and(not(y)) gate also from Banks, inclusive OR gate could be constructed and used in the unit cell. No crossroads were needed, just appropriate timings with delaying tricks (corners and side-changers, a right-angle turn from 1971 changes the side of the signal).

Also used an observation: the signal splitter is similar to the old (x)and(not(y)) gate, and they can be interbreed trivially, so the gate's output were duplicated immediately:

Code: Select all

x = 39, y = 41, rule = B3e4ejr5cinqy6-ei78/S012-e3-ajk4-akqw5-ajk6-e78
15bo$15b3o$15b2o$15b2o$15b2o$15b2o$15b2o$15b2o$15b2o$15b2o$15b2o$15b2o
$15b2o$15b2o$15b2o$15b2o$14bobo$17b3o$16b3o$16b3o$16b3o$16b4o$8bo7b3o$
8o8b3o$b8ob9o19bo$bo7b15ob14o$9b6o4b4ob15o$9bo4b2o3b20o$14bo4b3o16bo$
13b4o2bobo$20b2o$19b3o$19b3o$19b3o$19b3o$19b3o$19b3o$19b3o$19b3o$19b3o
$18b5o!
Unit cell has two states - and there is a generation among the 256 ones in which they differ only one cell, see here (the ON state cell is on top):

Code: Select all

x = 398, y = 281, rule = B3e4ejr5cinqy6-ei78/S012-e3-ajk4-akqw5-ajk6-e78
2b5o38b5o$3b3o40b3o$3b3o40b3o$3b3o40b4o$3b3o38b3o$3b3o39b2o$3b3o39b2o$
3b3o39b2o$3b3o20bo18b2o$3b3o20b21o$3b3o20b22o$3b3o16bo3b19o$3b3o16b6o
13bo2bo$3b3o16b6o$3b3o16bo2b3o$3b3o19b3o$3b3o18b4o$3b3o21b3o$3b3o21b2o
$3b3o21b2o$3b3o21b2o$3b3o21b2o8bo$3b3o21b11o$3b3o20b12o$3b3o23b9o3bo$
3b3o23bo2bo3b6o$3b3o30b6o$3b3o30b3o2bo$3b3o30b3o2bo$3b3o6b5o19b6o$3b3o
7b3o20b6o$3b3o7b3o20b6o$3b3o7b24o4bo$3b3o3b28o$3b3o4b3o3b21o3bo$3b3o4b
3o3b2o17b6o$3b3o4b3o3b2o17b6o$3b3o4b3o2b4o16b3o2bo$3b3o4b3o22b3o$3b3o
4b3o22b3o$3b3o4b3o22b4o$3b3o4b3o20b3o$3b3o4b3o21b2o$3b3o4b3o21b2o$3b3o
4b3o21b2o$3b3o4b3o12bo8b2o$3b3o4b3o12b11o$3b3o4b3o12b12o$3b3o4b3o8bo3b
9o$3b3o4b3o8b6o6bo$3b3o4b3o8b6o$3b3o4b3o8bo2b3o$3b3o4b3o11b3o$3b3o4b3o
10b4o$3b3o4b3o13b3o$3b3o4b3o13b2o$3b3o4b3o13b2o$3b3o4b3o13b2o$3b3o4b3o
13b2o8bo$3b3o4b3o13b11o$3b3o4b3o12b12o$3b3obo2b3o15b9o3bo$3b3ob6o15bo
6b6o$3b3ob6o9bo2bo9b6o$3b3obo3b15o9b3o2bo$3b3o5b18o6b3o$3b3o5b17o7b3o$
3b3o5bo14b2o7b3o$3b3o20b2o7b3o$3b3o20b2o7b3o$3b3o20b2o7b3o$3b3o19b3o7b
3o$3b3o21b4o4b3o$3b3o21b3o5b3o$3b3o14b4o3b3o2bo2b3o$3b3o15b2o4b6o2b3o$
3b3o15b2o4b6o2b3o$3b3o15b8o3bo2b3o$3b3o11b12o6b3o$3b3o12b11o6b3o$o2b3o
12b3o7bo6b3o$6o5b4o3b3o2bo11b3o$6o2bo3b2o4b6o11b3o$o3b5o3b2o4b6o11b3o$
4b5o3b8o3bo5b4o2b3o$4b16o10b2o3b3o$4bo4b11o6bo3b2o3b3o$9b3o7bo6b6o3b3o
$9b3o7bo6b13o$9b3o7b4ob11o$9b3o7b7o6b3o$9b3o2bo2b4o4bo6b3o$9b6o3b3o8bo
2b3o$5bo3b6o3b3o8b6o$5b6o3bo2b4o8b6o38bo2bo$5b6o7b3o8bo3b44o$bo3b6o7b
3o12b47o$b6o3b11o5bo6b46o$b6o3b17o6bo43b2o$bo2b3o3b8o3b6o50b2o$bo2b3o
3bo5b2o3b6o3bo46b2o$b6o9b2o3bo3b6o46b2o$b6o8b4o6b6o45b3o$b6o3bo14b3o2b
o47b4o$bo4b5o14b3o50b3o$6b5o14b3o6b4o40b3o2bo$2bo3b5o14b3o7b2o41b6o$2b
6o2bo14b3o7b2o41b6o$2b6o17b3o7b45o3bo$2bo2b3o17b3o3b49o$2bo2b3o17b3o4b
48o317bo$2b6o17b3o4b3o44b319o$2b6o17b3o4b3o44b319o$2b6o3bo13b3o4b3o44b
319o$2bo4b5o13b3o4b3o44b3o315bo$7b5o13b3o4b3o44b3o$3bo3b5o13b4o3b3o44b
3o$3b6o2bo11b3o6b3o30b4o10b3o2bo$3b6o15b2o6b3o31b2o11b6o$3bo2b3o15b2o
6b3o31b2o11b6o$6b3o15b2o6b3o31b15o3bo$5b4o15b2o6b3o27b19o$8b18o6b3o28b
18o$8b19o5b3o28b3o14bo$4bo3b16o8b3o28b3o$4b6o9bo3bo8b3o28b3o$4b6o22b3o
28b3o$4bo2b3o2b9o11b3o28b3o$7b3o3b2o2b3o2b4o6b3o2bo25b3o$7b3o3b2o2b3o
3b2o7b6o25b3o$7b3o3b7o3b2o7b6o25b3o$6b14o3b11o3bo25b3o$10b24o29b3o$10b
3o7b14o29b3o$10b3o7b3o10bo29b3o$9b5o6b3o40b3o$19b5o39b3o$62b5o6$2b5o
38b5o$3b3o40b3o$3b3o40b3o$3b3o40b4o$3b3o38b3o$3b3o39b2o$3b3o39b2o$3b3o
39b2o$3b3o20bo18b2o$3b3o20b21o$3b3o20b22o$3b3o16bo3b19o$3b3o16b6o13bo
2bo$3b3o16b6o$3b3o16bo2b3o$3b3o19b3o$3b3o18b4o$3b3o21b3o$3b3o21b2o$3b
3o21b2o$3b3o21b2o$3b3o21b2o8bo$3b3o21b11o$3b3o20b12o$3b3o23b9o3bo$3b3o
23bo2bo3b6o$3b3o30b6o$3b3o30b3o2bo$3b3o30b3o2bo$3b3o6b5o19b6o$3b3o7b3o
20b6o$3b3o7b3o20b6o$3b3o7b24o4bo$3b3o3b28o$3b3o4b3o3b21o3bo$3b3o4b3o3b
2o17b6o$3b3o4b3o3b2o17b6o$3b3o4b3o2b4o16b3o2bo$3b3o4b3o22b3o$3b3o4b3o
22b3o$3b3o4b3o22b4o$3b3o4b3o20b3o$3b3o4b3o21b2o$3b3o4b3o21b2o$3b3o4b3o
21b2o$3b3o4b3o12bo8b2o$3b3o4b3o12b11o$3b3o4b3o12b12o$3b3o4b3o8bo3b9o$
3b3o4b3o8b6o6bo$3b3o4b3o8b6o$3b3o4b3o8bo2b3o$3b3o4b3o11b3o$3b3o4b3o10b
4o$3b3o4b3o13b3o$3b3o4b3o13b2o$3b3o4b3o13b2o$3b3o4b3o13b2o$3b3o4b3o13b
2o8bo$3b3o4b3o13b11o$3b3o4b3o12b12o$3b3obo2b3o15b9o3bo$3b3ob6o15bo6b6o
$3b3ob6o9bo2bo9b6o$3b3obo3b15o9b3o2bo$3b3o5b18o6b3o$3b3o5b17o7b3o$3b3o
5bo14b2o7b3o$3b3o20b2o7b3o$3b3o20b2o7b3o$3b3o20b2o7b3o$3b3o19b3o7b3o$
3b3o21b4o4b3o$3b3o21b3o5b3o$3b3o14b4o3b3o2bo2b3o$3b3o15b2o4b6o2b3o$3b
3o15b2o4b6o2b3o$3b3o15b8o3bo2b3o$3b3o11b12o6b3o$3b3o12b11o6b3o$o2b3o
12b3o7bo6b3o$6o5b4o3b3o2bo11b3o$6o2bo3b2o4b6o11b3o$o3b5o3b2o4b6o11b3o$
4b5o3b8o3bo5b4o2b3o$4b16o10b2o3b3o$4bo4b11o6bo3b2o3b3o$9b3o7bo6b6o3b3o
$9b3o7bo6b13o$9b3o7b16o$9b3o7b7o6b3o$9b3o2bo2b4o4bo6b3o$9b6o3b3o8bo2b
3o$5bo3b6o3b3o8b6o$5b6o3bo2b4o8b6o38bo2bo$5b6o7b3o8bo3b44o$bo3b6o7b3o
12b47o$b6o3b11o5bo6b46o$b6o3b17o6bo43b2o$bo2b3o3b8o3b6o50b2o$bo2b3o3bo
5b2o3b6o3bo46b2o$b6o9b2o3bo3b6o46b2o$b6o8b4o6b6o45b3o$b6o3bo14b3o2bo
47b4o$bo4b5o14b3o50b3o$6b5o14b3o6b4o40b3o2bo$2bo3b5o14b3o7b2o41b6o$2b
6o2bo14b3o7b2o41b6o$2b6o17b3o7b45o3bo$2bo2b3o17b3o3b49o$2bo2b3o17b3o4b
48o317bo$2b6o17b3o4b3o44b319o$2b6o17b3o4b3o44b319o$2b6o3bo13b3o4b3o44b
319o$2bo4b5o13b3o4b3o44b3o315bo$7b5o13b3o4b3o44b3o$3bo3b5o13b4o3b3o44b
3o$3b6o2bo11b3o6b3o30b4o10b3o2bo$3b6o15b2o6b3o31b2o11b6o$3bo2b3o15b2o
6b3o31b2o11b6o$6b3o15b2o6b3o31b15o3bo$5b4o15b2o6b3o27b19o$8b18o6b3o28b
18o$8b19o5b3o28b3o14bo$4bo3b16o8b3o28b3o$4b6o9bo3bo8b3o28b3o$4b6o22b3o
28b3o$4bo2b3o2b9o11b3o28b3o$7b3o3b2o2b3o2b4o6b3o2bo25b3o$7b3o3b2o2b3o
3b2o7b6o25b3o$7b3o3b7o3b2o7b6o25b3o$6b14o3b11o3bo25b3o$10b24o29b3o$10b
3o7b14o29b3o$10b3o7b3o10bo29b3o$9b5o6b3o40b3o$19b5o39b3o$62b5o!

Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

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

Post by Naszvadi » November 21st, 2017, 4:19 pm

Naszvadi wrote:
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.
...

Code: Select all

big rle
...
There is an improvement (2017.11.21) a Glider-less W110 in Life, EightLife, Pedestrian Life and HoneyLife now have a constructive proof that they are computationally universal. See Unit cell here: ../forums/viewtopic.php?f=2&t=3154

Naszvadi
Posts: 1244
Joined: May 7th, 2016, 8:53 am
Contact:

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

Post by Naszvadi » January 17th, 2018, 4:59 am

Just a useful glider filter that deletes every second Glider from a period (8*k+4) stream; ripped from Life, namely the oscillator Blocker

Code: Select all

x = 23, y = 30, rule = B378/S23678
bo$2bo$3o3$6bo$7bo$5b3o3$11bo$12bo$10b3o3$16bo$17bo$15b3o3$21bo$22bo$
20b3o4$17bo$12b3ob2o2b2o$12b4o4b2o$16b2o!

Post Reply