gmc_nxtman wrote:... the program starts by "going down a tree"; It takes one cell in the bounding box, and turns it on or off. It then checks which result is closer to the specified spaceship, and then goes to that "branch" of the tree. Then it takes the next cell and does the same thing.
This algorithm has probably been thought of before.
simsim314 wrote:It's not such a big deal to search all possible collisions except that no one has done it. But 3 gliders are probably measured in thousands, and 4 gliders in millions, after that - 5 gliders is probably already out of scope of any normal few days search, probably from weeks to months.
Anyway there is nothing extremely novel in this collision search utility, I think Bob is conducting searched along those lines for couple of years now.
calcyman wrote:There's a finite positive integer, n, such that anything that can be synthesised with gliders can be synthesised with precisely n gliders.
calcyman wrote:SBM register so as to Gödel-encode the recipe for the object.
simsim314 wrote:EDIT OOPS I think I got it. You can encode large series using single integer and interpreter from this integer to the series. I don't see the finite design that can convert remote SL to series of gliders but I do agree it should be possible.
Do you have design in mind how to convert remotely located SL into sequence of operations?
dvgrn wrote:Yes, you can encode any sequence of positive integers into a single ridiculously huge integer
simsim314 wrote:Now what I don't see yet, is how to move SL located at distance X to SL at distance Int(X / 2), and shoot different glider depending on X mod 2, or any other mechanism with similar properties.
simsim314 wrote:Now what I don't see yet, is how to move SL located at distance X to SL at distance Int(X / 2), and shoot different glider depending on X mod 2, or any other mechanism with similar properties.
x = 954, y = 344, rule = B3/S23
950b2o$950bobo$951bobo$952bo5$742b2o$742bobo$743bobo$744bo5$534b2o$
534bobo$535bobo$536bo5$326b2o$326bobo$327bobo545b2o$328bo546bobo$876bo
bo$877bo5$667b2o$667bobo$668bobo$669bo3$922b2o$922bobo$459b2o462bobo$
459bobo462bo$460bobo$461bo3$714b2o$714bobo$251b2o462bobo$251bobo462bo$
252bobo$253bo3$506b2o$506bobo$507bobo$508bo5$298b2o$298bobo$299bobo$
300bo171$69bo199bo199bo199bo$69b2o198b2o198b2o198b2o$68bobo197bobo197b
obo197bobo12$116b2o198b2o198b2o198b2o$117b2o198b2o198b2o198b2o$116bo
199bo199bo199bo18$84b2o198b2o198b2o198b2o$85b2o198b2o198b2o198b2o$84bo
199bo199bo199bo5$24b3o197b3o197b3o197b3o$25bo199bo199bo199bo$22bo2bo
196bo2bo196bo2bo196bo2bo$22bo2bo196bo2bo196bo2bo196bo2bo$22bobo197bobo
197bobo197bobo$8b2o198b2o198b2o198b2o$8b2o198b2o198b2o198b2o3$25bo199b
o199bo199bo$24bobo197bobo197bobo197bobo$25bo199bo199bo199bo$8bo199bo
199bo199bo$2o7bo190b2o7bo190b2o7bo190b2o7bo$2o22b4o172b2o22b4o172b2o
22b4o172b2o22b4o$11bo10bo3b2o183bo10bo3b2o183bo10bo3b2o183bo10bo3b2o$
9bobo9bo4bo182bobo9bo4bo182bobo9bo4bo182bobo9bo4bo$10bo10b2obo185bo10b
2obo185bo10b2obo185bo10b2obo$23bo199bo199bo199bo3$10b2obobo194b2obobo
194b2obobo194b2obobo$13bobo16bo180bobo16bo180bobo16bo180bobo16bo$10bo
2bo17b3o176bo2bo17b3o176bo2bo17b3o176bo2bo17b3o$10bo3bo195bo3bo195bo3b
o195bo3bo$7b2o2b4o16b3o173b2o2b4o16b3o173b2o2b4o16b3o173b2o2b4o16b3o$
6b2o5bo14b2ob2o173b2o5bo14b2ob2o173b2o5bo14b2ob2o173b2o5bo14b2ob2o$8bo
21bo177bo21bo177bo21bo177bo21bo3$54b3o197b3o197b3o197b3o$55bo199bo199b
o199bo$52bo2bo196bo2bo196bo2bo196bo2bo$52bo2bo196bo2bo196bo2bo196bo2bo
$52bobo197bobo197bobo197bobo$38b2o198b2o198b2o198b2o$38b2o198b2o198b2o
198b2o$33bo199bo199bo199bo$32b3o197b3o197b3o197b3o$31b2ob2o19bo175b2ob
2o19bo175b2ob2o19bo175b2ob2o19bo$33bobo18bobo176bobo18bobo176bobo18bob
o176bobo18bobo$35bo19bo179bo19bo179bo19bo179bo19bo3$54b4o196b4o196b4o
196b4o$38bo13bo3b2o180bo13bo3b2o180bo13bo3b2o180bo13bo3b2o$37bobo11bo
4bo180bobo11bo4bo180bobo11bo4bo180bobo11bo4bo$39bo11b2obo184bo11b2obo
184bo11b2obo184bo11b2obo$36b2o15bo182b2o15bo182b2o15bo182b2o15bo$36bo
199bo199bo199bo$37b3o197b3o197b3o197b3o$37b2o198b2o198b2o198b2o$41bo
199bo199bo199bo$40b2o198b2o198b2o198b2o$40b2o198b2o198b2o198b2o$42b2o
6b2o190b2o6b2o190b2o6b2o190b2o6b2o$44b2o4b2o192b2o4b2o192b2o4b2o192b2o
4b2o$42bob2o196bob2o196bob2o196bob2o$42b2o198b2o198b2o198b2o5$42b2o
198b2o198b2o198b2o$42b2o198b2o198b2o198b2o!
Bullet51 wrote:simsim314 wrote:Now what I don't see yet, is how to move SL located at distance X to SL at distance Int(X / 2), and shoot different glider depending on X mod 2, or any other mechanism with similar properties.
Maybe we can make a extensible binary counter, which increments one when the block isn't at zero position,and then pulls the block.When the block is at zero position, the counter outputs the number it counts.
simsim314 wrote:EDIT2 This is pretty amazing - constant cells universal constructor (meaning one can encode caterpillar using around few K cells).
simsim314 wrote:Now what I don't see yet, is how to move SL located at distance X to SL at distance Int(X / 2), and shoot different glider depending on X mod 2, or any other mechanism with similar properties.
// Move rax into rbx:
label1:
cmp %%rax, $0
je label2
dec %%rax
inc %%rbx
jmp label1
// Move floor(rbx/2) into rax:
label2:
cmp %%rbx, $0
je label3
dec %%rbx
cmp %%rbx, $0
je label4
dec %%rbx
inc %%rax
jmp label2
// Do something if least significant bit was zero
label3:
(...)
jmp label1
// Do something if least significant bit was one
label4:
(...)
jmp label1
dvgrn wrote:It's just necessary to design a binary counter that can be read destructively as the recipe is being decoded, so that it will end up in a known state at the end of the construction.
calcyman wrote:You can just use two SBM registers, in the way that the pi calculator works for doing logical right shifts:
calcyman wrote:dvgrn wrote:It's just necessary to design a binary counter that can be read destructively as the recipe is being decoded, so that it will end up in a known state at the end of the construction.
Doesn't the two-register solution work? It terminates with rax = rbx = 0. It seems needlessly sophisticated to use a binary counter when you can instead LSR off the bottom bits of the contents of SBM registers.
x = 42, y = 22, rule = B3/S23
2$10bo$9bo28bo$9b3o25bo$37b3o8$4b2o$3bobo$5bo25b2o$30bobo$32bo!
simsim314 wrote:Сan someone explain how SBM works, or link to some article that explains it?
#C Sliding block memory -- Dean Hickerson, 1 March 1990
#C The block is initially in position 3 and gets incremented to 4.
#C From then on, the output of the zero-detector is inverted twice
#C and becomes the increment suppressing glider, so the increment
#C salvo will be released only when the register is decremented to 0.
#C Meanwhile, a glider is kicked back and forth between the decrement
#C suppressor's stream and an external gun, deleting one glider from
#C the decrement suppressor every 480 generations. So the register
#C gets incremented once, then repeatedly decremented until it
#C reaches 0, and from then on is alternately incremented to 1
#C and decremented to 0 forever.
x = 240, y = 192, rule = B3/S23
64b2o21b2o89b2o20bo$63b3o21bo91bo19bobo$60bob2o15bo5bobo91bobo7b2o6b2o
3bo$53b2o5bo2bo8b3o4bobo3b2o93b2o6bobo4b2obo3bo9b2o$53b2o5bob2o16bobo
8bo83bo11b3o4b3obo3bo9b2o$63b3o2b2o2bo7bo2bo5b3o83b3o8b3o4bo2b2obobo$
64b2o2bo3bo7bobo5bo89bo8b3o4b2o4bo$69bo2bo6bobo6b2o87b2o9bobo$69b2o8bo
109b2o2$68bo134bo$67b2o132bobo$52bo8bo5bobo132b2o10bo$52b3o6bobo113b2o
3b2o28b3o$55bo5b2o114bo5bo27bo$54b2o155b2o$84b5o89bo3bo$26b2o55bob3obo
89b3o$17b2o8bo28b3o25bo3bo$17b2o8bobo8b2o16b3o26b3o115bobo$28b2o7bobo
15bo3bo26bo101b2o13b2o4bo$36bo17bo5bo2bobo123b2o13bo3b3o$36bo2bo15bo3b
o4b2o122bo19b3o$36bo19b3o5bo$37bobo5b2o41bo94bo22b2o3b2o$33bo4b2o5bobo
40bo92bobo22b2o3b2o$34bo12bo33bo5bobo92b2o$32b3o12b2o32bobo2b2ob2o$71b
o9b2o2bo5bo86bo$14b2o3b2o51b2o14bo88b3o$71b2o12b2o3b2o84b5o$15bo3bo39b
2o114b2o3b2o24b2o$16b3o40bo116b5o26bo$16b3o22bo18b3o11bo14bo86bo3bo23b
3o$27bo11bobo11b2o7bo10bo15bo87bobo8bobo13bo$25bobo12b2o11bo19b3o14bo
87bo9b2o$19bo6b2o23bobo135bo$18b3o30b2o18b2o33bo87b2o$17bo3bo24b2o24bo
14b2o17b4o68b2o14bo$19bo28bo20b3o15b2o18b4o7bo59b2o15b3o$16bo5bo25bo
20bo23bo13bo2bo6bobo77bo$16bo5bo21bo3bo42b3o13b4o4b2o3bo$17bo3bo22bo
45bo7b2o6b4o5b2o3bo$18b3o24b3o10b2o19b2o9b2o5bobo6bo8b2o3bo$59bo19bo5b
o11bo19bobo8b2o$59bobo7bo7bobo4bo11b2o20bo9bobo$60b2o7b4o4b2o5b3o20bob
o20bo$70b4o33b2o21b2o$27bo10bo31bo2bo34bo$27b2o9b2o30b4o$16b2o5b2o3b2o
7bobo4bo24b4o$17bo10b3o13bobo22bo$14b3o11b2o15bobo4b2o58b2o$14bo5b2o5b
2o16bo2bo3b2o31b2o3b2o20bobo$19bobo5bo17bobo39b3o22bo$19bo24bobo16bo
22bo3bo37bo$18b2o24bo19bo22bobo38b3o$62b3o4bobo16bo42bo$70b2o58b2o$70b
o14b2o$86bo32b3o$83b3o33bo$58bo24bo36bo$4b2o21bo30b3o$5bo21b2o32bo68b
2o3b2o21bobo$5bobo7b2o11b2o30b2o68bobobobo21b2o$o5b2o6b3o3bo7b3o7b2o
91b5o23bo$3o8bob2o4b4o5b2o8b2o87b2o3b3o$3bo7bo2bo4bo4bo2b2o98bobo3bo$
2b2o7bob2o5bo3bo2bo22bo40b2o19b2o13bo$14b3o3b2obo24b3o41bo19bo$15b2o
30bo15bo28bobo6b2o7bobo$38b3o6b2o13b3o28b2o6b3o6b2o$40bo20b5o37b2obo7b
o$28bobo8bo20bobobobo9b2o25bo2bo7b2o$2b2o3b2o20b2o29b2o3b2o8bo2bo24b2o
bo6bobo$2b2o3b2o20bo14b3o27bo4bo21b3o26b3o$75b4o22b2o26b2ob2o58b3o$4b
3o37bobo82b2ob2o29b2o27bo$4b3o36b5o81b5o29bo4bo24bo$5bo10bo25b2o3b2o
27b2o50b2o3b2o15bo10bobo4b3o$16bobo23b2o3b2o11b2o14b2o71bobo9b2o8bo$
16b2o19b2o22bo86bob2o18b2o$37bobo18b3o25b2o59b2ob2o$39bo4b2o12bo26bobo
60bob2o$39b2o2b2ob2o39bo5bo50b2o3bobo7bo$7bo36bo2bo46bo48bobo4bo6b2o$
8b2o13b3o18bo47b3o4bobo7b2o17b2o13bo14b2o$7b2o16bo21bo52b2o7b2o18bo12b
2o26b2o3b2o$24bo20b2o53bo25b3o41b2o3b2o$2b3o121bo$bo3bo160b3o3b3o$o5bo
26b2o5b2o3b2o119bo5b3o$o5bo26bo7b5o5bo98bobo14bo5bo$3bo12b2o4bobo6bobo
8b3o7b2o74bobo19b2o$bo3bo11bo4bo2bo5b2o10bo7b2o75b2o6b2o13bo$2b3o10bob
o7b2o102bo7bo$3bo19bo3b2o108bobo20b2o$25b2o111b2o21b2o$14b2o6bo2bo134b
o9b3o$3b2o8bobo6bobo88bobo54b3o$3b2o8bo100b2o53bo3bo$12b2o93bo6bo$43b
2o63b2o35b2o21b2o3b2o$43b2o62b2o36bobo$145bo$87b2o$88b2o$87bo11b6o30bo
bo$52bo45bo6bo29b2o16b2o8bo75bo$51b2o44bo8bo29bo16bo2bo6bobo71b3o$50b
2o4b2o5bo34bo6bo42b2o2bo3bo7bobo6b2o61bo$40b2o7b3o4b2o3bobo35b6o42b3o
2b2o2bo7bo2bo5bo62b2o$40b2o8b2o4b2o2bobo11b2o61b2o5bob2o16bobo7b3o$51b
2o6bo2bo11b2o61b2o5bo2bo8b3o4bobo3b2o5bo$52bo7bobo53bo27bob2o15bo5bobo
43b2o$61bobo52b2o29b3o21bo43b2o$63bo51bobo30b2o21b2o$42b2o$44bo170bo$
31b2o12bo168b3o$31b2o4bo7bo167bo3bo$28b2o5b2o8bo169bo$27b3o5bo2b2o4bo
7b2o158bo5bo$28b2o6b5ob2o8bobo157bo5bo$22b2o7b2o4bo16bo78b2o78bo3bo$
21bobo7b2o21b2o77b2o79b3o$21bo19bo$20b2o17b2o178b2o$40b2o3bo174b2o$45b
o173bo$90bo$90b3o$93bo$92b2o2$17bo35bo3b2o158bo$17b3o31bobo4b2o156b3o$
20bo31b2o3bo158b3o$19b2o$214b2o3b2o$214b2o3b2o2$50bo50b3o$50b2o49bo$
49bobo34bo15bo$13b2o13bo2bo8bo20b2o23b2o$14bo13bo10bobo19bo23bobo$14bo
bo7bo2bo3b2o5bo3b2o8bo6bobo$15b2o4b4o3b2obobo4bo3b2o5b4o6b2o155b2o$20b
4o14bo3b2o4b4o57b2o105b2o$20bo2bo8b2o5bobo6bo2bo16bo40bobo$20b4o16bo7b
4o16b3o15b2o21bo$21b4o24b4o18bo14b2o$24bo27bo17bo$70bo2bo$74bo$61bo10b
o$59b3o54b3o9b2o$58bo57bo9bo2bo$58b2o11bo39bo5bo7bo$71b2o36b4o12bo11b
2o$70bobo11b2obob2o12b2o3bobob2o11bo11b2o$79b3o21b2o2bo2bob3o11bo2bo$
79bo4bo5bo17bobob2o14b2o$80bo28b4o$85b2ob2o21bo$55b3o29bo$54bo3bo4b2o$
53bo5bo4b2o$53bo5bo3bo21bo$56bo27bobo$54bo3bo24bo3bo$55b3o25b5o$56bo
25b2o3b2o$83b5o$53b2o29b3o$54bo4b3o23bo$51b3o5bo$51bo8bo6bo$65b2o$66bo
bo$68b2o$70bo8bo$67bo10bobo6b2o$63bo2bo3b2o5bo3b2o4bo$60b4o3b2obobo4bo
3b2o5b3o$52b2o5b4o14bo3b2o7bo$52b2o5bo2bo8b2o5bobo3b2o$59b4o16bo4bobo$
60b4o22bo$63bo22b2o!
dvgrn wrote:Start with the original article for Dean Hickerson's sliding-block memory from 1990.
x = 152, y = 73, rule = B3/S23
76bo23bo23bo23bo$74b3o21b3o21b3o21b3o$73bo23bo23bo23bo$65b2o6b2o14b2o
6b2o14b2o6b2o14b2o6b2o$65bobo21bobo21bobo21bobo$66bo23bo23bo23bo2$71b
2o22b2o22b2o$71b2o5b2o15b2o5b2o15b2o5b2o22b2o$78b2o22b2o22b2o14b2o6b2o
$142b2o2$61b2o22b2o22b2o22b2o$61b2o22b2o22b2o22b2o2$76b2o22b2o22b2o22b
2o$67b2o7bobo21bobo21bobo21bobo$68b2o8bo23bo23bo23bo$67bo10b2o22b2o22b
2o22b2o6$31b2o$31b2o5b2o$38b2o50b2o22b2o22b2o$90bo23bo23bo$88bobo21bob
o21bobo$7b2o8b2o17b2o50b2o22b2o22b2o$7b2o9bo17b2o$18bobo21b2o29b2o22b
2o22b2o$19b2o21b2o29b2o22b2o22b2o$b2o$b2o$5b2o27b2o54b2o22b2o22b2o$5b
2o76b2o5b2o22b2o15b2o5b2o$83b2o46b2o2$78bo23bo23bo$2o75bobo21bobo21bob
o$2o75b2o6b2o14b2o6b2o14b2o6b2o$85bo23bo23bo$86b3o21b3o21b3o$88bo23bo
23bo2$13bo20b3o$11b2o21bo$12b2o19b3o4$7b2o$8bo$5b3o$5bo41b2o$47b2o4$
42b2o$42b2o$46b2o$46b2o$5b2o21b2o$5b2o21bobo$11b2o17bo9b2o$11b2o17b2o
8b2o3$9b2o$9b2o5b2o$16b2o!
calcyman wrote:You can just use two SBM registers, in the way that the pi calculator works for doing logical right shifts:Code: Select all// Move rax into rbx:
label1:
cmp %%rax, $0
je label2
dec %%rax
inc %%rbx
jmp label1
// Move floor(rbx/2) into rax:
label2:
cmp %%rbx, $0
je label3
dec %%rbx
cmp %%rbx, $0
je label4
dec %%rbx
inc %%rax
jmp label2
// Do something if least significant bit was zero
label3:
(...)
jmp label1
// Do something if least significant bit was one
label4:
(...)
jmp label1
Users browsing this forum: No registered users and 5 guests