## Searching algorithms

For general discussion about Conway's Game of Life.
gmc_nxtman
Posts: 1150
Joined: May 26th, 2015, 7:20 pm

### Searching algorithms

This thread is for sharing searching algorithms that might be one day put to work. To start this thread, here is a possible spaceship search algorithm:

The user inputs speed, displacement and bounding box of the spaceship searched for, and 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.

dvgrn
Moderator
Posts: 7986
Joined: May 17th, 2009, 11:00 pm
Contact:

### Re: Searching algorithms

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.
Sounds identical to lifesrc / WLS / JLS, in fact. The only possible difference is the part about checking "which result is closer". The lifesrc variants don't have any way to measure "closer" -- either the pattern's descendant is identical to itself (with some spacetime offset) or a contradiction has been found and it's time to backtrack.

Every few years someone proposes evolving spaceships via some kind of genetic algorithm, where maybe you'd measure the number of matching and mismatching cells, and use that as a fitness criterion for making small changes and looking for mutants that were "closer" to being spaceships.

Unfortunately the smallest possible change -- turning one cell ON or OFF -- isn't nearly small enough! A one-cell change will generally either make no difference at all (a dying spark) or it will change everything. Change a single cell near a glider and you can get an R-pentomino or a pi-heptomino, or any number of other things, but the one thing you never get is a recognizable almost-glider.

simsim314
Posts: 1769
Joined: February 10th, 2014, 1:27 pm

### Re: Searching algorithms

Genetic algorithms are total failure for GOL. On the other hand statistical based algorithms are good direction which wasn't explored well enough yet.

I would suggest to give a score by choosing the "least contradictable" search branch. Say you can choose X cells (candidate cells) to turn on or off and Y cells as estimation cells that will give a contradiction statistics about the 2^X options of X candidate cells - from those X cells we chose only those configurations that have least contradictions, while computing contradictions score by trying all possible combination of all the 2^Y options.

Also if we on this topic - I think our community needs more and better construction tools (something like GOL studio), and less of a search tools. We have many nice and efficient search tools, which are great for those who knows how to use them but not so user-friendly.

Bullet51
Posts: 572
Joined: July 21st, 2014, 4:35 am

### Re: Searching algorithms

What about neural network based algorithms? Bellman may be an example.
Still drifting.

simsim314
Posts: 1769
Joined: February 10th, 2014, 1:27 pm

### Re: Searching algorithms

NNs are very bad at predicting behavior of chaotic systems, and they are just more sophisticated way to analyze statistical data.

Although pure statistical analysis could work for GOL, generalizing the statistics with smooth functions is pretty bad idea for GOL on my opinion. On other hand NNs could simulate GOL grid, but it has nothing to do with optimization or learning - it's just another implementation of GOL.

gmc_nxtman
Posts: 1150
Joined: May 26th, 2015, 7:20 pm

### Every possible n-glider collision?

I think I have a way to test every single glider collision for an n-number of gliders. This method would make a lot of trivial duplicates, but I have a feeling that there's some gems in the 5-10 glider range. First, test every single 2-glider collision. (All of these are known, there are 71 of them) Then, find every single 3-glider collision by finding every possible way for the glider to collide with the two-glider collision. Then reiterate this process until every collision up to n gliders has been tracked. I have, once again, no doubt that this has already been thought of. But I think it would make a good coding project. Although this would produce a lot of trivial duplicates, the program could sift out those after it's done finding every collision. Only after it has found every collision, and eliminated trivial duplicates, then does it run each collision in CGOL for something like 2^15 steps.

simsim314
Posts: 1769
Joined: February 10th, 2014, 1:27 pm

### Re: Searching algorithms

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.

dvgrn
Moderator
Posts: 7986
Joined: May 17th, 2009, 11:00 pm
Contact:

### Re: Searching algorithms

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.
There's a description of Bob Shemyakin's search and its limitations here. Only fairly close spacings of the last two gliders were considered -- which means that easily the majority of all four-glider collisions have still never been tested. Most of them will turn out not to do anything very interesting, but there will certainly be exceptions.

At this point it might well be worth attempting a reasonably complete enumeration of 3-glider collisions. Maybe it could be done with two independent approaches but a common output format, so that the final results can be compared against each other somehow.

A large database of the ash patterns from 3-glider collisions might be useful for optimizing syntheses. If it takes, say, four gliders to build two small still lifes one at a time, or six gliders to build three still lifes, there might well be a three-glider collision that happens to produce the same combination of still lifes simultaneously.

But it would be a very large database, even for three-glider collisions. An anywhere-near-complete database for five-glider collisions would be so big that a single computer couldn't even scan through it in a reasonable amount of time, or at least not without a very clever indexing system -- and then the time needed to generate the index would be a problem, let alone the time to do the five-glider collisions in the first place.

At the upper end of the suggested range, a 10-glider collision database would be unlikely to fit on a Jupiter-sized hard drive, even if every atom in Jupiter could store a byte of information.

calcyman
Posts: 2418
Joined: June 1st, 2009, 4:32 pm

### Re: Searching algorithms

There's a finite positive integer, n, such that anything that can be synthesised with gliders can be synthesised with precisely n gliders.

Proof: use n-2 gliders to build a universal computer-constructor with sliding block memory, and use the remaining two gliders to build a sufficiently distant block in an SBM register so as to Gödel-encode the recipe for the object.

Corollary: producing a complete list of constructions with k gliders is, at least morally, impossible.

Maybe 3-glider collisions can be fully classified (I'm imagining tens of thousands of individual cases together with a few hundred infinite families), but I doubt anyone could ever manage an exhaustive classification of all possible 4-glider collisions.

In particular, I doubt anyone could ever prove the falsity of the following claim:

"There is a 4-glider synthesis of the Caterpillar."
What do you do with ill crystallographers? Take them to the mono-clinic!

simsim314
Posts: 1769
Joined: February 10th, 2014, 1:27 pm

### Re: Searching algorithms

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.
This sounds very strange to me, and here is why: I do believe that using some sort of additive construction we can build exponentially growing number of SLs of size NxN.

Now this means that for very large N those gliders would have to be very sparse, and although I don't have proof it's impossible, I find it hard to believe it's possible to build exponential amount of SLs with 2^N x 2^N size using only N gliders.
calcyman wrote:SBM register so as to Gödel-encode the recipe for the object.
First of all I don't exactly understand the meaning of this, but how the Gödel-encode the recipe for the object can encode infinite amount of recipes in finite amount of data storage?

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
Moderator
Posts: 7986
Joined: May 17th, 2009, 11:00 pm
Contact:

### Re: Searching algorithms

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?
Yes, you can encode any sequence of positive integers into a single ridiculously huge integer using the same technique Kurt Gödel used in his incompleteness theorems -- two to the power of the first number, times three to the power of the second number, times five to the power of the third number, and so on.

The resulting N-glider construction is a ridiculous-looking thing that ought to be forbidden by the definition of "glider construction" somehow, but I suppose it isn't: in one location, a few million gliders building a huge pile of circuitry that's capable of pulling a block back from unimaginably far away, calculating and counting the prime factors of that distance, and using the results to run a universal construction arm; and, at a Skewes-number distance, very very very far away, two more gliders that collide to build the block.

-- Oh, and the universal construction arm's instructions also have to include a signal to send to the universal constructor, to tell it to self-destruct after building whatever the target object is.

All in all, I'd say that upper limit of N gliders is going to be an impressively large number... and it's going to take about umpteen to the power of Skewes' number generations to do all that calculation and construction work.

simsim314
Posts: 1769
Joined: February 10th, 2014, 1:27 pm

### Re: Searching algorithms

dvgrn wrote:Yes, you can encode any sequence of positive integers into a single ridiculously huge integer
I got an idea how to implement at least the part that converts sequence to movement. One only needs to convert a sequence reader that will have three basic operations: Push, Pull, Shoot (for monochromatic slow salvo or one can add Shoot Even, Shoot Odd commands). This will encode all slow salvo arms commands, and slow salvo is universal constructor. So we only need to read 2 bits at a time, and convert them into one of three operations, this doesn't seems to be so complex task.

----

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.

EDIT If this will work we can encode in 2N bits N slow salvo commands. And the time it will take to construct using this method is: O(2^2N). Not sure if golly is capable of simulating such enormous integers and run fast enough using them, but I do think we can start to encode some simple recipes with this approach.

EDIT2 This is pretty amazing - constant cells universal constructor (meaning one can encode caterpillar using around few K cells).

Bullet51
Posts: 572
Joined: July 21st, 2014, 4:35 am

### Re: Searching algorithms

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.That will make the time for construction into O(2^2N)^2=O(2^4N).
Still drifting.

chris_c
Posts: 966
Joined: June 28th, 2014, 7:15 am

### Re: Searching algorithms

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.
Here is a messy solution involving Corderships. You always get some junk at distance roughly X/2 and then based on which glider is returned, the UC would send a repair salvo to turn the junk back into the correct constellation of longboats.

Code: Select all

``````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!
``````

dvgrn
Moderator
Posts: 7986
Joined: May 17th, 2009, 11:00 pm
Contact:

### Re: Searching algorithms

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.
Yes, that would have to be the first stage of Calcyman's Build-Anything-You-Want-With-N-Gliders design. Then if the recipe is Gödel-encoded, there will have to be a second stage where the resulting binary number is factored to retrieve the actual string of integers.

I wouldn't worry too much about the specific encoding, though. If you pack more information into a shorter encoded sequence, you just tend to make each individual integer bigger. So if you're encoding, say, PULL 9, FIRE GLIDER PARITY0, PULL 6, FIRE GLIDER PARITY1, that could be

enc(9,0,6,1) = 2^9 * 3^0 * 5^6 * 7^1 = 5.6*10^7

The equivalent encoding using the X/2 and X mod 2 trick would be

enc(9*2+0, 6*2+1) = enc(18,13) = 2^18 * 3^13 = 4.18*10^11

-- much bigger, even though the prime bases are smaller. Or we could use as many zeroes in the prime exponents as possible, and store the same information as

1000000000000000000100000000000001

The 20th prime is 71, and the 34th is 139, so we could place the block at (19738, 19738) and build a decoder to retrieve that same information.

-- But why are we bothering with Gödel-numbering at all? If we're going to get a binary number out in the end, why not put the block at (8589950977, 8589950977) and get the above binary string out directly? Wouldn't need the horrible prime-factorization computation machinery after all.

In that case, there's no need to maximize the number of zeroes in the binary string, so maybe an encoding like this would be better:

11111111110111111100

-- block at (1048060, 1048060).

Then the biggest remaining problem is that we really need to be able to encode negative numbers -- PULL as well as PUSH operations.

... But maybe it would be simpler to have only four instructions -- no need to encode negative numbers then. FIRE PARITY0 GLIDER = 00, FIRE PARITY1 GLIDER = 01, PULL1 = 10, PUSH1 = 11, and just promise to always start with a PULL or a PUSH:

10 10 10 10 10 10 10 10 10 00 10 10 10 10 10 10 01

That might minimize the amount of circuitry needed in the universal constructor, which is really the important thing. Without the prime-factorization mechanism, the universal constructor will have a much smaller glider synthesis -- which is the important thing, really, not the efficiency of the recipe encoding. For any nontrivial recipe the sliding block is going to end up so far away anyway that a few million orders of magnitude one way or another won't matter in the least (!).
simsim314 wrote:EDIT2 This is pretty amazing - constant cells universal constructor (meaning one can encode caterpillar using around few K cells).
Well, don't get too carried away. You'd encode a Caterpillar with the position of a single block, but I'm not sure the sliding-block memory, binary counter, recipe decoder and universal constructor with self-destruct mechanism can be packed into a few thousand cells.

A few tens of thousands, maybe. That would give a surprisingly low upper bound on the value of N. Maybe the Gemini spaceship can be built with fewer gliders than the known recipe...!

Someone would still have to write a compiler to build a slow-salvo-constructible seed for the existing Gemini recipe, though -- or find a glider construction for the Caterpillar, if that's to be the target. Either one would be a pretty tall order.

(And no, Golly could never run any such pattern to completion, even with a relatively small sliding-block-encoded recipe. It would make the most sense to add a special algorithm that only works with sliding block memory patterns, binary counters, and universal construction arms -- then there might be a chance of seeing the whole thing working. It would be a bit of a fake... but it's not as if Golly runs every generation of Hashlife-based patterns anyway.)

calcyman
Posts: 2418
Joined: June 1st, 2009, 4:32 pm

### Re: Searching algorithms

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.
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
``````
What do you do with ill crystallographers? Take them to the mono-clinic!

dvgrn
Moderator
Posts: 7986
Joined: May 17th, 2009, 11:00 pm
Contact:

### Re: Searching algorithms

Ah, I see simsim314 already thought of the two-bits-per-operation idea.

Never mind about the self-destruct mechanism for the universal constructor, by the way -- you'll get a smaller N if you just shoot down the U.C. circuitry from very very very very far away, after the construction stage is done, probably with one glider for each catalyst or thereabouts. 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.

...A ridiculous idea, but technically it's still a glider recipe.

calcyman
Posts: 2418
Joined: June 1st, 2009, 4:32 pm

### Re: Searching algorithms

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.
What do you do with ill crystallographers? Take them to the mono-clinic!

simsim314
Posts: 1769
Joined: February 10th, 2014, 1:27 pm

### Re: Searching algorithms

calcyman wrote:You can just use two SBM registers, in the way that the pi calculator works for doing logical right shifts:
I actually have hard time to figure out the pi calculator design, and the SBM register.

Can you give some link/introduction to this topic?

It shouldn't be too hard to design something specific for this task - or maybe you can provide specific design?

dvgrn
Moderator
Posts: 7986
Joined: May 17th, 2009, 11:00 pm
Contact:

### Re: Searching algorithms

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.
You're right, of course. Takes twice as long to extract the data, but it already takes forever and a day -- why not twice forever and two days?

Both SBMs will need INC as well as DEC operations, so that's a little bigger than a single DEC-only SBM -- but tiny no doubt compared to a full binary counter.

Probably time to build a new Spartan SBM, though. Looks like the circuitry in the pi and phi calculators is only mostly Spartan. (And look at all those boojum reflectors instead of rectifiers! That's like seeing old ceramic insulators in your house wiring...)

EDIT: Come to think of it, there's no reason why the SBMs and the universal constructor have to be Spartan -- though it might be simpler all around if they were. In this application the U.C. doesn't have to construct itself. It's only constructing the final target object.

So... there are definitely some welded catalysts in various Herschel conduits that should be forbidden, since they'd be painful to construct and annoying to work around. But an occasional eater2 or even an isolated Snark would be fine, if it allows for significantly more efficient mechanisms.

I suspect that Spartan circuitry will turn out to give a lower total N-value -- cheaper to construct and cheaper to destroy when its work is done, and who cares if it's a little bulkier? But I could be wrong. The optimization problem might make for an interesting competition.

simsim314
Posts: 1769
Joined: February 10th, 2014, 1:27 pm

### Re: Searching algorithms

Сan someone explain how SBM works, or link to some article that explains it?

-----

I think I have the basic idea how to construct pretty fast integer converter.

For the parity reader, one need to send gliders to collide with SL and leave the SL but will shoot two gliders back. Now one can use this simple fact: in the following gliders position if the distance is even the left reaction will shoot back a glider, if odd the right one.

Code: Select all

``````x = 42, y = 22, rule = B3/S23
2\$10bo\$9bo28bo\$9b3o25bo\$37b3o8\$4b2o\$3bobo\$5bo25b2o\$30bobo\$32bo!
``````
After acordingly left or right glider came back, we can shoot glider salvo accordingly to fix the remaining debris.

---

As for division, what we actually need is "timer". This means that we could measure time that pass from the moment glider has been shot and was returned, and according to this timing we could shoot a glider after T * alpha time (where alpha can be varied).

This is done simply by using two recipes for block push and block pull. While block push will be made at speed X block pull will be done at speed 2 * X, thus measuring the timing of T / 2 (for example).

Actually this solution will force us to use division by numbers higher than 2, because the recipes are periodic, and this will limit us to work with division by this period, but this shouldn't be such a big issue, as the relative pull and push operations speed should be easy to adjust.

One can use something like period 30 and division by 30, so the recipes will be of type b1 + 30 * (b2 + 30 * (b3 + ... etc. where b1, b2, b3... are binary numbers (that correspond to left or right gliders as mentioned above).

dvgrn
Moderator
Posts: 7986
Joined: May 17th, 2009, 11:00 pm
Contact:

### Re: Searching algorithms

simsim314 wrote:Сan someone explain how SBM works, or link to some article that explains it?
Start with the original article for Dean Hickerson's sliding-block memory from 1990. I see there's no LifeWiki article for "sliding-block memory" yet, though it's been requested.

The demonstration pattern is based on p120 guns, which could be replaced by new Spartan p120 guns if that turned out to be a good idea. There's quite a bit of surplus circuitry designed to feed signals in to demonstrate the SBM.

Code: Select all

``````#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!``````
This could be switched over to stable Spartan-ish circuitry instead. Probably the two-glider pull, three-glider push, and zero test reactions would remain the same -- unless someone can find a two-glider PUSH and two-glider PULL, presumably with some common object other than a block. (A blinker or traffic light, possibly?)

simsim314
Posts: 1769
Joined: February 10th, 2014, 1:27 pm

### Re: Searching algorithms

dvgrn wrote:Start with the original article for Dean Hickerson's sliding-block memory from 1990.
OK thx. So assuming we have block at distance 2D (after reading the parity), what we need to do is just to call "pull" operation D times. Because the time it takes for glider to reach the block and come back is 16D (f2D+b2D/(c/4)) we can trigger a p16 slider gun after parity reading (or making two cycles with p32 slider gun), and move the block by D.

Any small adjustments can be made by glider salvo triggered by the returning glider.

So lets review the order of operations:

1. We have remotely located block at distance d.
2. We send glider salvo that will split the block into two blocks with two returning gliders.
3. Another salvo with two gliders will determine the parity of the block location. One glider will return to the "base" the other will destroy the block that was behind the glider at splitting time. The returning glider will indicate the parity of the block location.
4. Depending on the returning glider we trigger our slow salvo mechanism.
5. The returning glider also triggers salvo that fixes the state of the "ruined" block, by this read operation.

----

Move d/2:

1. After the reading glider is returned, with some constant delay we send salvo that will split the block into blockA and blockB and return a glider.
2. In the same time (with short delay) we trigger the pull operation p32 slider gun, that will operate on blockA.
3. The returned glider after 8d iterations will make another loop, and will be reflected again from blockB but now destroying it.
4. The glider returned from blockB will stop the slider gun pull operation, after exactly 16d ticks applying exactly d/2 pull operation
5. Except of stopping the pulling, we also need to make small adjustments to the blockA, to make it compatible with the initial lane of operation 1 for read parity.
6. We trigger with some constant delay read parity salvo.

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

So to make it look a little bit simpler we have 4 trigger gliders:

1. Gliders returning from parity reading. Triggers:
- Slow salvo operation.
- Fix to the read operation salvo.
- Block splitting salvo to blockA and blockB including new returning glider
- Activation of slider gun that operates on blockA

2. The glider that was returned by splitting operations. Triggers:
- New glider salvo that will destroy blockB and return new glider.

3. Glider that returned from the blockB. Triggers:
- Slider gun deactivation.

Thus closing the loop with only 3 trigger gliders and 8 salvos.

Kazyan
Posts: 1105
Joined: February 6th, 2014, 11:02 pm

### Re: Searching algorithms

I've been following this discussion and thinking about this question. I'm not quite up to speed on how universal constructors work, so bear with me if any of this is retreading old ground. This is how I imagine this all to work, and a lot of it is taking notes from Simkin:

The basic idea is the use of a base X counter, where X is the number of diagonals between the leftmost and rightmost gliders in a particular monochromatic p1 slow salvo. Since it has been shown that a slow salvo can be equivalent to a traditional synthesis given a frankly silly amount of time and gliders, I think this case could also be reduced to a monochromatic p1 slow salvo as well. The base X counter ticks up its stored integer every Y generations, where Y is whatever number turns out to be the cheapest in terms of primordial gliders--probably a multiple of 30 or 46.

The base X counter would work roughly like this:
• A pY shotgun reels in a block, using a method somewhat like that of the Parabolic Oscillator, except that the salvo would be one does not push back the "source" block--it leaves it in place. Once the "reel" block is pulled in by X diagonals, a constructible sparky oscillator (or oscillator set) converts it into a glider going off at a 90 degree angle to the shotgun's salvos. The shotgun's salvos continue firing, repeatedly peeling a new "reel" block off the "source" block and letting the oscillators shunt it away as a glider. Note that X is adjustable--if it needs to be higher, we'll just move the "source" block further away.
• This glider stream is fed into a glider-to-salvo converter, which works by suppressing the output of a fully-built shotgun with a single pY stream, and allowing the input to poke holes through the p120 stream that will allow one salvo of the shotgun through per glider.
• The salvos of the second shotgun will hit a "source" block, and peel back a "reel" block.
• Chain these units as necessary in a diagonal line.
It's basically this:

Code: Select all

``````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!``````
Except that instead of semi-snarks counting in binary (0 for one position of the internal block and 1 for the other), the repeatable unit "digits" count from 0 to X-1, and it's along a diagonal line instead of an orthogonal one.

Each digit should also come with a series of still lifes. If, at the start of the chain of digits, a glider is applied at the right location with the right timing, the SLs will destroy the digit a la Seeds of Destruction--with the exception of the siding "reel" block inside--and send another glider out perpendicularly from the digit chain. This glider will travel for ~10^6 generations (we can increase this if necessary for the slow salvo, but it has to be the same number for each digit), then hit a set of splitters and OTTs sufficient to send a salvo back at the "reel" block and another glider at the next digit. The next digit will start activating its self-destruct sequence, and the salvo will delete the "reel" block and send a new glider traveling in the direction opposite the direction of the self-destruct fuse we've ignited. In this way, firing one glider at the digit chain causes it to convert itself into a p1 monochromatic slow salvo, the lane of each glider corresponding to the position of the "reel" block inside each digit.

Here's how it all works:

Step 1: Primordial gliders synthesize a rake/puffer army whose output is the chain of digits, complete with their self-destruct fuse and OTT/splitter relays. Because the digits are all structurally the same, we can get arbitrarily many of them out of this army of puffers.
Step 2: Once the army of puffers has gone on for as many digits as we need, some primordial gliders destroy it.
Step 3: Primordial gliders create the input gun that activates the counter. The digits start doing their thing.
Step 4: We let the digits count up until the reel blocks are placed so as to generate the p1 monochromatic slow salvo we need, minus whatever delay from signal travel time that we'll have to account for in step 5.
Step 5: Some primordial gliders arrive to destroy the input gun
Step 6: A primordial glider triggers the self-destruct sequence of the digit chain. The digit chain converts itself into the p1 monochromatic slow salvo.
Step 7: Two primordial gliders create the block target for the slow salvo.
Step 8: The slow salvo synthesizes whatever we need it to.

At no point during this process do we need any more than a fixed number of primordial gliders. To find that fixed number, we just have to build the digit chain, the army of puffers (for arbitrary X), and then synthesize the army of puffers.

Any suggestions? It seems a bit elaborate for something that decodes time into a salvo, but it works.
Tanner Jacobi
Coldlander, a novel, available in paperback and as an ebook. Now on Amazon.

Bullet51
Posts: 572
Joined: July 21st, 2014, 4:35 am

### Re: Searching algorithms

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
``````
Since there are 4 different signals, why not use int(x/4) and x mod 4?
The code will be like:
label2:
cmp %%rbx, \$0
je label3
dec %%rbx
cmp %%rbx, \$0
je label4
dec %%rbx
cmp %%rbx, \$0
je label5
dec %%rbx
cmp %%rbx, \$0
je label6
dec %%rbx
inc %%rax
jmp label2

which label 3-6 represent different mod 4 values.
Still drifting.