Glider circuits: components and contraptions

For discussion of specific patterns or specific families of patterns, both newly-discovered and well-known.
User avatar
PM 2Ring
Posts: 152
Joined: March 26th, 2009, 11:18 am

Re: Glider circuits: components and contraptions

Post by PM 2Ring » April 3rd, 2010, 2:48 am

calcyman wrote:
Collatz sequence generator
I am absolutely stunned! You've probably found more uses for that adder circuit than anyone else.
Thanks, calcyman! It's fun building these things, and actually I'm a little surprised that there aren't more patterns floating around that use that adder circuit.
From what I can see, it appears to operate in binary, with a LWSS read-out device at the top of the pattern. I guess that tripling a number is accomplished by shift addition, whereas halving a number is a simple binary shift.
Yes. Binary shifting is easy, and can generally be performed by a simple delay (although some of my circuits have used the inline advancer). The adder circuit is used to add n & 2n+1, the 2n+1 is formed by inserting a copy of the parity bit (which is the LSB of n) in front of n. That was rather tricky to synchronize in space and time.
What are you using the bistable switch for?
It's part of the switchable glider reflector subsystem. If n is odd, the reflector gets turned on before the data arrives, and it needs to be turned off before the next cycle. The reflector gets turned on by one copy of the parity bit, and it's essentially turned off with another copy. A delay circuit of period around 7000 would be too large (although I did build a pretty Herschel based one), so instead I use the bistable switch as a simple 1 bit memory.

A copy of the parity bit sets the switch (from block to boat), so when the reflector reset bit arrives from the p7680 gun in the southeast corner it get's reflected by the switch into the p60 stream that controls the switchable p60 LWSS gun that is the heart of the switchable glider reflector. If the bistable switch is off, the reset bit travels through the switch & hits an eater.

The switchable glider reflector is a toggle switch, so attempting to turn it on when it's already on will turn it off, and vice versa. The former would never happen in this application, since an odd number in the Collatz sequence must always be followed by an even one. But it's nice to make these things work properly. :) I'm sure there are other applications for a mechanism that converts a toggle switch into one with separate on & off inputs.
That's very compact as well; if I attempted to make such a device, it would have been larger than 20000 * 20000.
Your computation-oriented structures do tend to be very large! :) I think I need to upgrade Golly (& my OS) before I can play with your recent constructions. I'd love to see how your efforts at display circuitry are going.

I suppose I could've made my Collatz generator a little bit smaller, but once I realized the period was going to be around 7000, I decided to make it p7680 so I could use that very compact p7680 glider gun. And so I didn't bother optimizing the space that much, and besides, I needed some space for all those Buckaroos that were required to get the glider spacing & timing correct. :)
It's a shame that your device only has finite memory. Since you like p30-oriented technology so much, I recommend that you have a look at Paul Callahan's extensible delay-line memory:
[...]
The data is contained in a loop of MWSSes, which circulate between two eaters. LWSSes can be launched to extend the delay-line memory, in order to accommodate more bits. I'd like to see a pattern exploting this beautiful mechanism; you might be the first to use it in an arithmetic/logic circuit.

Alternatively, you might want to use sliding-block memory, but I think that delay-line memory is more suited to your style of computation.
Thanks for that! I'll certainly play around with it, and see what I can do with it. I've looked at the sliding-block memory, but you're right, it's not my style. It's too bulky, and I prefer to work with bitstrings. OTOH, I do have a soft spot for any reactions that push, pull, or otherwise transform still-lifes, as you may have noticed from my avatar. :)

TLUL
Posts: 15
Joined: January 24th, 2010, 1:16 am

Re: Glider circuits: components and contraptions

Post by TLUL » May 24th, 2010, 2:49 am

calcyman wrote: It's a shame that your device only has finite memory. Since you like p30-oriented technology so much, I recommend that you have a look at Paul Callahan's extensible delay-line memory:

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!
The data is contained in a loop of MWSSes, which circulate between two eaters. LWSSes can be launched to extend the delay-line memory, in order to accommodate more bits. I'd like to see a pattern exploting this beautiful mechanism; you might be the first to use it in an arithmetic/logic circuit.
Ooh, that's a pretty mechanism.

I also tend to prefer p30 technology (my last experiment with herschels ended up with three conduits in the hospital), but my best attempt at a memory circuit was far more inefficient than this, was fixed to p30 (whereas this can be adapted to any common period), and had no extensibility. I think I'll use this in a few of my patterns, it's the best I've seen yet.

If anyone's interested in my not-so-great memory loop, here it is, complete with set and unset streams:

Code: Select all

x = 124, y = 92, rule = B3/S23
42b2o$43bo$43bobo8b2o$29b2o13b2o6bo2bo7bo$29b2o20bo7b2o3bo$51bo6bo5bo$
51bo7b5o$52bo2bo$30bo23b2o$29b3o$28bo3bo$27bob3obo$28b5o5$43bo$41b3o$
40bo$40b2o2$27b2o$28bo$25b3o$25bo2$38b2o$31b2o5bobo$30bobo5bo$32bo3$
46b2o8bo$46bo2bo6bobo$41b2o2bo3bo7bobo4b2o38b2o$23b3o14b3o2b2o2bo7bo2b
o3b2o38b2o$25bo4b2o5bob2o16bobo$24bo5b2o5bo2bo8b3o4bobo$37bob2o15bo$
40b3o$41b2o2$16b2o$15bobo86bo$17bo48b2o35b3o$66bo35b5o$64bobo3b2o29b2o
3b2o$64b2o4b2o3$8b3o92b3o$10bo92b3o$9bo$70b3o33bo$60b3o42bobo$54b3o3bo
9bobo31bo3bo$56bo4bo7b5o31b3o$b2o52bo12b2o3b2o23bo4b2o3b2o$obo65b2o3b
2o16b2o5bobo$2bo88b2o5b2o2$68b2o$47b2o17b2obo$46bobo17bo$48bo42bo$67b
3obo18bo$71bo18b3o15b2o$71bo36bo$109b3o$111bo$39b3o$41bo$40bo25b2o3b2o
$68b3o$67bo3bo$68bobo9b2o$69bo9b4o5b2o$32b2o44bo2bobo4bobo$31bobo43bob
o2b2o4bo$33bo42bobo$68b2o5b2o24b2o$68b2o5b3o23bobo$76bobo12bo4b2o4b3o$
77b2o11bobob2o2bo4b3o6b2o$89bo3bob3o4b3o7b2o6b2o$24b3o62bo3bob2o4bobo
16bobo$26bo62bo3b2o6b2o19bo$25bo54b2o8bobo29b2o$79bobo9bo$79bo$78b2o!
Carpe per diem: Seize the check.

Phantom Hoover
Posts: 20
Joined: May 16th, 2010, 3:54 pm

Re: Glider circuits: components and contraptions

Post by Phantom Hoover » May 24th, 2010, 11:42 am

Apropos of nothing, there is a binary adder in WireWorld that can handle arbitrarily large integers at http://www.quinapalus.com/wires8.html. This should be translatable into Life, though stabilising it might be tricky.

User avatar
Extrementhusiast
Posts: 1833
Joined: June 16th, 2009, 11:24 pm
Location: USA

Re: Glider circuits: components and contraptions

Post by Extrementhusiast » May 25th, 2010, 11:07 am

My triple-vanish reaction (kudos to PM 2Ring? need to confirm):

Code: Select all

x = 13, y = 11, rule = B3/S23
bo$2bo$3o3$8b4o$8bo3bo$8bo$b3o5bo2bo$3bo$2bo!
I Like My Heisenburps! (and others)

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

Re: Glider circuits: components and contraptions

Post by Naszvadi » December 17th, 2016, 1:25 pm

So many cool patterns... I wonder if other glider-compatible included nontotalistic rules are supported by any of them. I am working on collecting common circuit components in rules B3[678]/S23[678] in order to prove universality. included my partial results in one of my topics. (And subscribed here)

User avatar
gameoflifemaniac
Posts: 1049
Joined: January 22nd, 2017, 11:17 am
Location: There too

Re: Glider circuits: components and contraptions

Post by gameoflifemaniac » March 17th, 2017, 11:02 am

PM 2Ring wrote:Binary arithmetic with gliders

This circuit calculates the Fibonacci sequence in binary using p60 and p30 glider
streams. Output is displayed using LWSS bits. A new Fibonacci number is
generated every 2100 generations.

The arithmetic unit at the heart of this construction is the amazing
Binary Adder circuit created by David Buckingham in 1975, with size
optimization by Mark Niemec. This circuit adds two binary numbers
represented by p60 glider streams, with the least significant bits
leading. This allows numbers of any length to be added. Input data
enters the adder circuit at its upper left and the sum begins to emerge
from the circuit at its lower right after 600 steps.

How it works
The Fibonacci numbers are defined as follows:
F(0) = 0, F(1) = 1, and for n>1, F(n+1) = F(n) + F(n-1).

This circuit loops two copies of the output stream back into the adder
input, with one copy delayed so that the last two results get added
together.

The cycle starts with p60 glider streams representing the previous two
Fibonacci numbers entering the left side of the adder.

Step 600: The sum starts to emerge from the right of the adder.

Step 1200: The p60 data hits a p30 stream, which causes each p60 data
bit to create a pair of inverted p30 data bits.

Step 1500: The inverted p30 stream meets a p60 stream, which splits the
data into two streams. One copy of the data collides with the p60
stream, uninverting the data & sending it back up towards the adder
input. The other copy of the data passes through the p60 stream & heads
towards a p30 inverting reflector, which sends it up to a p30 inverting
reflector/duplicator.

Step 2960: Data hits the inverting reflector/duplicator. One copy of the
data (still inverted) continues around the loop, back towards the adder.
The other copy (now uninverted) heads towards the output section. This
data stream allows the output of a p60 gun to reach a glider to LWSS
converter, which creates the output display. The output region at the top
of the pattern show the last two Fibonacci numbers calculated. So this pattern can also be conidered as a calculator for phi, the golden ratio, in binary fraction form.

Meanwhile, at step 1860, data from the previous cycle in the big loop
reaches a p60 gun near the adder, which inverts it, sending it back up
into the adder.

Code: Select all

#C AdderLoopFib by PM 2Ring, April 2009.
#C
#C Calculates the Fibonacci sequence in binary using p60 and p30 glider
#C streams. Output is displayed using LWSS bits. A new Fibonacci number is
#C generated every 2100 generations.
#C
#C The arithmetic unit at the heart of this construction is the amazing
#C Binary Adder circuit created by David Buckingham in 1975, with size
#C optimization by Mark Niemec. This circuit adds two binary numbers
#C represented by p60 glider streams, with the least significant bits
#C leading. This allows numbers of any length to be added. Input data
#C enters the adder circuit at its upper left and the sum begins to emerge
#C from the circuit at its lower right after 600 steps.
#C
#C How it works
#C ------------
#C The Fibonacci numbers are F(0) = 0, F(1) = 1, F(n+1) = F(n) + F(n-1).
#C This circuit loops two copies of the output stream back into the adder
#C input, with one copy delayed so that the last two results get added
#C together.
#C
#C The cycle starts with p60 glider streams representing the previous two
#C Fibonacci numbers entering the left side of the adder.
#C Step 600: The sum starts to emerge from the right of the adder.
#C Step 1200: The p60 data hits a p30 stream, which causes each p60 data
#C bit to create a pair of inverted p30 data bits.
#C Step 1500: The inverted p30 stream meets a p60 stream, which splits the
#C data into two streams. One copy of the data collides with the p60
#C stream, uninverting the data & sending it back up towards the adder
#C input. The other copy of the data passes through the p60 stream & heads
#C towards a p30 inverting reflector, which sends it up to a p30 inverting
#C reflector/duplicator.
#C Step 2960: Data hits the inverting reflector/duplicator. One copy of the
#C data (still inverted) continues around the loop, back towards the adder.
#C The other copy (now uninverted) heads towards the output section. This
#C data stream allows the output of a p60 gun to reach a glider to LWSS
#C converter, which creates the output display.
#C Meanwhile, at step 1860, data from the previous cycle in the big loop
#C reaches a p60 gun near the adder, which inverts it, sending it back up
#C into the adder.

x = 1687, y = 554, rule = B3/S23
141b2o$141b2o3$141bo$140b3o$139bo3bo$141bo$138bo5bo$138bo5bo$139bo3bo$
140b3o7$134b2o$126bo7bo2bo$125bo3b2o7bo$125bo5bo6bo$126b5o7bo$134bo2bo
$134b2o$1683b2o$1683bobo$1685bo$167b2o9b2o28b2o28b2o28b2o28b2o28b2o28b
2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b
2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b
2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b
2o28b2o28b2o5b2o$167b2o9b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b
2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b
2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b
2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o2$
628b2o1048b2o$166b3o459b2o1048b2o$166b3o$628b2o1048b2o$628b2o1048b2o2$
164b2o3b2o$165b5o$166b3o$167bo7$169b2o$169bo$170b3o$172bo8$157b3o$151b
3o3bo$153bo4bo$152bo12$172b3o$136b3o33bo$138bo34bo$137bo2$126b2o$126bo
$117b2o5bobo53b2o9b2o$116b3o5b2o34b2o18bobo7bobo$104bo8bob2o44b2o11bo
5bo8bo6b2o2b2o$104bobo6bo2bo33bo9bo12bobo13bo2bo2bo2bob2o$92b2o11bobo
5bob2o33bobo19bob2o13bo6b2o$92b2o11bo2bo7b3o19b2o11bobo9b2o6b2ob2o14bo
bo$105bobo9b2o19b2o11bo2bo7b3o7bob2o15b2o$104bobo44bobo5bob2o5b2o3bobo
$104bo9bo35bobo6bo2bo4bo2bo3bo$115b2o4b3o26bo8bob2o5b2o$114b2o7bo38b3o
$122bo40b2o6$116b2o$116b2o4$103bo$103b2o24bo$102bobo25b2o$129b2o12$88b
o$88b2o54bo$87bobo55b2o$144b2o12$73bo$73b2o84bo$72bobo85b2o$159b2o12$
58bo$58b2o114bo$57bobo115b2o$174b2o12$43bo$43b2o144bo$42bobo145b2o$
189b2o8$2o$bo$bobo$2b2o$28bo$28b2o174bo$27bobo175b2o$204b2o$2bo$2b3o$
5bo$4b2o$13b2o$13bobo$13bo3$4b2o3b2o$4b2o3b2o10b2o$5b5o3bo7b2o$6bobo4b
2o204bo$12bobo205b2o$6b3o210b2o5$9bo$8bobo$7bo3bo$8b3o$6b2o3b2o14b2o$
26b2o$28bo2$234bo$235b2o$234b2o5$8b2o$8b2o3$42b2o$41b2o$43bo2$249bo$
250b2o$249b2o3$580bo$578b3o$577bo$577b2o2$586bo$57b2o527b3o$56b2o517bo
13bo$58bo515b3o11b2o$574b3o$264bo$265b2o305b2o3b2o$264b2o306b2o3b2o12b
o$590b3o$590b3o$555b2o17b2o$555b3o16bobo11b2o3b2o$541bo15b2obo12bo2b2o
10b2o3b2o$539bobo4b3o8bo2bo14b2o$538bobo16b2obo14b2o$537bo2bo7bo2b2o2b
3o6b2o10bo14b2o$72b2o345b2o117bobo7bo3bo2b2o7bobo23bobo$71b2o348bo112b
2o3bobo6bo2bo14bo3bo5bo12b2o2bo$73bo334b2o12bo110bobo5bo8b2o14b2o2bo5b
o13b2o$408b2o4bo7bo110bo37bo3bo6bo7b2o$279bo125b2o5b2o8bo109b2o38b3o5b
obo7bo$280b2o122b3o5bo2b2o4bo7b2o150b2o$279b2o124b2o6b5ob2o8bobo121b2o
4bo30bo5bo$399b2o7b2o4bo16bo120bobo2bobo30bo5bo$398bobo7b2o21b2o121bo
3b2o25b2o4bo3bo$398bo186b2o5b3o$397b2o23bo104b2o$423bo104bo$421b3o104b
obo5bo8b2o$529b2o3bobo6bo2bo25b2o$416b3o114bobo7bo3bo2b2o20b2o$87b2o
329bo14b2o19b2o76bo2bo7bo2b2o2b3o24bo$86b2o304b2o23bo16bo19bo78bobo16b
2obo20bo13b2o$88bo304bo40bob2o5b2o7bobo79bobo4b3o8bo2bo20b3o12bo$393bo
bo7b2o30bo7bobo6b2o82bo15b2obo32b3o$294bo99b2o7b2o4bo29bo4b3o103b3o7b
2o2b2o22bo$295b2o103b2o6b5ob2o21bo2bo4b3o102b2o8bobo2bo$294b2o103b3o5b
o2b2o4bo21b2o4b3o28bo65b2o19b2o10bo8bo$400b2o5b2o8bo25bobo28bobo19b2o
44bo19bo9bobo6b3o$403b2o4bo7bo8b2o15b2o29bobo19bo45bobo9bo5bobo10b2o5b
o$403b2o12bo8b2o24b2o19b2obobo5bo9bobo46b2o8bobo4b2o18b2o$416bo20bo15b
o19bo3b2o4bobo8b2o56bo3b2o$414b2o22bo14bobo6bo8bobo7b2o3bo65bo3b2o$
436b3o15b2o6b2o7b2o8b2o3bo65bo3b2o19b3o$457b2o4b2o16b2o3bo66bobo21b3o$
457b2o4b3o17bobo68bo21bo3bo$102b2o353b2o4b2o19bo77bo12bo5bo$101b2o359b
2o11b3o83bo14bo3bo$103bo358bo14bo76bo6b3o13b3o$476bo75b2o$309bo243b2o$
310b2o$309b2o$564bo4b2o$562b2o5bobo$563b2o4bo$452bo127b2o$453bo37bobo
86bo$451b3o38b2o87b3o$492bo90bo2$117b2o428bo$116b2o342b3o83bo$118bo
343bo76bo6b3o$461bo75b2o$324bo213b2o$325b2o$324b2o$549bo10bo23b2o$547b
2o11bobo21bobo$431bo116b2o13b2o6b2o11bo21b2o$431b2o34bo95b2o4bo3bo31bo
bo$430bobo35bo37bobo54b2o3bo5bo20b2o7bo13bobo$466b3o38b2o42b2o7bobo4b
2obo3bo20b2o7bo2bo6b2o2bo2bo$507bo42bobo7bo7bo5bo29bo8bobo5b2o$550bo
18bo3bo7b2o22bobo3bo3bo3bo3b2o$532bo16b2o20b2o8bobo22b2o2b2ob3o5b2o$
445b3o83bo29bo21bo29b2o3bo2bo5b2o$447bo76bo6b3o25b2o22b2o33bobo6bobo$
446bo75b2o36b2o67bo$339bo145bo37b2o104b2o$340b2o141b3o118bo$339b2o141b
o54b3o64bobo$482b2o50bo2bo27b2o32b2o3b2o$426bo105b2o4bo25b2o22b2o9bobo
$424b3o101b3o2b2o31bo21bo10bo$423bo63b2o19b2o18bo47b2o8bobo35b2o$423b
2o55bo7bo19bo12bobo5bo44bo3bo7b2o36bo$473bobo2b2ob2o5bobo10bo4bobo13b
2o41bo7bo5bo10b2o21bobo6bobo$441b2o30b2o14b2o9bobo3b2o14b2o41bobo4b2ob
o3bo11bo16b2o3bo2bo5b2o$441b2o31bo2bo5bo15bo3b2o20bo42b2o3bo5bo11bobo
7b2o2b2ob3o5b2o$147b2o271b3o76bo3b2o12bo5b2o29b2o12b2o4bo3bo13b2o6bobo
3bo3bo3bo3b2o$146b2o282b3o44b2obob2o15bo3b2o11bo7b2o20bo7b2o12b2o6b2o
21bo8bobo5b2o$148bo271bobo9bo67bobo6bo6b3o25b2o19bobo31bo2bo6b2o2bo2bo
$419b5o7bo69bo5b2o36b2o18bo33bo13bobo$354bo63b2o3b2o83b2o90bobo$355b2o
61b2o3b2o15b3o90bo36bobo28b2o$354b2o74b3o100b4o15b3o15bo2bo$430bo9bobo
91b4o14bo8b2o10b2o8bo$423b2o6bo7b5o33b2o55bo2bo15bo7b2o8bo3b2o5bobo$
423bob2o11b2o3b2o33bo55b4o28b2o5b2o6bob2o$426bo11b2o3b2o30b3o47b2o6b4o
5b2o21bo4bo2bo6b2ob2o$325b2o148bo48bobo6bo8bobo25bobo8bob2o$325b2o94bo
b3o32bobo63bo19bo37bobo8b2o$421bo16b2o8bo9b2o63b2o19b2o27bo9bo9bobo$
421bo14b2obo8b3o8bo112bo22bo$162b2o272bo14bo50bo69b3o20b2o$161b2o287b
2o49bo14bo$163bo273b3obo59b3o10b3o$441bo52bo18bo$420b2o3b2o14bo71b2o3b
o$422b3o57bo8b2o25b3o$421bo3bo26b3o25b3o9bo17bo10bo45b3o20b2o$422bobo
26b2ob2o23bo9b3o18bo9b2o45bo22bo$323b5o95bo27b2ob2o23b2o8bo4b2o15bo44b
2o10bo9bo9bobo$322bob3obo107b2o3b2o8b5o37bobo61bo19bobo8b2o$323bo3bo
97b2o11b3o9b2o3b2o36bo63bobo5bobo8bob2o$324b3o98bo11bo3bo50b2o14b2o3b
2o43b2o5bo2bo6b2ob2o$325bo100b3o9bobo67bo5bo53b2o6bob2o$428bo10bo82b3o
41bo3b2o5bobo$476b3o30bo3bo7bo3bo42b2o8bo$177b2o173b2o87b2o32bo3bo30b
3o7bo5bo38bo2bo$176b2o145bo29b2o86bo32bo5bo39b2obob2o38bobo$178bo144bo
28bo89b3o5b2o22b2obob2o$322bobo5bo113bo6bo$321b2ob2o2bobo117b3o72bo$
320bo5bo2b2o117bo28bo35b2o7bobo$323bo113b2o37bobo34bo8bobo$320b2o3b2o
108bo2bo7bo7bo21bobo35b3o6b2o$422bobo9bo7b2o3bo6b2o20b2o38bo8bo$422bo
3bo7bo6bo5bo5bobo19bo48b3o$323bo102bo7bo7b5o27b3o46bo3bo$322bobo97bo4b
o7bo2bo34bo3bo44bob3obo$322bobo101bo10b2o33bob3obo39bo4b5o$323bo90b2o
6bo3bo46b5o4bo33b2o$325b3o85bobo6bobo8bobo47b2o32b2o$192b2o131b3o9b2o
74bo20b2o46b2o$191b2o131bo3bo9b2o72b2o20bo$193bo129bo5bo7bo$324bo3bo$
325b3o$509bobo$489bobo17b2o11b2o$330bo86b2o20bo37b2o11b2o18bo12bo$330b
2o86bo20b2o36bo12bo29b3o$329bobo86bobo6bobo8bobo10b2o25b3o39bo$419b2o
6bo3bo19bo28bo$431bo10b2o5bobo$427bo4bo7bo2bo5b2o52bo$431bo7bo57bo3b2o
$427bo3bo7bo58b2o2b2o$207b2o218bobo9bo57b2o$206b2o120bo111bo2bo$208bo
118b3o112b2o$326b5o$325bobobobo$325b2o3b2o3$328bo$327bobo$327bobo$328b
o$328b2o$328b2o$328b2o$222b2o$221b2o$223bo13$237b2o$236b2o$238bo13$
252b2o$251b2o$253bo13$267b2o$266b2o$268bo13$282b2o$281b2o$283bo5$290bo
$289b2o$266bo22bobo$266b2o$265bobo4$297b2o$296b2o$298bo$257b3o$257b3o$
255bob2o$253b2o$256bobo46bo$257b3o44b2o$251bo6bo45bobo$251b2o10b2o$
250bobo10bobo$263bo$238b2o$237bobo$227b2o7bo6b2o4bo62b2o$227b2o7bo2bo
2bo2bo2bobo20b2o8bo29b2o$236bo6b3obob2o20bo2bo6bobo29bo$237bobo6b2ob2o
15b2o2bo3bo7bobo4b2o$238b2o7bob2o14b3o2b2o2bo7bo2bo3b2o$248bobo11bob2o
16bobo$249bo12bo2bo8b3o4bobo$262bob2o15bo38bo$265b3o51b2o$266b2o51bobo
6$327b2o$326b2o$328bo5$335bo$334b2o$334bobo6$342b2o$341b2o$343bo5$350b
o$349b2o$349bobo6$357b2o$356b2o$358bo5$365bo$364b2o$364bobo2$377b2o$
377bobo$367bo4b2o6bo$366bobo2bo2bo2bo2bo7b2o$366b2obob3o6bo7b2o$354b2o
10b2ob2o6bobo$354b2o10b2obo7b2o$366bobo$367bo!
I also have a larger version of this pattern, which I'll upload if anyone's interested. It's only advantage is that it can calculate much larger Fibonacci numbers before the delay loops "overflow". It's quite easy to convert this pattern to calculate Lucas numbers. Just change the initial data from 0 & 1 to 2 & 1.

I usually run this pattern with a step size of 2100^1, and hit TAB to get it to show the next number. But sometimes I'll run it continuously a slower speed, like 30^1 or even 2^2.
Upload it please.
I was so socially awkward in the past and it will haunt me for my entire life.

pcallahan
Posts: 508
Joined: April 26th, 2013, 1:04 pm

Re: Glider circuits: components and contraptions

Post by pcallahan » April 10th, 2019, 9:22 pm

calcyman wrote:I'd like to see a pattern exploting [the extensible delay line]; you might be the first to use it in an arithmetic/logic circuit.
I realize this reply is a long time in coming (from 2010!) but I at least wrote a binary counter based on some version of the extensible delay line. It used ripple increment and it would extend the line every time the carry overflowed. I think it missed some values around the overflows. I do not know what I did with that. It is possible I posted it to comp.theory.cell-automata in the 90s.

ADDED: Hmm... after some digging, I see that I made the first version of the delay line in early 1991 (?!) and that wound up in the XLife 3.0 distribution. Unfortunately, it's in #I format, so I can't import it into anything else. But I don't think that did anything with the delay line.

So I am left with a fairly vivid memory of watching some version of it implement a simple binary ripple counter. I.e.: invert 1s to 0s until you reach the first 0 and set that to 1. It would somehow determine overflow, maybe with another loop recirculating a marker, and in that case, it would extend the loop length.

I also remember it was rather buggy. E.g., instead of going from 11111 to 100000, it would somehow skip to something like 100101 (maybe it repeated some values without the leading 1). But all I have is the memory. I do not know if I published that pattern anywhere. It was pretty slow in Xlife on an old Sun workstation, but I'd like to see it run in Golly today.

User avatar
dvgrn
Moderator
Posts: 6737
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Glider circuits: components and contraptions

Post by dvgrn » April 11th, 2019, 1:42 pm

pcallahan wrote:... I am left with a fairly vivid memory of watching some version of it implement a simple binary ripple counter. I.e.: invert 1s to 0s until you reach the first 0 and set that to 1. It would somehow determine overflow, maybe with another loop recirculating a marker, and in that case, it would extend the loop length.

I also remember it was rather buggy. E.g., instead of going from 11111 to 100000, it would somehow skip to something like 100101 (maybe it repeated some values without the leading 1). But all I have is the memory. I do not know if I published that pattern anywhere. It was pretty slow in Xlife on an old Sun workstation, but I'd like to see it run in Golly today.
This message from 1994 looks like a good match for your description:
pcallahan wrote:From: Paul Callahan
Date: Sat, 18 Jun 94 01:24:38 EDT
Subject: Self-extending binary integer counter (almost)


Having built a smaller extensible delay line (my last mailing), I decided to construct something that actually does some computation with it. A natural choice was a an integer counter, because you can increment an integer in a delay line in one pass: You just maintain a carry bit. While the carry is 1, you replace every 1 that passes with a 0 until a 0 comes by. In this case you replace it with a 1 and reset the carry to 0. While the carry is 0, you recirculate the data unchanged. If an external clock pulse supplies "restore carry" signals at the appropriate times (just before the least significant bit comes along), you have a k-bit counter, where k is the length of the delay line.

Now the question is how to store the carry bit. I found a way that seemed parsimonious. The only component aside from the p120 delay line of MWSSs is a pair of p60 glider guns that interact with a block-producing collision. This is a standard way of doubling gun period (in a lot of Dean's patterns, anyway). Additionally, if you delete the block at any point, you phase-shift the gun by 60 steps, and this block can thus be used to store a bit. In the first state of the gun (representing a carry of 0), the spaceships narrowly avoid both the glider and the block produced once every 120 steps. In the second state (representing a carry of 1), the negative-logic left-going spaceships will destroy the block (resetting the carry) while the gliders from the gun will destroy the corresponding right-going positive logic spaceships, replacing 1 (negative logic, no spaceship) with 0 (positive logic, no spaceship).

Now, to make the counter self-extending, one must detect overflow. This can be done rather simply as well. The signal to restore the carry consists of a spaceship aimed to destroy a block. But if there is no block to destroy, the spaceship continues through. This can only happen if the entire length of the delay line consists of 1s (or else the carry would have been reset, resulting in a block). Fortunately, this happens to be the overflow condition.

I used a downward MWSS to restore the carry. This has the advantage that if it continues through, it can be converted into a right-going LWSS that deletes an eater, extending the delay line by 1 bit. I used the following reaction (I found it by search, but it's probably old):

Code: Select all

     .**
     .***
     .***
     *.**
     ***
     .*
     .
     .
     ..**
     ...**
     ..*
     ........***
     ........*
     .........*
The two gliders normally annihilate each other, but the collision of all three components produces an LWSS traveling to the right.

So far, so good, except for the clock pulse. This must grow in period as the number of bits grows, and this poses a problem I have yet to solve satisfactorily. I use a second delay line to store the clock pulse, and this is tied to the first in a way that forces it to (eventually) attain the same length. However, the transition between the k-bit and (k+1)-bit counters is rather problematic, and I have yet to characterize the sequence produced (I'll supply the whole construction below; it is big, but not at all bad with Xlife or Alan Hensel's program).

I also want to draw attention to a nice non-destructive reader for the delay line that can reside entirely to one side of the stream (clearly, there are several of these involving gliders that cross the stream). I found this useful for producing the output stream of the constuction. This too was produced by a search, and again may very well be old news.

Code: Select all

     ...*****
     ..*....*
     .......*
     ..*...*
     ....*
     .
     .
     .
     ***...***
     ..*...*..*
     .*....*
     ......*
     .......*.*
The upward spaceship and the glider will normally annihilate. However, this annihilation is converted by the MWSS spark into a glider traveling down and to the right. I found this useful for tapping the value of a p120 MWSS stream, though I haven't checked to see how small the period can be made (it's fairly fast).

Finally, the construction follows. For efficiency in observing, I have not used puffers for the extensible section. Hence, the period is large but finite. There should be no problem making the extensible section (eaters and left-going MWSSs) with p60 gliders, though I haven't worked out the close spacing of the two delay lines.

Code: Select all

x = 616, y = 283, rule = B3/S23
137bo$137b3o$140bo$128b2o9b2o$128b2o3$128bo12b3o$127bobo$126bo3bo10bob
o$126b5o9b5o$125b2o3b2o7b2o3b2o$126b5o8b2o3b2o$127b3o$128bo$142b2o$
140b2ob2o$140bo2bo$127bo15bo$129b2o9bo$128b3o10b2o$128b2o$129bo$128bob
o10b2o3b2o$129b2o11b5o$136bo6b3o$144bo$123b2obob2o3b2o2$123bo5bo2$124b
2ob2o$126bo19b2o$146bo$147b3o$149bo2$126b2o15bobo$126b2o4bo2b2o7b2o$
131bo3b2o2b2o3bo14b4o$131bo7b2o17b6o$132b4o21b8o$156b2o6b2o$157b8o$
158b6o$159b4o6$115bo$115b3o$118bo44b2o$106b2o9b2o45bo$106b2o56bobo7b2o
$159b2o4b2o7b2o$158b2o11b2o10bo4bo$160bo9b3o10bo4bobo$171b2o10bo7b2o$
117b2o3b2o50b2o2b2o11b2o$117b2o3b2o50b2o2bo2b2o8b2o355bo$118b5o35b2o
19b4o5bobo4b2o350bobo$119bobo35bo2bo19bo7bo6bobo332b2o14bo3b2o$106bo
53bo36bo332bobo13bo3b2o3b2o$105b3o11b3o38bo36b2o326b2o4b3o12bo3b2o3b2o
$104b5o48b2obo360b4o2bo4b3o12bobo$69bobo31b2o3b2o47b2o362b3ob2o4b3o7bo
6bo$68bo2bo32b5o421bobo9b2o$67b2o10bo6bo17bo3bo421b2o9b2o14b2o$59b2o4b
2o3bo8bo5bobo17bobo50b2o104b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o
51bo2bo$59b2o6b2o9bo6b2obo17bo10bo40b2o14b2o9b2o77bo29bo29bo29bo29bo
29bo29bo29bo29bo39bo$68bo2bo2b2o9b2ob2o3b2o21bo56b2o9bobo75bobo27bobo
27bobo27bobo27bobo27bobo27bobo27bobo27bobo39b2o11bo2bo$69bobo2bo2b3o5b
2obo4b2o21b3o49bo6bo7b3o4b2ob3o66b2o28b2o28b2o28b2o28b2o28b2o28b2o28b
2o28b2o39bobo10bo2bo$74b4o7bobo16bo17bo44bobo12b3o4bo2b4o360bobo$57b2o
16b2o9bo15b2ob2o14b3o36b2o3b2o3bo12b3o4b2o326b2o28bobo6bo$56bo2bo51bo
8b5o35b2o3b2o3bo13bobo332bo29b2o$56bo44bo5bo4bo6b2o3b2o39b2o3bo14b2o
332bobo6bo7bo12bo7b2o13b3o$56bo53b3o54bobo350b2o4bobo5b4o19b2o13b3o$
56bob2o8bo3b2o27b2obob2o60bo355b2o8b2o2bo2b2o30bo$58b2o6b2o3b2o48bo
402b2o11b2o2b2o30bo$67b2o4bo22b2o23bo402b2o7bo10b2o27bo$96bo85b2o86b2o
28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o14bobo4bo10b3o25bobo$57b2o26b
2o7bobo27b2o56bo87bo29bo29bo29bo29bo29bo29bo29bo29bo17bo4bo10b2o$41b3o
13b2o26bo2bo5b2o28bo45bo9bobo85bobo27bobo27bobo27bobo27bobo27bobo27bob
o27bobo27bobo30b2o7b2o$40bo3bo30bo3b3o7bo35b3o40bobo9b2o86b2o28b2o28b
2o28b2o28b2o28b2o28b2o28b2o28b2o31b2o7bobo19bobo$40bo3bo29b5o3bo6bo37b
o33b2o4bobo382bo20bo$41b3o29b2ob2o3bo7bo71b2o3bo2bo29bo352b2o19bo$72b
3ob2o3bo3bo2bo15b2o45bobo13bobo29b3o371bo$73b2ob4o5b2o17b2o8bo35bo17bo
bo6bo24bo369b3o$64b2o8b4o31b3ob2o2b2o31bo3bo15bo6bobo21b2o10bo119bo59b
o59bo59bo49bobo6b3o$63bobo9bo33b4o4b2o7bo23bo26b2o32bo3bo115bo3bo55bo
3bo55bo3bo55bo3bo48b2o$41b3o19bo49b2o12bo22bo2bo56bo119bo59bo59bo59bo
53bo$40bo3bo17b2o61b3o22b3o57bo4bo114bo4bo54bo4bo54bo4bo54bo4bo55b2o$
40bo3bo165b5o115b5o55b5o55b5o55b5o55b2o$41b3o528bo7b2o$581bo$581bobo7b
o$68b5o55b5o55b5o389b2o7bobo$67bo4bo54bo4bo54bo4bo401b2o6b2o$72bo59bo
59bo401b2o4bo3bo$34b2o31bo3bo55bo3bo55bo3bo402b2o3bo5bo$34bo34bo59bo
59bo70b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o28b2o89bobo4b2obo3bo$25b2o
5bobo225bo29bo29bo29bo29bo29bo29bo29bo29bo90bo7bo5bo$23bo2bo5b2o152bo
74b3o27b3o27b3o27b3o27b3o27b3o27b3o27b3o27b3o71b2o23bo3bo7b2o$10bobo9b
o161b4o75bo29bo29bo29bo29bo29bo29bo29bo29bo71b2o25b2o8bobo$10bo3bo7bo
160bobob2o403bo21bo$14bo7bo155b2o2bo2bob3o400b2o22b2o$10bo4bo7bo2bo
151b2o3bobob2o387b2o8b2o3b2o$14bo10b2o157b4o9b2o375bob2o7b2o$2b2o6bo3b
o24b2o145bo10bobo374bo12bo$bobo6bobo8bobo13bo2bo158bo374bo$bo20b2o175b
2o373bo2bo$2o20bo14bo2bo534b2o24bo$38bo2bo552b2obo3b4o$27bo11bobo92bo
33bo351b2o66b2o2b2obobo4b4o5b2o$27b2o11bo91bobo33b2o350bobo64bobo2b2ob
ob2o3bo2bo5b2o$26bobo94bo7bobo16b2o11b2o4b2o13b2o5bo315bobo13bo53b2o7b
3o8b2o3b4o$39b2o81b2o6bo2bo16b2o7b2o2b2o4b3o11b3o3bo3bo312bo2bo2b2o6bo
2bo7b2o44b2o6b3o8b2o3b4o$14b2o23b2o80b2o4b2o2bobo25b2o2b2o4b2o9bob2o5b
o315b2o5bobo8bo7b2o53b3o12bo$13bobo95b2o7b3o4b2o3bobo8b2o23b2o10bo2bo
4bo5bo302b2o4b2o3bo3bo3bo3bobo64bobo$3b2o7bo6b2o4bo54b2o29b2o8b2o4b2o
5bo8bobo22bo11bob2o9b2o302b2o6b2o5b3ob2o2b2o66b2o$3b2o7bo2bo2bo2bo2bob
o52b3o40b2o21bo26bo10b3o320bo2bo3b2o$12bo6b3obob2o10b2o37bob2o15bo27bo
21b2o25bobo9b2o321bobo23b2o$13bobo6b2ob2o10b2o30b2o5bo2bo8b3o4bobo37bo
36b2o359b2o$14b2o7bob2o42b2o5bob2o16bobo37bo22b2o360b2o$24bobo52b3o2b
2o2bo7bo2bo3b2o29b3o22bobo359b2o$25bo54b2o2bo3bo7bobo4b2o56bo371b3o$
85bo2bo6bobo63b2o354b2o15b2o$67b2o16b2o8bo12b2o86b2o296b2o20bobo12b2o$
67b2o40bo19b3o64bo298bo22bo12b3o$67b2o40bobo6bo12bo45bo2bo8bo4bobo298b
obo9bo24bobo$67bo42b2o6b4o8bo46bo10bobo3b2o300b2o8b4o23b2o$66bobo8bo4b
2o35b4o10b2o38bo2bo3b2o5bo3b2o312b2obobo6bobo$66bob2o7bobo2bobo34bo2bo
9bobo35b4o3b2obobo4bo3b2o311b3obo2bo3bo3bo28b3o$77b2o3bo23b2o11b4o8b3o
35b4o14bo3b2o312b2obobo4bo32bobo$106bo11b4o8b3o36bo2bo8b2o5bobo315b4o
4bo4bo28b3o$67b2o26b2o7bobo11bo12b3o23bo11b4o16bo317bo7bo32b3o$52bo14b
2o26bobo6b2o26bobo5b2o15bobo4b2o4b4o341bo3bo6b2o20b3o$51b3o31bo4b2o4b
3o34b2o5bobo7bo6b2o4bobo7bo343bobo6bobo19b3o$50b5o29bobob2o2bo4b3o42bo
8bo11bo364bo19bobo$83bo3bob3o4b3o28bo14b2o5b3o10b2o364b2o18b3o$83bo3bo
b2o4bobo29b3o$83bo3b2o6b2o33bo21b2o$74b2o8bobo42b2o21b2o$73bobo9bo92b
3o57b3o57b3o57b3o57b3o57b3o57b3o$73bo103b5o55b5o55b5o55b5o55b5o55b5o
55b5o$50b5o17b2o102b2ob3o54b2ob3o54b2ob3o54b2ob3o54b2ob3o54b2ob3o54b2o
b3o$51b3o123b2o58b2o58b2o58b2o58b2o58b2o58b2o$52bo503b2o$557bo$557bobo
4bo$80b2o476b3ob4o$77b3ob2o477b2obob2o14b2o$77b5o478bo2bob3o11bo2bo$
44b2o32b3o47bo432bobob2o11bo$44bo81b2o24b3o33b2o28b2o28b2o28b2o28b2o
28b2o28b2o28b2o28b2o132b4o12bo$35b2o5bobo82b2o25bo33bo29bo29bo29bo29bo
29bo29bo29bo29bo128b2o5bo5bo7bo$34bobo5b2o109bo5bo29b3o27b3o27b3o27b3o
27b3o27b3o27b3o27b3o27b3o119b2o4bobo9bo9bo2bo5b2o$20bo12b3o87b2o11b2o
20b2o31bo29bo29bo29bo29bo29bo29bo29bo29bo119b2o4bo11b3o9b2o5bobo$20b4o
8b3o87bobo12bo20bobo250b2o138b2o37bo$21b4o8b3o86bo11b3o274bobo138bo37b
2o$21bo2bo9bobo84b2o11bo278bo137bobo$21b4o10b2o376b2o135b2obo$12b2o6b
4o8bo16b2o512b2o$11bobo6bo12bo14bobo512b2o$11bo19b3o13b3o501b2o$10b2o
35b2o69bo432b2o22bo$50b2o66b3o453bobo$49b3o69bo440bobo8bob2o10b2o$36b
3o81b2o440bo2bo6b2ob2o10b2o$38bo184bo329b2o10b2o6bob2o$37bo11b2o96b2o
71b4o329b2o8bo3b2o5bobo$25bo23b2o97b2o69b4o16bo318b2o5b2o8bo$24b2o121b
o64b2o5bo2bo8b2o5bobo316bo4bo2bo$13b2o8b2o4b2o5bo175b2o5b4o14bo3b2o
319bobo$13b2o7b3o4b2o3bobo183b4o3b2obobo4bo3b2o3b2o$23b2o4b2o2bobo11b
2o74bo99bo2bo3b2o5bo3b2o3b2o$24b2o6bo2bo11b2o73b3o34b2o66bo10bobo$25bo
7bobo85b5o33b2o49b2o15bo2bo8bo$34bobo83b2o3b2o82bobo$36bo84b5o82b3o$
121bo3bo32b2o14b2o32b2o$122bobo33b2obo12bobo34b2o7bo3b3o$123bo37bo4bo
4b2obobo33b3o6bo4bo$161bo3b3o3bobobo43b3o3bo23b2o$120b2o36bo2bo3bob2o
4bo75bo$121bo5b2o30b2o5b3o3bo2bo34b2o26b2o7bobo$118b3o5b2o38b2o4bo16bo
20b2o21bo4b2o7b2o$118bo9bo43bo3bo11b2o37b2ob5o6b2o$172bo15bobo35bo4b2o
2bo5b3o$172bo2bo49bo8b2o5b2o$173bo51bo7bo4b2o$119b2o50bobobo49bo12b2o$
119bo51b2obobo40b2o7bo$111bo5bobo54bobo39bobo8b2o$111bobo3b2o28b2o25b
2o40bo$94bo17bobo28b2obo2bob2o62b2o$94b2o16bo2bo27bo4bo2b2o$90b2o3b2o
15bobo32bo8b2o8bo$95b3o13bobo30bobo9b2o7b3o$95b2o7bobo4bo52b2obo29bo$
87b2o5b2o9b2o10b2o5b2o8bo7b2o20b3o29bobo$86bobo5bo10bo12b2o3bo2bo7b3o
4b2o22b2o28bo3b2o$86bo30bo5bo13bo5bo40b2o9bo3b2o$85b2o36bo12b2o46b2o9b
o3b2o$123bob2o69bobo4b2o$125b2o70bo5bobo$112b2o91bo$112b2o35b2o54b2o$
124b2o23b2o3b2o3b2o$98bobo23b2o10b2obob2o$98bo3bo33bo5bo12bo3bo$88b2o
12bo10b2o22bo3bo14b3o$88b2o8bo4bo7bo2bo7bo15b3o3bo11b3o7bo$102bo7bo7b
2o3bo20b2o19b3o$98bo3bo7bo6bo5bo19bobo19bob2o$98bobo9bo7b5o32bo10b3o$
111bo2bo39b3o9b2o$113b2o38bo3bo23b2o$155bo25b2o$152bo5bo$141bo10bo5bo$
141bo11bo3bo$140bobo11b3o$139b2ob2o$138bo5bo$141bo40bo$138b2o3b2o36b3o
$166bo13b5o$165b3o11bobobobo$157b2o5b2obo11b2o3b2o$157bo6b3o$158b3o4b
2o$143b2o15bo21bo$143bo9bo27bobo$144b3o6b3o25bob2o$146bo9bo25b3o$155b
2o25bo2bo$183b3o$182bo3bo$181bo5bo$176bo5bo3bo$175bo7b3o$158bo7bo8b3o$
157b3o5b3o$156b5o4bob2o$155b2o3b2o4b3o$166b2o2$160b2o$162bo$159bo$159b
o2bo$158b2ob2o$159b2o$171b3o6b3o$171bo7bo3bo$157b2o3b2o8bo5bo5bo$157b
2o3b2o14b2obob2o$158b5o$159bobo$178bo$159b3o16b2o2$177b2obo$177b2o2bo$
178b4o2$160b2o$160b2o14b2o3b2o$179bo$176bo5bo$177b2ob2o$178bobo$179bo$
179bo5$178b2o$178b2o!
--Paul

pcallahan
Posts: 508
Joined: April 26th, 2013, 1:04 pm

Re: Glider circuits: components and contraptions

Post by pcallahan » April 11th, 2019, 1:52 pm

dvrgn wrote:This message from 1994 looks like a good match for your description:
OMG, thank you! It lives! I must have the original email on an archive of an archive somewhere but I haven't looked at any of that in a long time. I am also surprised that I was working on a delay line as early as Jan. 1991. I was still very naive about CGOL at the time, but I must have been plugging away. By 1994, I had done a lot more, and I guess I had already been invited to the email list.

User avatar
dvgrn
Moderator
Posts: 6737
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Glider circuits: components and contraptions

Post by dvgrn » April 11th, 2019, 5:17 pm

pcallahan wrote:
dvrgn wrote:This message from 1994 looks like a good match for your description:
OMG, thank you! It lives!
It's looking pretty good for quarter-century-old technology!

With today's mechanisms we could theoretically build a delay-line memory that extended itself on every overflow, and allowed storage of an unlimited number of bits without needing a linear-growth puffer to build Way Too Many Extension Units.

Anything like that would still be a painfully big and ugly pattern, though -- a universal regulator attached to huge memory loop containing single-channel recipe for a boojum reflector, or two p8 bouncers or two Snarks or whatever.

Maybe a more interesting memory-management project would be a modern rebuild of calcyman's O(sqrt(log(t))) pattern, which does its binary counting by storing bits as stable objects a growing triangle out in plain old empty space, no superstructure needed. Retrieving those bits and working with them isn't particularly easy, of course. But I wonder what a simplest-possible O(log(t)) binary counter would look like these days.

pcallahan
Posts: 508
Joined: April 26th, 2013, 1:04 pm

Re: Glider circuits: components and contraptions

Post by pcallahan » April 11th, 2019, 7:29 pm

I'm in the process of revisiting the delay line approach. Below is a modernized version of the delay line I posted on my web page a long time ago. A smaller, more direct design using two queenbee shuttles is used to make the LWSS to extend the line, and the MWSS source is simplified. I haven't taken't a look at the puffers.

One thing about this design is that it automatically recirculates the contents of memory. In practice, that will probably not allow for easy stream-based computation. You can set or reset a bit by deleting an MWSS on either the forward or backward stream, but by the time you have processed the bits, it is too late to do much with the backward stream, so it is probably better to convert the MWSSs into a glider stream for processing and forgo the elegance of automatic recirculation.

Note: when lengthening the line, it is important to know where the insertion occurs. In this case it should occur just before the MWSS (or empty space) that follows the LWSS. (Update: I slimmed this down further using a dvgrn's p120 MWSS based on Michael Simkin's small p120 in "unsure discoveries" thread)

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!
This shows three gliders entering to trigger three lenghtening LWSSs. The second illustrates the fact that they do not collide with either forward or backward MWSSs.
dvgrn wrote:storage of an unlimited number of bits without needing a linear-growth puffer to build Way Too Many Extension Units.
I'd like to think we're getting these for free, since it is a periodic structure and we have a nice way to make it. But I could be persuaded of a different esthetic depending on my mood.

There is also the "pollution" issue of gliders emitted at different points as the loop extends. I am not sure what to think about that. Of course we could add another puffer to build eaters for them, but I'm not sure what we're trying to optimize in that case. They can also be thought of as a computation trail or log. I guess it depends on the design.

ADDED: Is there any reason this could not be made to work at p60? I would need different puffers of course to produce the backward MWSS stream. Eater spacing could be the same as long as you don't mind inserting two spaces each time.

pcallahan
Posts: 508
Joined: April 26th, 2013, 1:04 pm

Re: Glider circuits: components and contraptions

Post by pcallahan » April 19th, 2019, 9:45 pm

I used this implementing rule110 on a p120 MWSS stream (other thread) but I think this is a pretty nice stream gadget. Maybe it's been used before and I just didn't notice. It is based on the fact that an MWSS can delete an LWSS passing in the the opposite direction without itself being deleted.

So this means that if your bitstream contains consecutive bits represented as MWSSs, you can easily check if there is a gap of k consecutive MWSSs in the stream. If a missing MWSS represents 1 (inverted logic) this is the AND of k consecutive bits. If it represents 0 (positive logic) you can think of it as NOR.

This illustrates a device for detecting gaps of 3 missing MWSSs in a p120 MWSS stream (including overlapping gaps; e.g. a gap of 4 is two overlapping gaps of 3) without affecting the MWSS stream. The output is a glider steam, also negative logic. I guess in positive logic, you could say the output stream consists of the OR of three consecutive bits.

Code: Select all

x = 643, y = 80, rule = B3/S23
514bo$514b3o$517bo$516b2o2$625b2o$625b2o2$505b2o5b2o$505b2o5b2o112bo$
625bobo$509b2o113bo3bo$509b2o113b5o$623b2o3b2o$624b5o$625b3o$532b2o92b
o$517b4o11b2o$516bo$515bo4bo8b2o5b2o$516bob2o9b2o5b2o$517bo2$632b2o$
631bobo$630b3o4b2ob3o$629b3o4bo2b4o$630b3o4b2o$631bobo$632b2o4$618b3o$
3b2o238b2o178b2o118b2o58b2o15bo$3ob2o234b3ob2o174b3ob2o114b3ob2o54b3ob
2o13bo$5o235b5o175b5o115b5o55b5o$b3o237b3o177b3o117b3o57b3o21$591bobo$
587bo3bobo8b2o5b2o$593b2o7b2o5b2o$593bo$587bobobo13b2o$587b3obo2bo10b
2o$588bo3bo3$582b2o$582b2o2$578b2o5b2o$578b2o5b2o5$589b2o$590bo$587b3o
$587bo!
Note that this is useful in rule110 because the one non-monotonic case is when all three bits in the 3-cell neighborhood are 1. Then the result is 0. I had avoided implementing it this way until realizing how easy it is to implement on the inverted logic stream.

Maybe this would be useful in implementing some other 1D CA of interest. The nice part is that you can accumulate the results of k bits without increasing the cell count of the device.

Post Reply