Cryptography Reference
In-Depth Information
X and Y
X
Y and not X
X and not Y
Y
X and Y
Figure 8.3: The three possible outcomes of a billiard ball AND gate.
The presence of a ball indicates an
on
signal. If only one ball is
present, then no bounce occurs and it continues on its way. If both
are present, then they bounce off each other. If none are present,
then nothing happens. (Adapted from Bennett )
The transition rules for thesemachines often look quite similar to the
Fredkin gate. There is just as much information coming out of each
step as going into it. This is balanced correctly so the position that
leads to another position can always be inferred and the machine
can be reversed.
This result shows that anything that can be done with a computer
can be done with a reversible computer. All that is necessary is find-
Reversible computation
is also
great
for
debugging programs.
ing a way to save the information from each step so it can be effec-
tively run in reverse. But what does this mean if you want to hide
information? It means that any computation can be used to hide in-
formation in the final outcome. How much can be stored? It all de-
pends on the calculation. Ordinarily, any random number generator
that is used to add realism or to scramble the outcome of a game can
be replaced by a collection of data to be hidden. This data can be
recovered as the machine runs in reverse.
Howwould such a systemwork? One obvious solution is to create
a universal, reversible Turing machine format. A standard program
