Cryptography Reference
In-Depth Information
waste bit.
Thesamesplittingprocessmustbedoneiftherearetwotriples
of the form:
(
s
b
,
lead to the same symbol existing to the right of the current position
of the read/write head. Choosing is impossible. Again, a new state
must be added and the transition rules duplicated and split.
It should be obvious that a Turingmachine will grow substantially
as it is made reversible. This growth can even be exponential inmany
cases. There is no reason why anyone would want to program this
way. The complications are just too great. But this example is a good
beginning.
s
a
,σ
k
,L
)
and
(
s
b
,σ
k
,L
)
. Both of these states,
s
a
and
8.3.2 Reversible Grammar Generators
The goal of this topic is to produce something that seems innocuous
but hides a great deal of information from plain sight. Chapter 7
didagoodjobofthiswithacontext-freegrammar,butthereare
numerous limitations to that approach. This part of the topic will
build a reversible, Turing-equivalent machine that will be able to do
all basic computations, but still be reversible. It will get much of
its performance by imitating the Fredkin gate, which merely swaps
information instead of destroying it.
Numerous problems that need to be confronted in the design of
this machine. Here are some of them:
Extra State
At the end of the computation, there will be plenty of
extra “waste” bits hanging around. These need to be conveyed
to the recipients so they can run their machines in reverse.
There are two possible solutions. The first is to send the ex-
tra state through a different channel. It might be hidden in
the least significant bits of a photo or sent through some other
covert channel. The second is to use a crippled version of the
machine to encode the bit as text without modifying any of the
state. That is, reduce the capability of the machine until it acts
like the context-free grammar machine from Chapter 7.
Ease of Programmability
Anyone using the machine will need to
come up with a collection of grammars to simulate some form
of text. Constructing these can be complicated, and it would be
ideal if the language could be nimble enough to handle many
constructions.
The solution is to imitate the grammar structure from Chapter
7. There will be variables and productions, but you can change
the productions en route using reversible code.
