Louis Howell's question of block clearing in life (simple solution)
Paul Callahan
... A limited answer is fine---I'd be happy to hear that there is a way to
guarantee destruction of a single randomly-placed block.) The related
sub-problem of how a formation can emit a glider on any desired trajectory
has, I believe, been solved as part of the "universal constructor" problem.
I thought this question probably had *some* answer, but I noticed a
fairly elegant (and very simple) one (under some assumptions about what
is meant by the question). It doesn't really speak to the general space
clearing issue, however. [Digression: the latter is probably harder than I
thought. Statistically, one can tunnel through junk, but this tends to
scramble the vicinity of the tunnel. I am now wondering about robust
replicators that survive in a network of constant-width crisscrossing
tunnels through a largely "scrambled" universe. Note that the scrambled
regions are safe if you let them stabilize and don't *ever* touch them again.]
I first interpreted this question as how to derive a small "salvo" of gliders
that would obliviously annihilate a block no matter how it hit it. I still
think this is the more interesting question, and probably has a
solution. However, Louis Howell's question doesn't require such generality.
Assumptions: The unknown block (or a sparse field of blocks) lies in a
diagonal band as follows:
?????????????????????........
?????????????????????........
?????????????????????........
?????????????????????........
?????????????????????........
?????????????????????........
?????????????????????........
?????????????????????........
?????????????????????........
"?" denotes a cell of the block field, while "." denotes sufficient
empty cells underneath to accommodate a single glider stream without
interactions. We use the following interaction:
.........................**
.........................**
. ba
. ba
. ba
. ba
..................**ba
..................**a
. ba
. ba
.
.
..................**
.................*.*
...................*
.
..............**
.............*.*
...............*
.
..........**
.........*.*
...........*
This triplet of gliders lies in a single glider-width band and annihilates
the first block it encounters that touches diagonal "a" but does not interact
with any cells in diagonal "b". Blocks must be sparse enough to prevent the
annihilations (which are well-contained) from affecting surrounding blocks.
Now, if we assume that each diagonal is touched by at most k blocks, then we
have cleared the lowest diagonal after k triplets of gliders. This moves the
known empty space up by one diagonal, so we can continue the process
inductively on a narrower band higher by one diagonal. After performing this
sweep over the width of the band, we are assured that the band is clear.
Semi-obligatory hand-waving: an explicit construction to perform the
sweep would require more work, of course, but it should be possible
using standard techniques.
--
Paul Callahan
call...@biffvm.cs.jhu.edu
Louis H. Howell
blocks by "scanning" a glider stream across it. Nice result!]
>I first interpreted this question as how to derive a small "salvo" of gliders
>that would obliviously annihilate a block no matter how it hit it. I still
>think this is the more interesting question, and probably has a
>solution. However, Louis Howell's question doesn't require such generality.
You want a salvo of gliders that will destroy any single block it hits.
Such a salvo might be useful for punching an initial hole through a sparse
field of blocks. Then the hole could be enlarged by the "scanning"
technique you describe. Since the original salvo may not encounter a block,
we may relax the problem slightly by permitting gliders moving outward in
the same direction as part of the debris. It might also be acceptable if
some collisions left a block behind, so long as we could guarantee that a
particular path (hole) would be clear after the salvo punched through.
Then one could attempt to clear sparse fields containing either blinkers
or blocks, or other still lifes.
Unfortunately, we can't assume that small objects will be widely separated,
even if the field is arbitrarily sparse. 3 live cells together can yield
either a blinker or a block, so these will be the most common objects
formed "out of the void". It is not so clear, however, what space will
look like after complex organisms have been around for a while, spewing
gliders and whatnot to the four corners of the universe. The most common
objects randomly occurring in a "mature ecosystem" may be all the possible
outcomes of random 2-glider collisions, some of which are rather complicated.
--
Louis Howell (naz...@llnl.gov)
Paul Callahan
>Actually, it's easy to enumerate all 2-glider collisions, and none
>produce anything very special. But some lead to explosions, like the
>pi-heptomino, b-heptomino, and the r-pentomino.
^^^^^^^^^^^^^
I believe I made a mistake here, unless my method of enumerating
collisions is wrong. There is a small interaction for producing the
r-pentomino explosion (as if anyone would want it), which is what I
was thinking of. It's a reaction between a glider and a lightweight
spaceship spark, nondestructive to the spaceship (so it can be used
in puffers):
.****.......
*...*.......
....*.......
*..*........
............
............
............
............
..........*.
.........**.
.........*.*
--
Paul Callahan
call...@biffvm.cs.jhu.edu
Paul Callahan
naz...@grover.llnl.gov (Louis H. Howell) writes:
>It might also be acceptable if
>some collisions left a block behind, so long as we could guarantee that a
>particular path (hole) would be clear after the salvo punched through.
You have to be a little careful to make sure multiple salvos aren't
producing a block that's oscillating between positions, or worse,
being dragged up the stream. Both can and will happen. But any new
block created will be at fewer potential positions than the initial
one, so a special-purpose cleanup team can be sent. In fact, this is
the general technique, to successively reduce possibilities until the
only possibility remaining is empty space. Since the process of
repeated collisions is deterministic, states merge but never
bifurcate. To me, it seems unlikely, however, that one can handle all
possibilities in a relatively dense field (including that left by
"natural" explosions). This is because the reactions tend to act beyond
a small bounding box.
This brings to mind a search computation I thought of performing. One
would start with a set of windows containing standard objects (blocks,
hives, blinkers) at all positions with respect to a glider stream.
Then represent a given stream as a sequence of integers (in some
reasonable range) denoting the time difference between adjacent
gliders in the stream (say between 14 and 40). These form a natural
search tree (i.e.: for any streams of length k, there is a branch for
each possibility of the (k+1)st glider). Anyway, the goal would be to
field the stream that minimizes the bounding box before the stream can
safely pass. If there is one with a very small bounding box, this
might be useful for punching holes through dense junk. There is a
caveat, however, which is that an interaction that destroys the first i
gliders in a stream will send off another stream (the ith suffix of
the original) lacking the nice property. This will hit the next object
on the way, possibly causing a much larger explosion.
>Unfortunately, we can't assume that small objects will be widely separated,
>even if the field is arbitrarily sparse.
That's a good point. Anyway, I don't think statistically sparse
fields are a realistic model of anything. Even small starting
patterns can produce rather big fields of objects packed at a
"natural" density. It's still an interesting puzzle to find streams
for destroying arbitrary fields of common objects while minimizing the
required separation between objects, but it has little to do with
anything one is likely to encounter in practice.
>The most common
>objects randomly occurring in a "mature ecosystem" may be all the possible
>outcomes of random 2-glider collisions, some of which are rather complicated.
Actually, it's easy to enumerate all 2-glider collisions, and none
produce anything very special. But some lead to explosions, like the
pi-heptomino, b-heptomino, and the r-pentomino. If the collisions
occur near each other, you get lots of side interactions. Typically,
however, it all looks like slag after it settles. I don't worry about
complicated objects, because they too tend to turn into slag after
they've been hit by a few gliders. The only exception I will buy is
one that is designed to shield itself with debris.
I'm interested in the statistical properties of tunneling through
"natural" debris. I'm fairly convinced that something can be
developed with a positive average tunneling velocity, but I haven't
done enough experiments (modifying the Xlife source to place a glider
at the origin periodically to avoid the fragility of a real gun).
Period-30 glider streams seem always to back up to the source.
Period-24 streams have better properties with respect to blocks, as
they avoid the larger explosions, but I haven't done a careful
experiment.
From my qualitative observations, tunneling is effective for a while,
because one can expect a moderate-length sequence of simple, contained
reactions that clear the stream path. Unfortunately, one eventually
gets an explosion going, and the stream of new gliders feeds it. This
explosion then backs up, destroying most of what has been
accomplished. It has occurred to me that one might benefit by halting
the stream to wait for any explosion to stabilize. This adds two new
parameters besides stream periodicity: namely the pulse length, and
the latency. Perhaps by varying these parameters one can find a
tunneling system with positive average velocity. Unless someone
comes up with an effective deterministic space-clearing technique,
this might be as good as any more complicated tunneling algorithm.
--
Paul Callahan
call...@biffvm.cs.jhu.edu
Paul Derbyshire
In a previous article, call...@biffvm.cs.jhu.edu (Paul Callahan) says:
>I wrote:
>
>
>>Actually, it's easy to enumerate all 2-glider collisions, and none
>>produce anything very special. But some lead to explosions, like the
>>pi-heptomino, b-heptomino, and the r-pentomino.
> ^^^^^^^^^^^^^
>
>I believe I made a mistake here...
Actually you didn't. There is a two-glider collision that produces an
early stage of the r-pentomino. Kaboom!
Re tunneling: what about quasiperiodic glider streams? A Fibonacci
sequence, perhaps...
. .. . .. .. . .. . .. .. . .. .. . .. . .. .. . .. . .. .. . .. .. .
.. . .. ..
--
Cheers, | **** ao...@freenet.carleton.ca ****
PGD | A large asteroid landed on Zeebat, killing the
________________________| tyrant Asmex. They called it a "historic milestone."
<><<><><<><> The leading cause of cancer in rats is laboratories <><>><><>><>
Bill Taylor
|>
|> You have to be a little careful to make sure multiple salvos aren't
|> producing a block that's oscillating between positions, or worse,
|> being dragged up the stream.
Can you post an example of this please, if you have one?
That is, a periodic glider stream dragging a block upstream in periodic
fashion. I sure would like to see one.
Thanks.
-------------------------------------------------------------------------------
Bill Taylor w...@math.canterbury.ac.nz
-------------------------------------------------------------------------------
I'm not one of the main actors in the computing world, just a bit player.
-------------------------------------------------------------------------------
Paul Callahan
>Can you post an example of this please, if you have one?
>That is, a periodic glider stream dragging a block upstream in periodic
>fashion. I sure would like to see one.
The following is the most obvious example, provided it meets your definition
of "stream" (the gliders aren't all in a line).
.......**...***
.......**...*
.............*
.
.
.
.
.
.
.
.
..............**
..............*.*
..............*
.
...........................***
...........................*
............................*
.
.
.
.
.
.
.
.
.............................**
.............................*.*
.............................*
.
..........................................***
..........................................*
...........................................*
.
.
.
.
.
.
.
.
............................................**
............................................*.*
............................................*
There are some other periodic effects, by the way, that look like
inverse puffers, in that the stream causes a trail to back up towards
the source. One of these occurs when a relatively high period (say >60)
single-file stream is aimed a block in a certain way. It leaves a
trail of pairs of beehives. I don't remember it offhand, but there are
not many possibilities to check.
--
Paul Callahan
call...@biffvm.cs.jhu.edu