Indestructible object- it’s time we answer the question

[Moosey]

Alright.

We need to solve this question. First, it’s a very old question by Conway. Second, it could be useful for other things.

I recommend we take a new approach to it. We play a game.

1. Submit your pattern (Conway requires it be 1000x1000, but that’s rather arbitrary, so make it as large as you want. Just keep it finite.) in a post. You can submit as many or as few as you want; limits would slow progress. Mark one cell with a lifehistory state.

2. Another way to “play” is to show a way to change the state of the marked cell in any submitted pattern by placing an “army” of stuff outside. Any part of this army must be at least 2 cells away (orthogonally , diagonally, or any other way) from any live cell in the challenge pattern, and must be outside all parts of the challenge pattern— if there is a gaping hole in the challenge pattern, no placing stuff inside!.

3. Over time, people will get stuck on the most difficult challenge patterns.

4. Someone will either prove that the state of the center cell cannot be changed for the challenge patterns in question (indestructible pattern found!) or show a way to do so without violating the rules.

The first challenge pattern. Easily solvable.

Code: Select all

x = 4, y = 4, rule = LifeHistory
.A$ADA$A2.A$.2A!

[dani]

When I think of an indestructible pattern I think of guns making each other in a circle such that each gun synth eats itself and self destructs when a crystal forms.

[pcallahan]

I suspect the answer is no, but all I have is intuition, not a pattern. One thing I got very interested in before I had much luck at all finding new patterns (posted to Usenet in early 90s) was whether a self-replicating pattern could survive in a random environment (with high probability). They are usually assumed to live in a vacuum, unlike living things we're familiar with.

In the mid-90s (earlier?) Nick Gotts took up the question of sparse random environments, and that may be necessary to make the question tractable, but I was interested in what happens if you start with a dense soup. Locally, it tends to stabilize and converge to the most common patterns. These patterns are not that hard to remove with glider collisions. What I wondered is whether a self-replicator could clear space around it with high probability, assuming it was not facing an adversary custom-designed to prevent it.

By analogy, you don't live in a friendly vacuum or sterile environment. You're hit by cosmic rays, UV radiation, toxic gases, droplets, and particulates, as well as biological pathogens. All these things damage your skin, which is why the surface of your skin if you're healthy is not as perfect as your internal organs, which depend on a controlled environment. You are also continually replacing layers of skin. So I wondered if you could have a replicator with the same approach. It would be very organized internally and fragile like most Life patterns, but would have a thick layer of barriers that would just look like spartan debris. It would stop errant gliders, spaceships, and random explosions. It would not stop them forever, just long enough to replace the barriers.

I am more pessimistic than I was at the time about clearing space with oblivious glider streams. I ran experiments that suggested (to me) that you could drill through junk and handle backward gliders. You need multiple diagonals to avoid spontaneous boat bits and eaters. You can do something similar with spaceships. Of course, the mess often propagates back to the gun. The question is whether you can find a strategy that drills forward on average. (I thought so then, but eventually got pessimistic and dropped it).

Anyway (long story for a little intuition) you can maybe protect the center from any known strategy, but I really think that a random bombardment will eliminate whatever was intended by the first layer of wall, then you remove it using the random removal mechanism (TBD!). Repeat as needed to peel off layers. I do not believe that there is a wall that can survive against every possible attack, though there may be some that do so with high probability and self-repair.

ADDED: The idea of clearing away random junk is highly dependent on reversibility. If you start with a densely populated random universe and reversible dynamics, you cannot eliminate randomness. If you have an infinite universe in which a finite patch of randomness is surrounded by empty space, you could conceivably clear that by moving the "entropy" into the surrounding space. But anyway, Life has no such constraints and there is no theoretical reason to believe that a small initial pattern could not clear space populated densely with debris. I think that for any strategy, though, there is likely to be an adversarial strategy that defeats it, just not one that is likely to be present by chance in random debris.

[dvgrn]

We need to solve this question. First, it’s a very old question by Conway. Second, it could be useful for other things.
...
3. Over time, people will get stuck on the most difficult challenge patterns.

Unfortunately the old questions tend to be the ones that are really painfully difficult to solve, and this one is no exception. To me it seems pointless to even try to build a candidate indestructible object -- it's clear (though not provable) that there's no such thing. Conversely, I'm very very confident of my ability to bombard any conceivable candidate with random gliders until the target cell changes state. There's never going to be a challenge pattern that's difficult enough for people to get stuck on, even momentarily.

I'm fairly sure that ten minutes with the Seeds of Destruction Game will be more than enough, for any candidate that anyone will ever actually come up with in my lifetime. If the pattern is so huge that it doesn't fit in the Seeds of Destruction Game, okay, I might need longer than that to shoot a path through whatever annoying junk has been put in my way, but the final outcome is going to be the same.

The simplest plan is (1) shoot one glider to make the nastiest biggest most unexpected chaotic mess that you can; (2) wait for the chaos to settle; (3) shoot a path through the ash toward the target area; (4) if there's something left besides small random settled-ash junk, repeat steps (1) and (2). You'll get there eventually.

[pcallahan]

The simplest plan is (1) shoot one glider to make the nastiest biggest most unexpected chaotic mess that you can; (2) wait for the chaos to settle; (3) shoot a path through the ash toward the target area; (4) if there's something left besides small random settled-ash junk, repeat steps (1) and (2). You'll get there eventually.

I agree, though I am not familiar with Seeds of Destruction. The point is to convert whatever incredible devious barrier was devised into a layer of random ash, possibly much thicker than the barrier, but removable with high probability. Remove that, including the remains of the barrier. Rinse and repeat. I made a small amount of headway on this idea a long time ago, but maybe it sounds like it has effectively been solved with Seeds of Destruction.

[dvgrn]

I agree, though I am not familiar with Seeds of Destruction... I made a small amount of headway on this idea a long time ago, but maybe it sounds like it has effectively been solved with Seeds of Destruction.

Well, Paul Chapman's Seeds of Destruction Game is a manual tool, not a solution for anything on its own. It's a huge help when you just want to do a little ad-hoc experimentation on a pattern, to get an intuitive sense of what might be worth searching for.

For example, if you want to be absolutely sure that three gliders are needed to clean up some annoying mess left over from a synthesis, then you still have to run an exhaustive two-glider search and make sure nothing shows up. But if you just paste the synthesis in as a puzzle to the latest Seeds of Destruction Game, and then switch to a glider and kind of wave it around the key problem area for a while, you might find that you can empirically zero in on a promising collision point where most of the mess goes away, and clean up the rest with one more glider.

The GUI takes a little getting used to (and it's good to have a mouse wheel) but it's quite powerful. The Seeds of Destruction Game was what found the reburnable fuse for the Centipede spaceship, in the first ten minutes of experimenting with waving a block around in a Herschel's reaction envelope.

There are also a couple of search programs by simeks, that start with an object to be destroyed and maintain a population of candidate adjustments, adding gliders or small ash objects to destroy the object as efficiently as possible. The searcher that adds small ash objects is "GoL-destroy". I don't think the glider-salvo destruction script has been released anywhere yet.

[Moosey]

By analogy, you don't live in a friendly vacuum or sterile environment.

In fact, if you did, you would be very dead.

I am more pessimistic than I was at the time about clearing space with oblivious glider streams. I ran experiments that suggested (to me) that you could drill through junk and handle backward gliders. You need multiple diagonals to avoid spontaneous boat bits and eaters. You can do something similar with spaceships.

And replicators, as I learned in highlife, to prevent bombers.