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)]

nextgen.append(str(output))

print(cells)

cells = "".join(nextgen)

Output:

`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).

`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.