ConwayLife.com

I was playing aound in Golly. I simulated a breeder for a while and then perturbed it. A chain of chaos destroyed most of the glider guns created. One of the glider guns survived, but it had a lot of broth in in its path. However, the gliders cleared a path and eventually went out to the open, with the glider gun never being destroyed.

This gave me inspiration on how to make a self-replicator that can survive in a random broth. The idea is that a it is possible to clear a narrow path simply by shooting gliders onto it. Therefore, a suitable construction might be able to create a long path, and then build something on the other end. In larger constructions there may be many of these paths between different centers.

Some things to think about:

[*] Does shooting gliders on path cleared out of the broth lengthen or shorten the path on average? If it shortens the path, this sort of plan is doomed. Does it depend on the period?
[*] What period clears out the path quickest? Alternatively, what non-periodic pattern clears out the path quickest?
[*] Can the path be made wider? This way gliders with different alignments can go along the same path. This is useful both for having more flexibility in building on the other end and for ensuring an eater doesn't get in the way. Again, what glider pattern is optimal for building such a path.
[*] Is clearing out an area on the other end actually possible? Bolded because this one seems more important. It would definitely be very difficult.

Not always. There are structures known as "crystals", which are periodic, glider-caused growths that slowly move towards the source of the gliders. That usually spells death for the gun.

itaibn wrote:Does shooting gliders on path cleared out of the broth lengthen or shorten the path on average?

As Extrementhusiast mentions, for slower even periods there's a common crystal that forms as soon as the lead glider hits the wrong kind of block. So you'd probably want to use an odd period -- maybe do some experiments to see which period seems to work best on average.

itaibn wrote:Can the path be made wider? This way gliders with different alignments can go along the same path. This is useful both for having more flexibility in building on the other end and for ensuring an eater doesn't get in the way. Again, what glider pattern is optimal for building such a path.

Punching through junk won't always work with a single glider lane. For example, you're in trouble as soon as the glider stream hits an eater or any boat-bit catcher. Might be better to experiment with pairs of gliders on lanes separated by one to ten cells -- there will still be unlucky eater or crystal-building constellations out there somewhere, but they'll be pretty rare.

Universal construction is possible with glider pairs with most possible offsets from 0hd {half diagonals} to 10hd, so after running a cleanout pattern with your chosen lane offset for a long time, you could push an elbow block some distance out along the hopefully clear path. Should probably pick a lane pairing that has a very narrow elbow push reaction -- otherwise you'll hit junk along the edges of the clear path most of the time. But I don't see any other good way to get a construction elbow out into the area to be cleared...

itaibn wrote:Is clearing out an area on the other end actually possible?

Here again, it seems very unlikely that a foolproof method can be found. I've always said that I'd much rather take the challenge of breaking someone else's foolproof cleanup method, than have to come up with a cleanup reaction myself! But it doesn't have to be foolproof -- it just has to fail less than one time in two, so that on average the number of replicators will still increase. Something like this would be much more likely to be viable in ash from a "sparse Life" random soup, where the initial conditions were much less than 50% ON cells.

Even so, the only thing that I could imagine might work would be a constructed reaction that, in empty space, makes a spark and returns a glider to the elbow area, where a one-time turner is waiting to send the signal back along the clear path to the parent replicator. The parent replicator would very slowly, one cell at a time, fire off this exploratory spark next to every location that needs to be clear for the final construction. If at any point the return glider doesn't come back when it's supposed to, the replicator would go back to path-clearing mode, then push out a new elbow, and then start the spark-testing of cells again from the beginning.

The trick will be to find a spark that reliably destroys or reduces the largest possible number of common still lifes -- blinkers, blocks, beehives, and ships, let's say. Some sparker reactions will certainly be better than others; it's not at all clear than any reaction will be good enough to reduce random ash to vacuum on average, but it does seem just barely possible. The idea would be that if something unexpected shows up and causes a big explosion, at least that will change the uncommon object into more random ash... which, the next time around, is fairly likely to be common junk that the sparker can handle.

Again, there's no possible way to make this work really reliably. In particular, it's possible to design constellations that will create fake return gliders when a test spark goes off near them, so the replicator would complete its cycle and start constructing a copy of itself on the assumption that the area was really cleaned out -- with inevitable disastrous results.

But very likely even simple random variation in the ash will be too much for any possible sparker reaction to handle -- there will be explosion after explosion, leading to repeated restarts of the cleaning process, and the replicator will never get anywhere. There are so many possible objects that show up in random ash... it takes a lot of faith, trust, pixie-dust and hand-waving to imagine that there's a test spark that would reliably reduce even a majority of them, without causing major explosions that would amount to "one step forward, two steps back" in the cleaning process.

This is possible in B35/S347.
You need to have a random stream of gliders. Maybe a vacuum cleaner that throws random gliders could work.
Take a look in the attachment:

Very cool idea. To get around the problems of common crystals and eaters, maybe you could use a pseudo-random stream of gliders in very close or overlapping lanes.

I'm not worried about crystals. I'm assuming a relatively high-density soup. The crystals I've seen are thicker the glider paths that construct them, so they would eventually be disrupted by still-lifes in the soup. Then again, just like how gliders might be able destroy all the debris in its path, a crystal be disrupted temporarily but continue expanding in the long run... (light bulb goes off) ...which would be an excellent way to make a wide path if the crystal can be reliably destroyed later.

Another idea: the area cleared off need not be very big. You can have a construction which consists only of these narrow paths with simple logic gates at their intersections. Then the area cleared off need only be the size of a single logic gate. Even a naive solution such "Assume the gate is there until it actually is" may work. While existing reflectors are pretty big, but an object that turns a specific salvo of gliders into a sideways glider are much smaller. But this makes the problem of duplication only more significant.

One technique that may be useful is pinging: If you shoot a glider along a path, it has a small chance of returning a glider along the same path. This may be used to determine how long the path actually is. If this is tried multiple times and no glider ever returns, then you know that you have hit an eater or crystal.

I did some experiements. First, I created a large soup and shot created many gliders from one point. I would wait an even number of steps between gliders, and would only create one when the dust from the last settled down. This is to simulate a gun with a large even period. The chaos caught up with the glider creation spot twice, but the gliders eventually escaped, clearing out a length of about 460 tiles. During that time there were two 'pings': Gliders going backwards along the cleared path. What I found was very dangerous though were almost-pings, where a glider returns slightly out and gunks up an earlier part of the path. Perhaps to stop these a lower period would be better. I also saw many crystals form; as I suspected, they would eventually get disrupted. Overall I am confident in the ability of gliders to form paths.

I also experimented with LWSSs; they seem not to be able to form paths. I also tried a short experiment with shooting two gliders one tile off in alignment. This seems more promising. I feel this should be done programmaticly if we study this further.

Also, a calculation based on http://wwwhomes.uni-bielefeld.de/achim/ ... _life.html, counting the fishhook and integral sign as eaters, suggests that a path of length 2.6 million tiles can be formed before it gets obstructed by an eater.

itaibn wrote:Also, a calculation based on http://wwwhomes.uni-bielefeld.de/achim/ ... _life.html, counting the fishhook and integral sign as eaters, suggests that a path of length 2.6 million tiles can be formed before it gets obstructed by an eater.

If you look at the rarity of most objects, it tends to track fairly closely with the number of gliders it takes to make them. Occasionally, there are aberrations. The eater is one of these. Its rarity suggest that it should take around 4 gliders to make (and, in fact, almost all syntheses of it do take at least four). However, the fact that there's a 2-glider collision that makes it skews the statistics a fair bit, because it's much more likely for two random gliders appearing in soup to make an eater than random soup experiments might suggest - especially since one of those gliders is a given, and it only requires one glider from the soup (with around a 1 in 70 chance of being in the right orientation). On the other hand, a second gliders arriving from the same stream will just kill the eater, so this might not be an issue after all.

itaibn wrote:Also, a calculation based on http://wwwhomes.uni-bielefeld.de/achim/ ... _life.html, counting the fishhook and integral sign as eaters, suggests that a path of length 2.6 million tiles can be formed before it gets obstructed by an eater.

Don't forget the boat-bit catchers, though -- either end of aircraft carriers and shillelaghs can "eat" pairs of gliders very easily. They're both more common than integrals, and snakes are about the same frequency... Both ends of eaters and integrals can do the same trick, for that matter, so there are more orientations of those to worry about.

Another line of inquiry: one old theory about the best way to protect a gun or replicator from random soup was to surround it with a well-spaced field of blocks, wide enough apart that the block+glider->pi reaction wouldn't reach the next neighbor block. No single block+glider collision sends out any gliders, and most collisions either move or destroy the block, so at least a few stray gliders will be absorbed before the potential trouble starts. Is there a particular arrangement of blocks that's minimally susceptible to erosion by incoming crystals or almost-pings?

One of the points I raise in the book chapter Dave Greene links to above (in his message of 13 October) is that living replicators are very different from those that occur in Game of Life or similar CAs, because they don't replicate in an empty or homogeneous environment (which the random soup replicators discussed here would do, after clearing junk away). Rather, they exploit the structured inhomogeneities in their non-living environment. I'm hoping to post updated versions of the papers the chapter was based on online before too long - meanwhile, anyone interested in learning more can email me as my_initial_my_surname, internet service provider gn period apc period org.

Now I did some more experiments with using scripting. In these experiments, long diagonal random strip is created and run until it reaches a stable state, and then many gliders are periodically created at a single spot. Here are the results:

* First of all, there is a large degree of random variation. An open path can go hundreds of tiles forwards or backwards just by chance. In addition, all my tests were done in an ad-hoc way and I didn't apply any statistical tests. Therefore I am not certain of all of these results

* I am fairly confident, and more confident than I was before, that it is in fact possible to clear a trail in the broth. This can be done by shooting gliders with a large even period. A period of 1000 seems to work, as does 200, but 100 and 30 seem not to work. In some of these experiments the gliders cleared out a distance of 10,000 tiles, which seems like a pretty conclusive demonstration. With a period of 200, it takes roughly 20 gliders on average to extend the path 1 tile diagonally.

* On the other, hand I believe odd periods cannot clear out paths. I noticed that with even periods it is common for crystals to be formed and then destroyed. I believe this somehow makes them work better. However, I am still not confident about them not working, since sometimes they can advance a few thousand tiles before retreating.

* It is fairly difficult to clear out a wider path. One method which seems to work is to shoot 1000 gliders in one alignment and then 1000 gliders in an alignment that's one tile off, and repeat this. (edit (2015-01-21): further experimentation shows this method does not work.)

* I have seen a number of times an eater or boat-bit catcher block the glider trail. I haven't kept track carefully how often they appear, but my earlier estimate that 2.6 million tiles can be cleared out before an eater is created was clearly a vast overestimate. Of particular note is the beacon bit-boat catcher. It is more common than any other eater and it can eat any glider stream of a fixed period. More irregular patterns should be able to kill the beacon.

* I have not tried to create paths that are any wider than wide enough to fit two different glider alignments.

Here is the script I used for my last experiment. All experiments were done with small variations of this script:

just a backlink, to form a link cycle of closely related pages:
https://www.reddit.com/r/cellular_autom ... e_that_we/