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.
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 1111111111111111011111111111111111If 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 00000If 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!!