Implementing rule 110 CA with p30 glider stream logic

[pcallahan]

I was wondering about the simplest way to implement rule 110 in Life and thus reduce the universality proof to universality of rule 110. One idea is a finite state transducer that acts on a stream of gliders. This gives a linear slowdown, because you have to process each row cell by cell, but the logic can be kept small. Each time you recirculate the stream through the transducer, you compute a new row. For universality, the stream cannot be limited to a fixed size, but this can be addressed with an extensible delay line memory (omitted from further discussion here).

The transducer itself can be implemented in a variety of ways, including by duplicating a window of 3 consecutive gliders and applying logic to implement rule 110. However, the following pattern uses something that just happens to work for rule 110 and might have a very simple implementation in Life (better, I hope, than the solution below).

Define a counter with two inputs. The first is "reset to 0" and the other is "increment." For present purposes, we only need to be able to count to 2, and are prevented from counting any higher by the logic before resetting to 0.
Define the following boolean variables:

Code: Select all

c0 counter=0
c1 counter=1
c2 counter=2
x next input bit
res reset counter to 0
inc increment counter
y output

For rule 110, the counter holds a state based on the leftmost two bits in the 3-cell window. Since 00 and 10 are equivalent, it uses the counter value 0 for both. Counter value 1 represents 01. Counter value 2 represents 11.

Then we can use the following logic (there are other ways, but this works well in Life collisions).

Code: Select all

res=not c0 and not x # next bit is 0 and counter is not already 0
inc=not c2 and x # next bit is 1 and counter is not already 2
y=(x and c0) or c1 or (not x and c2)  # output is x for 00x, 10x, 1 for 01x, and not x for 11x

To cut to the chase, here's the Life pattern starting with a single bit 1. It processes each bit in 1260 steps (slow but watchable; can we make it faster?).

Code: Select all

#C [[ STEP 50 ]]
x = 4797, y = 4874, rule = B3/S23
4729b2o$4729b2o4$4730bo$4729b3o$4728bo3bo$4727bob3obo$4728b5o6$4729bo
2b2o$4729bobo$4728b2o$4727b2o29b2o$4727b2obo27b2o16b2o$4728b3o45b2o2$
4757b3o$4729b2o3b2o21b3o$4732bo35b2o$4729bo5bo31bobo6b3o$4721bobo6b2ob
2o31b3o7b3o$4721b2o8bobo21b2o3b2o4b2o7bo3bo$4722bo9bo23b5o5b2o$4732bo
24b3o7bobo4b2o3b2o$4758bo9bo3$4715bo49b2o3b2o$4713b2o16b2o32b2o3b2o6b
3o$4714b2o15b2o42b2o$4767b3o5b2o$4759bo7b3o4b2o$4760b2o6bo6bobo$4759b
2o15b2o$4763b2o$4706bobo54b2o$4706b2o68b2o3b2o$4707bo68b2o3b2o$4753b2o
3b2o10bo$4755b3o10b2o8b3o$4754bo3bo10b2o7b3o$4755bobo21bo$4700bo55bo$
4698b2o$4699b2o2$4755b2o$4755b2o21b2o$4698b2o78b2o$4697b2o$4691bobo5bo
$4691b2o$4692bo35bo$4728b3o$4731bo$4706bo23b2o$4705b2o24b3o$4705bobo
24b2o$4732bobo2$4729bo$4727b3o16bobo$4726bo19b2o$4726b2o19bo$4740b2o$
4739b2o$4741bo4$4721bo$4720b2o26bo$4601b2o67bo28b2o19bobo24b2o$4600bob
o65b2o27bo2bo46bobo$4586bo12b3o4b2o61b2o71b2o$4586b4o8b3o4bo2b4o84bo
18bo24bo2bo$4580b2o5b4o8b3o4b2ob3o103bo$4579bo2bo4bo2bo9bobo94b2o13b2o
25bo$4579bo2bo4b4o10b2o11bo84bo28b2o$4582bo3b4o8bo13b4o111b2o11b2o13b
2o$4582bo3bo12bo6b2o3bobob2o14b2o19bo76bo12bo11b2o$4580bobo14b3o6b2o2b
o2bob3o11bo2bo19b3o41b2o3b2o53bo$4580bobo28bobob2o11bo7b5o14bo40b2o3b
2o$4581bo30b4o12bo6bo5bo12b2o41b5o3bo33b2o3b2o$4614bo13bo7b2o3bo56bobo
4b2o32b2o3b2o$4629bo2bo7bo63bobo29bo3b5o$4578b2o3b2o46b2o24bo40b3o34b
2o4bobo19bo$4578bo5bo21bo49b3o76bobo24b2o$4604bobo48bo3bo81b3o18bobo$
4579bo3bo21b2o47bob3obo$4580b3o72b5o$4701bo$4700bobo$4635b2o10b2o50bo
3bo36bo$4613bo3b3o15bobo9b2o51b3o36bobo28b2o$4614bo4bo16b3o59b2o3b2o
33bo3bo26b2o$4612b3o3bo18b2o33bo66b3o29bo$4581b2o54b2o31bobo64b2o3b2o$
4581b2o52bobo33b2o$4636bo155b2o$4792b2o$4610b2o44b2o120bo$4609bobo21b
2o3b2o16b2o119b2o$4611bo21b2o3b2o137bobo2$4635b3o8b5o$4635b3o7bob3obo
49b2o$4636bo9bo3bo50b2o$4647b3o89b2o$4591b2o9b3o11b2o30bo90b2o44b2o$
4583bo7bo2bo9bo11bo167b2o$4582bo3b2o7bo7bo5bo4bobo27bo141bo4b5o$4582bo
5bo6bo12b4ob3o27b2o145bob3obo$4583b5o7bo11b2obob2o28b2o4b2o141bo3bo$
4591bo2bo11b3obo2bo27b3o4b2o142b3o$4591b2o14b2obobo5b6o6b3o9b2o4b2o
143bo$4608b4o5bo6bo18b2o146b2o$4609bo6bo8bo18bo145bobo$4617bo6bo69bo
95bobo$4618b6o71bo95bo$4693b3o2$4788b2obob2o$4788bo5bo$4789bo3bo$4790b
3o2$4712bo$4710b3o$4709bo$4709b2o3$4790b2o$4707bo82b2o$4705b2ob2o2$
4704bo5bo2$4704b2obob2o$4646b2o$4646b2o$4694bo$4692b2o$4693b2o2$4704b
2o$4705bo$4702b3o$4702bo16$4670bobo$4670b2o$4671bo4$4704b2o$4704bo$
4693b2o7bobo$4693bo2bo5b2o$4688b2o7bo$4690bo6bo$4697bo$4685b2o6bo2bo$
4684bobo6b2o$4684bo$4683b2o6$4649bo$4647b2o$4648b2o14$4607bo$4604b4o4b
o$4595bo7b4o5bo$4594bobo6bo2bo9b2o$4593bo3b2o4b4o9b2o$4582b2o9bo3b2o5b
4o$4582b2o9bo3b2o8bo102b2o$4594bobo28bobo82b2o8bo$4595bo29b2o80b2o6bo
5bo$4604bobo19bo72b2o5b3o5bo3b2obo$4605b2o78b2o12b2o6b2o6b6o$4605bo78b
obo23b2o4b4o$4683b3o24b2o$4683b2o$4683b2o32b2obob2o$4684bobo$4685bo31b
o5bo2$4718b2ob2o$4682b2o3b2o31bo$4682b2o3b2o2$4684b3o$4684b3o$4609b2o
74bo$4610bo106bo$4607b3o105b2o4b3o$4607bo108b2o2bo3bo2$4719bo5bo$4687b
o31b2o3b2o$4688b2o$4687b2o$4708bobo11bo$4682b3o23b2o6b2o3bobo$4681bo3b
o23bo6b2o3bobo$4680bo5bo36bo$4538b3o139bo5bo36bo$4540bo142bo10bobo19bo
3bo2bo$4539bo141bo3bo9b2o18b3o3b2o$4682bo12bo18bo3bo$4683bo2bo15bo13bo
$4686bo26bo5bo$4685bo13b2o12bo5bo$4680bo5b3o25bo3bo$4679b3o6bo26b3o$
4678b2ob2o$4677b3ob3o$4677b3ob3o$4677b3ob3o$4677b3ob3o$4678b2ob2o$
4679b3o$4680bo2$4714bo$4713b3o$4713b3o2$4711b2o3b2o$4711b2o3b2o$4694b
2o$4693b3o$4690bob2o9b2o9bo$4690bo2bo4bo5bo8bobo$4690bob2o5bo15b2o$
4693b3o3bo3bo11b2o$4694b2o5bo12b3o$4713bobo$4682b3o28b2o$4681bo3bo$
4680bo5bo$4680b2obob2o$4691bo$4669b2o19bobo$4669bo13bo4b2o3bo9b2o$
4670b3o9bobo3b2o3bo9b2o$4672bo9bobo3b2o3bo$4683bo6bobo$4691bo4473$23b
3o$25bo$24bo$12bo23bo$11b2o22b2o$2o8b2o4b2o5bo11bobo$2o7b3o4b2o3bobo$
10b2o4b2o2bobo$11b2o6bo2bo$12bo7bobo$21bobo8b2o$23bo8bobo8b2o$34bo7b2o
$34b2o8bo5$51bo$50b2o$50bobo6$58b2o$57b2o$59bo5$66bo$65b2o$65bobo6$73b
2o$72b2o$74bo5$81bo$80b2o$80bobo6$88b2o$87b2o$89bo5$96bo$95b2o$95bobo
6$103b2o$102b2o$104bo4$126b2o$111bo14b2o$110b2o$110bobo6$118b2o7bo$
117b2o7b3o$119bo5b5o$124b2o3b2o3$124b2o$123bo$126bo$123bo2bo$123b2ob2o
$125b2o3$122b2o3b2o$122b2o3b2o$123b5o$124bobo2$124b3o6$124b2o$124b2o!

Set LifeViewer to x50 speed and you'll see it go through the strings 1, 11, 1101, 11111, 110001, ... which are the first five rows in rule CA excluding 0. Note that the pattern itself is pretty simple. The most complicated looking structures are actually the period 1260 guns (two of them) used for clock signals. That's currently the fastest this can be run (I think) mostly due to the time it takes to reset. Increment can be done in 540 steps.

The core of this pattern is just the following p90 glider gun that outputs two gliders and omits one every 90 generations:

Code: Select all

x = 50, y = 40, rule = B3/S23
24b2o$23b2o$3b2o20bo$3b2o$46b2o$17bo28b2o$17b2o$b2o13bobo13bo$31b2o$
31bobo10b2o3$2o3b2o$b5o3b2o$b2ob2o4b2o31b2o3b2o$b2ob2o3bo29b2o3b5o$2b
3o33b2o4b2ob2o$40bo3b2ob2o$45b3o3$4b3o$4b3o$3bo3bo35b3o$2bo5bo34b3o$3b
o3bo34bo3bo$4b3o34bo5bo$42bo3bo$43b3o8$5b2o$5b2o$43b2o$43b2o!

It has three states and can be incremented by suppressing a glider in the p30 gun that deletes or creates an internal blocks. Attempting to increment from 2 destroys it, so we make sure that doesn't happen. Reset is accomplished by suppressing two consecutive gliders from the opposing p30 gun.

This is the kind of thing that could have been built (and built better) at least 30 years ago, but at that time, there was no proof of rule 110 universality.

I am curious if a much smaller rule 110 transducer can be found. For example, a "natural" counter that counter 0, 1, 2, 2, 2, 2, 2 .... each time it is hit with a glider and has a simple reset would work.

A more general question: What is the smallest stationary pattern that implements some Turing-equivalent transducer on a glider stream. I bet there is something much smaller, maybe even using stable components.

[dvgrn]

I was wondering about the simplest way to implement rule 110 in Life and thus reduce the universality proof to universality of rule 110. One idea is a finite state transducer that acts on a stream of gliders. This gives a linear slowdown, because you have to process each row cell by cell, but the logic can be kept small. Each time you recirculate the stream through the transducer, you compute a new row. For universality, the stream cannot be limited to a fixed size, but this can be addressed with an extensible delay line memory (omitted from further discussion here).

I'm worried about how the extensible memory idea can be applied in this context. The universality of Rule 110 hinges on an infinite repetition of a fairly complex pattern, different depending on which cyclic tag system you're emulating:

Entering from the right are a series of left-moving structures... separated by varying amounts of horizontal space. Large numbers of these structures are combined with different spacings to represent 0s and 1s in the cyclic tag system's production rules. Because the tag system's production rules are known at the time of creation of the program, and infinitely repeating, the patterns of 0s and 1s at the initial condition can be represented by an infinitely repeating string.

I'm sure it's possible to invent a CGoL structure to feed this repeating pattern in at the correct place and time in an expanding memory loop, to simulate the right-side repeating pattern in Matthew Cook's proof. But that seems complicated enough that the resulting proof of CGoL universality would be considerably more complex than the usual CGoL-only one. I think there's some similar support that would have to be added on the left side to simulate the infinite series of incoming clock pulses.

-- Please don't quote me on any of the detail here. I'm far from being an expert on Rule 110 universality, but I've always been vaguely dissatisfied with the requirement for different infinite repeating patterns on the left and right sides of the finite central data string. If you really want to prove universality when you have only a 1D CA to work with, it definitely seems like a reasonable solution, but it doesn't seem as clean as an all-0 background.

[pcallahan]

I'm worried about how the extensible memory idea can be applied in this context. The universality of Rule 110 hinges on an infinite repetition of a fairly complex pattern, different depending on which cyclic tag system you're emulating:

That's good point, but I doubt it is a fatal flaw. Feeding in a periodic boundary is almost certainly doable, though it would spoil some of the simplicity (as would even adding the extensible loop to the pattern above). It's also not clear that Cook's methods are the only path to rule 110 universality, but I assume he would have used an all-0 background if he saw a way.

Note: if you just want to extend the loop with each pass, you can fit an "extend loop" bit in the glider stream. There is plenty of space (41 gaps between gliders, and maybe a way to sneak it through the logic of the pattern as a whole). I can almost picture how to choose and inject the repeating part from a recirculating loop at this point, but it's not worth doing for this prototype.

I'm less interested in building an explicit universal reduction for rule 110 than in building the simplest glider stream transducer that is Turing equivalent. There are a lot of options here. For instance, there is no reason that the rule needs to be stated in terms of bit strings. k consecutive glider positions in the stream could encode 2^k states. They could also encode k unary values, or any other subset of possible states.

This was my original reason for the extensible delay line, years back, but I always assumed the finite control would be huge and not really worth the effort. I remember I built an "increment unbounded binary integer" control using final carry to expand the loop (Is that archived anywhere? It was a little buggy on the starting phase).

My guess is that there is a small pattern (in 100x100 or even 50x50 box) that transforms a glider stream in such a way that repeating transformations on unbounded streams is Turing complete. I am not sure if anyone has looked for this. Has anyone? My immediate motivation was the observation that rule 110 could be computed using a 3-state counter in a way supported by a very simple collision of p30 guns (at least I thought that was surprising and cool).

If you had a synthesis for such a pattern, you could build it with a breeder-like pattern and feed the stream through without looping. In this case, the left periodic boundary would come from a gun and the right periodic boundary from a puffer. You would never actually see an entire row, but the bit stream leaving the kth box in the pipeline would cycle through the kth row sequentially, minus the right half of the repeating boundary.

Obviously, the more stuff I add, the more I might as well just be using a universal constructor. My real question is how small can you make the finite control. You don't have to implement rule 110. A rule that looked more like a Turing machine would be fine too if it worked with a 0 background.

ADDED: I'm not quite done with this prototype. The longest delay comes from the reset to 0. What has to happen is that (1) a single entering 0 is inverted and tested against the state. (2) (a) For count 0 (states ?0) its glider is destroyed along with output glider. (b) For counts 1 and 2, it allows output glider to escape and is reflected back to reset (3) Reset is initiated, but counter takes a few cycles to stabilize.

The above is what requires 1260 generations, or 14 p90 cycles (I could double check if faster clocking works). I am pretty sure I can optimize the reset and bring it down.

Increment takes 540 generations or 6 p90 cycles. That's mostly due to the delay in routing the glider to block increments when count=2. I suspect it will be hard to get reset down below this.

[simsim314]

I was thinking about a rake which generates SL readers just like in caterloopillar and a static tape which evolves by rule 110 due to the reading mechanism. Maybe a line of such readers can also be used to simulate 2D CA. As of your design (I still don't get how it works), maybe it's simpler to modify existing infinite hotel for this purpose.

[pcallahan]

As of your design (I still don't get how it works),

Have you convinced yourself by watching that it actually does work? I just want to make sure we're on the same page. There are many ways to calculate the transition for rule 110, and not all of them generalize in an obvious way to other elementary CAs. This is very much a custom fit to rule 110 that looks like a fortuitous coincidence.

So forget about rule 110 for a minute. We have a serial device based on a counter with internal states 0, 1, 2. The counter has two control inputs: (a) if reset is 1, it sets the counter back to 0. (b) if increment is 1, it increments the counter. A control input of 0 keeps the counter the same (and its undefined if both are 1).

There is also an input bit and an output bit. Output bits and control inputs are a function of counter and input, according to this table:

Screen Shot 2019-04-09 at 4.56.24 PM.png (18.89 KiB) Viewed 11427 times

Here's some Python code to illustrate:

Code: Select all

class Counter(object):
  value = 0

  def process_input(self, reset, increment):
    if reset:
      self.value = 0
    if increment:
      self.value += 1


rule = [[(0, 0, 0), (0, 1, 1)],
        [(1, 0, 1), (0, 1, 1)],
        [(1, 0, 1), (0, 0, 0)]]

counter = Counter()
nextrow=[]
for cell in "01110000110100":
    inp = int(cell)
    reset, increment, output = rule[counter.value][inp]
    counter.process_input(reset, increment)
    nextrow.append(str(output))
print("".join(nextrow))

You can see for yourself what it does in repl.it

As we discussed in connection to tiling, only 3 states are needed to remember the leftmost two bits of each window, (00x and 10x are equivalent). I can make up a "story" that the state transition is actually a counter, but this is pure luck I think.

maybe it's simpler to modify existing infinite hotel for this purpose.

I'm not familiar with that in detail but I think it is growing the length of the loop at a constant pace. This will cause exponential slowdown (at least I convinced myself once) because every time you complete a pass of the loop, it doubles in length. You really want a loop that can be grown at a controlled pace, like the delay line I made a long time ago.

I'm sure it's possible to invent a CGoL structure to feed this repeating pattern in at the correct place and time in an expanding memory loop, to simulate the right-side repeating pattern in Matthew Cook's proof. But that seems complicated enough that the resulting proof of CGoL universality would be considerably more complex than the usual CGoL-only one.

On further thought, I think there might be a nice solution here. The recirculating glider/spaceship stream has room for control bits in the gaps. Can we make stream like abc.xxxxxxxxxxxxxxx.abc where the dots indicate that abc should be copied and the loop expanded with each pass? If abc is a bounded length, we can use a finite delay structure to hold onto the copy for duplication. I don't think we will need to add a lot of extra logic for this.

ADDED: On even further thought, if I'm going to that much effort, it might be simpler just to implement a Tag system directly. They seem more suited to recirculating gliders than many other computational models, though I haven't given them much thought before. The question is to find a finite control that inputs a glider from a stream, changes state, outputs a glider into the stream, and possibly outputs a control glider to extend the stream.

[pcallahan]

Here is a slight improvement on the original pattern, shortening the reset path from 1260 to 1080 generations (12 90-generation cycles). It uses an LWSS collision to restart the counter and avoids going up and down again. I did this by eye in Golly (no serious calculation involved) and I had expected more improvement. (UPDATE 4/10: pulled the p1080 guns out of the main pattern, because they are just clock pulses and compacted the counter logic, but was unable to shorten the reset path.)

Code: Select all

#C [[ STEP 50 ]]
x = 2128, y = 2036, rule = B3/S23
2085b2o20b2o$2085b2o19b3o$2103bob2o9bobo$1680bo415b2o5bo2bo4bo6bo$
1678bobo415b2o5bob2o5bo$1677bobo17bo408b3o3bo4bo$1671b2o3bo2bo16b2o
388bo20b2o5b2o$1671b2o4bobo15b2o4b2o383bo$1660bo17bobo13b3o4b2o382bobo
$1658b4o18bo4bobo7b2o4b2o381b2ob2o25b2o3b2o$1649b2o5b4ob2o22b2o9b2o
385bo5bo$1647bo2bo3bo3b2ob3o22bo10bo388bo28bo3bo$1646bo7bo3b2ob2o420b
2o3b2o26b3o$1646bo6bo3b5o8b2o29bo414b3o$1646bo7b3o3bo9bobo27b3o$1647bo
2bo21bo26bo3bo380b4o$1649b2o21b2o24bob3obo379bo2b2o$1699b5o381bob2o$
1662bo$1663b2o421b2o25bo5bo$1662b2o423bo24bo5b3o$2112b3o3b3o2$1642b3o
436b2obob2o28b2o3b2o$1641bo3bo435bo5bo5bo22b2o3b2o$1640bo5bo435bo3bo7b
o$1640bo5bo22bobo411b3o6b3o$1643bo26b2o433bo$1641bo3bo24bo29b2o403bobo
$1642b3o28b2o25b2o403b2o$1643bo29b2o441b2o$2117bo5b2o$1690b2o422b3o6b
2o$1643b2o44bo2bo421bo$1643b2o47bo391b2o$1692bo391b2o$1689b2obo$1689b
2o2$1658bo$1657b2o31b2o422b3o6b3o$1649bo7b2obo29b2o422bo7bo3bo$1649b2o
6bo2b3o452bo5bo5bo$1644b2o4b2o7bobo4bo454b2obob2o$1640b2o2b2o4b3o3bob
3o5bobo$1640b2o2b2o4b2o5b3o7bobo4b2o$1649b2o16bo2bo3b2o445bo$1649bo17b
obo451b2o$1666bobo$1666bo426bo26b2obo$1866b2o221b2o2b2ob3o21b2o2bo$
1866b2o221b2o4b4o22b4o$2093b2o2$2119b2o3b2o$1866b3o253bo$1866b3o250bo
5bo$1865bo3bo250b2ob2o$1864bo5bo239b2o9bobo$1865bo3bo240bobo9bo$1866b
3o232b3ob2o4b3o8bo$2101b4o2bo4b3o$2105b2o4b3o$2110bobo$2110b2o$1867bob
o$1866bo2bo$1864bob2o2$1867bo$1864b2obo$1866bo3$1866b2o3b2o$1867b5o$
1867b2ob2o$1867b2ob2o$1868b3o4$1871b2o$1851bo19bo$1850bo13b3o5b3o$
1850b3o11bo9bo$1865bo5$1891bo$1889b3o$1888bo$1888b2o$1868b2o$1868b2o3$
1879b3o16b2o$1879bo18b2o$1880bo4$1868b3o$1828bo38bo3bo15b2o8b3o$1828bo
bo35bo5bo14bobo6b2ob2o$1828b2o36bo5bo14bo8b2ob2o$1896b5o$1872bo22b2o3b
2o$1814bo56b2o$1814b3o54b2o$1817bo51bo2b2o21bo$1816b2o52bobo20b2obo$
1870b2o24bo2$1893bob2o$1868b2o3b2o20bo2bo$1868b2o3b2o21bobo2$1870b3o$
1816b2o3b2o47b3o$1817b5o49bo$1817b2ob2o73b3o$1817b2ob2o72bo3bo$1818b3o
72bo5bo$1894bo3bo$1895b3o$1871b2o22b3o$1835bobo33b2o$1836b2o$1818b2o
16bo$1818b2o75b2o$1895b2o18$1858bo$1859b2o$1858b2o10bo$1868b3o$1867bo$
1867b2o3$1896bo$1894b3o$1864b3o26bo$1893b2o$1864bobo$1863b5o$1862b2o3b
2o20b2o$1862b2o3b2o21b2o$1889bo3$1808b2o$1808b2o$1862b2o18bo22b2o$
1863bo18b2o20bo$1860b3o18bobo9b2o8bo12b2o$1844bo15bo32b2o8bo7bo4b2o$
1844bobo56bo8b2o5b2o$1844b2o58bo4b2o2bo5b3o5b2o$1905b2ob5o6b2o6b2o$
1911bo4b2o$1874b2o11b3o26b2o$1875b2o10bo2bo$1874bo12bo15bo$1887bo14bo
11b2o$1888bobo11b3o8bo3bo$1912bo5bo3b2o$1912bo3bob2o2b2o$1867bo44bo5bo
$1867b2o44bo3bo$1866bobo45b2o$1906b2o$1906b2o2$1910b2o8bo$1910bo2bo6bo
bo$1859b2o44b2o2bo3bo7bobo4b2o$1860b2o42b3o2b2o2bo7bo2bo3b2o$1822bo36b
o16b2o23bob2o16bobo$1821bo53b3o16b2o5bo2bo8b3o4bobo$1821b3o41b2o5bob2o
9bobo6b2o5bob2o15bo$1865b2o5bo2bo4bo6bo16b3o$1872bob2o5bo23b2o$1852bo
22b3o3bo4bo$1834b2o16b2o22b2o5b2o$1834b2o15bobo3$1883b2o3b2o$1885b3o$
1834bo49bo3bo$1832b2ob2o7b2o39bobo$1845b2o39bo$1831bo5bo6bo2$1831b2obo
b2o$1885b2o$1885b2o$1837b2o$1836bobo$1837bo$1799bo36b2o$1799bobo34b3o$
1799b2o36b2o$1835bo4$1836bo$1835b3o65bo$1765b2o67b5o63bo$1765b2o4b3o
59b2o3b2o62b3o$1751bo10b2o6b5o59b5o$1751bobo7b3o5bo3bobo58bo3bo$1754b
2o6b2o6bo3b2o59bobo$1754b2o9b2o69bo$1754b2o9b2o$1742b2o7bobo$1741bobo
7bo11bo72b2o$1741bo19bobo72b2o$1740b2o20b2o5$1770bo$1771bo$1769b3o6$
1778bo$1767b2o7bobo$1768bo8b2o$1765b3o$1765bo3$1785bo$1786bo$1784b3o6$
1793bo$1791bobo$1792b2o5$1800bo$1801bo$1799b3o6$1808bo$1806bobo$1807b
2o5$1815bo$1816bo$1814b3o16$1831b2o$1831bo$1832b3o$1834bo542$1118b2o$
1119b2o$1118bo1088$15bo$15b3o$18bo15b2o$17b2o14bo2bo$36bo$36bo$34bobo$
34bobo$3b2o30bo$2bo2bo$2bo$2bo29b2o3b2o$2bobo11bo6bo8bo5bo$2bobo11b2o
5bo$3bo11bobo11b2o2bo3bo$28b2o4b3o$30bo$2o3b2o$o5bo2$bo3bo2b2o$2b3o4b
2o$8bo24bo$31b2ob2o2$30bo5bo2$30b2obob2o$5bo$3b2ob2o2$2bo5bo2$2b2obob
2o3$32b2o$32b2o5$5b2o$5b2o39$87b2o$88bo$88bobo5b2o$89b2o5bobo$97b3o$
98b3o$97b3o$96bobo7b2o$96b2o8bobo$108bo$108b2o!

I also shortened the glider loop so it runs each row faster in viewer. I'm about at the limits of my large pattern construction ability here, really struggling to make collisions by trial and error (I find a starting collision using gencols, then hope that subsequent collisions do what I need and tweak as needed). One thing is that because you don't know what phase the counter is in, you need to leave a window of 3 gliders in the p30 blocker streams to make sure it is open no matter the phase. Some collisions are fortuitous, like the collision when 0 enters at count 0 and the inverted bit glider destroys a succession of gliders. This is useful in synching up the windows (though I forget how). The main thing is that because the counter is based on a p90 gun, it reports its state every 90 generations and it is OK to destroy/ignore most of these copies.

ADDED: It may help to see the counter component separately. This demonstrates the counter using a p1080 increment pulse (northeast-going glider) and a p5400 reset pulse (north-going LWSS).

The first increment is deleted because the counter is already at 2. The reset brings it back to 0. The next two increments move it from 0 to 1, then 1 to 2. After that, the next two increments are ignored and the cycle repeats. This does not demonstrate the reset from 1 to 0, but it should be sort of clear that the LWSS always sets the p90 counter component to the same phase (which we call 0).

Code: Select all

x = 286, y = 226, rule = B3/S23
157b2o$157b2o11$156b5o$155bob3obo$156bo3bo$157b3o$158bo4$160bo$160bo$
153bo5bobo$153bobo2b2ob2o$153b2o2bo5bo$160bo$157b2o3b2o3$146bo$145bo6b
2o$145b3o4bobo$152bo9b2o$162bo$163b3o$165bo3$159b3o$159bo$160bo$182bo$
180b3o$179bo$179b2o$159b2o$159b2o3$160bo28b2o$159bobo27b2o$158bo3bo$
123bo34b5o$123bobo31b2o3b2o10b3o10bo$123b2o33b5o11bo13bo$159b3o13bo12b
o$160bo7b2o$168b2o$164b2o20b2o3b2o$163bobo23bo$165bo16b2o2bo5bo$105bo
76bobo2b2ob2o$105b3o74bo5bobo$108bo80bo$107b2o80bo3$161b3o$110bo49bo3b
o22bo$110bo75b3o$109bobo47bo5bo19bo3bo$108b2ob2o46b2o3b2o18bob3obo$
107bo5bo71b5o$110bo$107b2o3b2o48bo$161bobo$122bobo36bobo$111bo11b2o36b
o$111bo11bo37bo$112bo48bo2bo$162b2o2$109b2o$109b2o75b2o$186b2o14$145bo
$146b2o$145b2o6$153b2o$153bobo$155bo$155b2o32$76b3o$78bo172bo$77bo172b
2o13b2o$249b2o4b2o8b2o$248b3o4b2o2b2o$249b2o4b2o2b2o$239bo10b2o$196b2o
5bo5b2o19b2o6b3o10bo$196b2o5b3o4bo19bo7b3o$206bo3bobo6bobo6bobo35bo$
205b2o4b2o5bo2bo6b2o6b2o3b2o22b3o$196bo20b2o17b2o3b2o22b3o$195b3o17b2o
3bo$194bo3bo18b2o30bobo11b2o3b2o$196bo10b3o8bo2bo27bo3bo9b2o3b2o$193bo
5bo6b2ob2o8bobo31bo5b2o$193bo5bo6b2ob2o38bo4bo4b2o$194bo3bo7b5o33bo8bo
12b2o$195b3o7b2o3b2o32bo4bo3bo11bobo$249bobo12b2o2bo$13b2o204bo45b2o$
5bo5bo3bo202bo46b2o$4bobo3bo5bo192bo8b3o44bo$4bobo2b2obo3bo8b2o182bo$
5bo4bo5bo8b2o183bo54bo5bo$11bo3bo186b2o50bo10bo5bo9b2o$13b2o185bo2bo5b
o25b3o17bo3bo6bo3bo10b2o$2b2o3b2o190bo9bo24bo3bo15bo4bobo5b3o$2bo5bo
190bo34bo3bo20b2o$199bo12b3o5bo6bo7b3o$3bo3bo192bo2bo15b2o6b2o$4b3o
195b2o14b3o6b3o$33bo185b2o6b2o17b3o32b3o$29b2o2b2ob3o181bo6bo52b2ob2o$
8bo20b2o4b4o196b3o42b2ob2o$8bo24b2o199bo3bo10b2o4b2o23b5o$215b2o17bo3b
o9bobo3bo2bo10b2o9b2o3b2o$214b3o18b3o9b2o6b2o11b2o$213bobo2bo2b2o23b3o
6bo$213b2o2b2o2b2o24b2o$217b2o31b2o$250b2o28b2o$3bo$2b3o269bo$b5o267bo
bo$2o3b2o254bobo8bob2o$b5o255bo2bo6b2ob2o$bo3bo235b2o9b2o10b2o6bob2o$
2bobo236bo10b2o8bo3b2o5bobo$3bo38b2o198bo14b2o5b2o8bo$42b2o197b2o13bo
4bo2bo$13bo247bobo$3b2o6b3o10b2o$3b2o5bo12bobo17bo$10b2o13bo16bobo$30b
3o8bo3bo$30bo10b5o$31bo8b2o3b2o$41b5o$42b3o$7b3o6b3o24bo$6bo3bo7bo$5bo
5bo5bo$5b2obob2o2$165bo$11bo153b2o$10b2o26bo117b2o2b2o4b2o$38bo117b2o
2b2o4b3o$9bob2o147b2o4b2o$8bo2b2o152b2o9b3o$8b4o28b3o122bo$39bo3bo132b
obo$175b5o$7b2o3b2o24bo5bo129b2o3b2o$10bo27b2o3b2o129b2o3b2o$7bo5bo$8b
2ob2o$9bobo9b2o18bo135bo$10bo9bobo17bobo135b2o$10bo8b3o4b2ob3o8bobo$
18b3o4bo2b4o8bo139bo$19b3o4b2o12bo$20bobo17bo2bo132bo2bo$21b2o18b2o
133b2o!

In the rule 110 implementation, the reset depends on the input bit and needs to be complete and in the right part of the counter output stream in time for the next input bit, so this limits the clock speed.

I'm sure there is something faster even with the above component, but it might require some redundant calculations. This is designed to reuse collisions as much as possible. Note that given x and y, a collision outputs both (not x and y) and (x and not y), and in this case, both results often turn out to be useful.

Another path to rule 110 implementation is just to compute the logic directly. E.g. for a 3-cell window of abc, output f(a,b,c) = (b or c) and not (a and b and c). You need to capture the bits at the right section of the stream and use some kind of fanout. I think this may be much faster, but I'm not eager to work out the timing.

Again, the main reason for doing this at all, was the observation that rule 110 maps in a simple way to a state machine with a counter that supports increment up to 2 and reset. It is possible that a natural stable pattern could be found with this behavior, including ignoring increments after 2. This may not be faster than the faster collision logic implementation but it may be more compact.

[Naszvadi]

I wonder if a growing glider loop reflected back by 2 corderships could help and yields a constructive proof of Turing-completemenss of CGoL supporting a glider tape Rule-110 emulator. I mean that there is a marked glider among the members of the loop, which triggers the logic to insert stored glider sequences according to the infitine tiles used in the universality proof of Rule-110.

Some details were acquired from:
viewtopic.php?t=&p=54583#p54583
viewtopic.php?t=&p=54583#p54585

Code: Select all

x = 256, y = 263, rule = B3/S23
19b3o$19bo$20bo14$bo$2bo$3o14$17bo33b3o$18bo32bo$16b3o33bo14$33bo$34bo
$32b3o14$49bo33b3o$50bo32bo$48b3o33bo14$65bo$66bo$64b3o14$81bo33b3o$
82bo32bo$80b3o33bo14$97bo$98bo$96b3o14$113bo33b3o$114bo32bo$112b3o33bo
14$129bo$130bo$128b3o14$145bo33b3o$146bo32bo$144b3o33bo6$236bo$231b4o$
234bo$234bo2$232b2o$233b3o2$161bo84b2o$162bo83b2o$160b3o$200bo$199b3o$
199bobo$200b3o$199bobo$198b2obo$248b3o$198b2o48bo$200bo47b2ob2o$198bob
o49b3o$198bo51b3o2$200b2o$177bo72b3o$178bo74bo$176b3o2$230bobo3bo10bo
3bo$225b3o9b2o12bo3bo$225bo2b2o4b2obobo9bo$225b2ob4o4b4o9b2o$227b3o$
213b2o34b2ob2o$213b2o36bo6$193bo$194bo26b2o$192b3o26b2o$233b4o$232b2ob
2o$232b2o3bo2b3o$232b2ob2o$195b3o36bo5bobo$195b4o42bo$199bo$196bobo$
196bobo$196b2o2$210b2o$210b2o7$213bo$211b2obo$211bo4bo$212bo3b2o$214b
4o3$215bo$214bobo$215bo2$201bo$192b2o6b3o$188b2ob3o4b2obobo$187b3ob2o
10b2o7bobo$188b2ob3o4bo4bo8bo2bo$191b2o6b4o9bo2bo$177b2o22bo13bo$177b
2o35b3o7$185b2o$185b2o10bo$196bobob2o$198bo2b2o2bo$201bo2b3o$195bo2bo
2b4ob2o$196bobo5b3o$197bo7bo!

[fluffykitty]

One issue with that is the fact that the tape is stretched, so the only way to actually use any of the additional space is to insert additional cells between the existing ones, and properly using that requires a much more complicated 1DCA.

[pcallahan]

I haven't been idle on this topic, but I decided to take a different approach, throwing away the 3-state machine, though I am still fond of it, and doing the computation directly on p120 MWSS streams that can be extended indefinitely with a puffer construction.

Instead of a state machine, I use the transition function

Code: Select all

f(a,b,c) = (b or c) and not (a and b and c)

which implements the rule110 rule. I realized that there is an elegant way to compute AND for any series of k consecutive bits in the inverted side of the MWSS stream and a less elegant but workable way to compute OR of two consecutive bits. Then the rest is just routing the signals to the right place.

It's all p30 logic, basically doable 30 years ago, but not with the small p120 glider guns.

This can all be done fast enough to compute the rule110 transition function on a p120 stream, no need to thin it down further. I will leave the detailed explanation as an exercise, but I think the above is enough to start.

Code: Select all

#C [[ STEP 10 ]]
x = 849, y = 131, rule = B3/S23
786b2o$786b2o6$610bo174b3o$610b3o171b2ob2o$613bo170b2ob2o$612b2o170b5o
$783b2o3b2o16b2o$721b2o83bo$721b2o72b2o7bobo$795bo2bo5b2o$601b2o5b2o
176b6o7bo42b2o$601b2o5b2o175bo6bo6bo42b2o$785bo4b2o7bo$605b2o179b2o7bo
2bo8bo$605b3ob2o110b3o71b2o10b3o$21b2o583b4obo198bo31bo$21b2o584bobob
2o108bobo85b2o30bobo$606b2obo2bo107b5o115bo3bo$607b2o19b2o89b2o3b2o
115b3o$608b4o3bo12b2o89b2o3b2o113b2o3b2o$616bo$21bo592b3o8b2o5b2o164b
2o5b2o7b2o$21bo603b2o5b2o88bo75b2o5b2o$20bobo700b2o89bobo$19b2ob2o778b
2o14bo25bo$18bo5bo700bo2bo73b2o12b2obob2o21bo$21bo703bo2bobo87b2obo18b
3obo$18b2o3b2o695bo4bo5b2o4b2o81bo$11b2o705bo12b2o4b2o100bo$10bobo704b
o5bo7b2o92b2o12b2obo$9b3o4b2o3bo695bo3bo6bobo94b2o14b2o$2o6b3o4bo2b3ob
o694b4o7bo72bo$2o7b3o4b2ob2obo776b3o20b2o5b2o$10bobo8bo776bo23b2o5b2o
10b2o3b2o$11b2o785b2o41b2o3b2o$3b2o16b2o25b3o57b3o57b3o57b3o57b3o57b3o
57b3o57b3o57b3o57b3o57b3o57b3o57b3o63bo7b5o$3b2o15bobo24b5o55b5o55b5o
55b5o55b5o55b5o55b5o55b5o55b5o55b5o55b5o55b5o55b5o61bo9bobo$22bo24b3ob
2o54b3ob2o54b3ob2o54b3ob2o54b3ob2o54b3ob2o54b3ob2o54b3ob2o54b3ob2o54b
3ob2o54b3ob2o54b3ob2o54b3ob2o60b3o$50b2o58b2o58b2o58b2o58b2o58b2o58b2o
58b2o58b2o58b2o58b2o58b2o58b2o71b3o3$825b2o$3b3o581b2o235b4o$13b3o570b
2ob3o231bo4bo$3bobo9bo571b5o232b4o16b2o$2b5o7bo573b3o234b2o17b2o$b2o3b
2o41b2o785b2o$b2o3b2o10b2o5b2o7b2o14bo776bo8bobo$18b2o5b2o20b3o776bob
2ob2o4b3o7b2o$34bobo10bo597bo180bob3o2bo4b3o6b2o$6b2o14b2o14bo607bo
180bo3b2o4b3o$6bob2o12b2o12b2obob2o601b3o189bobo$9bo28b2obo794b2o$40bo
783b2o3b2o$4bob3o818bo$4bo40b2o763bo13bo5bo$4bo40b2o764b2o12b2ob2o$
810b2o14bobo$42b2o5b2o684bo11b2o5b2o71bo$42b2o5b2o639b2o42b2obo9b2o5b
2o71bo$689bobo43bob2o$3b2o3b2o681bo6b2o5b2o29bo13b2o$5b3o690b2o5b2o43b
2o$4bo3bo$5bobo30b2o641bo19b2o123b2o$6bo31bo641bobo18b2o123b2o$39b3o
640bo44b2o$41bo685b2o2$5b2o672bobo41b2o5b2o$5b2o671bo3bo40b2o5b2o$678b
o4bo$674b2o8bo$674b2o3b2o2bo97b2o44b2o$681b2o99bo44bo$734b2o43b3o46b3o
$735bo43bo50bo$732b3o$732bo$675bo$676bo$674b3o8$693b2o6b2o$692bo2bo4bo
2bo$692bo2bo4bo2bo$692bo2bo4bo2bo$693b2o6b2o17$642b2o$641bobo$631b2o7b
o$631b2o7bo2bo2b2o$640bo6bo$641bobo2b2o$642b2o6bo$650bo$649bobo$650bo$
650bo$650bo$650bo$649bobo$650bo$650bo!

The uninverted stream is running right to left so the rule110 rows read left to right: 1, 11, 111, 1101, 11111, 110001, etc. The extensible part is on the left in this pattern, but it is not extended here.

Two comments on making this pattern into a universal computer. (1) dvgrn rightly points out that Cook's proof relies on a periodic extension of the pattern that is not all 0s, so it is not that simple to grow the loop and simulate a tag system. (2) Even growing the loop with each pass would require some additional logic and maybe a second loop just to carry the "extend" bit.

Still, I think this might be the fastest stream computation of rule110 that has been made (probably not fastest possible). Any competitors?

For reference, here's the extensible loop without any extra logic. This one extends on the right side.

Code: Select all

x = 255, y = 122, rule = B3/S23
163bobo$163b2o$164bo15$235b2o$233b2ob2o13b2o$233b4o13b4o$234b2o14b2ob
2o$252b2o3$233bo4b2o$224bo7b3o3b2o9b2o$225b2o4b2ob2o12bo2bo$224b2o4b3o
b3o11bo2b2o$230b3ob2o11bo2b2o$232bobo12b4o$133bobo83bo$133b2o76b2o7b2o
$134bo73b3ob2o5b2o30b2o$208b5o29b4o4b4o$209b3o22bo2bo3bo3bo4b2ob2o$
214bo23bo6bo6b2o$215b2o9bo7bo3bo2bo2bo$167b2o45b2o8b3o3bo4b4o$165b2ob
2o13b2o39b2o5b2o$165b4o13b4o37bo6b3o$166b2o14b2ob2o37b2o5b2o$161bo22b
2o38b3o3bo4b4o$160bo65bo7bo3bo$160b2o76bo$159b2o73bo2bo$181b2o$175b3o
3bobo$154bo17b3o6bob2o44b4o$155b2o15bo9b2o44bo3bo12bo2bo$154b2o16b3o7b
o49bo16bo$199bo13b2o13bo2bo13bo3bo$143b2o55b2o9bo4bo29b4o$140b3ob2o3bo
33b2o14b2o16bo7b3o$140b5o5b2o22b4o4b4o25bo5bo$141b3o5b2o15bo2bo3bo3bo
4b2ob2o25b6o6bo2bo14b2o$5b2o163bo6bo6b2o38bobo18bo$5b2o159bo3bo2bo2bo
42bo20b2o4b2o$156b2o9b4o49bo18b2o6bo$41bo113b2o5b3o53b3o17b2o7bo$39b3o
109b3o6b2ob2o74bo3bo2bo$38bo64bobo49b2o5b3o79bo$38b2o63b2o51b2o9b4o43b
o$104bo34bo26bo3bo44bo22b2o5bo2bo$140b2o28bo30bo11b3o21b4o8bo$5b3o131b
2o25bo2bo30bo28b4o4b2ob2o3bo3bo$4bo3bo175bo15bo17bo9bo3bo6b2o5b4o$3bo
5bo32b2o5b2o134b2o32b2o11bo$3b2obob2o32b2o5b2o110b4o19b2o30b3o5b2o2bo
2bo$160bo3bo50b3o6b3o$45b2o117bo51b3o5b2o2bo2bo$6bo38b2o113bo2bo34bobo
18b2o11bo$5bobo189b2ob3o15bo9bo3bo$5bobo188b3ob2o27b4o$5b2o190b5o$4bo
17b2o174bobo$3b3o16b2o11b2o2bo159bo$2bo3bo27b3o2b2o6bo$bob3obo10b2o5b
2o8b2o2b3o5b3o74bo$2b5o4bo6b2o5b2o8b2o2b2o9bo74b2o$12b2o35b2o73b2o$11b
2o156bo4bo$51b5o55b5o54b2obo$51bo4bo54bo4bo52b2o2b2o3bo$51bo59bo66bo$
52bo3bo55bo3bo59bo$44bo9bo49bo9bo62bo$18bobo21bo3bo55bo3bo89b2o$19b2o
26bo59bo88b3o15b4o$19bo22bo4bo54bo4bo84b2o5bo3bo9bo3bo$3b2o38b5o55b5o
32b2o49b8o5b2o11bo$3b2o133b2ob2o48bo2bob2o3b3o5b2o2bo2bo$10bobo95b2o
28b4o53b2o3b3o6b3o$10bo3bo93bo30b2o54b2o4b3o5b2o2bo2bo$2o12bo94b3o83b
2obo5b2o11bo$2o8bo4bo4b3o88bo77bo4bo4bo3bo9bo3bo6b2o5b4o$14bo5b3o123b
2o42b10o14b4o4b2ob2o3bo3bo$10bo3bo4bo3bo111bo8b2ob2o42b5o3bo22b4o8bo$
10bobo5bo5bo32bo75bobo4bo3b4o51b3o21b2o5bo2bo$19bo3bo32bobo73bo2bo5bo
3b2o53b2o$20b3o32bob2o73bo6bo2bo56b2o27b2o$49b2o3b2ob2o6b2o56bo8bo2bo
5bo3b2o65bob2o11b5o$49b2o4bob2o63b2o9bobo4bo3b4o62bo5bo10bo4bo$56bobo
76bo8b2ob2o55b3o9bo10b3o2bo$57bo61bo26b2o5b2o5b4o42bo3bo5bo11bo2b2o$
63bo53bo3bo4b3o22b2ob2o3bo3bo41bo5bo3bo2b2o9b2o$64bo57bo5bo22b4o8bo33b
6o9b3o3b2o$64bo52bo4bo4bo24b2o5bo2bo33bo5bo$118b5o79bo$150bo45bo4bo29b
4o$21b2o39b2o3b2o62b3o15b2o8b2o37b2o13bo2bo13bo3bo$21b2o42bo67bo14bo9b
o2bo55bo16bo$62bo5bo63bo16b5o4bo2bo51bo3bo12bo2bo$63b2ob2o82b4o3b2ob2o
52b4o$64bobo86bo4b2o$65bo70b3o$65bo72bo$137bo$160b4o$142bo2bo13bo3bo$
146bo16bo$65b2o75bo3bo12bo2bo$65b2o76b4o!

ADDED: The code for extending the loop could consist of a string that cannot be created by any application of rule110 (i.e. a Garden of Eden). But the logic for recognizing it would probably be bigger than the computation itself. It would be sort of cool to make this extensible though. Any thoughts? I can definitely go the sledgehammer route of adding a second delay line, but I hate that idea.

ADDED (4/19/19): I have been thinking for the past couple of weeks about dvgrn's point on the difficulty of actually using rule110 as a proof of universality. One idea I'd like to suggest is that we think about what kind of universal model maps most easily to the extensible delay line. Contrary to my initial thoughts, it is not rule110, but it could be something like an elementary CA except that the output can include a zero insertion. So the transition function f(a,b,c) could have ranges consisting not just of single bits y, but bits preceded or followed by an inserted 0 (0y or y0). Then the tape extension code does not depend on identifying a full pass. It can occur in any 3-cell neighborhood. This design makes it pretty easy to insert 0s before or after an output bit, and I believe there is some universal stream-rewriting rule of this form. It might be necessary to extend the neighborhood beyond 3 bits.

(And yes, I know there are already plenty of universality proofs for Life; I also have Critters in mind one of these days, though it will require some kind of periodic input stream since glider guns cannot exist in it.)

[Naszvadi]

One issue with that is the fact that the tape is stretched, so the only way to actually use any of the additional space is to insert additional cells between the existing ones, and properly using that requires a much more complicated 1DCA.

No, does not need other 1DCA. Consider only adjusting the needed 14-cell infinite tiling's appropriate phase in W110 only on the right side, because it can generate the tiling safely to the left direction, might this be a new discovery?

Code: Select all

x = 184, y = 1, rule = W110
2obob2o2bo2b2ob3o2b3o3b2o3bo3b2ob2obob5ob3o6bo3b3o5b2ob5o3b3o4bob2o5bo
3b5ob2ob2o3b3obob5o3bo2b2ob3o2b2o3bo2b2ob5o3bo2b2ob5o3bo2b2ob5o!

It is a simplified version derived from this speed-c supporting by a blocking v0 spaceship on the right:

Code: Select all

x = 50, y = 1, rule = W110
bobobobo3bo2b2ob5o3bo2b2ob5o3bo2b2ob5o!

The tiling itself is a length-14 "bbbobboobooooo!"