- 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 ( 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: ... 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?
W110 CTS
Rule 110 unit cell pattern implementing a CTS
(20.64 KiB) Downloaded 288 times
User avatar
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: ... 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.
Wolfram 110 CTS
Cyclic tag system implemented in Rule 110 unit cells
(80.4 KiB) Downloaded 275 times
User avatar
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.
Wolfram 110 CTS 1
Another Rule 110 CTS implemented with unit cells
(79.02 KiB) Downloaded 268 times
User avatar
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:

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

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

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
        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")
W110 meta CTS
(133.21 KiB) Downloaded 275 times
User avatar
Posts: 13
Joined: March 31st, 2018, 9:43 pm
Location: Glasgow, Scotland

Re: Fun with Rule 110 unit cells

Postby 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:
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)]
  cells = "".join(nextgen)


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).
x = 400, y = 131, rule = S23/B3

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.
Posts: 298
Joined: April 26th, 2013, 1:04 pm

Return to Patterns

Who is online

Users browsing this forum: Google [Bot] and 10 guests