Q2R

[You need to enable java applets in your browser]
when the mouse is over a button, the status line will tell you what the button does

Think of cells as a red&blue checkerboard in your mind.  On alternate steps, update the red cells and the blue cells.
To update a cell, flip it if its neighbors are half black and half white.

This rule is reversible.

Clearly in a field of white, if black cells are inside a rect, then no cell outside the rect will ever turn black.
Almost as clearly, if the rect's top row's red cells are all white, then the blue cells can't change.
So bounding rects are invariant.

If we provide "wires" (lines of black cells), then all sorts of signals can be sent about.  Here are some simple ones:
 

A  . O . O . O . O O . O . O . O
L  . O . O . O . O O
                   O
                   O . O . O . O
B  . O . O . O . O
                 O . O . O . O .
                 O O
H  . O . O . O . O O . O . O . O
                 O O
                 O O
                 O O
H5 . O . O . O . O O . O . O . O
                 O O
                 O O
If an L comes to the end of a wire, it will either bounce back, or "stick", with an A bouncing back, which must pummel it repeatedly until the third time it can wrestle it free again!

If an H comes to a turn in the wire, it slowly emits two As onward before bouncing back itself!

An A can go around a turn in a wire.  So can a B, as long as it is "outside" the corner, which means it can only turn left then right then left, etc.

An A and a B will pass through each other, as will an A and an A.

A T with a top bar of fifteen (then dots) (three time steps later thirteen) sends a H5 downwards!
That is to say, two As meeting at a T junction in the right phase can combine to make an H5 going down.
(Just one A will coming in will get bounced back as two As the way it came, which is also what happens to incorrectly phased inputs.)
If we can convert the H5 back into an A, then we have an AND gate.
And of course we can, by using the same reaction in reverse:

10101010101111111111111110101010101
                 1
  an AND gate    1
                 1     all unshown sites are 0
                 1
             100010001
10101010101100000100000110101010101
The AND gate is shown here with an input coming in each side at the top (make sure 3 time steps later it still looks like a T).  This will cause a signal to be emitted on each of the lower output lines.  If only one signal were to be sent in on an upper wire, then it would just get bounced in duplicate.

Also, since As can turn corners, we can make an H5 turn a corner by splitting it into two As for the turn:

O O O O O O . . . . . . . . . . . . . . . . . . . . . . . .
O . . . . O . . . . . . . . . . . . . . . . . . . . . . . .
O . . . . O . . . . . . . . . . . . . . . . . . . . . . . .
O . . . . O . . . . . . . . . . . . . . . . . . . . . . . .
O . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
O . . . . . O . . . . . . . . . . . . . . . . . . . . . . .
O . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
O . . . . . . . . . . . . . . . . . . . . . . . O O . . . .
O . . . . . . . . . . . . . . . . . . . . . . . O O . . . .
O . . . . O O . O . O . O . O . O . O . O . O . O O . O . O
O . . . . . . . . . . . . . . . . . . . . . . . O O . . . .
O . . . . . . . . . . . . . . . . . . . . . . . O O . . . .
O . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
O . . . . . O . . . . . . . . . . . . . . . . . . . . . . .
O . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
O . . . . O . . . . . . . . . . . . . . . . . . . . . . . .
O . . . . O . . . . . . . . . . . . . . . . . . . . . . . .
O . . . . O . . . . . . . . . . . . . . . . . . . . . . . .
O . . . . O O O O O O O O O O O O O O O O O O O . . . . . .
O . . . . . . . . . . . . . . . . . . . . . . O . . . . . .
O . . . . . . . . . . . . . . . . . . . . . . O . . . . . .
O . . . . . . . . . . . . . . . . . . . . . . O . . . . . .
O . . . . . . . . . . . . . . . . . . . . . . O . . . . . .
O O O O O O O O O O O O O O O O O O O O O O O O . . . . . .
. . . . . . . . . O . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . O . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . O . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . O . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . O . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . O . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . O . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . O . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . O . . . . . . . . . . . . . . . . . . . .
Here an H5 is shown coming in on the upper right.  It will get split into two As that will recombine into an H5 going down the vertical wire at the bottom.

It turns out that in the right phase, an H5 "grazing" a wire end on each side can generate A signals on the wires.  If we do this twice, we can combine the As to make new H5s, and we have fan-out:

. . . . . . . . . . . . . . . . . . . . . . . O . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . O . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . O . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . O . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . O O O O O . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . O O O O O . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . O . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . O . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. O . O . O . O . O . O . O . O . O . O . . . O . . . O . O . O . O . O . O . O . O . O . O .
O O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . O O
. . . . . . . . . . . . . . . . . . . . . . . O . . . . . . . . . . . . . . . . . . . . . . .
O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . O
. . . . . . . . . . . . . . . . . . . . . . . O . . . . . . . . . . . . . . . . . . . . . . .
O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . O
. . . . . . . . . . . . . . . . . . . . . . . O . . . . . . . . . . . . . . . . . . . . . . .
O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . O
. . . . . . . . . . . . . . . . . . . . . . . O . . . . . . . . . . . . . . . . . . . . . . .
O . . . . . . . . . . . O . O . O . O O . . . . . . . O O . O . O . O . . . . . . . . . . . O
. . . . . . . . . . . O O . . . . . . . . . . O . . . . . . . . . . O O . . . . . . . . . . .
O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . O
. . . . . . . . . . . O . . . . . . . . . . . O . . . . . . . . . . . O . . . . . . . . . . .
O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . O
. . . . . . . . . . . O . O . O . O . . . . . O . . . . . O . O . O . O . . . . . . . . . . .
O . . . . . . . . . . . . . . . . O O . . . . . . . . . O O . . . . . . . . . . . . . . . . O
. . . . . . . . . . . . . . . . . . . . . . . O . . . . . . . . . . . . . . . . . . . . . . .
O . . . . . . . . . . . . . . . . . O . . . . . . . . . O . . . . . . . . . . . . . . . . . O
. . . . . . . . . . . . . . . . . . . . . . . O . . . . . . . . . . . . . . . . . . . . . . .
O . O . O . O . O O O . O . O . O . O . . . . . . . . . O . O . O . O . O O O . O . O . O . O
. . . . . . . . O O O . . . . . . . . . . . . O . . . . . . . . . . . . O O O . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . O . . . . . . . . . . . . . O . . . . . . . . . . . . . O . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . O . . . . . . . . . . . . . O . . . . . . . . . . . . . O . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . O . . . . . . . . . . . . . O . . . . . . . . . . . . . O . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . O . . . . . . . . . . . . . O . . . . . . . . . . . . . O . . . . . . . . .


Here an input (H5) is seen coming in the top, and it will cause three H5s to be sent down the three wires at the bottom.  There is enough clearance between the wires to allow the above "H5 turn" mechanism to be used.  (Though it's easy to see how to modify these devices if necessary.)
 

. . . . . . O O . . . . . . . . . .
. . . . . . O O . . . . . . . . . .
O . O . O . O O . O . O . O . O . O
. . . . . . O O . . . . . . . . . .    Two H5 signals about
. . . . . . O O . . . . . . . . . .    to pass each other,
. . . . . . . . . . O O . . . . . .    except they are too
. . . . . . . . . . O O . . . . . .    close, so they tangle
O . O . O . O . O . O O . O . O . O    up, sending As onward
. . . . . . . . . . O O . . . . . .    while bouncing back
. . . . . . . . . . O O . . . . . .    themselves.
This is very close to being a not gate...  We can send a fixed signal in one wire, and it will get through iff there is not a signal on the other wire.  The other wire can just end after a little bit.  But we need to "read" the emergence of the fixed signal, which is hard to do because our space is cramped by the upper wire.  For example, we can't just use the turning mechanism from above.

So here's how we can do that:

               . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
               . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
               O . O . O . O . O . O . O . O . O . O . O . O . O . O . O . O . O . O . O . O . O . O   I N P U T  X
               . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
               . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
               . . . . . . O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
               . . . . . . O O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
I N P U T  Y   O O O O O O O O . O . O . O . O . O . O . O . O . O O . . . . . . . . . . . . . . . .
               . . . . . . O O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
               . . . . . . O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
               . . . . . . . . . . . . . . . . . . . . . . . O O . O . O . O . O . O . O . O . . . .
               . . . . . . . . . . . . . . . . . . O . . . . . . . . . . . . . . . . . . . O O . . .
               . . . . . . . . . . . . . . . . . . O . . . . . . . . . . . . . . . . . . . . . . . .
               . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . O . . .
               . . . . . . . . . . . . . . . . . . O . . . . . . . . . . . . . . . . . . . . . . . .
               . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . O . . .
               . . . . . . . . . . . . . . . . . . O . . . . . . . . . . . . . . . . . . . . . . . .
               . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . O . . .
               . . . . O . O . O . O . O . O . O . O . . . . . . . . . . . . . . . . . . . . . . . .
               . . . O O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . O . . .
               . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
               . . . O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . O . . .
               . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
               . . . O . O . O . O . O . O . O . O . O . O O . . O O O . . O O . O . O . O . O . . .
               . . . . . . . . . . . . . . . . . . . . . . . . O O O O O . . . . . . . . . . . . . .
               . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
               . . . . . . . . . . . . . . . . . . . . . . . . . . O . . . . . . . . . . . . . . . .
               . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
               . . . . . . . . . . . . . . . . . . . . . . . . . . O . . . . . . . . . . . . . . . .
               . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
               . . . . . . . . . . . . . . . . . . . . . . . . . . O . . . . . . . . . . . . . . . .

                                                              O U T P U T
Here a H5 signal is shown coming in the upper left ("input Y").  (Across the top is the wire on which another H5 signal ("input X") could have prevented this one from coming in.)  The Y signal makes a big mess around the end of the wire, out of which two As are fished out by the wire ends there, which are then combined to form a new H5 going out the bottom wire ("output"), appearing about 200 generations after the state shown here.  The right-hand wire is consumed by the mess in another 100 generations, and 100 generations after that some As are sent back out the input wire.  But the output wire seems to be safe from the mess, at least for long time.

Since a signal is produced at the output iff there is a Y signal but no X signal, we'll call this a "less" gate, since an output is produced iff X is less than Y.  A less gate can clearly be used to make a NOT, since (X < 1) == NOT(X).  By NOT'ting any of the inputs and/or the output, we can make an AND, OR, etc., so it can be used to make any gate.

All that remains to be found is phase-adjusters to make sure signals can be combined as desired.
There are three phases of the H5, as it takes three generations to advance one cell:

. . . O . . . . . . O . . . . . . . . . . . . . . . . .
. . . . . . . . . . O . . . . . . O . . . . . . O . . .
. . . O . . . . . . O . . . . . . . . . . . . . . . . .
. . . . . . . . . . O . . . . . . O . . . . . . O . . .
. . O O O . . . . . O . . . . . . . . . . . . . . . . .  The first and last
. O O O O O . . O O O O O . . O O O O O . . . O O O . .  one are the same,
. . . O . . . . . O O O . . . O O O O O . . O O O O O .  but it has advanced
. . . O . . . . . . . . . . . . . . . . . . . . O . . .  by one cell.
. . . O . . . . . . O . . . . . . O . . . . . . O . . .
. . . O . . . . . . . . . . . . . . . . . . . . O . . .
. . . O . . . . . . O . . . . . . O . . . . . . O . . .
As we can see, the wire itself has a period-3 nature, so it is impossible to "realign" a signal on a given wire; if we want it to have a different phase, it must be put on a different wire.  The phase of a wire can be defined as the generation (mod 3) on which it is solid.  The phase of a signal can be defined as the phase of the wire in front of it.

So, in the "less" gate shown above, the phases of all the wires (except for behind the signal) are the same, so the phases of all the signals are (would be) the same.  The same is true for the picture of two signals tangling each other, and the same is true for the "fan-out" diagram.  Only the 90-degree turn diagram has a phase change that is not 0 mod 3.  But that's easy to fix -- we can just use three 90-degree turns in a row (e.g. left-right-left) to get a 90-degree turn with no phase change!

All that remains is precise positioning.  Well, look at this:

. . . . . . . . . . O . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . O . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . O O O O O . . . . . . .
. . . . . . . . O O O O O . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . O . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . O . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . O . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . O . . . O . . . O . . . . .
O O O O O . . . . . O . . . . . O O O O
O . . . . . . . . . . . . . . . . . . O
O . . . . . . . . . . . . . . . . . . O
O . . . . . . . . . . . . . . . . . . O
O . . . . . . . . . . . . . . . . . . O
O O O O O O O O O O O O O O O O O O O O
. . . . . . . . . O . . . . . . . . . .
. . . . . . . . . O . . . . . . . . . .
. . . . . . . . . O . . . . . . . . . .
. . . . . . . . . O . . . . . . . . . .
The H5 signal coming in the top will be split into two As which are recombined into a H5 one cell over to the left.  The phase changes, so we will probably need to use three in a row.

We can also widen the "loop" in this picture by a cell on each side to make the signal come out at the next later possible time.
Of course, we can also adjust the loop to get any horizontal displacement we want (not just 1).
So all in all, we can control the H5's position quite precisely.

So, we can build circuits to evaluate boolean expressions -- Q2R is P-complete!

12-20-98