Cryptography Reference
In-Depth Information
This means that a practical way needs to be constructed to ship the
extra variables and “waste” bits along.
8.3.1 Reversible Turing Machines
,asetof
symbols that can appear on the tape,
Σ
, and a set of transition rules,
δ
An ordinary Turing machine consists of a set of states,
S
, that tell the machine what happens when. For instance,
δ
might
specify that if the machine is in state
σ
4
is on
the tape underneath the read/write head, then the read/write head
should write the symbol
s
2
,andthesymbol
σ
5
on the tape, move the head to the right
one notch and change to state
s
42
.ThisishowyouprogramaTuring
machine. The abstraction is fairly crude, but it makes it simpler to
keep track of all the possibilities.
If a certain puritanical
tradition, for instance,
is profoundly suspicious
of the novel, this is
because the novel is felt
to celebrate and
encourage misconduct,
rather than censure and
repress it.
—D.A. Miller in
The
Novel and The Police
Converting such a machine to run backward is pretty straightfor-
ward. The main problem is looking for combinations of states and
tape symbols that lead to the same states. That is when it is impossi-
bletoputthemachineinreversebecausetherearetwodifferentpre-
ceding situations that could have led to the present one. The easiest
solution is to keep splitting up the states until there is no confusion.
For each state,
s
i
∈ S
, construct a list of triples of states, tape
symbols, and direction
(
s
j
,σ
k
,L
)
thatcouldleadtothestate
s
i
.That
is, if the machine is in state
s
j
with the read/write head over the
σ
k
and move to the left one step. In
other words, if the machine is running backward and it finds itself
in state,
σ
l
,thenitwillwrite
symbol
s
i
,withsymbol
σ
k
to the right of it, then it can move to the
right, change to state
s
j
,andoverwrite
σ
k
with
σ
l
and not violate the
program.Thatis,thisisacorrectmove.
Therewillbeaconflictiftherearetriplesoftheform
(
s
∗
,σ
∗
,L
)
and
(
s
∗
,σ
∗
,R
)
in the same set. (Let
s
∗
stand for any element
s
i
from
S
.) This is because it is possible that the machine will end up some-
place with one of the symbols to the left and one to the right. You
might be able to make meta-arguments that such a combination
could never exist because of the structure of the program, but these
are often hard to prove.
If such a conflict occurs, then create a new state and split apart
the actions. All of the triples that moved left into the old state,
s
i
,can
stay pointing to state,
s
i
. The triples that moved
right
, however, will
be moved to point to the new state
s
j
. The transition rules out of
s
j
will be a duplicate of
s
i
.
To a large extent, splitting these states is the same as finding a
place to keep a “waste” bit around. The Fredkin AND gate generates
some waste bits that must be stored. Splitting the state creates a
