## Searching algorithms

For general discussion about Conway's Game of Life.

### 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.

gmc_nxtman

Posts: 1147
Joined: May 26th, 2015, 7:20 pm

### 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.

dvgrn
Moderator

Posts: 5634
Joined: May 17th, 2009, 11:00 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.

simsim314

Posts: 1685
Joined: February 10th, 2014, 1:27 pm

### Re: Searching algorithms

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

Posts: 523
Joined: July 21st, 2014, 4:35 am

### 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.

simsim314

Posts: 1685
Joined: February 10th, 2014, 1:27 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.

gmc_nxtman

Posts: 1147
Joined: May 26th, 2015, 7:20 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.

simsim314

Posts: 1685
Joined: February 10th, 2014, 1:27 pm

### 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.

dvgrn
Moderator

Posts: 5634
Joined: May 17th, 2009, 11:00 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!

calcyman

Posts: 2031
Joined: June 1st, 2009, 4:32 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?

simsim314

Posts: 1685
Joined: February 10th, 2014, 1:27 pm

### 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.

dvgrn
Moderator

Posts: 5634
Joined: May 17th, 2009, 11:00 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).

simsim314

Posts: 1685
Joined: February 10th, 2014, 1:27 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.

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.
Bullet51

Posts: 523
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.

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.

`x = 954, y = 344, rule = B3/S23950b2o\$950bobo\$951bobo\$952bo5\$742b2o\$742bobo\$743bobo\$744bo5\$534b2o\$534bobo\$535bobo\$536bo5\$326b2o\$326bobo\$327bobo545b2o\$328bo546bobo\$876bobo\$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\$68bobo197bobo197bobo197bobo12\$116b2o198b2o198b2o198b2o\$117b2o198b2o198b2o198b2o\$116bo199bo199bo199bo18\$84b2o198b2o198b2o198b2o\$85b2o198b2o198b2o198b2o\$84bo199bo199bo199bo5\$24b3o197b3o197b3o197b3o\$25bo199bo199bo199bo\$22bo2bo196bo2bo196bo2bo196bo2bo\$22bo2bo196bo2bo196bo2bo196bo2bo\$22bobo197bobo197bobo197bobo\$8b2o198b2o198b2o198b2o\$8b2o198b2o198b2o198b2o3\$25bo199bo199bo199bo\$24bobo197bobo197bobo197bobo\$25bo199bo199bo199bo\$8bo199bo199bo199bo\$2o7bo190b2o7bo190b2o7bo190b2o7bo\$2o22b4o172b2o22b4o172b2o22b4o172b2o22b4o\$11bo10bo3b2o183bo10bo3b2o183bo10bo3b2o183bo10bo3b2o\$9bobo9bo4bo182bobo9bo4bo182bobo9bo4bo182bobo9bo4bo\$10bo10b2obo185bo10b2obo185bo10b2obo185bo10b2obo\$23bo199bo199bo199bo3\$10b2obobo194b2obobo194b2obobo194b2obobo\$13bobo16bo180bobo16bo180bobo16bo180bobo16bo\$10bo2bo17b3o176bo2bo17b3o176bo2bo17b3o176bo2bo17b3o\$10bo3bo195bo3bo195bo3bo195bo3bo\$7b2o2b4o16b3o173b2o2b4o16b3o173b2o2b4o16b3o173b2o2b4o16b3o\$6b2o5bo14b2ob2o173b2o5bo14b2ob2o173b2o5bo14b2ob2o173b2o5bo14b2ob2o\$8bo21bo177bo21bo177bo21bo177bo21bo3\$54b3o197b3o197b3o197b3o\$55bo199bo199bo199bo\$52bo2bo196bo2bo196bo2bo196bo2bo\$52bo2bo196bo2bo196bo2bo196bo2bo\$52bobo197bobo197bobo197bobo\$38b2o198b2o198b2o198b2o\$38b2o198b2o198b2o198b2o\$33bo199bo199bo199bo\$32b3o197b3o197b3o197b3o\$31b2ob2o19bo175b2ob2o19bo175b2ob2o19bo175b2ob2o19bo\$33bobo18bobo176bobo18bobo176bobo18bobo176bobo18bobo\$35bo19bo179bo19bo179bo19bo179bo19bo3\$54b4o196b4o196b4o196b4o\$38bo13bo3b2o180bo13bo3b2o180bo13bo3b2o180bo13bo3b2o\$37bobo11bo4bo180bobo11bo4bo180bobo11bo4bo180bobo11bo4bo\$39bo11b2obo184bo11b2obo184bo11b2obo184bo11b2obo\$36b2o15bo182b2o15bo182b2o15bo182b2o15bo\$36bo199bo199bo199bo\$37b3o197b3o197b3o197b3o\$37b2o198b2o198b2o198b2o\$41bo199bo199bo199bo\$40b2o198b2o198b2o198b2o\$40b2o198b2o198b2o198b2o\$42b2o6b2o190b2o6b2o190b2o6b2o190b2o6b2o\$44b2o4b2o192b2o4b2o192b2o4b2o192b2o4b2o\$42bob2o196bob2o196bob2o196bob2o\$42b2o198b2o198b2o198b2o5\$42b2o198b2o198b2o198b2o\$42b2o198b2o198b2o198b2o!`
chris_c

Posts: 892
Joined: June 28th, 2014, 7:15 am

### 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.)

dvgrn
Moderator

Posts: 5634
Joined: May 17th, 2009, 11:00 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:

`// Move rax into rbx:label1:cmp %%rax, \$0je label2dec %%raxinc %%rbxjmp label1// Move floor(rbx/2) into rax:label2:cmp %%rbx, \$0je label3dec %%rbxcmp %%rbx, \$0je label4dec %%rbxinc %%raxjmp label2// Do something if least significant bit was zerolabel3:(...)jmp label1// Do something if least significant bit was onelabel4:(...)jmp label1`
What do you do with ill crystallographers? Take them to the mono-clinic!

calcyman

Posts: 2031
Joined: June 1st, 2009, 4:32 pm

### 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.

dvgrn
Moderator

Posts: 5634
Joined: May 17th, 2009, 11:00 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!

calcyman

Posts: 2031
Joined: June 1st, 2009, 4:32 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?

simsim314

Posts: 1685
Joined: February 10th, 2014, 1:27 pm

### 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.

dvgrn
Moderator

Posts: 5634
Joined: May 17th, 2009, 11:00 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.

`x = 42, y = 22, rule = B3/S232\$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).

simsim314

Posts: 1685
Joined: February 10th, 2014, 1:27 pm

### 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.

`#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/S2364b2o21b2o89b2o20bo\$63b3o21bo91bo19bobo\$60bob2o15bo5bobo91bobo7b2o6b2o3bo\$53b2o5bo2bo8b3o4bobo3b2o93b2o6bobo4b2obo3bo9b2o\$53b2o5bob2o16bobo8bo83bo11b3o4b3obo3bo9b2o\$63b3o2b2o2bo7bo2bo5b3o83b3o8b3o4bo2b2obobo\$64b2o2bo3bo7bobo5bo89bo8b3o4b2o4bo\$69bo2bo6bobo6b2o87b2o9bobo\$69b2o8bo109b2o2\$68bo134bo\$67b2o132bobo\$52bo8bo5bobo132b2o10bo\$52b3o6bobo113b2o3b2o28b3o\$55bo5b2o114bo5bo27bo\$54b2o155b2o\$84b5o89bo3bo\$26b2o55bob3obo89b3o\$17b2o8bo28b3o25bo3bo\$17b2o8bobo8b2o16b3o26b3o115bobo\$28b2o7bobo15bo3bo26bo101b2o13b2o4bo\$36bo17bo5bo2bobo123b2o13bo3b3o\$36bo2bo15bo3bo4b2o122bo19b3o\$36bo19b3o5bo\$37bobo5b2o41bo94bo22b2o3b2o\$33bo4b2o5bobo40bo92bobo22b2o3b2o\$34bo12bo33bo5bobo92b2o\$32b3o12b2o32bobo2b2ob2o\$71bo9b2o2bo5bo86bo\$14b2o3b2o51b2o14bo88b3o\$71b2o12b2o3b2o84b5o\$15bo3bo39b2o114b2o3b2o24b2o\$16b3o40bo116b5o26bo\$16b3o22bo18b3o11bo14bo86bo3bo23b3o\$27bo11bobo11b2o7bo10bo15bo87bobo8bobo13bo\$25bobo12b2o11bo19b3o14bo87bo9b2o\$19bo6b2o23bobo135bo\$18b3o30b2o18b2o33bo87b2o\$17bo3bo24b2o24bo14b2o17b4o68b2o14bo\$19bo28bo20b3o15b2o18b4o7bo59b2o15b3o\$16bo5bo25bo20bo23bo13bo2bo6bobo77bo\$16bo5bo21bo3bo42b3o13b4o4b2o3bo\$17bo3bo22bo45bo7b2o6b4o5b2o3bo\$18b3o24b3o10b2o19b2o9b2o5bobo6bo8b2o3bo\$59bo19bo5bo11bo19bobo8b2o\$59bobo7bo7bobo4bo11b2o20bo9bobo\$60b2o7b4o4b2o5b3o20bobo20bo\$70b4o33b2o21b2o\$27bo10bo31bo2bo34bo\$27b2o9b2o30b4o\$16b2o5b2o3b2o7bobo4bo24b4o\$17bo10b3o13bobo22bo\$14b3o11b2o15bobo4b2o58b2o\$14bo5b2o5b2o16bo2bo3b2o31b2o3b2o20bobo\$19bobo5bo17bobo39b3o22bo\$19bo24bobo16bo22bo3bo37bo\$18b2o24bo19bo22bobo38b3o\$62b3o4bobo16bo42bo\$70b2o58b2o\$70bo14b2o\$86bo32b3o\$83b3o33bo\$58bo24bo36bo\$4b2o21bo30b3o\$5bo21b2o32bo68b2o3b2o21bobo\$5bobo7b2o11b2o30b2o68bobobobo21b2o\$o5b2o6b3o3bo7b3o7b2o91b5o23bo\$3o8bob2o4b4o5b2o8b2o87b2o3b3o\$3bo7bo2bo4bo4bo2b2o98bobo3bo\$2b2o7bob2o5bo3bo2bo22bo40b2o19b2o13bo\$14b3o3b2obo24b3o41bo19bo\$15b2o30bo15bo28bobo6b2o7bobo\$38b3o6b2o13b3o28b2o6b3o6b2o\$40bo20b5o37b2obo7bo\$28bobo8bo20bobobobo9b2o25bo2bo7b2o\$2b2o3b2o20b2o29b2o3b2o8bo2bo24b2obo6bobo\$2b2o3b2o20bo14b3o27bo4bo21b3o26b3o\$75b4o22b2o26b2ob2o58b3o\$4b3o37bobo82b2ob2o29b2o27bo\$4b3o36b5o81b5o29bo4bo24bo\$5bo10bo25b2o3b2o27b2o50b2o3b2o15bo10bobo4b3o\$16bobo23b2o3b2o11b2o14b2o71bobo9b2o8bo\$16b2o19b2o22bo86bob2o18b2o\$37bobo18b3o25b2o59b2ob2o\$39bo4b2o12bo26bobo60bob2o\$39b2o2b2ob2o39bo5bo50b2o3bobo7bo\$7bo36bo2bo46bo48bobo4bo6b2o\$8b2o13b3o18bo47b3o4bobo7b2o17b2o13bo14b2o\$7b2o16bo21bo52b2o7b2o18bo12b2o26b2o3b2o\$24bo20b2o53bo25b3o41b2o3b2o\$2b3o121bo\$bo3bo160b3o3b3o\$o5bo26b2o5b2o3b2o119bo5b3o\$o5bo26bo7b5o5bo98bobo14bo5bo\$3bo12b2o4bobo6bobo8b3o7b2o74bobo19b2o\$bo3bo11bo4bo2bo5b2o10bo7b2o75b2o6b2o13bo\$2b3o10bobo7b2o102bo7bo\$3bo19bo3b2o108bobo20b2o\$25b2o111b2o21b2o\$14b2o6bo2bo134bo9b3o\$3b2o8bobo6bobo88bobo54b3o\$3b2o8bo100b2o53bo3bo\$12b2o93bo6bo\$43b2o63b2o35b2o21b2o3b2o\$43b2o62b2o36bobo\$145bo\$87b2o\$88b2o\$87bo11b6o30bobo\$52bo45bo6bo29b2o16b2o8bo75bo\$51b2o44bo8bo29bo16bo2bo6bobo71b3o\$50b2o4b2o5bo34bo6bo42b2o2bo3bo7bobo6b2o61bo\$40b2o7b3o4b2o3bobo35b6o42b3o2b2o2bo7bo2bo5bo62b2o\$40b2o8b2o4b2o2bobo11b2o61b2o5bob2o16bobo7b3o\$51b2o6bo2bo11b2o61b2o5bo2bo8b3o4bobo3b2o5bo\$52bo7bobo53bo27bob2o15bo5bobo43b2o\$61bobo52b2o29b3o21bo43b2o\$63bo51bobo30b2o21b2o\$42b2o\$44bo170bo\$31b2o12bo168b3o\$31b2o4bo7bo167bo3bo\$28b2o5b2o8bo169bo\$27b3o5bo2b2o4bo7b2o158bo5bo\$28b2o6b5ob2o8bobo157bo5bo\$22b2o7b2o4bo16bo78b2o78bo3bo\$21bobo7b2o21b2o77b2o79b3o\$21bo19bo\$20b2o17b2o178b2o\$40b2o3bo174b2o\$45bo173bo\$90bo\$90b3o\$93bo\$92b2o2\$17bo35bo3b2o158bo\$17b3o31bobo4b2o156b3o\$20bo31b2o3bo158b3o\$19b2o\$214b2o3b2o\$214b2o3b2o2\$50bo50b3o\$50b2o49bo\$49bobo34bo15bo\$13b2o13bo2bo8bo20b2o23b2o\$14bo13bo10bobo19bo23bobo\$14bobo7bo2bo3b2o5bo3b2o8bo6bobo\$15b2o4b4o3b2obobo4bo3b2o5b4o6b2o155b2o\$20b4o14bo3b2o4b4o57b2o105b2o\$20bo2bo8b2o5bobo6bo2bo16bo40bobo\$20b4o16bo7b4o16b3o15b2o21bo\$21b4o24b4o18bo14b2o\$24bo27bo17bo\$70bo2bo\$74bo\$61bo10bo\$59b3o54b3o9b2o\$58bo57bo9bo2bo\$58b2o11bo39bo5bo7bo\$71b2o36b4o12bo11b2o\$70bobo11b2obob2o12b2o3bobob2o11bo11b2o\$79b3o21b2o2bo2bob3o11bo2bo\$79bo4bo5bo17bobob2o14b2o\$80bo28b4o\$85b2ob2o21bo\$55b3o29bo\$54bo3bo4b2o\$53bo5bo4b2o\$53bo5bo3bo21bo\$56bo27bobo\$54bo3bo24bo3bo\$55b3o25b5o\$56bo25b2o3b2o\$83b5o\$53b2o29b3o\$54bo4b3o23bo\$51b3o5bo\$51bo8bo6bo\$65b2o\$66bobo\$68b2o\$70bo8bo\$67bo10bobo6b2o\$63bo2bo3b2o5bo3b2o4bo\$60b4o3b2obobo4bo3b2o5b3o\$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?)

dvgrn
Moderator

Posts: 5634
Joined: May 17th, 2009, 11:00 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.

simsim314

Posts: 1685
Joined: February 10th, 2014, 1:27 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:

`x = 152, y = 73, rule = B3/S2376bo23bo23bo23bo\$74b3o21b3o21b3o21b3o\$73bo23bo23bo23bo\$65b2o6b2o14b2o6b2o14b2o6b2o14b2o6b2o\$65bobo21bobo21bobo21bobo\$66bo23bo23bo23bo2\$71b2o22b2o22b2o\$71b2o5b2o15b2o5b2o15b2o5b2o22b2o\$78b2o22b2o22b2o14b2o6b2o\$142b2o2\$61b2o22b2o22b2o22b2o\$61b2o22b2o22b2o22b2o2\$76b2o22b2o22b2o22b2o\$67b2o7bobo21bobo21bobo21bobo\$68b2o8bo23bo23bo23bo\$67bo10b2o22b2o22b2o22b2o6\$31b2o\$31b2o5b2o\$38b2o50b2o22b2o22b2o\$90bo23bo23bo\$88bobo21bobo21bobo\$7b2o8b2o17b2o50b2o22b2o22b2o\$7b2o9bo17b2o\$18bobo21b2o29b2o22b2o22b2o\$19b2o21b2o29b2o22b2o22b2o\$b2o\$b2o\$5b2o27b2o54b2o22b2o22b2o\$5b2o76b2o5b2o22b2o15b2o5b2o\$83b2o46b2o2\$78bo23bo23bo\$2o75bobo21bobo21bobo\$2o75b2o6b2o14b2o6b2o14b2o6b2o\$85bo23bo23bo\$86b3o21b3o21b3o\$88bo23bo23bo2\$13bo20b3o\$11b2o21bo\$12b2o19b3o4\$7b2o\$8bo\$5b3o\$5bo41b2o\$47b2o4\$42b2o\$42b2o\$46b2o\$46b2o\$5b2o21b2o\$5b2o21bobo\$11b2o17bo9b2o\$11b2o17b2o8b2o3\$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

Kazyan

Posts: 819
Joined: February 6th, 2014, 11:02 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:

`// Move rax into rbx:label1:cmp %%rax, \$0je label2dec %%raxinc %%rbxjmp label1// Move floor(rbx/2) into rax:label2:cmp %%rbx, \$0je label3dec %%rbxcmp %%rbx, \$0je label4dec %%rbxinc %%raxjmp label2// Do something if least significant bit was zerolabel3:(...)jmp label1// Do something if least significant bit was onelabel4:(...)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.
Bullet51

Posts: 523
Joined: July 21st, 2014, 4:35 am

Next