Miscellaneous topics in Conway's Game of Life -- unfinished projects of all kinds and conditions

18 November 2022

In Conway's Life, Fifteen Gliders Can Build Anything* !

A huge milestone in Conway's Game of Life history was finally reached on November 9, 2022. Pavel Grankovskiy completed the final subtask needed to build a complete RCT16 ("Reverse Caber Tosser", 16 gliders) demonstration pattern.

Some experimentation with variations on the theme proved that it was possible to perform the same trick without the sixteenth glider in the far northeast corner. Less than a week later, a revised "RCT15" demo pattern was made available, with scripts to make it easier to watch the action. This was followed soon after by an actual full RCT15 macrocell pattern containing just 15 gliders, which would build the same sample object as the demo pattern eventually -- if any existing software were capable of running the pattern for long enough!

Both of these RCT variants use an extraordinarily small number of gliders to construct a large and complex Life pattern. The 15- and 16-glider "demo" and "full" RCT patterns all produce exactly the same seed pattern for Alan Hensel's decimal counter -- a pattern over 1200 cells wide and 600 cells high. In the final stages, the patterns evolve into this:

Code: Select all
x = 1383, y = 627, rule = B3/S23
388b2o169b2o$389bo169bo$389bobo165bobo$390b2o165b2o8$386b2o173b2o$385b
obo173bobo$385b2o175b2o5$384b2o177b2o$383bo2bo175bo2bo$384bobo175bobo$
385bo177bo6$364bo219bo$363bobo217bobo$363b2o219b2o4$370b2o205b2o$369bo
bo205bobo$369b2o207b2o6$403b3o137b3o2$417bo113bo$416bobo111bobo$366b2o
48b2o113b2o48b2o$366b2o42b2o125b2o42b2o$409bobo125bobo$383b2o24b2o127b
2o24b2o$382bo2bo177bo2bo$352bo30b2o179b2o30bo$276bo74bobo241bobo$275bo
bo74b2o241b2o$276b2o100b2o38b2o109b2o38b2o$378b2o38b2o109b2o38b2o2$
385bo15b2o143b2o15bo$384bobo13bo2bo42bo55bo42bo2bo13bobo$385bobo13b2o
42bobo53bobo42b2o13bobo$386b2o40bo16b2o55b2o16bo40b2o$428bo91bo$428bo
91bo2$381b2o183b2o$381b2o23b2o133b2o23b2o$405bo2bo25b2o77b2o25bo2bo$
405bo2bo24bobo77bobo24bo2bo$406b2o25b2o79b2o25b2o$377b2o191b2o$376bobo
191bobo$377bo193bo$403b2o139b2o$403b2o37b2o61b2o37b2o$442b2o61b2o2$
413b2o10b2o95b2o10b2o$244b2o167b2o9bo2bo93bo2bo9b2o$243bobo179b2o95b2o
$244bo5$430b2o85b2o$429bo2bo83bo2bo$429bo2bo83bo2bo$430b2o85b2o4$427b
2o91b2o$427b2o91b2o$293b2o$292bobo$293bo4$153b2o$152bobo$151bobo$152bo
131b2o$149bo135bo$148bobo131b3o$149b2o131bo16bo$200b2o96bobo$199bobo
96b2o$132bo57b2o6bobo$131bobo55bobo7bo83b2o$127b2o3bo55bobo11b2o78bo2b
o20bo$127bobo42bo16bo12bobo77bo2bo19bobo$128bo42bobo12bo16bo16bo62b2o
21bo$144bo25bobo12bobo31bobo$143bobo24b2o14b2o27b2o3bo$142bobo29b2o39b
obo82b2o$121bo20b2o30bobo39bo82bobo104b2o$120bobo52bo124bo106bo$119bob
o285bobo$119b2o287b2o$2b2o119b2o$2bobo42b2o74bobo$3bo42bobo75bo$37b2o
6bobo$bo34bobo7bo43b2o249bo380bo$obo32bobo11b2o39bobo247bobo80b2o99b2o
195bobo$bo17bo16bo12bobo39bo248b2o81b2o99b2o161b2o33b2o$18bobo12bo16bo
74b2o158b2o117b2o281bobo$17bobo12bobo54bo34bobo157bobo116bobo34b2o65b
2o179bo$17b2o14b2o53bobo32bobo157bobo117b2o34bo2bo63bo2bo$21b2o61b2o3b
o17bo16bo159bo155b2o65b2o$21bobo59bobo20bobo12bo$22bo51b2o6bobo20bobo
12bobo$73bobo7bo21b2o14b2o312b2o75b2o$72bobo11b2o21b2o291b2o31b2o75b2o
$73bo12bobo20bobo289bo2bo47b2o41b2o511bo$70bo16bo22bo291bobo37bo9b2o
41b2o9bo500bobo$69bobo331bo37bobo61bobo470b2o27b2o$70b2o208bo161bobo
59bobo222bo247bobo31bo$279bobo161b2o59b2o222bobo247bo31bobo$275b2o3bo
260b2o185b2o281bobo$275bobo263bo438bo31b2o$276bo22bo123b2o114bobo437bo
bo$298bobo81bo39bobo13b2o69b2o28b2o439bo$297bobo81bobo39bo14b2o69b2o$
297b2o82b2o144b2o461bo$527bobo411b2o46bobo$528bo367b2o24b2o16bobo47bob
o$291bo12bo591bobo23bobo16bo49b2o$290bobo10bobo82b2o507bobo6b2o15bobo
84b2o$269bo19bobo11b2o82bobo508bo7bobo15bo18bo66bobo$268bobo18b2o96b2o
154b2o349b2o11bobo32bobo66bobo$267bobo273bobo347bobo12bo34bo3b2o63bo$
267b2o275b2o331bo16bo16bo35bobo$271b2o23bo579bobo31bobo35bobo$271bobo
21bobo579bo3b2o27b2o37bo$272bo8bo13b2o583bobo62b2o$280bobo25b2o111b3o
457bo62bobo$279bobo25bobo235b2o318bo79bo$279b2o27bo126bo108bo2bo316bob
o$434bobo107bobo318bobo$384b2o48b2o109bo320b2o$286bo97b2o42b2o$272bo
12bobo139bobo$271bobo11b2o14b2o98b2o24b2o$270bobo27bobo97bo2bo418b2o$
270b2o29bo68bo30b2o419bobo$369bobo194bo256bobo$370b2o193bobo256bo$264b
o12bo118b2o38b2o128b2o252b2o$263bobo10bobo117b2o38b2o381bobo$262bobo
11b2o87b2o436bo16bo$262b2o100bobo36bo15b2o381bobo$292b2o71bo36bobo13bo
2bo42bo94b2o242bo3b2o21b2o$291bobo109bobo13b2o42bobo93bobo244bobo20bob
o$256bo12bo22bo111b2o40bo16b2o95b2o210bo34bo22bo$255bobo10bobo175bo
324bobo17bo$254bobo11b2o176bo324b2o17bobo39bo$254b2o467b2o50bo15bobo
37bobo$399b2o322bobo48bobo15b2o38bo$399b2o23b2o298bobo48bobo$248bo12bo
22b2o137bo2bo25b2o71b3o197bo50b2o$247bobo10bobo20bobo137bo2bo24bobo
230bo$246bobo11b2o22bo139b2o25b2o60bo169bobo$246b2o147b2o115bobo169b2o
$394bobo116b2o48b2o$395bo123b2o42b2o$240bo12bo167b2o54b2o40bobo$239bob
o10bobo22b2o142b2o37b2o15bobo40b2o24b2o$238bobo11b2o22bobo181b2o16bo
66bo2bo180bo$238b2o37bo268b2o30bo149bobo$431b2o10b2o132bobo149bo3b2o$
431b2o9bo2bo131b2o153bobo$232bo12bo197b2o66b2o38b2o180bo$231bobo10bobo
264b2o38b2o$230bobo11b2o24b2o$230b2o37bobo256b2o15bo$270bo213bo42bo2bo
13bobo159bo33bo$483bobo42b2o13bobo159bobo31bobo$224bo12bo210b2o34b2o
16bo40b2o161bobo31bobo$223bobo10bobo208bo2bo51bo101b2o101b2o32b2o$222b
obo11b2o209bo2bo51bo101bobo130b2o$222b2o39b2o183b2o155bo130bobo$262bob
o283b2o151bo12bo22bo$263bo196b2o61b2o23b2o150bobo10bobo$216bo12bo229bo
2bo32b2o25bo2bo175b2o11bobo$215bobo10bobo214b2o13b2o33bobo24bo2bo189b
2o$214bobo11b2o215b2o49b2o25b2o$214b2o336b2o$256b2o294bobo154bo12bo$
255bobo295bo154bobo10bobo$208bo12bo34bo200b2o67b2o181b2o11bobo$207bobo
10bobo233bo2bo27b2o37b2o195b2o$206bobo11b2o234bobo28b2o206b2o$206b2o
249bo237bobo$445b2o57b2o10b2o178bo20bo12bo$249b2o194bobo55bo2bo9b2o
198bobo10bobo$200bo12bo34bobo195b2o56b2o211b2o11bobo$199bobo10bobo34bo
481b2o$198bobo11b2o235bo$198b2o248bobo251b2o$449b2o251bobo20bo12bo$
703bo20bobo10bobo$192bo12bo36b2o255b2o93b2o4b2o123b2o11bobo$191bobo10b
obo34bobo254bo2bo91bo2bo4bo137b2o$190bobo11b2o36bo255bo2bo91bo2bo4bobo
$190b2o307b2o93b2o6b2o$709b2o22bo12bo$709bobo20bobo10bobo$184bo12bo
512bo22b2o11bobo$183bobo10bobo36b2o265b2o243b2o$182bobo11b2o36bobo265b
2o$182b2o51bo$741bo12bo$716b2o22bobo10bobo$176bo12bo526bobo22b2o11bobo
$175bobo10bobo526bo37b2o$174bobo11b2o38b2o$174b2o51bobo$228bo520bo12bo
$472b2o274bobo10bobo$168bo12bo290b2o249b2o24b2o11bobo$167bobo10bobo
540bobo37b2o$166bobo11b2o273b2o267bo$166b2o53b2o231bo2bo$220bobo232b2o
300bo12bo$221bo534bobo10bobo$160bo12bo583b2o11bobo$159bobo10bobo285b2o
268b2o39b2o$158bobo11b2o286b2o268bobo$158b2o283b2o286bo$214b2o227b2o9b
o310bo12bo$213bobo237bobo308bobo10bobo$152bo12bo48bo237bobo310b2o11bob
o$151bobo10bobo285b2o325b2o$150bobo11b2o304b2o265b2o$150b2o318bobo264b
obo$471bo266bo34bo12bo$207b2o248b2o313bobo10bobo$144bo12bo48bobo248b2o
314b2o11bobo$143bobo10bobo48bo579b2o$142bobo11b2o$142b2o600b2o$453b2o
68b2o219bobo34bo12bo$452bobo20b2o46bobo219bo34bobo10bobo$149bo50b2o
251bo21b2o47bo256b2o11bobo$148bobo48bobo593b2o$148b2o50bo291b2o$491bo
2bo$492b2o257b2o36bo12bo$454b2o295bobo34bobo10bobo$454bobo295bo36b2o
11bobo$193b2o260bo31b2o314b2o$192bobo292b2o42b2o$193bo310b2o24bo2bo$
494bo9b2o25b2o264bo12bo$141b2o350bobo262b2o36bobo10bobo$141b2o351bobo
261bobo36b2o11bobo$495b2o262bo51b2o$186b2o$185bobo340b2o$186bo340bo2bo
274bo12bo$473b2o15b2o35bobo274bobo10bobo$466bo5bo2bo14b2o36bo236b2o38b
2o11bobo$465bobo5b2o290bobo51b2o$465bo2bo297bo$179b2o285b2o$178bobo
279b2o351bo12bo$179bo279bobo35b2o313bobo10bobo$460bo36bo315b2o11bobo$
498b3o271b2o53b2o$482b2o16bo95bo175bobo$481bobo111bobo175bo$172b2o308b
o55b2o56b2o223bo12bo$171bobo256bo107bobo279bobo10bobo$172bo256bobo107b
o281b2o11bobo$429b2o67b2o335b2o$497bo2bo278b2o$497bobo279bobo$320bo73b
o103bo281bo48bo12bo$319bobo71bobo46b2o161bo222bobo10bobo$319b2o72b2o
47bobo159bobo222b2o11bobo$443bo57b2o102b2o236b2o$501bobo$502bo283b2o$
786bobo48bo$313bo473bo48bobo$312bobo297bo224b2o$312b2o297bobo239bo$
612b2o238bobo$853bobo$793b2o59b2o$477b2o314bobo$306bo170bobo314bo$305b
obo170bo140bo228bo$305b2o311bobo226bobo$619b2o227b2o2$800b2o$800bobo$
801bo$298bo55b2o270bo$297bobo54b2o198b2o69bobo$297b2o255b2o70b2o2$807b
2o46b2o$807bobo45b2o$808bo$633bo$290bo341bobo$289bobo341b2o$289b2o56b
2o211b2o$346bobo211bobo251b2o$347bo213bo252bobo$815bo$640bo$283bo69b2o
199b2o83bobo$282bobo54b2o11bobo199bobo83b2o$282b2o54bobo10bobo201bobo$
339bo12bo203bo13b2o$472b2o96bobo$471bobo97bo$345b2o125bo174bo176b2o$
276bo54b2o11bobo299bobo175bobo$275bobo52bobo10bobo218b2o81b2o176bo$
275b2o54bo12bo219bobo11b2o$565bobo10bobo$566bo12bo$337b2o$336bobo315bo
$269bo52b2o11bobo234b2o79bobo$268bobo50bobo12bo235bobo11b2o66b2o$268b
2o52bo250bobo10bobo$574bo12bo2$328b2o$327bobo250b2o79bo$313b2o11bobo
251bobo11b2o64bobo$261bo50bobo12bo253bobo10bobo64b2o$260bobo50bo268bo
12bo$260b2o2$319b2o267b2o$305b2o11bobo159bo107bobo11b2o$304bobo10bobo
159bobo107bobo10bobo64bo$254bo50bo12bo161bobo107bo12bo64bobo$253bobo
225b2o186b2o$253b2o263bo$311b2o204bobo76b2o$297b2o11bobo162bo42bo77bob
o11b2o$296bobo10bobo162bobo120bobo10bobo$297bo12bo164b2o43bo77bo12bo$
247bo271bobo$246bobo270b2o157bo$246b2o55b2o299b2o71bobo$289b2o11bobo
299bobo11b2o58b2o$288bobo10bobo301bobo10bobo$289bo12bo303bo12bo$382bo$
240bo140bobo$239bobo53b2o85b2o136b2o90b2o71bo$239b2o53bobo223bobo89bob
o11b2o56bobo$280b2o11bobo225bobo89bobo10bobo56b2o$279bobo12bo227bo91bo
12bo$42bo237bo625bo$41bobo488bo372bobo$42b2o16b2o171bo297bobo86b2o265b
2o16b2o$60b2o170bobo51b2o244bo87bobo11b2o251b2o$232b2o38b2o11bobo57b2o
274bobo10bobo$271bobo10bobo57bobo187bo87bo12bo$272bo12bo59bo187bobo47b
o$533b2o47bobo111bo$583bo44b2o65bobo$226bo51b2o264bo83bobo65b2o$225bob
o36b2o11bobo263bobo6bo32bo43bobo11b2o$225b2o36bobo10bobo264b2o7b3o29bo
bo43bo12bobo$23b2o239bo12bo262bo14bo28b2o58bo279b2o$22bobo514bobo12b2o
368bobo$23bo28b2o486bobo7b2o43bo107bo191b2o28bo$52b2o216b2o269b2o7bobo
41bobo6bo33b2o63bobo190b2o$219bo36b2o11bobo280bo41b2o7b3o31bobo63b2o$
42b2o174bobo34bobo10bobo281b2o11bo25bo14bo31bobo264b2o$42b2o13bo160b2o
36bo12bo294bobo23bobo12b2o32bo13b2o236bo13b2o$56bobo506bobo23bobo7b2o
50bobo234bobo$49bo6bobo507b2o24b2o7bobo50bo235bobo6bo$48bobo6bo204b2o
339bo287bo6bobo$47bobo198b2o11bobo339b2o11bo282bobo$47b2o163bo34bobo
10bobo352bobo29b2o63bo187b2o$211bobo34bo12bo354bobo28bobo11b2o48bobo$
211b2o404b2o29bobo10bobo48b2o$622bo26bo12bo$254b2o261b2o102bobo$240b2o
11bobo260bo2bo101b2o3bo$239bobo10bobo261bo2bo105bobo27b2o$205bo34bo12b
o263b2o107bo28bobo61bo$50b2o8b2o142bobo449bobo59bobo166b2o8b2o$50b2o8b
2o142b2o451bo61b2o166b2o8b2o$246b2o$77b2o10b2o141b2o11bobo271bo112bo
40b2o183b2o10b2o$76bo2bo9b2o140bobo10bobo270b3o111bobo39bobo182b2o9bo
2bo$77b2o153bo12bo164bo105bo114b2o41bo195b2o$198bo210bobo104b2o109b2o
97bo$197bobo208bo2bo215bobo13b2o80bobo$72b2o123b2o39b2o169b2o217bobo
12bobo21b2o57b2o147b2o$72b2o150b2o11bobo389bo9bo5bo21bobo11b2o192b2o$
223bobo10bobo193bo206b3o3b2o21bobo10bobo$79bo144bo12bo179b2o12bobo208b
o26bo12bo186bo$78bobo336b2o13b2o207b2o225bobo$71b2o6bobo651bo133bobo6b
2o$70bobo7b2o148b2o443b2o55bobo132b2o7bobo$70b2o144b2o11bobo443bobo55b
2o142b2o$215bobo10bobo214b2o229bobo$187bo28bo12bo214bobo203b2o25bo13b
2o$75b2o109bobo256bo204bobo38bobo178b2o$75b2o109b2o463bobo38bo179b2o$
65b2o155b2o428bo229b2o$64bobo141b2o11bobo517bo140bobo$64b2o141bobo10bo
bo439bo22b2o53bobo140b2o$208bo12bo439bobo21bobo11b2o40b2o$180bo481bo
23bobo10bobo$179bobo505bo12bo$179b2o33b2o448bo$213bobo447bobo$212bobo
245bo202b2o28b2o53bo$213bo179b2o57bo6bobo231bobo11b2o38bobo$393bobo54b
3o7b2o232bobo10bobo38b2o$173bo22b2o196bo54bo14bo230bo12bo$172bobo20bob
o251b2o12bobo$172b2o22bo256b2o7bobo$452bobo7b2o237b2o$452bo211b2o35bob
o11b2o$202b2o235bo11b2o211bobo35bobo10bobo$188b2o11bobo234bobo224bobo
35bo12bo$166bo20bobo10bobo234bobo226bo$165bobo20bo12bo235b2o320bo$165b
2o266bo275b2o47bobo$432bobo274bobo47b2o$194b2o233bo3b2o275bobo11b2o$
180b2o11bobo232bobo280bo12bobo$179bobo10bobo234bo295bo$159bo20bo12bo$
158bobo262bo342bo$158b2o222bo39bobo246b2o45b2o45bobo80b2o$186b2o193bob
o39b2o246bobo44bobo11b2o32b2o81bo$172b2o11bobo190bo3b2o43b2o238bo5bo
45bobo10bobo111b3o$171bobo10bobo190bobo31b2o13bobo238b3o3b2o45bo12bo
112bo$172bo12bo192bo16bo14bobo12bobo242bo$152bo241bobo13bo5bo9bo242b2o
$151bobo218bo22b2o12b2o3b3o309b2o45bo$151b2o25b2o191bobo25bo13bo312bob
o43bobo$164b2o11bobo192b2o24bobo12b2o312bobo43b2o$163bobo10bobo197b2o
19bobo328bo$164bo12bo182b2o13bobo19b2o275bo$359bobo12bobo296bobo68b2o$
145bo213bo5bo9bo297b2o69bobo$144bobo23b2o186b2o3b3o303b2o74bo34bo$144b
2o10b2o11bobo190bo306bobo107bobo$155bobo10bobo191b2o306bobo107b2o$156b
o12bo501bo66b2o$342bo395bobo11b2o$341bobo395bobo10bobo$162b2o178bo397b
o12bo$148b2o11bobo69b2o23b2o98bo319bo108bo$147bobo10bobo69bobo22bobo
80bo16bobo317bobo106bobo$148bo12bo71bo23bo5bo75bobo16b2o317b2o3bo63b2o
39b2o$256b2o3b3o76b2o20b2o317bobo62bobo11b2o$260bo100bobo318bo64bobo
10bobo$154b2o104b2o45bo22bo29bobo385bo12bo$153bobo150bobo13bo6bobo29bo
326bo$152bobo152b2o11b3o7b2o355bobo$153bo157b2o6bo14bo352b2o65b2o$295b
2o13bobo6b2o12bobo347b2o69bobo11b2o26bo$125b2o124b2o26bo14bobo12bobo
11b2o7bobo348bobo13b2o54bobo10bobo24bobo$124bobo123bobo25bobo13bo5bo9b
o11bobo7b2o350bobo12bobo54bo12bo26b2o$125bo123bobo27b2o12b2o3b3o21bo
362bo9bo5bo$238b2o10bo32bo13bo23b2o372b3o3b2o$168bo69bobo41bobo12b2o
399bo63b2o$167bobo69bo41bobo413b2o63bobo11b2o$168b2o111b2o480bobo10bob
o24bo87b2o$60bo111b2o590bo12bo24bobo86bo$59bobo109bobo629b2o87b3o$60b
2o16b2o90bobo721bo$78b2o91bo17bo468bo47b2o62b2o$188bobo466bobo46bobo
61bobo$189bo54b2o411b2o48bobo61bobo$149b2o54bo22bo14bobo462bo63bo13b2o
22bo$149bobo35bo16bobo13bo6bobo13bo5bo536bobo20bobo$150bo35bobo16b2o
11b3o7b2o12b2o3b3o468bo68bo22b2o$187b2o20b2o6bo14bo13bo470bobo$208bobo
6b2o12bobo12b2o470bo$207bobo11b2o7bobo547b2o$41b2o165bo11bobo7b2o488bo
59bobo11b2o$40bobo177bo498bobo59bobo10bobo$41bo28b2o147b2o498b2o61bo
12bo$70b2o84b2o661bo$156bobo571bo87bobo$60b2o95bo493bo77bobo6bo49b2o
29b2o$60b2o13bo574bobo76b2o7b3o47bobo11b2o$74bobo574b2o73bo14bo47bobo
10bobo$67bo6bobo648bobo12b2o48bo12bo$66bobo6bo650bobo7b2o$65bobo659b2o
7bobo87bo$65b2o671bo57b2o27bobo$738b2o11bo44bobo27b2o60bo$750bobo44bob
o87bobo$751bobo44bo13b2o55b2o16b2o$752b2o58bobo54b2o$673b2o138bo$672bo
2bo157bo$672bo2bo156bobo$68b2o8b2o593b2o131b2o25b2o$68b2o8b2o726bobo
11b2o$121bo15bo669bobo10bobo$95b2o10b2o11bobo13bobo669bo12bo$94bo2bo9b
2o12bo15bo537bo76bo$95b2o576b3o76b3o151b2o$672bo82bo58b2o90bobo$672b2o
80b2o44bo13bobo11b2o47b2o28bo$90b2o658b2o47bobo13bobo10bobo46b2o$90b2o
24bo15bo617bobo47b2o14bo12bo$115bobo13bobo566b2o50bo134b2o$97bo18b2o
14b2o566b2o50b2o119bo13b2o$96bobo723b2o48bobo$89b2o6bobo722bobo22b2o
23bobo6bo$88bobo7b2o592b2o129bobo21bobo23bo6bobo$88b2o601bo2bo129bo23b
o32bobo$692bobo187b2o$117b2o574bo64bo$93b2o22bobo637bobo$93b2o23bo638b
2o$83b2o669bo$82bobo668bobo$82b2o670bobo$755b2o3bo$759bobo107b2o8b2o$
760bo108b2o8b2o$819b2o$762bo55bobo19b2o10b2o$144b2o615bobo55bo20b2o9bo
2bo$89b2o53bobo614b2o89b2o$89bobo53bo$90bo$857b2o$857b2o2$795bo55bo$
762b2o30bobo53bobo$762bobo29b2o53bobo6b2o$763bobo24b2o57b2o7bobo$764bo
25bobo66b2o$791bobo$681b2o91bo17bo$680bobo90bobo78b2o$681bo92bo79b2o$
864b2o$776bo50b2o6b2o27bobo$775bobo48bo2bo4bobo28b2o$775b2o49bo2bo4bo$
827b2o4b2o17$752b2o$751bobo$752bo$843b2o$842bobo$843bo11$1380bo$1378bo
3bo$142b2o1233bo$142b2o1233bo4bo$1377b5o2$141b2o$141b2o4$135b2o$135b2o
$774b2o$773bobo$141b2o631bo$141b2o!
#C [[ X -52 Y -143 ZOOM -2 STEP 5 AUTOSTART LOOP 12000 THUMBNAIL THUMBSIZE 2 ]]

What Is This All About?

A glance through the LifeWiki will tell you that throughout the half-century-plus history of Conway's Life as a mathematical recreation, Lifenthusiasts have liked to build things. As the decades went by, they designed and constructed more and more complicated mechanisms.

Relatively recently, these mechanisms have begun to include Life patterns that make copies of themselves. This kind of construction is generally done by crashing gliders together in just the right way. A big research topic has always been what exactly can we build by crashing gliders together? -- and an obvious corollary, for any given Life pattern, is how few gliders can we use?

For the last few decades, glider synthesis problems have been for some dedicated Lifenthusiasts what daily Wordles, weekly Sudokus, or monthly cryptic crosswords might be for other types of puzzle-solvers.

One big difference, though, is that glider synthesis puzzles generally don't have a solution you can look up in the back (with a few rare exceptions nowadays in the Life textbook). They're all puzzles that nobody has ever solved before, and there's an unbounded number of them. A recent set of extra-hard problems was posted on November 10th, for example -- and they were all solved in well under a week.

Conversely, we can ask what can we build with a fixed number of gliders? And for a while, it's clear that the more gliders we have, the more different objects we can build, and the objects get gradually larger and more complex on average. We can ask

how many gliders does it take to construct...
... a block? (Two.)
... a lightweight spaceship? (Three.)
... a glider-producing switch engine? (Four.)
... a unix oscillator? (Five.)
... a queen bee shuttle? (Six.)
... a Coe ship? (Seven.)
... a Gosper glider gun? (Eight.)
... a 2-engine Cordership? (Nine.)
... a blinker puffer? (Ten.)

Code: Select all
x = 998, y = 822, rule = B3/S23
991bobo$991b2o$992bo5$195bo$178bo17b2o$176bobo16b2o$177b2o$992bo$991bo
$991b3o9$997bo$995b2o$996b2o23$851bo$851bobo$851b2o34$183bo$184bo$182b
3o26$221bo$222bo$220b3o5$202bo$200bobo$201b2o31$677bo$677bobo16bo$677b
2o17bobo$161bobo10bo521b2o$162b2o11b2o$162bo11b2o32$145bo436bo$146b2o
433bo$145b2o434b3o4$581bo$149bo431bobo$150bo430b2o$148b3o3bo$155bo$
153b3o34$117bobo355bo$118b2o355bobo$118bo356b2o34$92bo$93bo$91b3o7$
358bo$357bo$357b3o$107bo$108bo$106b3o2$350bo$349bo$349b3o17$237bo$237b
obo$237b2o27$83bo$81bobo$82b2o$222bo$221bo$221b3o24$127bo$125b2o$41bo
84b2o$39bobo$40b2o21$27bo$27bobo$27b2o$2bo$obo$b2o55$126b2o$126bobo$
126bo31$225bo$224b2o$224bobo65$376b2o$375b2o$377bo29$121bo356b2o$108b
2o11b2o355bobo$109b2o9bobo355bo$108bo$464b3o$464bo$465bo36$145b3o$147b
o$146bo$142b2o$141bobo$143bo34$171b2o520b2o$172b2o519bobo9b3o$171bo
521bo11bo$188bo517bo$188b2o$187bobo31$224b2o$223bobo$225bo$812b2o$811b
2o$813bo15$204b3o$206bo$205bo600bo$805b2o$805bobo5$183b3o$185bo$184bo
68$186b2o782b2o$187b2o781bobo$186bo783bo14$193b2o$194b2o$193bo4$995b3o
$995bo$996bo$204b3o$206bo$205bo!
#C [[ THUMBNAIL THUMBSIZE 2 LABELSIZE 50 COLOR LABEL Yellow LABELALPHA .8 ]] #C [[ ZOOM 10 X -483 Y -10 AUTOSTART PAUSE 2 GPS 20 LOOP 1800 ]]
#C [[ T 50 ]] # block
#C [[ T 150 X -413 Y 0 ]]
#C [[ T 200 ]] # LWSS
#C [[ T 300 X -340 Y 0 ]]
#C [[ T 360 ]] # GPSE
#C [[ T 450 X -270 Y 0 ]]
#C [[ T 575 ]] # unix
#C [[ T 650 X -200 Y 0 ]]
#C [[ T 700 ]] # queen bee shuttle
#C [[ T 820 X -130 Y 0 ]]
#C [[ T 880 ]] # Coe ship
#C [[ T 950 X -60 Y 0 ]]
#C [[ T 1100 ]] # 2-engine Cordership
#C [[ T 1150 X 20 Y 0 Z 8 ]]
#C [[ T 1250 ]] # blinker puffer
#C [[ T 1550 X 96 Y 0 Z 10 ]]
#C [[ T 1700 ]]
#C [[ T 1775 X -483 Y -10 ]]
#C [[ LABEL 13 413 10 "block\n(2 gliders)" ]]
#C [[ LABEL 85 423 10 "LWSS\n(3 gliders)" ]]
#C [[ LABEL 150 423 10 "GPSE\n(4 gliders)" ]]
#C [[ LABEL 223 423 10 "unix\n(5 gliders)" ]]
#C [[ LABEL 292 423 10 "queen bee shuttle\n(6 gliders)" ]]
#C [[ LABEL 368 423 10 "Coe ship\n(7 gliders)" ]]
#C [[ LABEL 435 423 10 "Gosper glider gun\n(8 gliders)" ]]
#C [[ LABEL 512 428 10 "2-engine Cordership\n(9 gliders)" ]]
#C [[ LABEL 595 423 10 "blinker puffer\n(10 gliders)" ]]

... and so on, with buildable structures getting just a little bigger and more complicated each time we add another glider. This all holds up very nicely, until suddenly we get to

... a pattern that can compute the digits of pi and print them out in the Life universe? (Fifteen.)

Substitute a description of any Life pattern that can be constructed -- a thousand gliders that collide and produce nothing but empty space, or a million blocks in the shape of the Flying Spaghetti Monster, or a spaceship that travels by making reflected copies of itself, or whatever. No matter what pattern you ask about, if it can be constructed at all, the answer is always fifteen gliders -- or less, of course. But for big patterns, it's usually fifteen.

That doesn't seem to make a lot of sense, to put it mildly. So... what exactly is going on here?

The Full-Sized RCT15

The simple version of any RCT15 pattern starts with exactly fifteen gliders in an otherwise empty Life universe. Ordinarily you would have to collide two thousand gliders or more, to construct a pattern as large and complex as Hensel's decimal counter. The activated pattern contains almost a hundred gliders, after all, just in its various signal loops. But the entire pattern can be constructed with exactly fifteen gliders... provided that those gliders start very, very far apart.

Completely counterintuitively, any pattern that can be constructed by colliding any number of gliders, can also be constructed by these exact same fifteen gliders, in three groups: 7 in the far southwest, and 4 each in the far northwest and far southeast. The RCT16 design had one more glider in the far northeast, as shown in the four-quadrant diagram below. In either RCT15 or RCT16, the only thing that changes is the groups' relative positions. In general, to build a bigger and more complex object, the groups will have to move farther apart -- a lot farther apart.

For example, moving those groups of gliders to exactly the correct distances from each other would build a complete Gemini spaceship -- eventually! -- even though a Gemini spaceship is an enormous pattern consisting of over 800,000 live cells. Constructing one of these spaceships would otherwise require 173,449 colliding gliders (at least that's the current known recipe).

We can do this same construction in 15 gliders, but we'll have to expand the size of the RCT pattern, and also wait an inordinately long time. It will be, not just hundreds of thousands of times bigger and slower, but hundreds of thousands of factors of two bigger and slower than the RCT demo pattern that builds the decimal counter pattern shown above.

Storing Data in Empty Space: How Does It Work?

The target Life pattern's "construction recipe" is encoded into the distances between glider groups, with a tricky "divide by two and take the remainder" mechanism. See this LifeViewer animation to get a closer look at the details. The mechanism is also described in detail in previous posts on this blog, and elsewhere. Anyone interested in either the developmental history of the RCT idea, or the low-level mechanisms that make it all work, should definitely have a look at Brett Berger's November 16 blog post on these subjects.

Briefly, a glider bounces back and forth between the center of the pattern and a slowly moving object known as a GPSE, which is approaching from the southeast. The distance that the glider travels between successive bounces is always decreasing, and the glider is exactly three times as fast as the GPSE. The result is that the distances reduce by a factor of two after each round trip by the glider. We can adjust the initial separation between the 15 gliders, to get a free choice of ending up with a remainder of either 0 or 1 after each division.

Another useful feature of GPSEs -- "glider-producing switch engines" -- is that they emit streams of gliders aimed in the direction they're traveling. The RCT's initial configuration produces four GPSEs in three corners of the pattern, all aimed toward the center. The collision of streams of gliders in the center is carefully arranged to perform a mechanical calculation where the total distance is repeatedly divided by 2, and the remainder (either 0 or 1) can be tested.

Depending on this remainder, the central collision releases either a single glider or a pair of gliders, heading northeast. The sequence of single and double gliders corresponds to the sequence of bits in the binary representation of the original distance, reading from right to left.

Getting Something for (Almost) Nothing

The very sparse sequence of single and double gliders is aimed at a target object, which originally is just some junk from an initial collision between gliders from tne northwest and southwest. Or, in the RC16 case, the initial target is the lone glider from the northeast.

With just the right sequences of single and double gliders, it turns out that we can change the target object -- pull it southwest, push it northeast, emit perpendicular gliders, and so forth. By carefully stringing together these sequences, we can instruct the target object to construct simple objects in specified locations. An early demonstration was a 2028-bit sequence for building an 8-cell object called a shillelagh.

The problem is that the GPSEs in the original pattern are very messy, producing long streams of ash as they move towards the center. The various collisions create even more clumps of mess along those trails, culminating in the final big collision at the centre. To qualify as a genuine glider synthesis, our 15-glider recipe has to be completely 'clean': it has to produce nothing other than the desired object, not even any escaping gliders. So a big part of the RCT project is to figure out how to reliably clean up all of the extra mess, including the incredibly long ash trails, each slightly different from the others, coming from each of three corners of the initial pattern.

Ours Not To Reason Why...

A very reasonable question might be asked at this point! If this GPSE-based mechanism produces such a huge mess, why not use some other structure instead that doesn't create all these difficulties? In point of fact, an earlier design for universal construction with a fixed number of gliders had a cost of 329 gliders instead of 15, with only relatively minor cleanup problems. Here again, see Brett Berger's blog post for more details.

Long story short, the RCT project acquired a certain momentum after a while. It was clear several years ago that fixed-cost universal construction was possible, so the interesting question once again was: what is the absolute smallest total number of gliders that we can do this with? As of November 15th, the RCT15 patterns represent our collective best effort to answer this question: "Fifteen!"

Yet More Obsessive Optimizing

After the total cost of a fixed-cost recipe was successfully boiled down to the current minimum of 15, reducing the size of the bounding box became a secondary goal. For the RCT design, this is equivalent to minimizing the number of bits in the recipe. Every time you find a way to reduce the recipe by a single bit, the pattern's diameter is cut in half (!). Compared to this, other possible optimizations really aren't going to amount to much of anything.

The sequences of single and paired gliders coming from the central collision are capable of universal construction, but it's a very inefficient process -- you need a lot of bits to successfully fire even a single glider. It would be much cheaper to encode construction-arm operations in a much shorter bit sequences. So the first thing that the RCT project builds is a decoder for exactly those shorter bit sequences, or "codons". This structure is called a "decoder and better construction arm" (DBCA), and as soon as it is fully constructed, it immediately takes over the work of constructing and destroying things, much more efficiently: DBCA recipes are about twelve times cheaper.

That isn't the end of the bootstrap process, though! The DBCA is efficient enough to build an even more complicated mechanism, the "extreme compression construction arm" (ECCA), which takes over construction work from the DBCA. The ECCA is 30% more efficient than the DBCA, and it can fire gliders in multiple directions, and it contains integrated self-destruct circuitry: it is designed to disappear completely when it is struck by just one single glider in exactly the right place.

Remember, the point of this whole exercise is not to build a DBCA or an ECCA. The point is to build whatever pattern we want to build, starting with just fifteen gliders. The DBCA and ECCA are just intermediate steps along the way. They're very useful intermediate steps, but in the end they're going to have to get cleaned up along with all the rest of the mess -- leaving behind nothing besides the Life pattern that we're really trying to construct.

This three-stage bootstrap design turned out to be much more cost-effective than two stages, or just one stage. However, the improvements stop there: building a fourth bootstrap stage would just make everything more expensive. The ECCA can already do everything that we need it to do, including cleaning up itself, the DBCA, and all of the GPSE ash trails -- and constructing the final target pattern.

The RCT Demo Pattern

The full RCT16 pattern from November 9 encodes a 1,650,504-bit recipe into the distances between the initial gliders -- which means that the pattern fits in a bounding box with each side somewhat longer than 2^1650504 cells. That's a number with almost half a million digits. RCT15's recipe contains a slightly larger number of bits -- 1,665,791 -- both because it hasn't been optimized as thoroughly as the RCT16 was, and because there's slightly more to clean up.

Neither of the full patterns can be simulated effectively on any software that we currently have available. Golly, the software we use to work with these RCT patterns, is very good at handling big bounding boxes, but even it can't readily deal with such a ridiculously large size.

Luckily there's a good workaround! Bits come in from the RCT retrieval mechanism very slowly at first, then faster and faster -- each one arriving in half the time of the one before. So we can build a smaller RCT pattern that shows exactly how the mechanism works, and then "supercharge" it by inserting extra gliders to represent additional bits, during one of the very slow stages where the early-stage RCT is waiting around for a long time for the next bit to come in.

These extra gliders are constructed with sparse streams of MWSSes, carefully placed out of the way of the rest of the pattern. The inserted gliders arrive at the mechanism that interprets incoming bits, in exactly the same way as any other gliders encoding incoming bits. But they arrive fast enough that we can actually watch the entire process of construction and destruction that the RCT needs to go through to accomplish its magic.

The RCT Viewer script

It can be hard to zoom and pan around in Golly to find the locations where interesting things are happening, in a ridiculously large and long-running pattern like the RCT demo pattern. This Lua script is currently the easiest way to get Golly to do most of the tricky zooming and panning work for you. The script can be stopped at any time by hitting the Escape key, to investigate a particular stage in more detail.

To use the script, start by opening the rct15.mc.gz file in Golly. Then navigate to the forum page where the RCT viewer Lua script is published, click "Select All" in the code box, hit Ctrl+C to copy, and then in Golly choose File > Run Clipboard. The script will do the rest. Lua is embedded in the Golly executable on all platforms that Golly supports, so there's no extra language download/install process.

The above final stage of an RCT15 synthesis of a decimal counter appears at T=6,749,629,825,000 in the demo pattern. This may still seem like a very large number, but it's easily with reach of a Golly simulation -- as you'll see if you try running the pattern yourself, either with or without the viewer script.

... Anything* ?

In Conway's Life, the claim of universal construction -- the ability of a mechanism to build "anything" -- is inevitably limited by the existence of Gardens of Eden, grandparentless patterns, and other patterns that provably can not be constructed by any number of colliding gliders -- including some recently discovered still lifes and oscillators.

To summarize: all Conway's Life universal constructors can construct anything that can be constructed, so they can all build any structure that any other universal constructor can build.

The big surprise is that a structure consisting of just 15 gliders can now be officially added to the group of proven universal constructors. Other known universal constructor mechanisms (there are several known just in Conway's Life) encode their instructions in the positions of objects on a 1D or 2D "memory tape", or in the positions of long streams of gliders. It's very strange to find a way to encode the same information using just fifteen gliders and a whole lot of empty space.

For the RCT there are some lower limits even smaller than the classic initial pattern with 15 gliders and 75 cells, if we're measuring in terms of total population and bounding box size. The initial four quadrants of the RCT always look exactly like the following, except that they're initially a lot farther apart. The mechanism can't really store any information at this small scale, and the glider-producing switch engines crash in an uncontrolled way. However, these views of the four quadrants might make it easier to inspect what the corners of all RCT patterns look like:

Code: Select all
x = 2611, y = 1354, rule = LifeHistory
542.14D114.7D1365.14D$456.29D53.22D15.56D37.11D32.38D1207.29D53.22D
15.56D39.7D53.16D$455.33D47.28D12.57D34.13D31.40D1205.33D47.28D12.57D
36.10D49.23D$455.36D42.32D10.57D33.14D31.40D1205.36D42.32D10.57D34.
13D45.28D$455.38D39.35D8.57D31.16D31.40D1205.38D39.35D8.57D33.14D43.
31D$455.39D36.38D7.57D30.17D31.40D1205.39D36.38D7.57D31.16D42.32D$
455.40D34.40D6.57D28.19D31.40D1205.40D34.40D6.57D30.17D40.34D$455.42D
31.42D5.57D27.20D31.40D1205.42D31.42D5.57D28.19D39.35D$455.42D30.44D
4.57D25.22D31.40D1205.42D30.44D4.57D26.21D38.36D$455.43D28.45D4.56D
24.24D31.39D1206.43D28.45D4.56D26.22D37.37D$455.11D14.19D26.18D13.15D
27.11D45.25D31.11D1234.11D14.19D26.18D13.15D27.11D46.24D36.17D13.8D$
455.11D18.15D25.16D19.12D27.11D43.27D31.11D1234.11D18.15D25.16D19.12D
27.11D45.25D35.15D19.5D$455.11D20.14D23.15D23.10D27.11D42.16D.11D31.
11D1234.11D20.14D23.15D23.10D27.11D43.27D35.13D$455.11D21.13D23.14D
26.8D27.11D41.15D3.11D31.11D1234.11D21.13D23.14D26.8D27.11D42.28D34.
13D$455.11D22.13D21.14D29.6D27.11D41.14D4.11D31.11D1234.11D22.13D21.
14D29.6D27.11D41.15D2.12D33.13D$455.11D22.13D20.14D31.5D27.11D41.12D
6.11D31.11D1234.11D22.13D20.14D31.5D27.11D40.14D4.12D33.12D$455.11D
23.12D20.13D34.2D28.11D40.11D8.11D31.11D1234.11D23.12D20.13D34.2D28.
11D40.13D5.12D32.12D$455.11D23.12D19.13D65.11D40.10D9.11D31.11D1234.
11D23.12D19.13D65.11D40.11D7.12D32.11D$455.11D24.11D19.12D66.11D41.7D
11.11D31.11D1234.11D24.11D19.12D66.11D40.9D9.12D31.12D$455.11D24.12D
17.13D66.11D41.5D13.11D31.11D1234.11D24.12D17.13D66.11D40.8D10.12D31.
11D$455.11D24.12D17.12D67.11D41.4D14.11D31.11D1234.11D24.12D17.12D67.
11D40.6D12.12D31.11D$455.11D24.12D16.13D67.11D59.11D31.11D1234.11D24.
12D16.13D67.11D41.3D14.12D30.11D$455.11D24.12D16.12D68.11D59.11D31.
11D1234.11D24.12D16.12D68.11D58.12D30.11D$455.11D24.11D17.12D68.11D
59.11D31.11D1234.11D24.11D17.12D68.11D58.12D29.11D$455.11D24.11D16.
12D69.11D59.11D31.11D1234.11D24.11D16.12D69.11D58.12D29.11D$455.11D
24.11D16.12D69.11D59.11D31.11D1234.11D24.11D16.12D69.11D58.12D29.11D$
455.11D23.12D16.12D69.11D59.11D31.11D1234.11D23.12D16.12D69.11D58.12D
29.10D$455.11D23.12D16.11D70.11D59.11D31.11D1234.11D23.12D16.11D70.
11D58.12D29.10D$455.11D22.12D16.12D70.11D59.11D31.11D1234.11D22.12D
16.12D70.11D58.12D28.11D$455.11D22.12D16.12D70.11D59.11D31.11D1234.
11D22.12D16.12D70.11D58.12D28.11D$455.11D21.13D16.12D70.11D59.11D31.
11D2.9D1223.11D21.13D16.12D70.11D58.12D28.11D$455.11D20.13D17.12D70.
11D59.11D31.29D1216.11D20.13D17.12D70.11D58.12D28.11D11.11D$455.11D
18.14D18.11D71.11D59.11D31.32D1213.11D18.14D18.11D71.11D58.12D28.10D
7.20D$455.11D16.16D18.11D71.11D59.11D31.34D1211.11D16.16D18.11D71.11D
58.12D28.10D5.25D$455.11D10.21D19.11D71.11D59.11D31.36D1209.11D10.21D
19.11D71.11D58.12D28.10D2.29D$455.41D20.11D71.11D59.11D31.37D1208.41D
20.11D71.11D58.12D27.44D$455.39D21.12D71.11D59.11D31.38D1207.39D21.
12D71.11D58.12D27.45D$455.38D22.12D71.11D59.11D31.39D1206.38D22.12D
71.11D58.12D27.46D$455.36D24.12D71.11D59.11D31.40D1205.36D24.12D71.
11D58.12D27.47D$455.34D26.12D71.11D59.11D32.10D6.24D1204.34D26.12D71.
11D58.12D27.47D$455.33D27.12D71.11D59.11D55.18D1203.33D27.12D71.11D
58.12D27.22D9.17D$455.35D25.12D71.11D59.11D57.16D1203.35D25.12D71.11D
58.12D27.18D16.15D$455.36D25.11D71.11D59.11D59.15D1202.36D25.11D71.
11D58.12D27.15D20.14D$455.37D24.11D71.11D59.11D60.14D1202.37D24.11D
71.11D58.12D27.13D24.12D$455.11D11.16D23.11D71.11D59.11D61.14D1201.
11D11.16D23.11D71.11D58.12D27.12D25.13D$455.11D13.14D23.11D71.11D59.
11D62.13D1201.11D13.14D23.11D71.11D58.12D27.11D27.12D$455.11D15.13D
22.11D71.11D59.11D63.12D1201.11D15.13D22.11D71.11D58.12D27.11D27.12D$
455.11D16.13D21.12D70.11D59.11D63.12D1201.11D16.13D21.12D70.11D58.12D
27.11D28.11D$455.11D17.12D21.12D70.11D59.11D63.13D1200.11D17.12D21.
12D70.11D58.12D27.11D28.12D$455.11D17.13D20.12D70.11D59.11D64.12D
1200.11D17.13D20.12D70.11D58.12D27.11D28.12D$455.11D18.12D20.12D70.
11D59.11D64.12D1200.11D18.12D20.12D70.11D58.12D27.11D28.12D$455.11D
19.12D20.11D70.11D59.11D64.12D1200.11D19.12D20.11D70.11D58.12D27.12D
28.11D$455.11D19.12D20.12D69.11D59.11D64.12D1200.11D19.12D20.12D69.
11D58.12D28.11D28.11D$455.11D20.12D19.12D69.11D59.11D64.12D1200.11D
20.12D19.12D69.11D58.12D28.11D28.11D$455.11D20.12D19.12D69.11D59.11D
64.12D1200.11D20.12D19.12D69.11D58.12D28.11D28.11D$455.11D20.13D18.
13D68.11D59.11D64.12D1200.11D20.13D18.13D68.11D58.12D28.11D28.11D$
455.11D21.12D19.12D68.11D59.11D64.12D1200.11D21.12D19.12D68.11D58.12D
28.11D28.11D$455.11D21.12D19.13D67.11D59.11D64.11D1201.11D21.12D19.
13D67.11D58.12D28.11D27.12D$455.11D22.12D18.13D67.11D59.11D64.11D
1201.11D22.12D18.13D67.11D58.12D28.12D26.11D$455.11D22.12D19.13D66.
11D59.11D63.12D1201.11D22.12D19.13D66.11D58.12D29.11D26.11D$455.11D
23.12D18.13D66.11D59.11D63.12D1201.11D23.12D18.13D66.11D58.12D29.11D
26.11D$455.11D23.12D19.13D36.D28.11D59.11D62.12D1202.11D23.12D19.13D
36.D28.11D58.12D29.11D25.12D$455.11D23.12D19.14D33.4D27.11D59.11D62.
12D1202.11D23.12D19.14D33.4D27.11D58.12D29.12D24.12D$455.11D24.12D19.
14D30.6D27.11D59.11D61.13D1202.11D24.12D19.14D30.6D27.11D58.12D30.11D
24.11D$455.11D24.12D19.15D28.7D27.11D59.11D60.13D1203.11D24.12D19.15D
28.7D27.11D58.12D30.12D22.12D$455.11D25.12D19.16D24.9D27.11D59.11D28.
3D28.14D1203.11D25.12D19.16D24.9D27.11D58.12D30.12D21.12D$455.11D25.
12D20.17D20.11D27.11D59.11D27.7D24.14D1204.11D25.12D20.17D20.11D27.
11D58.12D31.12D19.13D$455.11D25.12D20.20D14.14D27.11D59.11D27.9D20.
16D1204.11D25.12D20.20D14.14D27.11D58.12D31.13D17.13D$455.11D26.12D
20.25D.21D27.11D43.40D14.12D14.18D1205.11D26.12D20.25D.21D27.11D58.
12D32.13D15.14D$455.11D26.12D21.46D27.11D42.43D12.43D1206.11D26.12D
21.46D27.11D43.40D19.15D11.15D$455.11D26.13D21.45D27.11D41.44D12.42D
1207.11D26.13D21.45D27.11D41.44D18.39D$455.11D27.12D22.43D28.11D41.
44D12.41D1208.11D27.12D22.43D28.11D41.44D18.39D$455.11D27.12D23.40D
30.11D41.45D11.40D1209.11D27.12D23.40D30.11D41.44D19.37D$455.11D28.
12D24.37D31.11D41.44D13.37D1211.11D28.12D24.37D31.11D41.44D20.35D$
455.11D28.12D26.33D33.11D41.44D14.35D1212.11D28.12D26.33D33.11D41.44D
21.32D$455.11D28.12D28.29D35.11D41.44D16.31D1214.11D28.12D28.29D35.
11D41.44D22.30D$455.10D30.11D30.24D38.11D42.43D18.27D1216.10D30.11D
30.24D38.11D41.44D24.26D$457.7D33.7D36.16D44.7D109.19D1222.7D33.7D36.
16D44.7D43.44D26.22D$725.2D1496.16D$2229.3D50$603.D$603.D$603.D$603.D
$603.D$603.D$603.D$603.D$603.D$603.D$603.D$603.D$603.D$603.D$603.D$
603.D$603.D$603.D$603.D$603.D$603.D$603.D$603.D$603.D$603.D$603.D$
603.D$603.D$603.D$603.D$603.D$603.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D505.A$603.D1499.D504.A$603.D1499.D504.
3A$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$131.A.A469.D1499.D$132.2A
469.D1499.D$132.A470.D1499.D$135.2A466.D1499.D$136.2A465.D1499.D$135.
A467.D1499.D$142.3A458.D1499.D$142.A460.D1499.D$143.A459.D1499.D$603.
D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1011.A.A485.D$603.D1012.2A485.D$603.D1012.A486.D$603.D1015.2A482.D$
603.D1016.2A481.D$603.D1015.A483.D$603.D1022.3A474.D$603.D1022.A476.D
$603.D1023.A475.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D985.2A512.D$603.D984.A.A512.D$603.D986.A512.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$271.3A329.D
1499.D$271.A331.D1499.D$272.A330.D1499.D$603.D1499.D$603.D1499.D$603.
D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$73.1061D475.979D$603.DF1498.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1447.F51.D$603.D1499.D$603.D1499.
D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D484.A.A1012.D$603.D484.2A1013.D$603.D485.A1013.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$512.F90.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$570.F32.D1499.
D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1074.A
424.D$603.D1072.A.A424.D$603.D1073.2A424.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$602.FD1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1409.A89.D$603.D
1409.A.A87.D$603.D1409.2A88.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$2.A600.D1499.D$A.A600.D1499.D$.2A
600.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D270.A1228.D$603.D271.A1227.D$603.D269.3A1227.D$603.D
346.A1152.D$603.D344.2A864.A288.D$603.D345.2A862.A289.D$603.D1209.3A
287.D$603.D1202.A296.D$603.D1203.2A294.D$603.D1202.2A295.D$603.D1199.
A299.D$603.D1199.2A298.D$603.D1198.A.A298.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D349.A1149.D$603.
D348.2A1149.D$603.D348.A.A1148.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$337.A265.D1499.D$337.A.A263.D
1499.D$337.2A264.D1499.D487.A$603.D1499.D487.A.A$603.D1499.D487.2A$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D382.A$603.D1499.D383.A$603.D1499.D381.3A$603.D1499.D458.A$603.D
1499.D456.2A$603.D1499.D457.2A$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$138.A464.D1499.D$137.A465.D1499.D$137.
3A463.D1499.D$130.A472.D1499.D$131.2A470.D1499.D$130.2A471.D1499.D$
127.A475.D1499.D$127.2A474.D1499.D$126.A.A474.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$
603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D
1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D1499.D$603.D$603.D$
603.D$603.D$603.D1961.A$603.D1960.2A$603.D1960.A.A$603.D$603.D$603.D$
603.D$603.D$603.D$603.D$603.D$603.D$603.D1407.A$603.D1406.2A$603.D
1406.A.A$603.D$603.D1131.2A$603.D1132.2A$603.D1131.A$603.D$603.D$603.
D$603.D$603.D$603.D$603.D$603.D$603.D$603.D$603.D155$335.A$334.2A$
334.A.A2$59.2A$60.2A$59.A! #C [[ WIDTH 800 HEIGHT 500 ZOOM -4 ]]

After fifteen ticks, the RCT16 pattern drops to a population of only 66 cells, in a slightly smaller bounding box, and the RCT15 pattern drops to 61 cells at the same point (not too surprisingly). Some nontrivial re-working of the RCT design might possibly drop the minimum population by another ten cells or more.

It has not been proven that 15 gliders is the minimal number that supports RCT-type universal construction. However, we can be confident that there are less than a dozen new smaller RCT{n} pattern records remaining to be set! (Collisions between three gliders have been enumerated fairly thoroughly at this point.)

05 July 2022

Current RCT Technology, Part 3: The Extreme Compression Construction Arm (ECCA)

Quick Recap

There's been a lot of detail in the last couple of posts, and there's probably some danger of getting lost in the weeds here. Time for a short summary of what pieces of the RCT project have been completed so far, and which pieces are still left to do.

1. COMPLETE: Fifteen gliders crash to create four glider-producing switch engines, which send long streams of gliders to collide at the RCT epicentre.

2. COMPLETE: A sixteenth glider hits the initial output gliders from that glider-stream collision, to provide a target elbow for the RCT's initial construction arm.

3. COMPLETE: Using a "divide by two and take the remainder" mechanism, the RCT repeatedly measures the parity of the distance between the epicentre and the southeastern GPSE, and emits either a single glider or a pair of gliders toward the target elbow.

4. COMPLETE: Recipes are known that create a target a safe distance off to the side, move the elbow forward and back as needed, and emit gliders on any chosen lane. The RCT's initial construction arm is therefore provably universal.

5. COMPLETE: The RCT's initial construction arm builds a DBCA (see previous post) and routes data from the RCT into these, for a ~12x improvement in construction efficiency.

6. PARTLY COMPLETE: The DBCA builds an ECCA -- Extreme Compression Construction Arm, see below -- and routes input RCT data into it, for an additional ~30% efficiency improvement. The ECCA has been completely designed (implementation details here) but as of 5 July 2022, integrated self-destruct circuitry still needs to be added.

7. PARTLY COMPLETE: The DBCA builds a "catcher" for incoming GPSEs, then builds a pseudo-BSRD (more details here) and routes all remaining RCT construction data into it. The pseudo-BSRD delays the final construction and cleanup stages until after the GPSEs have crashed at the epicentre and all debris can be safely cleaned up.

8. TBD: The ECCA, working with data emitted by the pseudo-BSRD, cleans up all of the DBCA's circuitry, and all of the non-periodic ash from the GPSE crashes.

9. COMPLETE: The ECCA builds a seed for the ATBC -- the Actual Thing Being Constructed, which is the real end goal of one of these RCT construction/deconstruction projects. A sample ATBC seed for a large object not ordinarily constructible with 16 gliders can be found here. When triggered, the seed will build Alan Hensel's decimal counter. To construct the seed, the ECCA will fire 7284 slow gliders, which will be encoded by about 52,000 bits coming from the RCT mechanism.

10. MOSTLY COMPLETE: The ECCA builds and triggers 106 Cordership seeds. These Corderships fly past the periodic GPSE ash and clean it all up. The required fleet of Corderships has been designed and tested; a recipe to build and launch them one at a time has not been compiled yet, but this is a fairly straightforward task.

11. PARTLY COMPLETE: The Corderships are caught and cleanly removed by "Corderabsorbers" which will have been constructed at the sites of the "ash blobs" left behind by the GPSE launches. All Corderabsorbers have been designed and tested, but recipes to build them have not been compiled yet. For the southwest Corderabsorbers, this will require using slow^2 salvos. No generalized compiler for slow^2 salvos exists at the moment, but one can easily be written.

12. COMPLETE: The final Corderabsorber in the southeast releases an output glider, which triggers the ATBC seed. All cleanup is complete, so the only thing left in the Life universe is the ATBC.

The ECCA

A detailed description of the Extreme Compression Construction Arm can be found here.

EDIT 11/11/2022: I'll leave this post as a snapshot of the RCT blueprint as it was at this stage of development. The final design (see links in the November 10 post) still works very much along these same lines, but several changes have been made to the build order and other details. For example, to improve Golly's ability to explore the final stages of the pattern, the Actual Thing Being Constructed has been moved to the epicentre instead of the far southwest corner.

29 May 2022

Current RCT Technology, Part 2: the DBCA (Decoder and Better Construction Arm)

Part 1 of this series of posts on RCT (reverse caber tosser) patterns described the basic mechanism of storing construction information in very large distances, and extracting it with a mechanism that amounts to repeatedly dividing the distance by two and taking the remainder. The minimum number of gliders needed to produce a working universal construction arm turns out to be ridiculously small -- only 16 gliders as of this writing, and there's no guarantee that this is the cheapest possible mechanism.

However, a construction-arm mechanism can make it possible to build any desired constructible object, without necessarily being very efficient about it. In this case, the RCT's native construction arm needs a very long string of bits to produce an output glider -- over an order of magnitude more bits than we would need with a more efficient encoding mechanism.

The DBCA...

This means that, in our continuing quest to build any possible glider-constructible object using only sixteen gliders, it's now time for an apparently insane diversion. Rather than going ahead and building what we want to build -- the ATBC, or Actual Thing Being Constructed, which is the real goal of any RCT construction -- we instead go through a "bootstrap" stage, where we build a whole new construction arm mechanism that's much more efficient than the original, and then use that new construction arm to do a lot of cleanup ... plus building the ATBC, almost as an afterthought, at the very end.

This extra "bootstrap" mechanism is called the DBCA -- Decoder and Better Construction Arm.

Somewhat counterintuitively, if an RCT pattern takes the time to build a DBCA before doing anything else, it will end up completing its final construction much faster than it would have otherwise. Any given construction -- even if it's only something very small and simple, like the single shillelagh from the example -- will need only a fraction of the number of bits that would have to be stored in the RCT mechanism if it used only the native RCT construction arm.

This first bootstrap stage will also help to enable a second bootstrap stage, which will be even more useful than the first. The DBCA allows for roughly a twelvefold efficiency improvement, but the actual construction and cleanup problem is still painfully difficult: new bits will only keep getting fed into the DBCA while the switch-engines are still producing incoming gliders. We can't do any cleanup until after the four GPSEs have arrived at the epicenter and have been safely stabilized -- but at that point, we won't have any more recipe information coming in to tell the DBCA how to do the cleanup!

... And The BSRD

The idea behind the next bootstrap stage -- called the BSRD, for "Binary Storage and Retrieval Device" -- is to find a way to store incoming information, so that we can delay the last stage of the RCT's complicated construction and cleanup process. We'll still complete the repeated process of dividing the RCT distance by two and taking the remainder, but now we'll store all that information somewhere instead of building anything immediately. Then, after the incoming glider streams have all been absorbed, and the incoming switch engines have all stabilized into very long trails of safe stable ash, we'll make use of the stored information to run the DBCA to do any final construction and cleanup tasks.

The original plan was to construct a BSRD with a static data tape -- a long line of blocks and blanks representing 1s and 0s, let's say, that can be read by an "index elbow" moved by a slide gun type device, similar to the binary tapes in the pi and phi calculators, but rebuilt to make them more easily constructible by slow salvos.

However, it turns out that a storage unit can probably be built that's at least a couple of orders of magnitude cheaper than that. See the "pseudo-BSRD" discussion below.

A complete DBCA recipe

On 27 May 2022, Pavel Grankovskiy completed an RCT recipe for a working DBCA mechanism, including quite a bit of periodic circuitry, based in part on an earlier design by Adam P. Goucher. Periods that are multiples of 8 happen to work well with incoming GPSE glider streams, and it's somewhat cheaper to build a period-8 bumper or bouncer than a stable Snark reflector. It's also cheaper to build a suppressed period-256 shotgun for the common parts of the various salvos for a construction arm, than to build an all-stable synchronized shotgun.

The combined improvements to the original design allow the entire DBCA structure to be constructed at about 60% of the original estimated cost.

... and a complete BSRD, too!

In regards to completing a proof-of-concept RCT design, a further pleasant surprise showed up on May 27th, when Grankovskiy pointed out that only a few small circuits needed to be added to produce a completely functional BSRD -- or rather, a "pseudo-BSRD", since the structure is not really a binary storage device. Instead of writing data to a static binary tape near the epicentre, the pseudo-BSRD will simply deflect the gliders coming in from the RCT mechanism, sending them out to faraway reflectors near the southeast GPSE launch point.

By the time the first gliders get back to the epicentre, the incoming GPSEs have safely finished their work and have been caught by carefully placed absorbers, all the stored bits have been sent to the pseudo-BSRD, and the DBCA can begin the incredibly long process of cleaning up the GPSEs' ash trails. The original pseudo-BSRD design used p8 reflectors and Snarks, which was more expensive than strictly necessary. A stable rebuild was completed a few days later, and for the time being there seems to be a consensus that that's a good enough option to implement. The pseudo-BSRD is probably somewhere between two and three orders of magnitude simpler than the original projected BSRD design, so this was a massive reduction in the complexity of the full RCT prototype.

Highlights of the DBCA

Some of the key details of the new Goucher-Grankovskiy construction arm are summarized in an earlier forum post in the same thread. The DBCA recipe pattern is too big to be readily animated with LifeViewer, but several key moments are highlighted in that post. The full pattern can very easily be run to completion using Golly.

Here are a few items that weren't called out in detail in the forum post. Zoom in toward the upper left corner below, and you'll see labels appear for the nine possible output signals from the unary counter there. The following LifeViewer pattern places nine single-glider signals that produce each of those nine outputs (one right after the other, instead of separated by vast amounts of time as in a real RCT pattern). There are four types of glider output (even and odd color-changing and color-preserving 90-degree gliders), followed by INC16, DEC8, INC4, DEC2, and INC1.

Code: Select all
x = 1319, y = 2156, rule = B3/S23
583b2o$583b2o$569bo$569b3o$572bo9bob2o$571b2o9bobo$583bo$576bo6b2o$
575bobo5b2o$575bo2bo4b2o$576b2o11$550b2o81bo$546b2obo2bob2o8b2o66b3o$
546b2o2bo4bo7bobo65bob3o$551bo13bo55bo8bo3bo$552bobo66b3o5bo3bo$624bo
3b3obo$623b2o4b3o$555bo74bo$554bobo69bo$553bo2bo68bobo$554b2o65b2o2b2o
$621b2o2$550b2o$549bobo$549bo$548b2o5$598b2o$591b2o5b2o$591b2o3$593b2o
27b2o$593b2o27b2o$587b2o$587b2o$628b2o$628b2o$624b2o$624b2o$550b2o51bo
$550b2o51b2o$536bo65bobo$536b3o90b2o$539bo11b2o76b2o$538b2o9bob2o105b
2o5b2o$549bo75bobo30b2o5bo$543bo5bo76b2o35bobo$542bobo4bo2bo73bo36b2o$
542bo2bo4b2o107b2o$543b2o114bobo$588b2o70bo$587bo2bo$586b6o71b2o$586b
6o71b2obo$586b2o79bo$585b3o76bo$585b2o78bob2o$582b2ob2o80b2o$582bobobo
11b2o46bo$583b4o6b2o2b3o2b2o40b2o$584b2o7bo2bobo4b2o40b2o$589b2o3bo3bo
b2obo$588bo2bo5bo3b2o28bo$587bo3bo40b2o$583b2o2bo2bo40b2o$583b2o2bo2bo
$624b2o$624b2o$588bo2bo26b2o$589b2o27b2o3$620b2o$519b2o92b2o5b2o$520b
2o91b2o$519bo6$636b2o3b2o$635bo2bobo2bo$630bo5b2o3b2o5bo$629bobo15bobo
$630bo17bo2$600b2o$601bo$601bobo$602b2o3$606b2o18bo$605bo2bo16b3o$606b
obo15b3obo$607bo17bo3bo8bo$626bo3bo5b3o20b3o$533b2o92bob3o3bo26bo$533b
o70b2o22b3o4b2o21bo3bo$531bobo70b3o22bo18bo8bobo2bo$516b2o13b2o65b2o2b
o2bobo25bo14b3o4bo2bobo$516b2o80b2o2b2o2b2o24bobo16bo3bo3bo$602b2o29b
2o2b2o11b2o3bo$637b2o17b3o$496b2o155bo$496b2o154bobo$648b2o2b2o$648b2o
$495bo193bobo$494bobo193b2o$495bo194bo$492b3o$492bo$629bobo$630b2o$
630bo61bo$535b2o153bobo$535b2o154b2o7$532b2o$532bo$533b3o$535bo6$503b
2o$503b2o2$455b2o23b2o$456b2o22b2o$455bo46b2o$502bo186b2o5b2o$460b2o
38bobo186b2o5bo$460b2o38b2o192bobo$694b2o$690b2o$459bo230bobo$458bobo
230bo$459bo$456b3o235b3o$456bo237b3o$694b3o$697b3o$697b3o$499b2o196b3o
$499b2o7$496b2o$496bo$497b3o$499bo6$467b2o$467b2o2$444b2o307bobo$444b
2o308b2o$466b2o286bo$466bo$424b2o38bobo$424b2o38b2o227bobo$694b2o$694b
o61bo$423bo330bobo$422bobo330b2o$423bo$420b3o$420bo4$463b2o$463b2o6$
744bo$460b2o281bobo$460bo281bo3bo$461b3o277bo3bo$463bo276bo3bo$391b2o
346bo3bo$392b2o346bobo$391bo349bo$737bo$736bobo$431b2o303b2o$431b2o
307b2o$740bobo$408b2o325b2o5bo$408b2o325b2o5b2o$430b2o$430bo$388b2o38b
obo$388b2o38b2o3$387bo$386bobo$387bo$384b3o$384bo124bo$507b3o$506bo$
505bobo$427b2o76bobo$427b2o77bo42bo$547b3o$546bo$546b2o2$490b2o99bo$
490b2o97b3o$424b2o162bo$424bo100b2o60bobo$425b3o96bobo60bobo$427bo82b
2o12bo63bo$510bobo10b2o292bobo$512bo305b2o$503b2o7b2o304bo$503b2o23b2o
$527bobo42b2o$395b2o96bob2o30bo44b2o183bobo$395b2o94b3ob2o29b2o230b2o$
490bo267bo61bo$372b2o117b3ob2o254b3o64bobo$372b2o119bobo96b2o160bo64b
2o$394b2o97bobo96bobo155bo3bo$394bo99bo99bo145bo8bobo2bo$352b2o38bobo
142b2o46b2o7b2o144b3o4bo2bobo$352b2o38b2o143b2o46b2o156bo3bo3bo$545b2o
195b2o3bo$545bo29bob2o169b3o$351bo194b3o24b3ob2o166bo$350bobo150b2o43b
o23bo171bobo$351bo151b2o68b3ob2o161b2o2b2o$348b3o196bo27bobo162b2o$
348bo197bobo26bobo$546bobo27bo$490bo54b2ob3o$489bobo59bo$391b2o96bobo
53b2ob3o$391b2o94b3ob2o52b2obo$486bo$487b3ob2o44b2o46b2o$327b2o160bob
2o35b2o7b2o46b2o$328b2o199bo$327bo201bobo$530b2o$388b2o182bo$388bo182b
obo$389b3o96b2o81bobo$391bo95bobo60b2o17b3ob2o$487bo62b2o16bo$486b2o7b
o73b3ob2o$494bobo74bob2o$495bo$502b2o$359b2o141b2o31bo$359b2o173bobo$
534bobo$336b2o197bo34b2o$336b2o194b3o34bobo$358b2o172bo36bo$358bo209b
2o7bo$316b2o38bobo217bobo$316b2o38b2o219bo$554b2o28b2o$554b2o28b2o195b
2o5b2o$315bo253bo211b2o5bo$314bobo237bo12b3o216bobo$315bo237bobo10bo
49b2o168b2o$312b3o238bo2bo9b2o48b2o164b2o$312bo241bo2bo73bo150bobo$
562bo53bo12b3o151bo$554bo2bo3bobo51bobo10bo$554b2o4bo2bo51bo2bo9b2o
156b3o$355b2o204b2o53bo2bo166b3o$355b2o267bo161b3o$616bo2bo3bobo163b3o
$616b2o4bo2bo163b3o$623b2o164b3o89bobo$882b2o$588b2o292bo2$352b2o233bo
3bo$352bo233bo4bo229bobo$353b3o229bobobo232b2o$355bo228bobobo233bo61bo
$582bo4bo294bobo$517b2o63bo3bo118bo177b2o$517bo15bo9bo159b3o$515bobo
15b3o5b3o37bo2b2o116bo$515b2o19bo3bo39bobo119b2o$323b2o210b2o3b2o38b2o
$323b2o259b2o161bo$584bobo158b3o163bo$300b2o192b2o83b2o5bo157bo164b3o$
300b2o192b2o83b2o5b2o93b2o60bobo162bo$322b2o356bobo60bobo162b2o$322bo
357bo63bo$280b2o38bobo356b2o$280b2o38b2o204b2o$526b2o$538b2o144b2o$
279bo257bo2bo142bobo42b2o$278bobo257b2o4b2o137bo44b2o$279bo264bobo135b
2o$276b3o267bo$263b2o11bo269b2o$264b2o270b2o210b2o$263bo242b2o29bo210b
obo$506bo27b3o213bo$319b2o186b3o11b2o11bo140bo17b2o46b2o7b2o120b2o$
319b2o188bo11b2o2b2o147bobo16b2o46b2o129b3o$525bobo145bo3bo23b2o163b2o
2bo2bobo$526bo145bo3bo24bo29bob2o131b2o2b2o2b2o$530bo140bo3bo26b3o24b
3ob2o135b2o$523b2o4bobo138bo3bo29bo23bo$524bo3bo3bo138bobo55b3ob2o$
521b3o5bo3bo138bo30bo27bobo$316b2o203bo8bo3bo133bo33bobo26bobo132bo$
316bo214bo3bo131bobo32bobo27bo132bobo$317b3o212bobo132b2o32b2ob3o135b
2o21bo2bo$319bo213bo137b2o34bo134b2o22b2o$671bobo27b2ob3o$666b2o5bo27b
2obo$666b2o5b2o195b2o$693b2o46b2o127bobo$684b2o7b2o46b2o129bo$287b2o
312bo83bo186b2o$287b2o310b3o83bobo$598bo87b2o$264b2o332b2o128bo58b3o$
264b2o461bobo56bo$286b2o439bobo56bo3bo$286bo419b2o17b3ob2o55bo2bobo91b
3o$244b2o38bobo139b2o278b2o16bo63bobo2bo91bo$244b2o38b2o291b2o146b3ob
2o58bo3bo90bo$424bo3bo147bobo148bob2o62bo$424bo4bo146bo213b3o$243bo
182bobobo144b2o218bo$242bobo182bobobo259bo102bobo$243bo184bo4bo256bobo
102b2o$240b3o186bo3bo94b2o50b2o108bobo98b2o85b2o$240bo286bo2bo4b2o42bo
bo109bo34b2o62bobo84bo2bo4b2o$430b2o2bo92bobo5b2o42bo108b3o34bobo62bo
5b2o79bobo5b2o$433bobo92bo49b2o108bo36bo63b2o5b2o80bo$434b2o288b2o7bo
151bo$283b2o145b2o91b2o9b2o196bobo138b2o9bobo$283b2o144bobo92bo9b2obo
195bo140bo9bo2bo$429bo5b2o84b3o13bo172b2o28b2o129b3o11bo2bo$428b2o5b2o
84bo15bo172b2o28b2o129bo$534bo2bo51b2o134bo159bo2bo$535b2o52b2o119bo
12b3o159b2o$597b2o110bobo10bo198b2o20b2o$597bo111bo2bo9b2o193b2o2b2o2b
2o16b2o$280b2o316b3o109bo2bo203bobo2bo2b2o$280bo319bo117bo199b3o$281b
3o426bo2bo3bobo199b2o$283bo315bo110b2o4bo2bo$598bobo116b2o$454b2o142bo
bo316bo$450b2o2b2o141b2ob3o313bobo$449bobo75bo75bo312bo2bo$450bo76b3o
67b2ob3o314b2o9b2o$251b2o277bo66b2obo327b2o$251b2o192b3o4b2o75b2o213b
2o$445b3o4bo91b2o43b2o330b2o$228b2o215b3o5b3o88bo35b2o7b2o152bo3bo173b
obo$228b2o212b3o10bo86bobo36bo160bo4bo175bo$250b2o190b3o86bo10b2o37bob
o157bobobo177b2o$250bo191b3o85bobo49b2o156bobobo$199b2o7b2o38bobo279bo
bo205bo4bo$200b2o6b2o38b2o275b2o4bo141b2o63bo3bo$199bo324bobo15b2o129b
o15bo9bo$524bo17bobo57b2o67bobo15b3o5b3o37bo2b2o206b2o$207bo305b2o8b2o
19bo57b2o67b2o19bo3bo39bobo209bo$206bobo304b2obo27b2o145b2o3b2o38b2o
211b3o$207bo309bo222b2o209bo$204b3o307bo225bobo$204bo310bob2o131b2o83b
2o5bo$517b2o68bo62b2o83b2o5b2o176b2o5b2o$586bobo332bo5b2o$521bo11b2o
51bobo332bobo$247b2o271bobo10b2o52bo334b2o$247b2o272b2o61b3o95b2o242b
2o$517b2o65bo97b2o241bobo10b2o$516bobo175b2o230bo11b2o$516bo5b2o90b2o
77bo2bo$515b2o5b2o170b2o4b2o220b2o$612bo3bo83bobo217bob2o$612bo4bo84bo
216bo$244b2o300bo67bobobo83b2o218bo$244bo299b3o68bobobo72b2o134b2o88b
2obo27b2o$245b3o295bo72bo4bo40b2o29bo109bo9bo15bo88b2o8b2o19bo$247bo
295b2o72bo3bo40bo27b3o110b3o5b3o15bobo97bo17bobo$663b3o11b2o11bo115bo
3bo19b2o97bobo15b2o$618b2o2bo42bo11b2o2b2o122b2o3b2o118b2o4bo$621bobo
57bobo251bobo$622b2o58bo252bobo$618b2o66bo164b2o83bo10b2o$215b2o305b2o
93bobo59b2o4bobo163b2o94bobo$215b2o306bo93bo5b2o55bo3bo3bo260bo$191b2o
330bobo90b2o5b2o52b3o5bo3bo259b2o$187b4o4b2o327b2o151bo8bo3bo243b2o$
187b3ob2o2b2o490bo3bo127b2o114bo$192bo495bobo128b2o111b3o$146b2o541bo
117b2o123bo$139b2o5b2o658bo2bo$79b2o58b2o660b2o4b2o$79b2o58b2o55bo603b
obo$65bo74b2o3b2o48bobo602bo$65b3o71bo2bo2b2o23b2o22bo2bo601b2o$68bo9b
ob2o58bo2bo26b2o23b2o445b2o165b2o$67b2o9bobo54b2o6bo494b2o2b2o165bo29b
2o$79bo55b2o3bo2bo6b2o386b2o97bobo170b3o27bo$72bo6b2o59bobo33b2o13b2o
345b2o98bo173bo11b2o11b3o$71bobo5b2o60bo34b2o12bobo520b3o104b2o2b2o11b
o$71bo2bo4b2o63b2o26b2o16bo442b3o4b2o71b3o103bobo$72b2o71bo26b2o15b2o
442b3o4bo72b3o100bo3bo$633b3o5b3o72b3o97b2o$630b3o10bo72b3o96b2obo3b2o
$630b3o83b3o95bo2b3o2bo$177b2o451b3o180bobobo5b3o$134b2o41b2o542bo90bo
bobo8bo$135bo9bo574bobo87b3o2bo$135bobo3bo3bo575b2o88bob2o$136b2o4bo2b
o538b2o31b2o93b2o$142b2ob2o16bobo517bo2bo4b2o23bobo55b2o37bo$143bobo
18b2o517bobo5b2o23bo5b2o50bo238b2o$144bo19bo519bo30b2o5b2o48bobo212b4o
22b2o$772b2o208b2o7bo$216b2o461b2o9b2o290b2o2b2o3bo$209b2o4bo2bo461bo
9b2obo292b2o2bo$209b2o5bobo458b3o13bo74b2o$217bo459bo15bo73bo2bo$171b
2o37bo479bo2bo73bobo$171bo37bobo9b2o327b2o139b2o75bo213bo$130b2o40b3o
33bo2bo9bo327bo2bo4b2o422bobo$130b2o42bo32bo2bo11b3o324bobo5b2o422bo2b
o13b2o$224bo325bo431b2o14b2o$207bo2bo561b2o$209b2o334b2o9b2o210b2obo2b
ob2o$135b2o409bo9b2obo208b2o2bo4bo208b2o$135b2o406b3o13bo213bo212bobo$
131b2o410bo15bo214bobo211bo$131b2o423bo2bo428b2o$172b2o383b2o$172b2o$
137b2o27b2o$137b2o27b2o850b2o$1018bo$749b2o268b3o$168b2o572b2o4bo2bo
269bo$161b2o5b2o572b2o5bobo$142b2o17b2o579b2o6bo$143bo599bo$140b3o599b
obo9b2o$140bo600b2obo9bo247b2o$755b3o245bo23b2o$757bo242b3o24bo$742b2o
256bo7b2o15bobo$742b2o264b2o15b2o10$4b2o$2obo2bob2o$2o2bo4bo997b2o$5bo
1000bobo$6bobo997bo$1005b2o2$9bo$8bobo$7bo2bo$8b2o$1023b2o$1023bo$4b2o
1018b3o$3bobo1020bo$3bo$2b2o4$1015b2o$1006b2o7b2o$1007bo$921b2o84bobo$
921b2o2b2o81b2o$925bobo$926bo$929b3o$923b2o3bo$924bo3bo3bo$921b3o4bo2b
obo$921bo8bobo2bo$931bo3bo$935bo150b2o$692bo239b3o151b2o$105b2o2bo580b
3o346b2o4b2o$101b2o2b2o3bo578bo348bo2bo3b2o$101b2o7bo578b2o348b2o$106b
4o$1013bo$162b2o848bobo$161bo2bo4b2o841bobo$110bo50bobo5b2o497b2o343bo
$109bobo50bo504bobo401b2o$108bo2bo57bo497bo376b2o25b2o$109b2o46b2o9bob
o495b2o353b2o21b2o$158bo9bo2bo840b2o7b2o$155b3o11bo2bo229b2o5b2o601b2o
33b2o$105b2o48bo247bo5b2o260b2o374b2o$104bobo62bo2bo230bobo264bobo384b
2o$104bo64b2o233b2o264bo386bo$103b2o303b2o259b2o384bobo$407bobo645b2o$
408bo$404bo686b2o$1091bo$402b3obo685b3o$401bob2o275b2o412bo$401b2obo
275b2o$399bob3o284b2o$688bo$401bo287b3o359b2o22b2o$691bo359bobo20bobo$
1053bo20bo25b2o$690bo362b2o18b2o25bo$689bobo389b2o15bobo$420b2o267bobo
389b2o15b2o$420b2o2b2o262b2ob3o$424bobo267bo$425bo262b2ob3o$428b3o257b
2obo344b2o$422b2o3bo608b2o$423bo3bo3bo248b2o362b2o$420b3o4bo2bobo238b
2o7b2o362bo$420bo8bobo2bo237bo372b3o$430bo3bo237bobo372bo$434bo238b2o$
431b3o612bo$1045bobo32b2o$1045bobo31bobo$693b2o349b2ob3o29bo$693b2o
355bo27b2o$74b2o968b2ob3o$74b2o968b2obo2$1036b2o63b2o5b2o$678bo348b2o
7b2o63b2o5bo$677bobo348bo77bobo$677bobo348bobo75b2o$678bo350b2o71b2o$
675b3o412b2o10bobo$675bo414b2o11bo3bo$1106b2o$1049b2o54bob2o$1049b2o
53b3o2bo35b2o$1106bobobo34b2o$25b2o1080bobobo$25b2o1052b2o27bo2b3o$
1080bo19b2o7b2obo$1034bo45bobo17bo9b2o$1033bobo45b2o15bobo9bo$1033bobo
57bo4b2o$1034bo57bobo$1031b3o58bobo$33b2o996bo49b2o10bo36b2o$33b2o
1045bobo47b2o$1080bo$1079b2o$710bo383b2o$708b3o383bo$707bo387b3o$707b
2o388bo4$1150b2o$686b2o462bo$685bobo463b3o$685bo467bo$684b2o3$574bo
114b2o$574b3o111bobo443b2o$577bo110bo446bo23b2o$576bobo108b2o443b3o24b
o$576bobo553bo24bobo$577bo579b2o2$2o$2o$698b2o$592b2o62bo41b2o442b2o$
592b2o62b3o47b2o434b2o7b2o$659bo46bo444bo$658bobo46b3o439bobo$658bobo
48bo439b2o$572b2o85bo472b2o$571bobo134bo423b2o$571bo135bobo412b2o$570b
2o7b2o126bobo413bo$579b2o125b2ob3o411bobo$674b2o36bo411b2o$587b2obo83b
2o30b2ob3o$587b2ob3o113b2obo$593bo$587b2ob3o105b2o$588bobo63b2o33b2o7b
2o$588bobo62bobo34bo$589bo63bo36bobo$652b2o7b2o28b2o$590bo70b2o465b2o$
588b3o536bobo$587bo81b2obo454bo$587b2o80b2ob3o36b2o413b2o$579b2o94bo
35b2o$579b2o88b2ob3o$670bobo$670bobo$671bo$696bo446b2o$672bo22bobo445b
2o$568b2o100b3o22bobo437b2o$569bo99bo26bo439bo$569bobo97b2o22b3o437b3o
$570b2o89b2o30bo439bo$661b2o$1134bo$565b2o566bobo$566bo566bobo$566bobo
562b3ob2o$567b2o561bo$650b2o479b3ob2o$651bo481bob2o$651bobo$652b2o489b
2o$588b2o553b2o7b2o72b2o$588bo563bo73b2o$589b3o55b2o501bobo$591bo56bo
501b2o$648bobo$649b2o2$1130b2o$1130b2o2$670b2o539b2o$670bo540b2o$671b
3o$673bo472bo$1145bobo$1145bobo$1146bo$1147b3o$502bo646bo$502b3o$505bo
$504bobo724b2o$504bobo724bo$505bo726b3o$1234bo$1134b2o11bo$1134b2o10bo
bo$1146bobo31b2o21b2o5b2o$520b2o62bo560b2ob3o2b2o25bo23bo5b2o$520b2o
62b3o564bo2bo23bobo23bobo$587bo557b2ob3o3bobo21b2o25b2o$586bobo556b2ob
o6b2o52b2o$586bobo619bobo10b2o$500b2o85bo621bo11b2o$499bobo$499bo704b
3o$498b2o7b2o695b3o$507b2o695b3o$602b2o538b2o13b2o42b3o$515b2obo83b2o
538b2o13b2o42b3o28b2o$515b2ob3o606b2o72b3o7b2o19bo$521bo604bo2bo82bo
17bobo$515b2ob3o604bob2o83bobo15b2o$516bobo63b2o541bo87b2o4bo$516bobo
62bobo540b2o92bobo$517bo63bo557b2o77bobo$580b2o7b2o548bo79bo10b2o$518b
o70b2o549b3o23b2o62bobo$516b3o623bo24bo64bo$515bo81b2obo563b3o4b2o59b
2o$515b2o80b2ob3o561bo6b2o44b2o$507b2o94bo614bo$507b2o88b2ob3o612b3o$
598bobo614bo$598bobo$599bo2$600bo$496b2o100b3o$497bo99bo$497bobo97b2o$
498b2o89b2o$589b2o$893bo$493b2o398b3o$494bo401bo364b2o$494bobo398bobo
363b3o$495b2o398bobo357b2o2bo2bobo$578b2o316bo358b2o2b2o2b2o$579bo679b
2o56b2o$579bobo735b2o$580b2o$516b2o$516bo394b2o342bo$517b3o55b2o334b2o
341bobo$519bo56bo677bo2bo$576bobo676b2o$577b2o$891b2o$890bobo366b2o$
890bo368bobo$889b2o7b2o361bo$598b2o298b2o361b2o$598bo$599b3o304b2obo$
601bo304b2ob3o$912bo$906b2ob3o$907bobo$907bobo$908bo2$909bo$907b3o$
906bo$906b2o$898b2o$898b2o6$887b2o$888bo$888bobo$889b2o4$887b2o$887b2o
6$907b2o$907bo$908b3o$910bo32$737bo$737b3o$740bo$739bobo$739bobo$740bo
5$755b2o$755b2o4$735b2o$734bobo$734bo$733b2o7b2o$742b2o2$750b2obo$750b
2ob3o$756bo$750b2ob3o$751bobo$751bobo$752bo2$753bo$751b3o$750bo$750b2o
$742b2o$742b2o6$731b2o$732bo$732bobo$733b2o4$731b2o$731b2o6$751b2o$
751bo$752b3o$754bo21$887bo$887b3o$890bo$889bobo$889bobo$890bo5$905b2o$
905b2o4$885b2o$884bobo$884bo$883b2o7b2o$892b2o2$900b2obo$900b2ob3o$
906bo$900b2ob3o$901bobo$901bobo$902bo2$903bo$901b3o$686b2o212bo$686b2o
2b2o208b2o$690bobo199b2o$691bo200b2o$695bo$688b2o4bobo$689bo3bo3bo$
686b3o5bo3bo$686bo8bo3bo$696bo3bo180b2o$697bobo182bo$698bo183bobo$883b
2o4$881b2o$881b2o5$1046b2o$901b2o142bo2bo4b2o$901bo143bobo4bo2bo$902b
3o141bo5bo$904bo147bo$1041b2o9bob2o$1042bo11b2o$1039b3o$1039bo$1053b2o
$1053b2o46$836b2o$836b2o2b2o$840bobo$841bo$845bo$838b2o4bobo$839bo3bo
3bo$836b3o5bo3bo$836bo8bo3bo$846bo3bo$847bobo$848bo654$1300b3o11$1280b
o$1279bobo$1278bo3bo$1277bo3bo$1276bo3bo$1275bo3bo$1276bobo$1277bo$
1273bo$1272bobo$1272b2o$1276b2o$1276bobo$1271b2o5bo$1271b2o5b2o23$
1250b2o$1248bob2o$1247bo$1250bo$1246b2obo$1246b2o2$1243bo$1242bobo$
1242b2o$1246b2o$1246bobo$1241b2o5bo$1241b2o5b2o360$874bo2$871b3o$873bo
$872bo39$824b2o$823bobo$825bo!
#C [[ THEME Blues STEP 16 X 0 Y -200 Z -4 ]]
#C [[ LABELANGLE 45 ]]
#C [[ LABEL 300 500 2 "FIRE_CC_ODD_DEC1" ]]
#C [[ LABEL 336 464 2 "FIRE_CP_EVEN_DEC1" ]]
#C [[ LABEL 372 428 2 "FIRE_CC_EVEN_DEC1" ]]
#C [[ LABEL 408 392 2 "FIRE_CP_ODD_DEC1" ]]
#C [[ LABEL 444 356 2 "INC16" ]]
#C [[ LABEL 480 320 2 "DEC8" ]]
#C [[ LABEL 516 284 2 "INC4" ]]
#C [[ LABEL 552 248 2 "DEC2" ]]
#C [[ LABEL 588 212 2 "INC1" ]]
#C [[ PASTET 1024 PASTE 2110$874bo2$871b3o$873bo$872bo39$824b2o$823bobo$825bo! 0 0 ]]
#C [[ PASTET 2048 PASTE 2110$874bo2$871b3o$873bo$872bo39$824b2o$823bobo$825bo! 0 0 ]]
#C [[ PASTET 3072 PASTE 2110$874bo2$871b3o$873bo$872bo39$824b2o$823bobo$825bo! 0 0 ]]
#C [[ PASTET 4096 PASTE 2110$874bo2$871b3o$873bo$872bo39$824b2o$823bobo$825bo! 0 0 ]]
#C [[ PASTET 12288 PASTE 2110$874bo2$871b3o$873bo$872bo39$824b2o$823bobo$825bo! 0 0 ]]
#C [[ PASTET 16384 PASTE 2110$874bo2$871b3o$873bo$872bo39$824b2o$823bobo$825bo! 0 0 ]]
#C [[ PASTET 18432 PASTE 2110$874bo2$871b3o$873bo$872bo39$824b2o$823bobo$825bo! 0 0 ]]
#C [[ PASTET 20480 PASTE 2110$874bo2$871b3o$873bo$872bo39$824b2o$823bobo$825bo! 0 0 ]]
#C [[ STOP 33000 ]]

With a combination of some subset of these nine operations, the DBCA can generally fire exactly the right next glider in its recipe, at a standard cost of just nine bits on the tape (one "codon"). In any bit position, two incoming gliders will suppress the output and nothing will happen; one incoming glider will allow that operation to happen.

Slow And Steady Wins The Race

Notice what happens when the unary decoder in the northwest reaches the ninth output position, and the entire bistable switch stack has to be reset to return to zero position. Feeding the final bistable switch output back into one of its inputs does a great job of resetting the entire stack -- eventually. It's all done in 35,000 ticks or so -- see below.

Code: Select all
x = 636, y = 595, rule = LifeHistory
583.2A$583.2A$569.A13.2A$569.3A12.A$572.A10.A.A$571.2A9.2A.A2$576.A$
575.A.A5.2A$575.A2.A4.2A$576.2A10$547.A.A$550.A$546.A4.A2.2A30.A.A$
546.2A.A2.A.2A31.2A$550.2A35.A4$555.A$554.A.A$553.A2.A$554.2A3$550.2A
$549.A.A$549.A$548.2A5$598.2A$591.2A5.2A15.F$591.2A22.F$615.F$615.F$
593.2A27.2A$593.2A27.2A$587.2A$587.2A$628.2A$628.2A$624.2A$624.2A$
550.2A$549.A2.A$536.A15.A$536.3A13.A66.3A7.2A$539.A9.2A.A34.2A30.A2.A
6.2A$538.2A9.2A35.2A30.A3.A$588.A34.A$619.3A.2A$543.A.2A3.2A71.A$541.
3A.3A2.2A66.A3.2A$542.A.A.2A74.A$543.3A$543.3A$615.A.A$615.2A18.F$
616.A18.F$635.F$626.F8.F$582.2A42.F$582.2A42.F$626.F3$587.2A$587.2A$
583.2A$583.2A$624.2A$624.2A$589.2A27.2A$589.2A27.2A3$620.2A$613.2A5.
2A$613.2A24$533.2A$533.A$531.A.A$516.2A13.2A$516.2A3$496.2A$496.2A3$
495.A$494.A.A$495.A$480.2A10.3A$481.2A9.A$480.A3$535.2A$535.2A7$532.
2A$532.A$533.3A$535.A6$503.2A$503.2A2$480.2A$480.2A$502.2A$502.A$460.
2A38.A.A$460.2A38.2A3$459.A$458.A.A$459.A$456.3A$456.A29.2A$485.A.A$
486.A10$496.2A$496.A$497.3A$499.A6$467.2A$467.2A2$444.2A$444.2A$466.
2A$416.2A48.A$417.2A5.2A38.A.A$416.A7.2A38.2A3$423.A$422.A.A$423.A$
420.3A$420.A29.2A$449.A.A$450.A10$460.2A$460.A45.4B$461.3A43.4B$463.A
44.4B$509.4B$510.4B$511.4B$512.4B$513.4B$431.2A$431.2A2$408.2A$408.2A
$430.2A$430.A$388.2A38.A.A$388.2A38.2A3$387.A$386.A.A$387.A$384.3A$
384.A29.2A$413.A.A$414.A10$424.2A43.4B$424.A45.4B$425.3A43.4B$427.A
44.4B$473.4B$474.4B$475.4B$352.2A122.4B$353.2A122.4B$352.A42.2A81.4B$
395.2A82.3B$480.2B$372.2A107.B$372.2A$394.2A$394.A$352.2A38.A.A$352.
2A38.2A3$351.A$350.A.A$351.A$348.3A$348.A29.2A$377.A.A$378.A7$433.B$
433.2B$433.3B$388.2A43.4B$388.A45.4B$389.3A43.4B$391.A44.4B$437.4B$
438.4B$439.4B$440.4B$441.4B$359.2A81.4B$359.2A82.4B$444.4B$336.2A107.
4B$336.2A108.4B$358.2A87.4B$358.A89.4B$316.2A38.A.A90.4B$316.2A38.2A
92.4B$451.4B$452.4B$315.A137.4B$314.A.A137.4B$315.A139.4B$312.3A141.
4B$312.A29.2A113.4B$341.A.A114.4B$342.A116.4B$460.4B$461.4B2$394.B$
394.2B$394.3B$394.4B$395.4B$288.2A106.4B$289.2A61.2A43.4B$288.A63.A
45.4B$353.3A43.4B$355.A44.4B$401.4B$402.4B$403.4B$404.4B$405.4B$323.
2A81.4B$323.2A82.4B$408.4B$300.2A107.4B$300.2A108.4B$322.2A87.4B$322.
A89.4B$280.2A38.A.A90.4B$280.2A38.2A92.4B$415.4B$416.4B$279.A137.4B$
278.A.A137.4B$279.A139.4B$276.3A141.4B$276.A29.2A113.4B$305.A.A114.4B
$306.A116.4B$424.4B$425.4B$426.4B$427.4B6$316.2A43.4B$316.A45.4B$317.
3A43.4B$319.A44.4B$365.4B$366.4B$367.4B$368.4B$369.4B$287.2A81.4B$
287.2A82.4B$372.4B$264.2A107.4B$264.2A108.4B$286.2A87.4B$286.A89.4B$
244.2A38.A.A90.4B$244.2A38.2A92.4B$379.4B$380.4B$243.A137.4B$242.A.A
137.4B$243.A139.4B$240.3A141.4B$240.A29.2A113.4B$269.A.A114.4B$270.A
116.4B$224.2A162.4B$225.2A162.4B$224.A165.4B$391.4B$392.4B$393.4B$
394.4B$395.4B$396.4B$280.2A115.4B$280.A117.4B$281.3A43.4B68.4B$283.A
44.4B$329.4B$330.4B$331.4B$332.4B$333.4B$251.2A81.4B$251.2A82.4B$336.
4B$228.2A107.4B$228.2A108.4B$250.2A87.4B$250.A89.4B$208.2A38.A.A90.4B
$208.2A38.2A92.4B$343.4B$344.4B$207.A137.4B$206.A.A137.4B$207.A139.4B
$204.3A141.4B$204.A29.2A113.4B$233.A.A114.4B$234.A116.4B$352.4B$353.
4B$354.4B$355.4B$356.4B$357.4B$358.4B$359.4B$360.4B$244.2A43.4B68.4B$
244.A45.4B68.4B$245.3A43.4B68.4B$247.A44.4B68.4B$293.4B68.4B$294.4B
68.4B$295.4B68.4B$296.4B68.4B$297.4B68.4B$215.2A81.4B68.4B$215.2A82.
4B68.4B$191.A108.4B68.4B$187.2A2.2A.3A104.4B68.4B$187.2A4.4A105.4B68.
4B$191.2A110.4B$146.2A156.4B$139.2A5.2A157.4B$79.2A58.2A165.4B$78.B2A
2B113.A110.4B$65.A13.2A2B77.2A33.A.A110.4B$65.3A11.BA2B58.2A18.2A7.2A
22.A2.A111.4B$68.A9.BABA59.2A17.A9.2A23.2A113.4B$67.2A9.2ABA53.2A174.
4B$77.4B54.2A175.4B$72.A4.4B95.2A13.2A120.4B$71.A.A3.2B2AB94.2A12.A.A
121.4B$71.A2.A4.2A91.2A16.A124.4B$72.2A98.2A15.2A125.4B$317.4B$318.4B
$319.4B$177.2A141.4B$134.2A41.2A142.4B$135.A186.4B$135.A.A185.4B$136.
2A186.4B$325.4B$326.4B$327.4B$328.4B$216.2A42.B68.4B$209.2A4.A2.A41.
2B68.4B$209.A2.A3.A.A41.3B68.4B$217.A42.4B68.4B$171.2A36.A2.A48.4B68.
4B$171.A36.A2.A9.2A39.4B68.4B$130.2A40.3A33.A.A10.A41.4B68.4B$130.2A
19.A22.A34.A12.3A39.4B68.4B$150.2A72.A40.4B68.4B$150.A.A56.2A55.4B68.
4B$209.2A56.4B68.4B$135.2A23.3A105.4B68.4B$135.2A20.A.A.A.A105.4B68.
4B$131.2A23.2A.A3.A106.4B68.4B$131.2A24.A.A2.2A107.4B68.4B$155.A5.A
10.2A98.4B68.4B$155.2A.A2.A10.2A99.4B$137.2A18.2A.A5.2A106.4B$137.2A
27.2A107.4B$276.4B$277.4B$168.2A108.4B$161.2A5.2A109.4B$142.2A17.2A
117.4B$143.A137.4B$140.3A139.4B$140.A142.4B$284.4B$285.4B$286.4B$287.
4B$288.4B$289.4B$290.4B$291.4B$292.4B$293.4B$294.4B$295.4B$.ABA292.4B
$.3BAB2.B288.4B$A4BA2B2A288.4B$2ABA2BAB2A289.4B$.B2.2A3B291.4B$6.3B
292.4B$302.4B$303.4B$9.A294.4B$8.A.A294.4B$7.A2.A295.4B$8.2A297.4B$
308.4B$309.4B$4.2A304.4B$3.A.A$3.A$2.2A19$102.4A$101.A7.2A$101.A3.2A
2.2A$102.A2.2A2$162.2A$161.A2.A4.2A$110.A50.A.A3.A2.A$109.A.A50.A$
108.A2.A55.A2.A$109.2A46.2A9.A2.A$158.A10.A.A$155.3A12.A$105.2A48.A$
104.A.A62.2A$104.A64.2A$103.2A32$153.A$152.2A$152.A.A!
#C [[ THEME Blues ]]

Compared to the amount of time between successive bits coming in from the RCT mechanism, 35,000 ticks is practically instantaneous. This is a case where the simplicity of the mechanism is paramount (because we're trying to minimize the total number of bits that have to be stored in the RCT mechanism). The length of time that the mechanism takes to recover doesn't matter at all, compared to how much it costs to build it -- and Paul Callahan's bistable switch is made out of just a few Spartan still lifes, and is very cheap to construct.

What Comes Next

Current RCT plans call for a second optional bootstrap stage, further improving the encoding efficiency of the system. The ECCA (Extreme Compression Construction Arm) uses 4-bit and 7-bit codons instead of 9-bit codons, and will be constructed with its own integrated self-destruct circuitry. As described in the next post, the ECCA will be responsible for several cleanup tasks, as well as for building the ATBC -- the Actual Thing Being Constructed, which we should be careful not to lose sight of because it's really supposed to be the whole point of this RCT exercise.

24 April 2022

Current RCT Technology, Part 1 (Build Anything Constructible, Now With Just 16 Gliders)

... This is an ambitious title in a couple of ways, but I'll try to keep this post up to date as new developments inevitably come along. The most recent update was 28 April 2022.

The Reverse Caber Tosser (RCT)

The idea of fixed-cost glider construction recipes got its start in 2015, when Gustavo Rehermann inspired the idea of encoding recipes for large patterns using vast distances between a small number of gliders. Actual prototype patterns started showing up in 2018. Rather than directly colliding large number of gliders to build a large structure, these "RCT" patterns essentially measure the distance between two structures, convert those measurements into a very long universal construction arm recipe of a type that we already know about -- and then use that recipe to incrementally build the large structure.

The RCT construction method produces recipes with a very small initial population, only 80 cells... at the cost of an unimaginably enormous bounding box, and a similarly huge number of ticks needed to complete the construction.

The first estimates (by Chris Cain) of cost in gliders for a fixed-cost construction system were somewhere in the high three-digit or low four-digit range. This was then reduced to a surprisingly small 329 gliders, and then gradually over the next several years to a series of ever smaller and more surprising numbers. We're currently at a fixed cost of 16 gliders to build any glider-constructible pattern, no matter how large -- and there's still no guarantee that 16 is the minimum.

Some Terminology To Start Out

We'll need a few key terms from this source, for this post and future posts in the series:

epicentre: the area of interest where all of the gliders collide
parsec: the distance between the construction site of the southeastern GPSE and the epicentre
aeon: the time it takes for a lightspeed diagonal signal to traverse a parsec
singularity: the moment when all construction bits have been read
BS: Before Singularity
AS: After Singularity
GPSE: glider-producing switch engine
BRG: Bit-Reading Glider -- see below.
DBCA: Decoder and Better Construction Arm, an optimization stage described in the next post BSRD: Bit Storage and Retrieval Device, a method of delaying construction to simplify some cleanup problems, described in a future post ATBC: the Actual Thing Being Constructed -- the RCT's target object. The goal is to eventually turn 16 gliders into this object, with nothing else left in the infinite Life universe.

How RCT Works, From the Beginning

A template RCT pattern that's easy to zoom in on and watch, in Golly if not in LifeViewer, can be found in this forum post. It's slightly out of date, in that it contains 17 gliders rather than 16. I will probably add an embedded LifeViewer copy here once we have a 16G version of the template available, but all the main ideas are the same.

1) In the southwest corner of any RCT pattern, 7 gliders crash to produce a pair of GPSEs (glider-producing switch engines) that produce a specific two-glider salvo of gliders heading northeast. Until recently this construction needed 8 gliders, so this is the improvement that reduced the minimum fixed cost from 17 to 16.

2) A very long way north, in the northwest corner, four more gliders collide to make another GPSE. We can't use just three gliders; there are known 3G GPSE recipes, but they create a lot of uncontrolled gliders flying off in different directions.

3) Much later, four more gliders collide, southeast of the epicentre. The long delay here ultimately reduces the cost of the RCT: a potentially very long series of gliders being reflected back from the northwest GPSE would normally need an extra glider to handle, e.g., by setting up a crystal to absorb them. With the extra delay, these gliders can instead be harmlessly caught by an eater built by the construction arm (see below).

4) All glider streams meet at the epicentre with specific timing, so that one glider escapes southeastward, and then all four gliders mutually annihilate each other, repeatedly building and destroying a temporary blinker. Let's call that one key escaped glider the "Bit-Reading Glider".

5) Bit-Reading Gliders always travel southeast from the four-stream collision point, to the GPSE whose position encodes the RCT recipe. The return signal after a Bit-Reading Glider reaches its destination may be a glider, or it may be a "hole" -- a glider missing from the standard northwest-traveling GPSE glider stream.

6) Every time a signal bounces back and forth, it allows either one or two gliders to escape past the blocking blinker to strike the central target -- depending on which phase of the GPSE is encountered by each of the Bit-Reading Gliders (BRGs).

How the Math Works

Each new return signal arrives twice as quickly as the previous one. The entire system is designed to retrieve a series of bits from the large distance between the epicentre and the southeast GPSE, in an operation that amounts to repeatedly dividing the distance by two and taking the remainder. See the next section for the specific mechanisms.

If a period-256 stream of gliders could be arranged to bounce off of an approaching c/12 Cordership, the returning glider stream would be period 128 instead of period 256, due to the Doppler effect. Something similar is happening here, but in the 17G and 16G RCT designs, the p256 glider stream is very very intermittent. An occasional BRG manages to escape, but all the rest of the gliders in that southeast-traveling p256 stream are suppressed at the epicentre.

Each BRG may reach the approaching GPSE at either time 0 (mod 256) or 128 (mod 256) -- and the gliders colliding at the epicentre are very carefully arranged to do something different with the results of those two possible BRG + GPSE collisions. Each time the distance from the epicentre to that southeast GPSE is divided by two, there's another free choice of possible original starting positions for the GPSE -- one producing the 0 (mod 256) collision, and one producing the 128 (mod 256) collision.

Something To Try Out In Golly

For a bigger and more functional example, download the "shillelagh_final_cropped.mc" pattern here and open it in Golly.

At around T=2500 in this cropped pattern, a Bit-Reading Glider is approaching the southeast GPSE for the first time. The BRG is circled in the northwest corner of this snapshot:

Code: Select all
x = 221, y = 174, rule = B3/S23
3bobo$bo5bo2$o2bobo2bo$4b2o$o3bo3bo2$bo5bo$3bobo50$53bo$52b2o$52bobo4$
132b3o$131bo$130bo4b2o$129bo3bo15b3o$129bo2bo4bo4b2o$129bo3bo3bo4b3obo
$130b2obob3o$133bo$134b4o20b2o$136b2o11bob2o5b2o$149bo2bo$149b3o5$166b
2o$166b2o2$153b3o$138b2o13bo$138b2o14bo3$158b3o$159b2o2$173b2o$146b2o
9b3o13bobo$146b2o11bo14bo$165b2o$156bob2o5b2o$151bo7bo$150b3o6bo$149b
2obo3b2obo$150bobo3b3o$150b3o3bo$151b2o3$190b2o$190b2o13b2o$204bo2bo$
205b2o$179bo$178bobo$165bo12b2o$164bobo$164b2o$208bo$208bo2bo6b2o$208b
o3bo5b2o$174bo34bo2bo5bo$173bobo37bo$173b2o36b2ob2ob2o$213bo3$117bo$
116b2o$116bobo2$209bo$209bo$211b2o$174b2o30b3ob2obo$173bo2bo29b2o2b2ob
obo$174b2o30b3o3b3o$208b4o$170b3o36b3o$210bo$174bo$174bo$174bo2$176b2o
$176b2o2$197bo$196bobo$196b2o4$206bo$205bobo$205b2o2$168b2o$168b2o7$
164b2o$164b2o40b2o$205bo2bo$206b2o2$202b3o2$206bo$206bo$206bo$174b2o$
173bobo32b2o$173b2o33b2o$218b3o!
#C [[ THEME Blues ]]

Run the above for about a thousand ticks to see the returning "1" signal glider being generated, to head northwest parallel to the regular GPSE glider stream.

At around T=13800 in the "shillelagh_final_cropped.mc" pattern (not in the above snapshot of it!), you'll see this in the center:

Code: Select all
x = 175, y = 163, rule = B3/S23
21bobo$22b2o$22bo62$85bobo$86b2o$86bo4$84b3o3$81bo$81b2o$80bobo16$73bo
bo$71bo5bo$109bo$70bo3bo3bo29b2o$73b2o33bobo$64b2o4bo2bobo2bo$65b2o$
64bo6bo5bo$73bobo38$17bo$17b2o$16bobo18$173bo$172b2o$172bobo$2o$b2o$o!
#C [[ THEME Blues ]]

Here I've circled the returning "1" signal from the Bit-Reading Glider. This is the same northwest-traveling glider that we saw being created in the previous snapshot.

The collision releases a single construction-arm glider headed northeast, and a new Bit-Reading Glider heads southeast. There's also an extra glider heading northwest, but these are absorbed harmlessly by the ash of the incoming GPSE, and that ash will get cleaned up later. In one possible phase of the collision a glider is created heading back towards the epicentre, but we've already talked about how an eater will be constructed to catch those.

At around T=24550 there's another central collision, resulting in another singleton glider heading northeast.

At around T=29900 another central collision, another singleton glider -- the bouncing glider gets back twice as quickly for each new collision.

At around T=30800, the next Bit-Reading Glider is approaching the GPSE in the southeast:

Code: Select all
x = 189, y = 139, rule = B3/S23
3bobo$bo5bo2$o2bobo2bo$4b2o$o3bo3bo2$bo5bo$3bobo31$110b2obo$109b3obo6b
obo$108bo4bobo4bo$109b2o6bobo3bo$110bo3bo2bo2b2o$113bob2o3bo$112bobo
16b2o$112bobo16b2o6$47bo$46b2o$46bobo$117bo10b2o$112bo3b5o5bo2b3o$111b
obo7b2ob3ob2ob2o$111bo7bob2o2bo2bobob2o$112bo8b2o3b2obo2bo$113bo3b4o6b
3obo$118b3o8b2o$125b2o11bo$125b2o7bo2bo$134bo2bo$119b2o12bo$119b2o12b
2o$133b2o2$155b2o$131b3o21b2o$131bo2b2o$132b3o$133bo10bo$143bobo$143b
2o$135b2o$134bo2bo$134b5o31bo$135b3o31b3o$159b2o8b2obo4bo$139bo18bo3bo
6b3ob6o$138bobo17bo5bo3b4o2b2o2b2o$138b2o18b2o4bo3bob2obo2bo2b2o$153b
2o6bo3b2o4b2ob4obo$153b2o6b4o7b3ob2obo$164b3o$164b2o$165bobo$164bo2bo$
165bob2o4bo$167b2obo3b2o$162b3o3bobo2b2o$164bo$139b2o22bo$138bo2bo$
139b2o2$135b3o2$139bo$139bo47b2o$139bo47b2o2$141b2o$141b2o33bo$175bobo
$162bo12b2o$161bobo$161b2o4$171bo$170bobo$170b2o$111bo$110b2o21b2o$
110bobo20b2o2$129bo$128bo$127b2o$123b3o3bo$122bo6b2o$120b3o$119bo2bob
2o2b2o41b2o$119b4ob5o41bo2bo$121b8o21bo20b2o$123b4o22b3o$148bo18b3o$
149b2o$171bo$171bo$171bo$139b2o$138bobo32b2o$138b2o33b2o$183b3o!
#C [[ THEME Blues ]]

This time, though, thanks to the magic of Dividing By Two And Checking The Remainder, the mod-256 timing of the collision is clearly very different! It's offset by 128 ticks from what we've seen before. Instead of hitting a block and making an extra offset glider, here the Bit-Reading Glider strikes an active part of the GPSE glider-generating reaction, and no return glider is released at all for one cycle -- no extra offset glider, and no glider in the GPSE stream either.

Side note: If you're paying close attention here, when you run the above snapshot you'll see a worrisome detail: an extra glider gets generated that heads off to the southeast! It turns out that this glider gets absorbed by the ash of the next Bit-Reading Glider collision to the southeast, without generating any new gliders. The resulting variation in BRG collision ash is still a concern, because it complicates the problem of cleaning up all that ash -- but we'll deal with that in future episodes!

At around T=32750 another central collision is about to happen:

Code: Select all
x = 181, y = 169, rule = B3/S23
21bobo$22b2o$22bo62$85bobo$86b2o$86bo7$87b3o6$81bo$81b2o$80bobo15$114b
obo$112bo5bo2$111bo7bo2$111bo7bo$64b2o$65b2o45bo5bo$64bo49bobo39$17bo$
17b2o$16bobo18$179bo$178b2o$178bobo$2o$b2o$o!
#C [[ THEME Blues ]]

In the snapshot above I've circled the location where that suppressed glider would ordinarily be in the standard GPSE stream.  The result of that missing glider is that two construction-arm gliders will be released toward the target in the northeast, instead of just one. Run the pattern and watch it happen. This is all a very tricky and clever series of interactions, originally invented by MathAndCode (Daniel Vargas) and proved out by Adam P. Goucher in late 2020.

Universality Achieved

The above patterns show the binary choice of one glider versus two gliders, that turns out to give us just enough control to create slow salvos of gliders that can build any glider-constructible object.  See this forum post for an actual example of the full 17-glider macrocell pattern, openable in Golly, that constructs a small example object, a shillelagh -- but leaves a lot of ash to clean up (to put things very mildly).  Forum posts following that post document a way of reducing the initial population of an RCT pattern to 16 gliders.

The final fate of that shillelagh-making macrocell pattern's central area is the shillelagh_final_cropped.mc pattern that we were looking at above.  The two-glider output is the last bit that can be retrieved by the Bit-Reading Glider. After that point the GPSEs all reach the epicentre, crash into the construction area, and make a big mess. That big mess is obviously no good: for this RCT trick to work, we really want to end up with just a our intended object, and nothing else. What we're getting instead is, in this case, a shillelagh at the center of several incredibly long trails of GPSE ash. Blog posts yet to come will describe the details of the cleanup process for those ash trails.

See, It Actually Works

4)The "binary slow salvo" described above (a free choice at each point of either a single glider, or two gliders) is known to be capable of very slowly generating new target objects at a safe distance from the construction lanes, and also clean 90-degree gliders on any lane we choose, aimed at those targets. We know from previous experience that this is sufficient for universal construction.

In this forum post by Adam P. Goucher is a demonstration of the 1-glider and 2-glider operations being sent in a very precisely chosen order to one of these construction arms, to build the shillelagh from the example macrocell pattern. The demo skips the part about encoding the recipe in a ridiculously large 16-glider macrocell pattern, and instead just sends the recipe gliders one after another (so there are a lot more than sixteen of them).

I may add a version of the demo pattern here as a LifeViewer animation eventually. In the meantime, the demo is still far too large to fit in LifeViewer without PASTET scripting commands. However, it will run very quickly if loaded into Golly and run with a high step size.

This Is Where It Starts To Get Complicated (!)

The next post will talk more about about the DBCA -- "Decoder and Better Construction Arm" -- which is an optional stage of the RCT that allows us to build much more complex objects with the same number of bits encoded in the RCT distance. That is to say, with roughly the same sized parsec (to use the terminology from the top of this post) you can produce a much more complex final pattern if you include something like a DBCA stage. In fact, for a very wide range of parsec sizes, the DBCA will be the only thing that makes it possible to build any recognizable object at all, as opposed to just creating a truly humongous quantity of repetitive junk plus a (relatively) tiny constructed object at the RCT epicentre.

The third post will briefly describe the rationale behind a second optional bootstrap stage, the ECCA -- "Extreme Compression Construction Arm". This stage really only improves the efficiency of construction data storage by a relatively minor percentage, but it turns out that it's worth building it anyway because it's very useful to have a construction arm pointing in a different direction.

The fourth and final post will walk through current plans for completely cleaning up all of that repetitive junk, leaving only the constructed ATBC object behind. Again, ATBC just means the Actual Thing Being Constructed -- the shillelagh, or whatever object the main construction recipe codes for, up to and including a pi-calculator pattern or a fleet of a million Gemini spaceships.