Build Anything Constructible with a Fixed Number of Gliders

[dvgrn]

Just a quick new topic -- simsim314 mentioned this unfinished project in the Pattern of the Year thread today. It was a topic that came up tangentially in the Searching algorithms thread in 2015, and hasn't been seen since. It's an awesome idea so I wouldn't want it to get lost permanently.

Briefly, there's a way to use a relatively small piece of decoder circuitry to retrieve any finite amount of information in the position of a single block. The information in question is a series of PUSH, PULL and FIRE instructions for a construction arm.

We can prove that monochromatic monoparity slow salvos can construct any glider-constructible object. So just like that, we've achieved construction universality -- at least, unless an additional constraint is added about constructions having to be finished in a reasonable amount of time...!

After some discussion in August 2015, chris_c posted a completed decoder/constructor:

I did eventually optimise by removing some guns and using cheaper p690 technology. This new pattern is probably glider constructible in around 1,000 gliders. Note that the operations have been swapped so that now we have PUSH = 0, PULL = 1 and FIRE = 2.

Code: Select all

x = 1235, y = 944, rule = B3/S23
303b2o$302bo2bo$305bo$305bo$303bobo$303bobo$304bo3$301b2o3b2o$301bo5bo
2$302bo3bo$291b2o10b3o$289bo3bo$288bo5bo$283b2o2b2obo3bo$283b2o3bo5bo$
289bo3bo$291b2o4$298b2o$297bobo$296b3o6bo$296b2ob3ob2ob2o$297b5ob2ob2o
28bo$299bo5bo29bobo$300b2ob2o2$335b3o$335b3o$299bo5bo30bo$298b2o5b2o$
297bob2o3b2obo$297bob2o3b2obo28bo$298b3o3b3o28b3o$298b3o3b3o28b3o3$
335bobo$336bo5$321b2o302b2o$321bo2bo300b2o$313b5o7bo$298b2o12bo5bo6bo$
298b2o12bo3b2o7bo$313bo7bo2bo$321b2o29b2o$353bo$353bobo7bo$332b3o19b2o
5bobo$331bo3bo23b2o12b2o$330bo5bo22b2o12b2o$330bo5bo22b2o$333bo27bobo$
331bo3bo27bo25bo$332b3o53b3o4b2o$333bo53bo3bo3b2o$387b2ob2o$387b2ob2o$
333b2o$333b2o52b2ob2o$387b2ob2o$387bo3bo$388b3o$389bo7$388bo7bo$387b4o
3b4o$387bo3bobo3bo$388bo2bobo2bo$388b3o3b3o2$688b2o$689bo$402bo286bobo
9bo$400b5o10bo274b2o9bobo$399bo2bob2o9b2o285bobo4b2o$398bo7bo9b2o284bo
2bo3b2o$399bo2bob2o5b2o2b2o285bobo$400b5o296bobo$402bo298bo2$411b2o2b
2o$398b2o16b2o7b2o$398b2o15b2o8b2o$415bo$302bo2bob2obo2bo$301b2o2bo4bo
2b2o12bo$302bo2bob2obo2bo12bobo$324b2o3bo9b2o$324b2o3bo9b2o$324b2o3bo$
326bobo$323bo3bo$322bobo$322bobo$323bo3$320b2obob2o$320bo5bo$321bo3bo$
322b3o8$323b2o$323b2o5$284b2o11b3ob3o9b2o$283bobo10bob2ob2obo7b2ob2o$
282bo6b2o4b2o7b2o7bo2bo$273b2o7bo2bo2bo2bo4bob2ob2obo8bo2bo$273b2o7bo
6b2o6b3ob3o10b2o$283bobo$284b2o28b2o$313bo2bo$288b3o5b2o15bo2bo6b2o$
288b3o5b2o14b2ob2o6b2o$287bo3bo21b2o$286bo5bo$287bo3bo$288b3o6$556bo$
554b3o$553bo49bo$552bobo48b3o$289b2o262bo52bo$289b2o314b2o$309b2o3bo2b
o3b2o295bo18bo5b2o12bo$309b5o4b5o12bo215b2o63b3o18b3o3b2o10b3o$309b2o
3bo2bo3b2o10b4o214b2o62bo24bo13bo$332bobob2o9b2o266b2o22b2o13b2o$331bo
2bob3o8b2o102bo$332bobob2o114bo109b2o$332b5o113b3o110bo25bo11b2o$331bo
3bo227bobo21b3o11b2o25b2o$330bobo126bo104b2o20bo41bo7b2o$330bobo124bob
o126b2o38bobo8bo$331bo126b2o166b2o9bobo$638b2o$463bo$328b2o3b2o129bo
94bo$328bobobobo127b3o92b3o$329b5o222bo$330b3o223b2o38b2o$331bo264b2o
26b2o$624b2o43b2o$458b2o209bo$458b2o210b3o$672bo2$565b2o32b2o38b2o$
331b2o232b2o11b2o20bo39bo$331b2o125b3o117bo18b3o37b3o$458b3o118b3o15bo
39bo$457bo3bo119bo65b2o$531b2o114b2o$306bo3bo145b2o3b2o68b2o20b2o6b2o$
292b2o11bobobobo8b4o229bo7bo$291bobo9b2o2bobo2b2o6bo2b2o229b3o5b3o$
290b3o4b2o4b2o7b2o7bo2b2o191b2o37bo7bo$281b2o6b3o4bo2bo3b2o2bobo2b2o7b
o2bo192b2o$281b2o7b3o4b2o6bobobobo10b2o$291bobo12bo3bo$292b2o28b2o221b
2o$297bo23bo2bo126bo93b2o3b2o107b2o$296bobo5b2o15bo2b2o5b2o116b4o45b2o
50b2o101b2o4b2o$295bo3bo4b2o14bo2b2o6b2o110b2o3bobob2o44b2o153b2o$295b
5o20b4o119b2o2bo2bob3o$294b2o3b2o147bobob2o97b2o$295b5o149b4o92b2o4bo$
296b3o152bo93b2o5b3o99b2o$297bo256bo99b2o2b2o$658bobo$534b2o110b2o12bo
$534bobo109bobo11b2o$536bo111bo$536b2o110b2o3$512bo$297b2o212bobo$297b
2o212b2o133b2o$646bobo$528b2o118bo$528bo58bo60b2o$529b3o55b3o$531bo58b
o$525b2o62b2o$519b2o4bo58bo$519b2o5b3o53b3o$528bo52bo$581b2o55b2o$571b
2o56b2o7b2o$572bo57bo$572bobo55bobo$573b2o4b2o44b2o4b2o$578bo2bo44bo
20b2o$579b2o45bobo18bo$591b2o34b2o16bobo$591b2o52b2o8$577b2o3b2o32b2o$
578bo3bo20b2o11b2o$575b3o5b3o18bo$575bo9bo15b3o35b2o$601bo37b2o2b2o$
643bobo$645bo$645b2o8$464b2o$434b2o28bobo$433bobo28bo$435bo5$436b3o$
438bo$437bo4$415b3o$417bo2b2o$416bo4b2o$402b2o16bo$403b2o$402bo32$457b
2o$457b2o7$456b3o$455bo3bo$548bo$454bo5bo85b5o10bo21b2o$454b2o3b2o84bo
2bob2o9b2o20bo2bo$544bo7bo9b2o14b2o7bo$447bo97bo2bob2o5b2o2b2o14bo2bo
6bo6b2o$444b4o98b5o27b2o7bo6b2o$422b2o12b2o5b4o101bo34bo2bo$422b2o12b
2o5bo2bo136b2o$443b4o4b2o2b2o100b2o2b2o16bo$444b4o5bo90b2o16b2o7b2o5b
3o$447bo96b2o15b2o8b2o4bo3bo$458bo102bo17bo$422b3o3b3o27bo117bo5bo$
422bo2bobo2bo27bo117bo5bo$421bo3bobo3bo145bo3bo$422bo2bobo2bo147b3o$
424bo3bo$422b2o5b2o19b2o$421b3o5b3o17bobo8bo$421b3o5b3o19bo7bobo65bo$
458bo3bo54b2o6bo2bo25bo$458bo3bo52bob3o5b5o24bobo$458bo3bo50b3o4bo4b3o
b2o16b2o8b2o$458bo3bo52bob3o6b2obo20bo6b2o4b2o$428b3o27bo3bo54b2o8b2o
18bo9b2o4b2o13b2o$428b3o27bo3bo88bo2bobo21b2o$427b5o27bobo65b2o22bo2bo
$426b2o3b2o27bo65b2obo$426b2o3b2o80b2o10b3ob2o9b2o7b2o$465b2o46b2o10b
5o10b2o6bo$464bobo58bo2bo$466bo60bo$426b2o3b2o112b2o3b2o$422b2o2b2o3b
2o112b2o3b2o$422b2o3b5o114b5o$428b3o116bobo$428b3o$547b3o$418b2o$416bo
2bo7b2o$407b2o6bo7b2o4bo$407b2o6bo6bo6bo$415bo7b6o$416bo2bo127b2o$418b
2o127b2o2$425b2o3b2o$426b5o$221b2o203b2ob2o$221b2o203b2ob2o$427b3o$
325bo$325b2o$310b3o11bobo$312bo$220b3o88bo$427b2o$220bobo204b2o$219b5o
$218b2o3b2o$218b2o3b2o2$243b2o3bo$221bo6b2o13b3obob2o4b2o149b2o$219b2o
7b2o13b3o4bo4b2o147bo2bo$246bo3bo$215bo2bo28b3o153bo$213bobo2bo10b2o3b
2o$205b2o4b2o9bo5b3o3b3o10b3o154b2o$205b2o4b2o6bo6b3o7b3o7bo3bo155bo$
211b2o8b2o3b3o7b3o4b3o4bo$213bobo10b3o7b3o4b3obob2o$215bo12b3o3b3o6b2o
3bo154b2o3b2o$229b2o3b2o167b2o3b2o$404b5o$405bobo2$396bo8b3o$396bobo$
371b2o12b2o12b2o$371b2o12b2o12b2o$399b2o$396bobo$396bo8$171b2o235b3o$
171b2o234bo3bo$371b2o5b2o26bo5bo$370bo2bo3bo2bo$373b2ob2o27bo7bo$372bo
bobobo26bo7bo$372bobobobo806b2o$370bo9bo25bo5bo772b2o$369bo11bo25bo3bo
$408b3o$171bo201b2ob2o$170b3o198bo2bobo2bo805b3o$169b5o197b3o3b3o805b
3o$168b2o3b2o1009bo3bo$169b5o1009bo5bo$169bo3bo4b6o5b4o12b2o164b2o811b
o3bo$170bobo5b4o7b2obo12b2o164b2o812b3o$171bo9b2obo7bo$166b2o15b2o5b2o
$165bobo127b4o866bo$155b2o7b3o4b2o10b2o5b2o87b2o14bo2b2o6b2o57b2o797bo
2bo$155b2o6b3o4bo2bo7b2obo7bo86b2o15bo2b2o5b2o57b3o783b2o10b5o10b2o$
164b3o4b2o8bo7b2obo68b3o3bo28bo2bo56b2o9b2obo780b2o9b2ob3o10b2o$165bob
o13b3o5b4o70bo4bo28b2o57bo5bo4bo2bo792bob2o$166b2o94bo3b3o12bo3bo75bo
5b2obo5b3o785b2o26b2o$280bobobobo10b2o58bo3bo3b3o8b3o812bobo$278b2o2bo
bo2b2o7bo2bo59bo5b2o8bo3bo784b2o8b2o14bo6b2o2b2o$278b2o7b2o7bo2b2o862b
ob2o6b3obo12bo2bo2bo2bob2o$278b2o2bobo2b2o6bo2b2o74b2o3b2o781b2ob3o4bo
4b3o10bo6b2o$280bobobobo8b4o864b5o5b3obo13bobo$281bo3bo878bo2bo6b2o16b
2o$1165bo$269b3o3b3o$269bo2bobo2bo$243b2o23bo3bobo3bo$242bobo3bo20bo2b
obo2bo$244bo3b2o21bo3bo$230bo16bobo19b2o5b2o$230b2o36b3o5b3o97b2o$229b
obo36b3o5b3o97b2o5$269b3o$269b3o931b2o$268b5o930b2o$267b2o3b2o$267b2o
3b2o2$1204bo$1203b3o$267b2o3b2o928bo3bo$267b2o3b2o2b2o923bob3obo$268b
5o3b2o924b5o$269b3o$269b3o2$1183b2o$1182bo$1169b2o10bo2b2o10b2o$1169b
2o10bo2bo11b2o$236b3o3bo938bobo$229b2o3b5o2bobo12b2o924b2o27bo$229b2o
2b2o3b2o3bo12b2o952b2o$234b2o3bo2bo939b2o9b2o14b2o4b2o2b2o$235bo3b3o
939bobo7b2o3bo11b3o4b2o2b2o$1181bo2bo6bo4bo12b2o4b2o$235bo3b3o939bo2b
2o5b2o3bo13b2o$234b2o3bo2bo939bo10b2o16bo$233b2o3b2o3bo939b2o$234b5o2b
obo$236b3o3bo7$89b2o$89b2o3$219b3o3b3o$219bo2bobo2bo989b2o$219b2obobob
2o989b2o$219b2o5b2o3$89bo1127b3o$88b3o1126b3o$87b5o129b2ob2o990bo3bo$
86b2o3b2o126bo2bobo2bo987bo5bo$87b5o20b4o103bobo3bobo988bo3bo$87bo3bo
4b2o14bo2b2o6b2o94b3o3b3o989b3o$88bobo5b2o15bo2b2o5b2o101b2o$89bo23bo
2bo109b2o$84b2o28b2o110b2o$83bobo12bo3bo1090b2o$73b2o7b3o4b2o6bobobobo
10b2o1067b2o7bobo15b2o$73b2o6b3o4bo2bo3b2o2bobo2b2o7bo2bo1066b2o6b2obo
15b2o$82b3o4b2o4b2o7b2o7bo2b2o1074b2o$83bobo9b2o2bobo2b2o6bo2b2o1076bo
30b2o$84b2o11bobobobo8b4o993bo113bobo$98bo3bo1004b2o84bo10b2o3b2o11bo
6b2o2b2o$1108b2o82b2o9bob2ob2obo10bo2bo2bo2bob2o$1191b2obo8bo7bo10bo6b
2o$1192bobo8bob2ob2obo11bobo$1193b2o9b2o3b2o13b2o$57b2o$57b2o4$55b2o
1150bobo$232b2o973b2o$232b2o974bo$189b2o333b2o$189bo334b2o$54b2o3b2o
126bobo22bo$55b5o127b2o22b2o$55b2ob2o137b2o11b3obo9b2o298bo$55b2ob2o
137b2o10b2o13b2o297b3o$56b3o151b2o310bo3bo$64b2o12b2o2bo4b2o2b2o73b2o
43bo312bo$64b2o12bob2o6b2ob2o73b2o353bo5bo$79bo6bobo122bo10bo256b2o40b
o5bo$54bo24b3o4b2o122b2o8b2obo254bo2bo40bo3bo$53bobo153b2o8b2ob3o256bo
41b3o$41b2o10b2obo22b3o4b2o122b3obo5bo2bo257bo$41b2o10b2ob2o21bo6bobo
122b2o8b2o256bobo$53b2obo21bob2o6b2o122bo266bobo61bo3bo$53bobo22b2o2bo
4b2o391bo50b2o9bo5bo9b2o$54bo476b2o9bo15b2o$138b2o402b2o3bo$137bobo
337b2o3b2o33b2o25b3o$139bo55b2o280bo5bo25bo7bo2bo$195bo312bo3b2o7bo22b
3o6bob2o$196b3o279bo3bo25bo5bo6bo20b2o3bo5bobobo$176b2o20bo268b2o10b3o
27b5o7bo20bo9bo4bo$176b2o287bo3bo47bo2bo5bobo13bo5bo4bobobo$69bo394bo
5bo46b2o8b2o14bo3bo5bob2o$70b2o387b2o2b2obo3bo56bo598bo$69b2o388b2o3bo
5bo655bobo$465bo3bo12bo643b2o$16b2o449b2o14b2o$16b2o126bo337b2o$142bob
o$140b2o12b2o$140b2o12b2o318b2o$140b2o332b2o$16bo118b2o5bobo$16bo117bo
bo7bo$15bobo116bo$14b2ob2o114b2o$13bo5bo$16bo$13b2o3b2o2$29bob2o156bob
o3bobo$15bo7b2o3bo2b2o2b3o12b2o106bo17b2o2bobo8bo3bo278b3o3b3o$15bo7b
2o3bo6b2o13b2o106bobo14b3obo3bo3bo11bo273bo2bo3bo2bo$14bo13b2o3b3o123b
obo12b2o6bo3bo3bo5bo3bo276bobo$9bo20bo3bo111b2o11bo2bo12bob5o5bo11bo
277bobo$7bobo34bo5bo95b2o11bobo14b3o12bo3bo281bobo$2o4bobo21bo3bo9bo5b
o107bobo28bobo3bobo275bo2bo3bo2bo$2o3bo2bo7b2o10b2o3b3o122bo17b3o295bo
7bo$6bobo19bo6b2o3b2o11b2o120bob5o$7bobo18bo2b2o2b3o131b2o3b2o6bo13b2o
$9bo19bob2o11bo5bo111bo6b2o4b3obo3bo12b2o$44bo5bo111bo13b2o2bobo298bo$
161bobo315b2ob2o$160b2ob2o$159bo5bo313b2ob2o37b2o$108bo53bo316bo3bo38b
o$107bobo49b2o3b2o314b3o39bobo8bo$106bob2o10b2o352b2o47b2o8bobo$105b2o
b2o10b2o352b2o60b2o4b2o$106bob2o51bo374b2o4b2o$101b2o4bobo51bo374b2o$
100bobo5bo51bo372bobo21b2o$100bo432bo23b2o20bo$99b2o476b3o$162b2o412bo
$162b2o412b2o6$601b3o$588b3o8b2obob2o$588bo3bo5bo5b2o$588bo4bo5b2obob
2o$589bo3bo7b3o$547b2o$547b2o40bo3bo$588bo4bo$578b2o8bo3bo12b2o$578b2o
8b3o14b2o$568b2o$568bobo$570bo$570b2o4$520bobo3bobo$485bo21b2o2bobo8bo
3bo$483b4o19b3obo3bo3bo11bo$57b2o12bo410bobob2o17b2o6bo3bo3bo5bo3bo$
58b2o11bobo403b2o2bo2bob3o17bob5o5bo11bo$57bo14bobo4b2o396b2o3bobob2o
19b3o12bo3bo$72bo2bo3b2o402b4o33bobo3bobo$72bobo410bo21b3o$60b2o9bobo
432bob5o$59bobo9bo428b2o3b2o6bo13b2o$59bo440b2o4b3obo3bo12b2o$58b2o
447b2o2bobo2$572b2o$573bo$490b2o3b2o76bobo6bo$574b2o4bobo$491bo3bo83bo
bo11b2o$492b3o83bo2bo11b2o$492b3o84bobo$580bobo$582bo$533b2o$533b2o$
493b2o$493b2o6$533b3o3b3o117b2o$532bo2bo3bo2bo114bo2bo$532b2obo3bob2o$
656bo2$657b2o$16b2o24b3o7b2o605bo$15bobo23bo4bo4bo2bo$14b3o4b2o17bo5bo
4bo2bo$5b2o6b3o4bo2bo17bo8bo3bo601b2o3b2o$5b2o7b3o4b2o19b2o8b2o602b2o
3b2o$15bobo522bo116b5o$16b2o24b2o8b2o484b2ob2o115bobo$21bo19bo8bo487b
2ob2o127b2o$20bobo5b2o10bo5bo8b2o601b3o8bobo$19bo3bo4b2o11bo4bo9bo480b
obobobo124bo6b2o2b2o$19b5o18b3o7bo615bo2bo2bo2bob2o$18b2o3b2o27bo2bo
482b2ob2o125bo6b2o$19b5o509b2o4b3o71b2o54bobo$20b3o510b2o5bo73bo55b2o$
21bo592bobo6bobo$615b2o4bo3bo$621bo12b2o$527b2o91bo4bo8b2o28b2o$527bob
o91bo42b2o$518b3ob2o4b3o90bo3bo$518b4o2bo4b3o91bobo$522b2o4b3o8bo$527b
obo9bo$21b2o504b2o9bobo$21b2o514b2ob2o76bo$536bo5bo76b2o$539bo78b2o$
536b2o3b2o2$566b2o$540bo25b2o60bobo$540bo88b2o26b2o5b2o$541bo87bo27bob
2ob2obo269bobo$658bobobobo270b2o$658bobobobo271bo$538b2o117bo7bo$538b
2o$566b3o3b3o$566bo2bobo2bo$565bo3bobo3bo83b2ob2o$565b4o3b4o81bo2bobo
2bo$566bo7bo82b3o3b3o$658bo5bo371bo$1034b2o$657b2o5b2o369b2o$657b2o5b
2o3$573bo$572b3o$571bo3bo$571b2ob2o$571b2ob2o2$571b2ob2o$571b2ob2o32b
2o$566b2o3bo3bo32b2o$566b2o4b3o$573bo3$560b2o$560bobo46bo$551b3ob2o4b
3o44b3o43bo$551b4o2bo4b3o43b3o41bobo$555b2o4b3o8bo80b2o$560bobo9bo33b
2o3b2o$560b2o9bobo32b2o3b2o$570b2ob2o25bo$569bo5bo23b2o$572bo15b2o8b2o
4b2o3bo344bo$569b2o3b2o12b2o7b3o4b2o2bobo49bobo290bo$598b2o4b2o2bobo
50b2o290b3o$599b2o8bo44bobo4bo$573bo26bo54b2o52b2o$573bo81bo53b2o$574b
o2$603b2o98bo5bo$571b2o30b2o5bo91b3o3b3o$571b2o36b3o90bob2ob2obo$608bo
bobo88b2o7b2o$609bo2bo88b2o7b2o$609b3o89b3o5b3o$610bo92b3ob3o$705bobo$
702bo2bobo2bo$701bo2bo3bo2bo$702b2o5b2o$603bo7bo2$601b3o7b3o$602b2ob2o
b2ob2o29b2o$603b3o3b3o21bo8b2o$604bo5bo21bo5bo6b2o6b2o$632bob2o3bo5b3o
5b2o$633b6o6b2o$634b4o4b2o$642b2o89b2o3b2o$720bo3b2o6b3o3b3o$630b2obob
2o81b2obob3o4b3o7b3o$718bo4b3o4b3o7b3o$630bo5bo81bo3bo7b3o7b3o$719b3o
10b3o3b3o$631b2ob2o97b2o3b2o$603b2o5b2o21bo85b3o$603b2o5b2o46b2o58bo3b
o$658b2o52b2o4bo4b3o13b2o$712b2o4b2obob3o13b2o$720bo3b2o$633b2o$633b2o
7$658b3o3b3o$657bo3bobo3bo$656bo3b2ob2o3bo$656bob2o5b2obo$658bo7bo4$
719bo$720b2o5bo$664b3o52b2o7bo$664bobo59b3o$663bo3bo$663bo3bo2$658b2o
4b3o$658b2o4$655bo$655bobo$643b2o11bobo5bo83b2o$643b2o11bo2bo3b3o83bo$
656bobo3bo3bo82bobo7bobo$655bobo6bo85b2o7bo3bo$655bo5bo5bo95bo5b2o$
661bo5bo91bo4bo4b2o$662bo3bo96bo$663b3o93bo3bo$759bobo3$711b3o$711b3o$
705b2o3b5o$705b2o2b2o3b2o$709b2o3b2o$663b2o$663b2o2$709b2o3b2o$709b2o
3b2o$710b5o$711b3o$711b3o5$704b3o5b3o$704b3o5b3o$705b2o5b2o$707bo3bo$
705bo2bobo2bo$704bo3bobo3bo$705bo2bobo2bo$705b3o3b3o5$705b2o101b2o$
705b2o101b2o4$699b2o$699bobo$690b2o2b2o6bo$690b2obo2bo2bo2bo$694b2o6bo
$699bobo8b3o$699b2o$710bobo$709b5o$708b2o3b2o$708b2o3b2o3$711bo$712b2o
2$714bo2$710bo2bo$710b2o11$862bobo$862b2o$863bo2$810b2o$809bo$810bobo$
811bo55$871b2o$871b2o10$796b3o$797bo$797bo$796b3o2$796b3o$796b3o2$796b
3o$797bo$797bo$796b3o!

Since then no one has gotten around to optimizing it further, or completing an actual glider construction for it. There are some ideas elsewhere in the thread for possible lines of investigation to reduce the amount of construction-arm circuitry. Maybe it's worth spending a little more time on that before coming up with a recipe.

For example, chris_c's solution for the PUSH/PULL/FIRE salvos looks like it takes an eight-glider salvo plus the suppression guns. It doesn't seem too unlikely that there's a PUSH/PULL/FIRE combination with half as many gliders in the base salvo, which would greatly reduce the amount of circuitry that needs to be built (and destroyed).

Once we have a specific construction recipe for one of these decoder/constructors, plus a few more gliders to shoot it down again when its work is done, we'll know an exact upper limit for N. Only N gliders will be enough to construct any glider-constructible pattern of any size, even a million fleets of a billion Geminoids each, or a digital representation of the complete-so-far works of John Conway Himself.

N seems likely to be in the low four digits for the current design, but if it could be reduced to only three digits, it would be an extra-impressive LifeWiki Did-You-Know ...!

EDIT: Comment from simsim314 on the Pattern of the Year thread:

As this pattern is "glider destroyable" we don't need to add self destruct - the destruction can be simply part of the dried salvo coded inside the tape. I don't think we need to "prove" this pattern is glider destroyable, as I think it's self evident.

Good point. I was thinking it would be more efficient -- take a lot less gliders -- to just include the destruction gliders in the recipe... but if we code them on the tape, it will obviously reduce N, so that's the way to do it.

[chris_c]

Here my notes on making a few of the necessary components. I never got around to making all of the components or putting the whole thing together, but some back of the envelope calculations that I did (long since lost) made me confident that N would be less than 1000.

P690 gun in 16G:

Code: Select all

x = 90, y = 95, rule = B3/S23
obo$b2o85bo$bo85bo$87b3o18$27bo$26bo$26b3o7$43bo26bo$19bo23bobo24bobo$
17bobo23b2o25b2o$18b2o$26bo$26bobo$26b2o4$30bo$29b2o$29bobo3$11bo$12bo
$10b3o5$b2o10b3o$obo12bo24b2o25b2o$2bo11bo25bobo24bobo$18b2o20bo26bo$
17b2o$19bo34$87b3o$bo85bo$b2o85bo$obo!

P690 gun attached to herschel based inserter in 33G (one kickback is used):

Code: Select all

x = 299, y = 316, rule = B3/S23
obo$b2o181bo$bo181bo$183b3o18$123bo$122bo$122b3o7$139bo26bo$19bo119bob
o24bobo$17bobo119b2o25b2o$18b2o$122bo$122bobo$122b2o9$11bo$12bo$10b3o
13$194bo$193bo102bo$193b3o100bobo$296b2o17$228bo$227bo$227b3o13$218bo$
217bo$217b3o$249bo26bo$248bo26bo$248b3o24b3o15$72bo$70bobo$71b2o151bo$
222b2o$223b2o17$126bo$125b2o$125bobo10$b2o10b3o$obo12bo120b2o25b2o$2bo
11bo121bobo24bobo$114b2o20bo26bo$113b2o$115bo34$183b3o$bo181bo$b2o181b
o$obo18$198b2o$197b2o$199bo55$230b3o$230bo$231bo13$220b3o$220bo$221bo$
251b3o24b3o$251bo26bo$252bo26bo2$289bo$288b2o$288bobo$41b3o$43bo$42bo
19$296b2o$296bobo$48b2o246bo$49b2o$48bo!

P30 period tripler mechanism in 11G:

Code: Select all

x = 50, y = 60, rule = B3/S23
44bobo$44b2o$45bo7$22bo$23b2o$22b2o$45bo$43b2o$44b2o$31bo$30bo$30b3o$o
$b2o9bobo$2o11b2o$13bo11$47b2o$47bobo$47bo4$10bo$10b2o15bo$9bobo16bo$
26b3o9$45bo$44b2o$44bobo5$42b2o$42bobo$42bo!

[simsim314]

The only problem that I have with this thing, is that it can't construct itself.

So although the tape can construct "anything" as large as we want, the builder bounding box must be significantly larger than the construction. So we lose something on universality here.

Maybe just for purpose of exploration, we should also add a property that construction of "even more complex tape" should be achievable. In other words the construction should be turing complete on its own right. Not exactly sure how to formulate it, but the basic idea is removing the constraint of: builder >> construction, and in some less trivial way than just artificially copying the distantly placed SL.

EDIT Although this taking us to another research brunch, instead of just finding the minimal number of glider to construct anything.

EDIT2 I've counted 33 p690, so Chris's design should be possible to construct in ~ 33 * (16 + 11) gliders, so it should be ~1K.

[dvgrn]

The only problem that I have with this thing, is that it can't construct itself.

So although the tape can construct "anything" as large as we want, the builder bounding box must be significantly larger than the construction. So we lose something on universality here.

That's not clear to me. It's definitely not a trivial problem to build an exact copy of the original constructor/decoder complete with the identical faraway block location -- unless as you say you send out a few gliders to duplicate the block before you start to read the data.

But If that's considered cheating, then instead we'll have to program the decoder/constructor to build some self-destructing computational circuitry as well as the decoder/constructor copy -- and, let's say, a Cordership heading out to where the copy's block will have to be.

The computational circuitry will have to count to just the right number of ticks, then self-destruct while sending a salvo of gliders out to stop the Cordership and clean it up into a block. Or probably something equivalent could be done by starting up a block-pushing gun, then having the computer stop it at the right time.

It would probably be a horrible job to figure out how to do make this work in practice, of course: every minor change you make to the computational circuitry changes its slow-salvo recipe, which changes the location of the original block.

But it does seem possible with this method to construct new decoder/constructors with a bounding box larger than the original. I don't think there's any reason why the initial block location and the copy's block location couldn't be arranged to match exactly.

-- In fact, it seems as if some Gödel-Incompleteness-Theorem-like argument might guarantee that such an exact match has to exist somewhere out there in Ridiculously Far-Away Land. I'm out of practice at thinking about this kind of thing; is there an easy mathematical trick to guarantee such a match?

[simsim314]

On other thought - Chris's "tape block" is moving quite slow, much slower than c/12, so at some point we could code a c/12 cordership, send it forward and then code a destruction glider salvo, with correct timing. It should be possible to code "other designs" this way, even those which are much larger.

Another point is that we can vary the factor of Chris's mechanism to slow it down as much as we want using lower period guns, this will decrease even further the "tape block" speed, by any desirable factor, and in principle glider gun size is logarithmic, and our interception mechanism (c/12 meets c/4) is linear, so we can code logarithmic guns in O(log(N)) operations, but the coding length is exponential to number of operations, this way we get linear factor of bounding box growth to use slower guns, which in their own right slow down the mechanism by factor of N.

Not sure it all adds up - but looks promising (UC can at least code a slower UC, or can code X copies of slowe UCs).

EDIT As an option for Chris's design we can use a sawtooth, that shoots glider every N^2 generations. Construction of a larger sawtooth is also logarithmic, so the size is increasing linearly but the reading speed slows down quadratically, thus our c/12-c/4 interception that works at constant speed, will reach its destination faster than quadratic sawtooth based tape reader can read the operations block.

[dvgrn]

On other thought - Chris's "tape block" is moving quite slow, much slower than c/12, so at some point we could code a c/12 cordership, send it forward and then code a destruction glider salvo, with correct timing. It should be possible to code "other designs" this way, even those which are much larger.

The "tape block" moves at c/686, I believe.

With this proposed method, aren't there are going to be huge gaps between the locations where the destruction salvo can be made to catch up with the Cordership? It's not absolutely impossible, but it seems as if the odds would be ridiculously low that one of those stopping locations will just happen to match the location of the original block, and thus code for an exact copy of the decoder-constructor.

This whole design is so counterintuitive that maybe it's worth going through the first few cycles of operation as an example. I apologize in advance for probably getting some of the following math wrong... hopefully it will still give an intuitive picture that's reasonably accurate.

A decoder-constructor with 100 instructions
Let's say we start with a block 3^100 cells away from the decoder-constructor. The decoder pulls that block in to the zero point, three cells at a time, at c/686. At the same time, it pushes another block away at c/2074 -- slightly slower than c/(686*3) because of the Doppler effect, but that detail doesn't really matter.

Eventually the PUSHed block gets moved over to the PULL channel, at roughly 3^99 cells away... and the cycle can be repeated to read another 99 instructions (or almost that) until the block gets stuck at the zero distance.

If the very first instruction read by the decoder launches a Cordership, and the second instruction sends a salvo to stop it, we'll have

-- c/12 Cordership launch at T ~ 686 * (3^100)
-- c/4 glider launch at T ~ 686 * (3^100+3^99)

So we'll end up with a block at around (1/4-1/12)(686)(3^99) = about 39*(3^100) cells away, 39 times as far out as the original block.

If we wait for the third instruction to launch the following glider

-- c/4 glider launch at T = 686 * (3^100 + 3^99 + 3^98)

then we have another location we can place the block, at (1/6)(686)(4*3^98) = ~ 48*(3^100) cells away. Every location between 39 times the original distance and 48 times the original distance, is unreachable by this specific mechanism. 3^102 cells is a lot of unreachable distance... and that's with the decoder reading only 100 instructions.

Wait Longer, Get Closer -- But Not Close Enough
If we wait longer to launch the Cordership, the gaps between instructions keep getting shorter. So if we knew how many instructions would actually be needed, we could launch the Cordership and glider at a time that would allow the block to be placed somewhere near the original location -- the right order of magnitude, at least! But we're going to have to hit the spot exactly, or the original decoder-constructor hasn't made a copy of itself after all.

Adding A Programmable Computer May Not Be Good Enough
I figured that this level of precision was going to have to be a job for a programmable computer of some sort. Let's see: with some kind of binary encoding for the computer program, we can set things up so that writing a "0" or a "1" to the program takes exactly the same number of encoded instructions. If we know the total number of encoded instructions on the tape, then we have a fair idea of where the block will be... if there are a million PUSH/PULL/FIRE instructions, for example, then the block will be somewhere between 3^1000000 and 3^1000001 cells away.

-- But it could be anywhere in that range, depending on what the specific instructions are... and that's a mighty big range! There may not be enough different possible programs for the computer, to hit the specific location that matches the construction recipe for the decoder-constructor plus the computer plus the program.

If we give the computer more states, that just means the construction recipe gets longer, which pushes the block exponentially farther away and makes the range of possible locations even larger. Is there a way to show mathematically that somewhere out there in the Land of Exponentially Far-Away, we'll catch up somehow and be guaranteed to be able to encode an exact match?

I don't see how higher-period guns or an N^2 sawtooth, or any delay mechanism along those lines, would solve the problem of the extreme sparsity of reachable block locations. If anything, it seems like it would make the problem worse...?

Maybe "Artificially Copying" Ain't So Bad After All...
This all makes it seem like a really good idea to cheat. Just add two gliders to the N-glider recipe, to make another block at a known small offset from the first one, out of the way. Then suddenly it's trivial (relatively speaking) to program the decoder-constructor to make an exact copy of itself, including the positions of the two blocks.

[simsim314]

-- But it could be anywhere in that range, depending on what the specific instructions are... and that's a mighty big range! There may not be enough different possible programs for the computer, to hit the specific location that matches the construction recipe for the decoder-constructor plus the computer plus the program.

This is obvious to me that to code N programs we need at least N numbers. This is why I think we should code our program in some other way. For example if instead of push, push, ... , push we will use (100)xPUSH, this will allow us to optimize the coding for some subset of "natural" programs. This is basically the idea of archivation.

Now to "code" any program, we could always add in the end of a program milion times (1000xPUSH)(1000xPULL) operations, this will cause the block to be as far away as we want, and the program can be shorten by any factor we want. Thus any program even those that takes much more time to code, we just add NONE operation in the form of KxPUSH+KxPULL to make it reducible by any desirable factor.

Of course this requires to build a programmable computer, but yet again - this is very theoretical question anyway.

[dvgrn]

Of course this requires to build a programmable computer, but yet again - this is very theoretical question anyway.

Yeah, it sounds like we agree that the current draft of the decoder-constructor can't build an exact copy of itself, without building a self-destructing programmable computer as part of the recipe. (But the current draft plus a second block at a known offset from the original tape block _could_ build an exact copy of itself, if only in a "trivial" way.)

Really I'm not too concerned about the self-construction problem you brought up --

The only problem that I have with this thing, is that it can't construct itself.

-- I just can't see in detail how to guarantee that any specific block position on this kind of tape will actually be able to "construct itself".

This design stores information in such an incredibly inefficient way that a "tape" with N+1 instructions is always about three times as long as a tape with N instructions. So your idea of adding a million (1000xPUSH)+(1000xPULL) statements still kind of worries me, because it makes the problem of hitting a precise block location 3^2000000 times worse than it would have been otherwise.

I'm definitely not saying that your idea won't work -- would just like know if there's a way to prove that it definitely will work. I don't have a lot of practice thinking about numbers like 3^2000000, but getting a computer program to precisely hit a number in that range will require calculating or encoding over 954,000 digits of precision. And that's just the multiplication factor due to adding your PUSH+PULL padding idea (though I know it was just a random guess on your part). The actual program for building the computer might well need more additional digits of precision than that.

It seems possible to me that as we try to encode more of these digits of precision, we make the problem bigger and have to encode still more digits, and we might never catch up.

--------------------------------------

Anyway... I think I'll go back to more interesting problems that I might be more competent to solve. After reviewing chris_c's eight-glider salvo, it seems pretty clear that there will be an equivalent PUSH/PULL/FIRE salvo that needs only five gliders. In fact, Paul Chapman's original prototype construction arm includes two five-glider subsets that would work:

Code: Select all

x = 98, y = 65, rule = LifeHistory
32.2A28.2A28.2A$31.A.A2.2C23.A.A2.2C23.A.A2.2C$33.A2.2C25.A2.2C25.A2.
2C$21.E29.D$21.2E28.2D$20.E.E27.D.D$26.D29.C$26.2D3.A24.2C3.A29.A$25.
D.D3.2A22.C.C3.2A28.2A$30.A.A27.A.A27.A.A2$16.E29.D$16.2E28.2D$15.E.E
27.D.D25$23.2E$22.E.E$24.E7.2A28.2A28.2A$31.A.A2.2C23.A.A2.2C23.A.A2.
2C$33.A2.2C25.A2.2C25.A2.2C4$26.D29.C$26.2D3.A24.2C3.A29.A$25.D.D3.2A
22.C.C3.2A28.2A$30.A.A27.A.A27.A.A13$3E$2.E$.E!

The only technical problem is that the salvo's central white glider can't be shot down without damaging the two yellow gliders, if those are present. So it would be necessary to suppress the white glider close to its source gun, before other gliders are added (but I think that's doable). Both yellow gliders in either version can be suppressed with one 90-degree glider:

Code: Select all

x = 84, y = 41, rule = LifeHistory
53.2B$52.4B$53.4B$54.4B$55.4B$.2B53.4B$4B53.4B$.4B27.2C24.4B20.2C$2.
4B26.2C25.4B19.2C$3.4B53.3BA$4.4B53.ABA$5.4B53.2A$6.4B$7.4B$8.BABA47.
2E$10.2A46.E.E$10.A7.2A40.E7.2A$17.A.A47.A.A$19.A49.A$7.E$7.2E$6.E.E$
12.C49.C$12.2C3.A44.2C3.A$11.C.C3.2A42.C.C3.2A$16.A.A47.A.A2$2.E$2.2E
$.E.E9$36.3E$38.E$37.E!

I think something along these lines ought to cut down on the decoder-constructor's guns and other circuitry, enough to really guarantee a three-digit N. (?)

It might be wishful thinking, but there's some hope of a solution with a four-glider salvo as a base, so I'll try those searches first.

EDIT: Drat -- so close...

Code: Select all

x = 17, y = 11, rule = LifeHistory
.A$.2A8.2A$A.A7.A.A2.2A$12.A2.2A4$5.A$5.2A3.A$4.A.A3.2A$9.A.A!

With five gliders, at least the fifth glider doesn't have to be synchronized with the fourth one:

Code: Select all

x = 57, y = 14, rule = LifeHistory
21.2A28.2A$11.E8.A.A2.2C23.A.A2.2C$11.2E9.A2.2C25.A2.2C$10.E.E28.E$
41.2E$40.E.E2$20.A29.A$20.2A28.2A$3E16.A.A27.A.A$2.E$.E29.3E$33.E$32.
E!