Cryptography Reference
In-Depth Information
Both metaphors turn out to be quite close to each other. The
context-free grammars and the stack-based machines for interpret-
ing them are equivalent. This also illustrates why it is possible to im-
itate certain details about a baseball game like the number of outs or
the number of strikes, while it is much harder, if not impossible, to
give a good imitation of the score. There is no way to rearrange the
information on the stack or to recognize it out of turn.
The Turing machine is about as general a model of a computer as
can be constructed. Unlike the push-down automata, a Turing ma-
chine can access any part of its memory at any time. Inmost models,
this is described as a “tape” that is read by a head that can scan from
left to right. You can also think of the “tape” as regular computer
memory that has the address 0 for the first byte, the address 1 for the
second byte, and so on.
The main advantage of using a Turing machine is that you access
any part of the memory at any time. So you might store the score
of the baseball game at the bytes of memory with addresses 10140
and 10142. Whenever you needed this, you copy the score to the out-
put. This method does not offer any particularly great programming
models that would make it easier for people to construct a working
Turing mimicry generator. Alas.
The real reason for exploring Turing machines is that there are
a wide variety of theoretical results that suggest the limits on how
they can be analyzed. Alan Turing originally developed the models
to explore the limits of what computers can and can't do [Tur36a,
Tur36b]. His greatest results showed how little computers could do
when they were turned against themselves. There is very little that
computers and the programs they run can tell us definitively about
another computer program.
These results are quite similar to the work of Kurt Godel, who
originally did very similar work on logical systems. His famous the-
orem showed that all logical systems were either incomplete or in-
consistent. The result had little serious effect on mathematics itself
because people were quite content to work with incomplete systems
of logic— they did the job. But the results eroded the modernist be-
lief that technology could make the world perfect.
Turing found that the same results that applied to Godel's logi-
cal systems could apply to computers and the programs that ran on
them. He showed, for instance, that no computer program could
definitively answer whether another computer program would ever
finish. It might be able to find the correct answer for some subset of
computer programs, but it could never get the right answer for all of
them. The program was either incomplete or inconsistent.
