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

Fun with Rule 110 unit cells

For discussion of specific patterns or specific families of patterns, both newly-discovered and well-known.

Fun with Rule 110 unit cells

Postby thorsilver » April 25th, 2018, 9:18 pm

So I've been developing some interesting patterns to show off as part of some lectures about computational universality, and ended up putting together a pattern that's kind of interesting to observe.

I went back to Matthew Cook's 2004 paper proving the universality of Wolfram Rule 110, then looked at a follow-up paper by Martinez (http://uncomp.uwe.ac.uk/genaro/rule110/ctsRule110.html) which implemented a very simple cyclic tag system construction in Rule 110. I took that construction and converted the initial condition to a single binary string, then fed it to Naszvadi's Rule 110 unit cell script from here: http://conwaylife.com/forums/viewtopic. ... 604#p38065

The result is the pattern below, which implements 56,240 Rule 110 unit cells, which in term implement a cyclic tag system. So in essence you can demonstrate the universality of GoL and Rule 110 simultaneously.

Of course the resulting pattern is huge so it can be hard to find where the action is -- zoom in quite close to the right-hand edge and you'll see the initial data encoded in a set of gliders, which as the pattern evolves will be struck by packs of gliders coming in from the left at various intervals until the pattern reaches its final state.

Next step is to follow the ideas outlined in Matthew Cook's follow-up paper 'A concrete view of Rule 110 computation' which outlines a compilation process for cyclic tag systems in Rule 110, and then construct a more complex CTS.

Anyone else have interesting ideas for things to do with Rule 110 unit cells?
Attachments
W110 CTS full.mc
Rule 110 unit cell pattern implementing a CTS
(20.64 KiB) Downloaded 175 times
User avatar
thorsilver
 
Posts: 13
Joined: March 31st, 2018, 9:43 pm
Location: Glasgow, Scotland

Re: Fun with Rule 110 unit cells

Postby thorsilver » April 26th, 2018, 12:47 am

Another experiment with a Rule 110 cyclic tag system implemented with unit cells.

This time, I generated an initial condition using Mathematica for a cyclic tag system defined by the rule set [{{0, 0, 0, 0, 0, 0}, {}, {1, 1, 1, 1, 1, 1}, {}}, {1}]. The script for accomplishing this can be found in the Notes from A New Kind of Science on this page: http://www.wolframscience.com/nks/p1116 ... versality/

I routed this output to a text file, and ended with 3 huge blocks of cell states for Rule 110 -- to run the CTS indefinitely, blocks 1 and 3 need to be repeated infinitely, so the base output of this script produces an initial state that will run the CTS just for one step (if I'm understanding it correctly). I then stripped all punctuation and spaces out of the text file to produce a single long binary string.

So now we have a massive initial state consisting of 235,857 Rule 110 cells, and after running it through Naszvadi's script we end up with the same number of W110 unit cells in a 696MB RLE file! Thankfully it slims down to 82KB in MC format.

I've attached the file in case anyone wants to try it. With this method it's easy to generate cyclic tag systems for Rule 110, but of course the process of converting them to unit cells in Life takes a long, long time. Generating the RLE for this one took about an hour.
Attachments
Wolfram 110 CTS 3.mc
Cyclic tag system implemented in Rule 110 unit cells
(80.4 KiB) Downloaded 165 times
User avatar
thorsilver
 
Posts: 13
Joined: March 31st, 2018, 9:43 pm
Location: Glasgow, Scotland

Re: Fun with Rule 110 unit cells

Postby thorsilver » April 26th, 2018, 3:04 pm

One more for the road -- this CTS is defined by the rule [{{1, 1, 0, 1, 0, 1}, {1, 1, 0, 0, 0, 0}}, {0, 1}] and is again an example taken from Wolfram's book. The resulting pattern contains 219,205 unit cells.
Attachments
Wolfram 110 CTS 1 v2.mc
Another Rule 110 CTS implemented with unit cells
(79.02 KiB) Downloaded 157 times
User avatar
thorsilver
 
Posts: 13
Joined: March 31st, 2018, 9:43 pm
Location: Glasgow, Scotland

Re: Fun with Rule 110 unit cells

Postby thorsilver » April 28th, 2018, 2:47 pm

Just finished up a little Python script that will make generating these patterns much easier for anyone who cares to :lol:

Now there's just two steps in the process, and it's orders of magnitude faster than before:

1) Generate your CTS initial condition for Rule 110 in Mathematica using the CTToR110 function given at the page linked above, and redirect the output to a file called 'initial_conditions_W110.txt' like so:
initcond = CTToR110[{{}, {0, 0, 1, 0, 0, 1}, {}, {}, {}, {}}, {0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0}]
Export["initial_conditions_W110.txt", initcond]

2) Run the Python script below in the same folder where 'initial_conditions_W110.txt' lives

That's it! The script will print the number of unit cells in the output pattern, then output two files: a text file containing the binary string encoding the initial condition, in case you want to do something else with it besides generating a unit cell pattern; and a (massive) RLE file containing the W110 unit cell pattern.

The Python script on my machine converts CTS initial conditions of several hundred thousand cells into unit cell patterns in just a few seconds, whereas the same patterns converted with the bash script linked above took multiple hours in some cases. I just tested it with a CTS implementing an instance of the Collatz function, consisting of 576,935 unit cells, and it generated the 1.68GB(!) RLE file in about 5 seconds.

Just for kicks I've attached that RLE converted to an MC file.

Enjoy! Here's the script, sorry for my quick-and-dirty Python:

import re

with open('initial_conditions_W110.txt', 'r') as myfile:
    a=myfile.read()

b = re.sub('[{,} ]', '', a)
b = b.replace('\r', '')

with open("initial_conditions_W110_binary.txt", "w") as text_file:
    text_file.write(b)

binary_list = list(b)

cell1 = '33b2o$34bo$34bobo6b2o$35b3o5bobo$37b3o6bo$37bo2bo2bo2bo7b2o$38b2o6bo7b2o$43bobo$43b2o12$4b2o$4b2o11$2b2o3b2o$4b3o$3bo3bo$4bobo$5bo$16b3o$6b3o7bo$6b3o8bo4$4b2o3b2o$5b5o14b2o$6b3o15bobo$7bo16bo6$31b3o62bo$31bo62bobo$7b2o23bo53bo5b2o12b2o$7b2o76bobo4b2o12b2o$84bo3bo3b2o$84b5o5bobo$83b2o3b2o6bo$39b2o43b5o$39bobo43b3o$39bo46bo14b2o$102bo$102bobo9bo$103b2o9bobo$115bobo$115bo2bo3b2o$46b3o66bobo4b2o$46bo67bobo$47bo66bo$85b2o$85b2o3$54b2o$54bobo$54bo6$61b3o$61bo$62bo4$61bo$61b3o5b2o$64bo4bobo$63b2o4bo5$66bo8bo$65b3o7b2o$64b5o7b2o2b2o$63bobobobo10b2o$63b2o3b2o5bobo$75bobo$76bo6b2o$68b2o14bo$68b2o14bobo6bo$70bo14b2o4bobo$55b2o11b3o18b2o18b2o$55b2o9bo22b2o17bo3bo$66b5o12b2o4b2o16bo5bo3b2o$67b2o13b2o7bobo4bo8bo3bob2o2b2o$84bo8bo3bo9bo5bo$97b3o2bo5bo3bo19b2o$65b2o3b2o37b2o21bo$66b5o53bo5bobo$66b2ob2o52bobo4b2o$66b2ob2o20bo31b2obo$55b3o9b3o20b2o19b2o10b2ob2o$54bo3bo31bobo18b2o10b2obo$53bo5bo45bo17bobo$53bo5bo38b2o4bobo17bo$56bo41b2o5bo$54bo3bo34b2o$55b3o9b2o24b2o6b3o$56bo10b2o32bo$102bo12bo$33b2o64bo13b3o$33b2o22b3o38bobo11bo$57b3o39bo12b2o11b2o$56bo3bo64b2o$50bobo56b2o$50b2o3b2o3b2o28b2o17bobo49b2o$51bo38b2o17bo51b2o2$133b2o$133b2o2$44bo$31b5o6b2o72b3o$30bob3obo6b2o71bo7b3o15b2o$31bo3bo81bo5bo3bo15bo$32b3o23b2o31bo30bo5bo4b3o4b3o15b2obob2o$33bo24b2o30b3o30bo3bo12bo$89b5o30b3o6bobo10b2o10bo5bo$88b2o3b2o28bo2bo5b5o9b2o$89b5o29b3o5b2o3b2o21b2ob2o$31bo10b2o45b5o28bob2o5b2o3b2o23bo$31bo11bo46bo2bo28bobo$30bobo10bobo7bo36bo3bo28bo$29b2ob2o2bobo5b2o4b4o40bo7b2o29b2o$28bo5bo2bo11b4o38b2obo6b2o29b2ob2o8b3o15b2o$31bo17bo2bo40bo9bo16b2o3b2o6bo2bo7b2ob2o14bo$28b2o3b2o14b4o67bobobobo6bo10b2ob2o15b3o$50b4o7b2o58b5o10bo7b5o17bo$53bo7bobo26b2o3b2o25b3o9b2o7b2o3b2o$32bo30bo26bo5bo26bo$32bo30b2o45bo$33bo57bo3bo13b2o18b2o3b2o$92b3o14bobo18b5o5bo5bo$131b3o7b2o2bobo77b2o$30b2o100bo7b2o3bobo77b2o$30b2o114bo$122b2o$122b2o101bo$117b2o105b3o$93b2o21b2o25bo79bo3bo$93b2o23bo10b2o10b2ob2o79bo$130bo91bo5bo$127b3o10bo5bo75bo5bo$127bo95bo3bo$140b2obob2o77b3o$125bo$124b2o$124bobo2$223bo3$223bo$132b2o9b2o78bobo$131b2o10b2o78b2o$133bo2$145b2o65b2o$145bo2bo63b2o10b2o3b2o$135bo3b3o7bo6b2o58bo$134b5o3bo6bo6b2o57bo9bo3bo$133b2ob2o3bo7bo65b3o8b3o$122b2o8b3ob2o3bo3bo2bo77b3o$122b2o9b2ob4o5b2o$134b4o$135bo93b2o$229bo$146b2o60bo21b3o$146b2o60bobo21bo$208b2o27bo$235b3o$234bo$234b2o2$147bo53bo$146b3o51bo$146b3o51b3o2$144b2o3b2o80b3o$144b2o3b2o79bo3bo$156bo56b2o$156b2o55bo15bo5bo$147bo3b2o4b2o43b2o7bobo15b2o3b2o$146bobo2b2o4b3o7b2o33bobo6b2o$146bobo2b2o4b2o8b2o23bo4b2o6bo$147bo8b2o33bobo2bo2bo2bo2bo26bo$156bo34b2obob3o6bo25bobo$179b2o10b2ob2o6bobo26bobo$179b2o10b2obo7b2o29bo$191bobo39bo$192bo37bo2bo$231b2o3$68bo2bob2obo2bo$68b4ob2ob4o119bobo$68bo2bob2obo2bo119bo2bo$92bo4bo92b2o10b2o$90b2ob4ob2o90b2o8bo3b2o$92bo4bo97b2o5b2o$194bo4bo2bo$199bobo5$128b2o76bo$128bobo74b3o$123b2o6bo7b2o63b5o$122bo2bo2bo2bo7b2o62bobobobo$122b3o6bo71b2o3b2o$120b3o5bobo$119bobo6b2o$119bo86bo$118b2o85bobo$205bobo$206bo$206b2o$206b2o$206b2o11$o$'

cell0 = '33b2o$34bo$34bobo6b2o$35b3o5bobo$37b3o6bo$37bo2bo2bo2bo7b2o$38b2o6bo7b2o$43bobo$43b2o12$4b2o$4b2o11$2b2o3b2o$4b3o$3bo3bo$4bobo$5bo$16b3o$6b3o7bo$6b3o8bo4$4b2o3b2o$5b5o14b2o$6b3o15bobo$7bo16bo6$31b3o62bo$31bo62bobo$7b2o23bo53bo5b2o12b2o$7b2o76bobo4b2o12b2o$84bo3bo3b2o$84b5o5bobo$83b2o3b2o6bo$39b2o43b5o$39bobo43b3o$39bo46bo14b2o$102bo$102bobo9bo$103b2o9bobo$115bobo$115bo2bo3b2o$46b3o66bobo4b2o$46bo67bobo$47bo66bo$85b2o$85b2o3$54b2o$54bobo$54bo6$61b3o$61bo$62bo4$61bo$61b3o5b2o$64bo4bobo$63b2o4bo5$66bo8bo$65b3o7b2o$64b5o7b2o2b2o$63bobobobo10b2o$63b2o3b2o5bobo$75bobo$76bo6b2o$68b2o14bo$68b2o14bobo6bo$70bo14b2o4bobo$55b2o11b3o18b2o18b2o$55b2o9bo22b2o17bo3bo$66b5o12b2o4b2o16bo5bo3b2o$67b2o13b2o7bobo4bo8bo3bob2o2b2o$84bo8bo3bo9bo5bo$97b3o2bo5bo3bo19b2o$65b2o3b2o37b2o21bo$66b5o53bo5bobo$66b2ob2o52bobo4b2o$66b2ob2o20bo31b2obo$55b3o9b3o20b2o19b2o10b2ob2o$54bo3bo31bobo18b2o10b2obo$53bo5bo45bo17bobo$53bo5bo38b2b4bobo17bo$56bo41b2b5bo$54bo3bo34b2o$55b3o9b2o24b2o6b3o$56bo10b2o32bo$102bo12bo$33b2o64bo13b3o$33b2o22b3o38bobo11bo$57b3o39bo12b2o11b2o$56bo3bo64b2o$50bobo56b2o$50b2o3b2o3b2o28b2o17bobo49b2o$51bo38b2o17bo51b2o2$133b2o$133b2o2$44bo$31b5o6b2o72b3o$30bob3obo6b2o71bo7b3o15b2o$31bo3bo81bo5bo3bo15bo$32b3o23b2o31bo30bo5bo4b3o4b3o15b2obob2o$33bo24b2o30b3o30bo3bo12bo$89b5o30b3o6bobo10b2o10bo5bo$88b2o3b2o28bo2bo5b5o9b2o$89b5o29b3o5b2o3b2o21b2ob2o$31bo10b2o45b5o28bob2o5b2o3b2o23bo$31bo11bo46bo2bo28bobo$30bobo10bobo7bo36bo3bo28bo$29b2ob2o2bobo5b2o4b4o40bo7b2o29b2o$28bo5bo2bo11b4o38b2obo6b2o29b2ob2o8b3o15b2o$31bo17bo2bo40bo9bo16b2o3b2o6bo2bo7b2ob2o14bo$28b2o3b2o14b4o67bobobobo6bo10b2ob2o15b3o$50b4o7b2o58b5o10bo7b5o17bo$53bo7bobo26b2o3b2o25b3o9b2o7b2o3b2o$32bo30bo26bo5bo26bo$32bo30b2o45bo$33bo57bo3bo13b2o18b2o3b2o$92b3o14bobo18b5o5bo5bo$131b3o7b2o2bobo77b2o$30b2o100bo7b2o3bobo77b2o$30b2o114bo$122b2o$122b2o101bo$117b2o105b3o$93b2o21b2o25bo79bo3bo$93b2o23bo10b2o10b2ob2o79bo$130bo91bo5bo$127b3o10bo5bo75bo5bo$127bo95bo3bo$140b2obob2o77b3o$125bo$124b2o$124bobo2$223bo3$223bo$132b2o9b2o78bobo$131b2o10b2o78b2o$133bo2$145b2o65b2o$145bo2bo63b2o10b2o3b2o$135bo3b3o7bo6b2o58bo$134b5o3bo6bo6b2o57bo9bo3bo$133b2ob2o3bo7bo65b3o8b3o$122b2o8b3ob2o3bo3bo2bo77b3o$122b2o9b2ob4o5b2o$134b4o$135bo93b2o$229bo$146b2o60bo21b3o$146b2o60bobo21bo$208b2o27bo$235b3o$234bo$234b2o2$147bo53bo$146b3o51bo$146b3o51b3o2$144b2o3b2o80b3o$144b2o3b2o79bo3bo$156bo56b2o$156b2o55bo15bo5bo$147bo3b2o4b2o43b2o7bobo15b2o3b2o$146bobo2b2o4b3o7b2o33bobo6b2o$146bobo2b2o4b2o8b2o23bo4b2o6bo$147bo8b2o33bobo2bo2bo2bo2bo26bo$156bo34b2obob3o6bo25bobo$179b2o10b2ob2o6bobo26bobo$179b2o10b2obo7b2o29bo$191bobo39bo$192bo37bo2bo$231b2o3$68bo2bob2obo2bo$68b4ob2ob4o119bobo$68bo2bob2obo2bo119bo2bo$92bo4bo92b2o10b2o$90b2ob4ob2o90b2o8bo3b2o$92bo4bo97b2o5b2o$194bo4bo2bo$199bobo5$128b2o76bo$128bobo74b3o$123b2o6bo7b2o63b5o$122bo2bo2bo2bo7b2o62bobobobo$122b3o6bo71b2o3b2o$120b3o5bobo$119bobo6b2o$119bo86bo$118b2o85bobo$205bobo$206bo$206b2o$206b2o$206b2o11$o$'

for i in xrange(len(binary_list)):
    if binary_list[i] == '1':
        binary_list[i] = cell1
    else:
        binary_list[i] = cell0       

print len(binary_list)
final_text = ''.join(binary_list)

with open("initial_conditions_W110.rle", "w") as text_file:
    text_file.write("x = 0, y = 0, rule = B3/S23\n")
    text_file.write(final_text)
Attachments
W110 meta CTS Collatz.mc
(133.21 KiB) Downloaded 165 times
User avatar
thorsilver
 
Posts: 13
Joined: March 31st, 2018, 9:43 pm
Location: Glasgow, Scotland


Return to Patterns

Who is online

Users browsing this forum: No registered users and 5 guests