Date: Wed, 22 Nov 89 03:38 EST
From: Dean Hickerson
Subject: Description of block pusher
To: rwg@YUKON.SCRC.SYMBOLICS.COM, dba@ANDREW.CMU.EDU, rcs@LA.TIS.COM,
acw@YUKON.SCRC.SYMBOLICS.COM
Here's the promised description of block pusher. It's fairly detailed and
includes some things which you've all seen before; I put them in so I can
send it to Wainwright, Trevorrow, and others who haven't been following
our discussion.
The block pusher consists of a stationary pattern made of guns,
eaters, and glider streams, and a block some distance to the SE. The
pattern fires a group of 5 gliders at the block; when they hit, the block
is moved farther SE and a glider is sent back NW. When this glider reaches
the stationary part, another glider group is sent toward the block. Since
the round trip time keeps increasing, points along the gliders's flight
paths never become periodic.
The collision which moves the block is shown below. The gliders are
labelled A, B, C, D, and E. Gliders A and B move the block 7 units west
and 4 units south. Gliders C and D turn it into a boat. Glider E turns it
back into a block, 5 units SE of its original position, and sends back a NW
glider. (I'd known the glider+boat -> block+glider reaction for several
years. I found the gliders+block -> boat reaction after just a few minutes
of experimenting. Putting these together results in pushing the block, but
also moves it off the diagonal. I then tried hundreds of collisions
between 2 gliders and a block until I found one which moved the block back
to the correct diagonal; I was hoping for a combination which moved it
15 or 23 units, but 5 was the best I found. My search was by no means
complete, so it's possible that there's a group of only 4 (or maybe even 3
or 2) gliders which does the job.)
e.e...............................
.ee...............................
.e................................
..................................
..................................
.....d............................
......d...........................
....ddd...........................
..................................
..................................
..........c.......................
...........c..........b...........
.........ccc...........b..........
.....................bbb..........
..................................
..................................
..................................
............................a.....
.............................a..oo
...........................aaa..oo
The stationary part of block pusher lies along a NW-SE diagonal, and
consists of 3 pieces. At the NW end is the shotgun, which produces a 5
glider group every 120 generations. Next there's the suppressor, which
shoots gliders at the shotgun's output, destroying the groups. Finally,
there's the catcher, which waits for a glider to come from the block and
then deletes one of the suppressor's gliders, thereby allowing one glider
group to escape toward the block.
The shotgun builds the groups's gliders in the order A, E, D, C, B.
Gliders A are produced by a p120 gun aimed SE. Gliders E are produced by a
p120 gun aimed SW; they hit a queen bee shuttle which reflects them 90
degrees to SE, as shown here:
o.........
ooo.....o.
...o...o..
..oo...ooo
..........
......o...
......o...
.....o....
..........
..........
..oo...oo.
..o.....o.
..........
...o...o..
....ooo...
..........
..........
..........
..........
..oo......
...o......
ooo.......
o.........
Next, gliders D are produced by a LW spaceship gun aimed north and a glider
gun aimed SW; they collide as shown here:
.o....
.o.o..
.oo...
......
......
ooo...
o..o..
o.....
o.....
.o.o..
Gliders C and B are produced in the same way, except that for B the LW
spaceship gun is aimed west and the glider gun is aimed NE. Each LW
spaceship gun is made from 2 glider guns whose gliders collide in the
vicinity of a pentadecathlon. (Thanks to Bill for providing both the 90
degree turn and the LW synthesis.)
..............o.o...
...............oo...
...............o....
....................
....................
....................
.................oo.
.................o.o
.o..oo....oo..o..o..
o...ooo..ooo...o....
.o..oo....oo..o.....
Altogether, the shotgun consists of 11 p120 glider guns, one shuttle, and 3
PDs.
The suppressor is essentially a p120 glider gun whose output
annihilates the glider groups. (Actually I used a p30 gun, 3/4th of whose
gliders get deleted by a glider stream from the catcher.) The annihilation
is done like this:
e.e...............................
.ee...............................
.e................................
..................................
..................................
.....d............................
......d...........................
....ddd...........................
..................................
..................................
..........c.......................
...........c..........b...........
.........ccc...........b..........
.....................bbb..........
..................................
..................................
..................................
............................a.....
.............................a....
...........................aaa....
..................................
...............................o.o
...............................oo.
................................o.
Finding a way to delete a group with just one glider wasn't really
necessary, but made the catcher's circuitry much simpler. Fortunately, the
gliders+block reaction shown earlier occurs in 3 stages, so there's some
flexibility in the spacing of the glider group. Hence there are more ways
to crash a glider into a group than if its geometry were fixed, so the
chance that one of them would cause annihilation was increased. It only
took a couple hours of experimenting to find the one shown above.
The catcher's job is to detect a glider coming from the block. There
are two difficulties. First, the phase of the return glider is only known
mod 40: If the block is 5 units farther away, the round trip time is
increased by 40. That's why I chose p120 logic; there are only 3
possibilities for the return glider's phase. Second, the return glider's
flight path overlaps that of the glider groups, so whatever detects the
glider must not interfere with the groups. Fortunately, a NE glider can
slip between gliders B and C. (If this hadn't been possible, it would have
been necessary to either use slower guns, thereby increasing the number of
possible return glider phases, or to add circuitry to turn off the
detectors when a glider group goes by.) Here's a circuit diagram of the
catcher:
Shotgun Suppressor
\ /
\ /\
\ E / \
\ \/ \
\ /\ \
\ E / \ \
\ \/ \ \
\ /\ \ \
\ / \ \ \
\ / \ \ \
\/ \ \ \
\ /\ \ \
\ / G5 /\ \
\ / / G4 /\
\/ / / G3
/\ / /
/ \ / /
G2 \ / /
\/ /
/\ /
/ \ /
G1 \ /
\/
/\
/ \
G0 .
.
.
\
\
Block
"G" is a gun, "E" is an eater. Guns G0-G2 have period 120, while G3-G5 and
the suppressor have period 30. Wherever gliders meet, they both vanish.
Normally, during a 120 generation cycle, one of the 4 gliders produced by
G3 is deleted by one from G0; hence 3 of the 4 from the suppressor are
deleted. There's also one missing from each of G4 and G5, so the
suppressor's remaining glider gets through to hit the shotgun's output.
But when a glider comes from the block, one glider is deleted from either
G0, G1, or G2, so an extra one escapes from either G3, G4, or G5, the usual
escapee from the suppressor is deleted, and a glider group escapes.
----------------------------------------------------------------------
It should be possible to modify this construction to give a pattern
whose population grows like C sqrt(t) for some C: Reposition G3 so its
output hits the output of G0 in a ternary reaction, replace the suppressor
by a p120 gun, and add two p120 guns and an eater as shown:
E Suppressor
\/
/\ G7
/ \ \
. \ /\
. \ / \
. \/ \
/\ .
/ \ .
G6 /\ .
/ G3
.
.
.
/
G0
The G3 stream's data, after its collision with the G0 stream, will be
0011/1111 in a 120 generation cycle; the first bits occur normally, the
others when a return glider has deleted one from G0. G6 produces 0100 and
hits the stream from G3 in a vanish reaction, so it becomes 0100/0000.
This then hits the output of G7 (0100) in a vanish reaction, so a glider
escapes from G7 only if a return glider has deleted one from G0.
Meanwhile, the G3 stream after its collision with the G6 stream is
0011/1011; the first of these bits is used to release or delete the
suppressor's output. Eventually, the population will be dominated by the
outputs from G7 and will grow like C sqrt(t).