Flip If Same

The "Raissa" Rule

(Or is it Margolus's?)
[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

Color the grid into a checkerboard of red and black squares in your mind. On even steps, update red squares; on odd steps, update black squares.

The update rule is: Flip if all four neighbors are the same.

This rule is its own reverse -- just skip an update to start the reversal.

Wires

Use horizontal stripes as the background.
(Diagrams below will have enough "context" to make it clear how they fit in.)

Toggle a vertical or horizontal line to make a wire.

To bend a wire by 90 degrees, also toggle one of the cells (call it C) that's one past the bend B.

Here's a signal:

                 there it is
                      vv
1111111111111111111111111111111111
0000000000000000000000000000000000
0101010101010101010101001010101010
0000000000000000000000000000000000
1111111111111111011111111111111111
If a wire just ends, then signals will be reflected.

Where a wire bends, recall B and C and consider the wire cell E that is two-over from B, perpendicular to BC. One of B or E will not be flashing. Consider the direction from the flashing one (of B or E) to the not-flashing one. That is the direction a signal can be passed in. (Signals coming the other way lead to mayhem.) When the signal passes through, it changes which one is flashing. So signals must be sent back and forth, rather than all in the same direction, around a bend like this. For our purposes, we are only really interested in just a single signal anyway.

Here's two horizontal signals meeting to form a vertical one, and then when it bounces back up (all three branches just end in this picture), it splits back into two:

1111111111111111111111111111111111
0000000000000000000000000000000000
1111100000001010101010000000111111
0000000000000000000000000000000000
1111111111111111011111111111111111
              00100
              11111
              00100
              11111
              00100
              11111
              00100
              11111
              00100
              11111
              00100
              11111
              00100
              11111
              00000
If we only send in one of the upper signals, then it goes down the middle, then up, then back down, then up and out the other side!

And, believe it or not, the same thing can happen for a T that's on it's side (one horizontal and two vertical branches). But the phases have to be aligned right.

So, assuming the upper inputs and lower output are connected to further stuff, that is an OR gate.

Now, if we put something at the bottom that reflects a signal the first time, but lets it through the second time, then we have an XOR gate (since if two upper signals arrive at the same time, then the first time the vertical signal bounces back up, it will split back into two signals going back along the inputs rather than bouncing down a second time).

So of course, the thing we need at the bottom is just an upside-down OR-gate-with-one-signal-having-passed-through:

            111111111111111111111111111111111111111
            000000000000000000000000000000000000000
  input --> 000000010101010101010101010101010000000 <-- input
            000000000000000000000000000000000000000
            111111111111111111101111111111111111111
                         000000100
                         111111111
An XOR gate, shown       000000100
with two incoming        11111111111111111111111
signals, which will      00000010000000000000000
be bounced back.         11101001010101010101010 --> output
One incoming signal      00000000000000000000000
would pass through       11111111111111111111111
to the output.

And an XOR can make a NOT. And NOTs and ORs can make ANDs.

We'll have to use little delays to make sure signals are properly synchronized. And we'll have to make little spirals to delay fixed signals for the NOT gates.

And so...... [it's planar but we have NOT gates, so...]... it's P-COMPLETE!!

Conclusion is Premature -- Remaining to be Shown:

Actually, I bet we don't need that sort of thing for P-completeness. Cris?