Cryptography Reference
In-Depth Information
waste
x
waste
output
Fredkin
AND Gate
y
0
OUT
IN
x y
0 0 0 0 0 0
0 1 0 0 1 0
1 0 0 1 0 0
1 1 0 1 0 1
Figure 8.2: An AND gate built out of a Fredkin gate. The extra waste
bits must be stored at the gate so that computation can be reversed
later. [BL85]
ergy to the balls so that nothing would be lost and there would be
just as much kinetic energy at the beginning of the computation as
at the end.
Figure 8.3 shows how two billiard balls can build an AND gate.
The presence of a ball is considered to be the on state, so if both balls
are there, they will bounce off each other and only one ball will con-
tinue on its way. If the balls reach the end of the computation, then
they can bounce off a final wall and make their way back. It should
be easy to see that this gate will work both forward and backward. OR
gates are more complicated and include extra walls to steer the balls.
This is an interesting concept, but it is hardly useful. No one can
build such a frictionless material. If they could, it might be years be-
fore we got to actually trying to use it to compute. There would be
too many other interesting things to do, like watching people play
hockey on it. More practical implementations, however, use cellu-
lar automata that come before and after it. Toffoli described revers-
ible cellular automata in his Ph.D. thesis [Tof77a] and in other subse-
quent articles [Tof77b, TM87]. N. Margolus offers one solution that
implements the billiard ball models. [Mar84]
The key result about reversible computers comes from Charles
David Hillman has
written about reversible
one-dimensional
cellular automata
[Hil91b, Hil91a].
Bennett who showed that any computation can be done with a re-
versible Turing machines. He created a few basic examples of revers-
ible Turing machines with well defined commands for moving the
read/write head of the tape and changing the state of the machine.
 
Search WWH ::




Custom Search