Together with "Traffic Circle", copies of [NAND Gate, Crossover, and Copycat]
can be put together to perform universal computation. The bits are
represented by inactive robots, which enter from the top and right of
each board, and exit from the bottom and left. If a robot is placed on
the initial conveyor belt square before stage 1, that represents a "0" bit,
whereas if it placed on the initial conveyor belt square before stage 3, it
represents a "1" bit. Similarly, exiting to the next board represents
a 0 or 1 bit based on which stage of a turn it is. In all cases, the
time to transit a board is two full turns, plus or minus two stages if
the state of the bit changes.
[The first version of this page contained an editorial comment clarifying what
"before stage 1" meant, saying " at the end of stage 3 or later in the previous
turn". Not so:
"`Before stage 1' means just before, i.e., on stage 5 of the
previous turn. Similarly, `before stage 3' means `on stage 2'.
In a couple of places, it doesn't really matter, but most of the
boards are extremely sensitive to timing."
So it's at the very beginning of the stage 1 or 3, before the non-existent
program cards kick in. - djr]
"NAND Gate" takes two inputs x and y from the top and right. The left
output is always 0, and the bottom output is
x NAND y = NOT (x AND y).
This is a universal gate if you can perform it in any pair of bits,
assuming you have an ample supply of "0" bits to start with. (You can
then create 1s since 0 NAND 0 = 1, which means you can also do NOT,
since x NAND 1 = NOT x. Then you can do x AND
y = NOT (x NAND y), and x OR y = (NOT x)
NAND (NOT y).)
Since "NAND Gate" erases one of its inputs, you also need to be able to
copy bits. "Copycat" does this: it takes a 0 bit from the right and
bit x from the top, and outputs x at both the bottom and left.
"Crossover" and "Traffic Circle" are simply routing boards. "Crossover"
takes x from the top and y from the right, and outputs x at the bottom
and y at the left. "Traffic Circle" takes x from the top and y from
the right, and outputs x at the left and y at the bottom. That is,
it switches horizontal bits and vertical bits.
By combining copies of these four boards, you can perform any network
of gates, and therefore any universal computation.
[Signed,] Daniel
|