Make your own free website on
Daniel wrote me:

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

Gee. And all along I thought all I was doing on this site was a game. :)