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.
