Fun with Rule 110 unit cells

For discussion of specific patterns or specific families of patterns, both newly-discovered and well-known.
Post Reply
User avatar
thorsilver
Posts: 13
Joined: March 31st, 2018, 9:43 pm
Location: Glasgow, Scotland

Fun with Rule 110 unit cells

Post by 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 516 times

User avatar
thorsilver
Posts: 13
Joined: March 31st, 2018, 9:43 pm
Location: Glasgow, Scotland

Re: Fun with Rule 110 unit cells

Post by 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 495 times

User avatar
thorsilver
Posts: 13
Joined: March 31st, 2018, 9:43 pm
Location: Glasgow, Scotland

Re: Fun with Rule 110 unit cells

Post by 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 487 times

User avatar
thorsilver
Posts: 13
Joined: March 31st, 2018, 9:43 pm
Location: Glasgow, Scotland

Re: Fun with Rule 110 unit cells

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

Code: Select all

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:

Code: Select all

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 502 times

User avatar
pcallahan
Posts: 845
Joined: April 26th, 2013, 1:04 pm

Re: Fun with Rule 110 unit cells

Post by pcallahan » April 1st, 2019, 6:03 pm

I am resurrecting this thread mainly as an acknowledgement of prior art, but I'm curious if anyone has approached the rule 110 simulation problem from a more concise perspective, albeit with linear slowdown.

A single generation of Rule 110 is easily implemented using a finite-state transducer. Suppose you read the cells of a finite Rule 110 pattern beginning with the first 1. Then you can maintain a state representing the first two cells in the 3-cell neighborhood and apply a transition rule as you read the next cell that changes the state and outputs the next value based on the rule. Note that you can't output it until you have read the whole 3-cell neighborhood (assuming a deterministic state machine) so the results may be shifted, but the rule is equivalent.

For a further simplification, note that if the middle cell of the 3-cell neighborhood is 0, the value of the left cell does not matter, so there are really only three states: ?0, 01, 11. Representing them as 0, 1, 2 and storing the transition table in an array, this is easy to implement in Python:

Code: Select all

transition =[[(0, 0), (1, 1)],
             [(0, 1), (2, 1)],
             [(0, 1), (2, 0)]]

cells = "1"
for i in range(10):
  nextgen = []
  state = 0
  for cell in cells + "0":
    state, output = transition[state][int(cell)]
    nextgen.append(str(output))
  print(cells)
  cells = "".join(nextgen)
Output:

Code: Select all

1
11
111
1101
11111
110001
1110011
11010111
111111101
1100000111
The transition table has some interesting antisymmetry when written this way but I don't claim there is any significance to that. I can make up a "story" that the state is a counter with reset. Starting at 0, a 1 increments the count with a maximum of 2. 0 always resets the count back to 0. It also suggests that there could be an implementation that is nicer than a direct implementation of the logic.

What does this buy us? Well, in Life we can implement a finite state transducer by cycling gliders through a fixed pattern. In fact, we can increase the length of this cycle to provide an unbounded recirculating glider memory, as I showed years back before I knew about much besides p30 technology and before I actually understood that the sliding block memory had infinite capacity (albeit with exponential slowdown).

Code: Select all

x = 400, y = 131, rule = S23/B3
129bo$127boo$128boo14$379b4o$378bo3bo12bobbo$382bo16bo$378bobbo13bo3bo
$396b4o$373bo$374bo$372b3o$389bo4boo$386b4o3booboo$368bo16b5o4bobbo$
369bo14bo9bobbo$367b3o15boo8boo$386bo$354b5o$353bo4bo4bo24boo5bobbo$
358bo5bo22b4o8bo$44boo307bo3bo4b3o22booboo3bo3bo$43bo3bo307bo26boo5boo
5b4o$27boo13bo5bo318bo12booboo$20b3o4boo13bo3boboobboo257b4o43bo8bo8bo
3b4o$19b5o6boo10bo5bo3boo256bo3bo12bobbo28bo11boobbobo3boo$18bobo3bo5b
3o10bo3bo266bo16bo25b3obboo6bobboo3bo$18boo3bo6boo12boo264bobbo13bo3bo
39boobbobo3boo$27boo9bobo287b4o35bo8bo3b4o$27boo10boo13boo311bo12boob
oo$39b3o12boo326boo$41boo260bo13boo$42boo260bo7bo4boo$41bo13boo245b3o
6b3o13b3o45boo$53boboo253bo18bo44b4o$15boo29bo6bo256b5o7boo3bobo44boob
oo$16bo30boo4bo244bo20bo7boo47boo15boo$16bobo4bo9boo11boo5bobbo242bo
91booboo$17boo3bobo7b4o18boo230b5o6b3o91b4o$21boboo5b3obbobbobo244bo4b
o29boo5bobbo12bo17boo29boo$20booboo9boobbobbo248bo28b4o8bo12bo12b4oboo
$21boboo6bo9boo242bo3bo3bo25booboo3bo3bo10b3o12b6o3bobo13bo3bo$22bobo
5bo8bo3boo242bo6bo19boo5boo5b4o26b4o5boo13boo5b3o$23bo6bo10boo108bobo
138b3o8bo8booboo50bo9boo9bob3o$38bobbo5boo97bo4bobbo146bobo4bo3b4o60bo
6bo8boo$38bobo6bobo61boo34boo5boo8bo135bobbo5bo3boo60bo3bo3b8obo$49bo
60bo3bo27boo8bo3boo5bobo134bo6bobbo50bobo12bo3bo7b4o$49boo43boo13bo5bo
26boo10boo6boboo134bobbo5bo3boo47boo16bo8bo$87b3o4boo13bo3boboobboo30b
obbo6booboo10boo123bobo4bo3b4o46bo$86b5o6boo10bo5bo3boo30bobo8boboo10b
oo125bo8booboo65bobbo$61bo23bobo3bo5b3o10bo3bo48bobo148boo59boo9bo6boo
$62boo21boo3bo6boo12boo27boo22bo118bo72bo17b4o4bo3bo4booboo$61boo31boo
9bobo32boo142bo69b3obobo13booboo4b4o4b4o$94boo10boo13boo29boo128b3o22b
oo45boo9b3oboo5boo14boo$106b3o12boo29boo152b4o18bo25boboo6boo5bo$108b
oo29boobo163booboo18bo25boo6bo7boo$109boo29bobo165boo17b3o34boo5bo$
108bo13boo17bo37boo184b3oboo5boo$120boboo16boo37bo194booboo$82boo29bo
6bo19boo4bo11b3o9boo5bobo194b4o$83bo30boo4bo19boo4bobo9bo9bobbo5boo
196boo$83bobo4bo9boo11boo5bobbo22boo5bo5bo7bo$84boo3bobo7b4o18boo28b4o
12bo$88boboo5b3obbobbobo42boboboo11bo20bo$87booboo9boobbobbo40bobbob3o
11bobbo16b3o$88boboo6bo9boo39booboboo14boo19bo$89bobo5bo8bo3boo35b3ob
4o35boo76bo$90bo6bo10boo36bobo4bo95b3o17bo39b3o$105bobbo5boo30bo101b5o
14b3o38b5o$36bo68bobo6bobo28boo100boob3o54boob3o$34bobo79bo131boo58boo
$24boo6boo25bobo54boo$23bo3bo4boo12boo10bo$22bo5bo3boo12boo5boobbo4bo
297boo$12boo8bo3boboo4bobo16boobobboboo66boboo58boo145b3o18b4o$12boo8b
o5bo7bo20boo69boboboo54b3oboo143boboo18booboo$23bo3bo101b4o55b5o91b4o
45bo5boo9b3oboo5boo$24boo104boo57b3o91bo3bo44bo16boo5bo$35bo213boo36bo
44bo6bo8bo7boo$31boo3boo10boo199bo33bobbo50boo10boo5bo$30bobooboo9boob
oo199b3o77boobo4bo11b3oboo5boo14boo$32bo13b4o202bo76boboobobo22booboo
4b4o4b4o$31b3o13boo241b4o35bobbo5bo20b4o4bo3bo4booboo$32boo255bo3bo36b
3o6bo20boo9bo6boo$31bobbo16bo233bo7bo37boboo4boo26bobbo$32bo13boobo3bo
boo223b7obbobbo45b3o$46bo9bo222bobb3oboo53bo6bo16boo$23b3o21boo5boo
224b7obbobbo48boo5boo15boo8boo$25bo18b3obb5obb3o211bo14bo7bo47boo4bobo
14bo3bo5bobbo$24bo19bobbo7bobbo203boo6boo17bo3bo12boo57bo3bo4bobboo$
12bo32boo9boo211bobo18b4o3b4o4b4o56bo4bobbobboo$11boo26b3o254bo3bo4boo
boo33b4o6bo13bobo3b4o$oo8boo4boo5bo15bo61boo163boo32bo6boo33b6o5boo$oo
7b3o4boo3bobo16bo9bo50bo161b3oboo6bo20bobbo42b4oboo3bobo$10boo4boobbob
o26bobo39bo7bobo161b5o7boo69boo29boo$11boo6bobbo14bobo8boboo10boo25bob
o7boo163b3o7bobo99b4o$12bo7bobo14bobbo6booboo10boo15boo6boo199b3o13boo
70booboo$21bobo16boo6boboo26bo3bo4boo198b4o13bobo54boo15boo$23bo14bo3b
oo5bobo25bo5bo3boo191bo6bo3bo12boboo51booboo$40boo8bo26bo3boboo4bobo
188boo6b3o14boo52b4o$37bobbo36bo5bo7bo187bobo6b3o3boo9bo54boo$37bobo
29boo7bo3bo23boo186boo$68bobo8boo24bobbo$68bo21bo14bo200boo$67boo22boo
12bo199b4o$90boo3boo8boboo196booboo$96boo9boo181boo15boo$95bo192booboo
$288b4o$106boo181boo$81bo24boo$78b4o3boboo$70boo5b4o4boboboobboo$70boo
5bobbo3booboboobbobo$77b4o3boo8b3o7boo$78b4o3boo8b3o6boo$81bo12b3o$93b
obo$93boo!
This is almost custom-made for implementing the Python loop above. You just need to add the logic for handling state change and output, and send the length-increasing spaceship every time the inner loop completes (gauged with some kind of marker).

This is surely a modest pattern compared to the kinds of things that have come out in recent years. It could probably be generalized to make the state table itself programmable in a finite loop (that was something I thought of doing at the time but never got around to).

I guess my real question is: what is the minimum finite control using current technology that could apply rule 110 to a recirculating glider loop and extend it as needed.

ADDED: So what does this finite control look like from a CGOL perspective? It has three states, and assuming it has a built-in clock synchronized with the loop memory, we can encode 0 by no glider and 1 by a single glider arriving at the right time and place (for a stable device we need to represent 0 as well).

State 0: If it receives a glider, it outputs a glider and advances to state 1. Otherwise, no glider, no state change.
State 1: If it receives a glider, it advances to state 2. Otherwise it resets to 0. Always outputs a glider.
State 2: If it receives a glider, there is no state change it does not output a glider. Otherwise it outputs a glider and resets to state 0.

The fact that the lack of a glider always resets the state to 0 suggests some general mechanism. E.g., a reset stream that is inhibited by the entering glider (or a copy). The other operations are not as obvious.

Is this behavior simple enough that we could actually find a custom mechanism by searching rather than engineer it out of logic? There could be something like a multiple glider stream collision that had three stable configurations that and the appropriate transitions when hit by a glider.

ADDED: Another idea would be to make a moving finite state transducer on a spaceship. It could be as simple as a flotilla of c/2 ships with presence or absence of some ships to indicate state. The Rule 110 tape would consist of blocks that are modified as the spaceship/flotilla passes over (and if we made it long enough, it could read ahead and send output backwards).

Now a single pass of the ship implements one generation of Rule 110. To extend this, create a left-going puffer to output right-going flotillas. Then the succession of spaceships applies the rules to the blocks. This eliminates the O(n) slowdown because ultimately every block location has a dedicated worker. Of course, it is being calculated in pipeline fashion, so the row at time t is never present at once, just a single cell, right between the row at time t+1 and time t-1.

I think this could potentially be the most concise implementation of Rule 110 in Life that does not have linear slowdown. Has anyone built something like this?

ADDED (and that's it): I can't quite picture it, but of course, you could stream the bits as spaceships through fixed transducers produced by a puffer. At this point, you're basically back to unit cells, but the communication is simpler. Again you get pipelining so you never see the whole time t row at once.

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

Re: Fun with Rule 110 unit cells

Post by Naszvadi » August 6th, 2019, 3:47 pm

thorsilver wrote:...
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
...
Anyone else have interesting ideas for things to do with Rule 110 unit cells?
Martínez is probably still interested in such CA-related threads.

And also Rule-110 unit cells can prove (kind of weak) Turing-completeness of some one-neighour cellular automata with at most 4 states. It is known and I proved (unpublished) that two states are not enough. However rule-54 can be simulated with one-neighbour CA with 3 states.
The integer programming model I developed had run and provided the above results.

(Not) sorry for bumping this topic :)

Post Reply