Appendix A: Mathematical Facts - Codes: The Guide to Secrecy from Ancient to Modern Times - page 502

Now we need the notion of a Turing machine , which is a finite-state machine
having an infinite read-write tape, i.e., our theoretical computer has infinite
memory and the ability to search for and retrieve any data from memory.
More specifically, a (deterministic, one-tape) Turing machine has an in-
finitely long magnetic tape (as its unlimited memory) on which instructions
can be written and erased. It also has a processor that carries out the instruc-
tions: (1) move the tape right, (2) move the tape left, (3) change the state of
the register based upon its current value and a value on the tape, and write
or erase on the tape. The Turing machine runs until it reaches a desired state
causing it to halt. A famous problem in theoretical computer science is to de-
termine when a Turing machine will halt for a given set of input and rules.
This is called the halting problem . Turing proved that this problem is undecid-
able , meaning that there does not exist any algorithm whatsoever for solving
it. The Church-Turing thesis , which came out of the 1936 papers of Turing and
Church (see page 92), essentially says that the Turing machine as a model of
computation is equivalent to any other model for computation. (Here we may
think of a “model” naively as a simplified mathematical description of a com-
puter system.) Therefore, Turing machines are realistic models for simulating
the running of algorithms, and they provide a powerful computational model.
However, a Turing machine is not meant to be a practical design for any actual
machine, but is a suGciently simple model to allow us to prove theorems about
its computational capabilities while at the same time being suGciently complex
to include any digital computer irrespective of implementation.
Complexity theory designates a decision problem to be in class P if it can be
solved in polynomial time, whereas a decision problem is said to be in class NP
if it can be solved in polynomial time on a nondeterministic Turing machine,
which is a variant of the normal Turing machine in that it guesses solutions to a
given problem and checks its guess in polynomial time. Another way to look at
the class NP is to think of these problems as those for which the correctness of
a guess at an answer to a question can be proven in polynomial time. Another
equivalent way to define the class NP is the class of those problems for which a
“yes” answer can be verified in polynomial time using some extra information,
called a certificate .
The class P is a subset of the class NP since a problem that can be solved in
polynomial time on a deterministic machine can also be solved, by eliminating
the guessing stage, on a nondeterministic Turing machine. It is an open problem
in complexity theory to resolve whether P = NP . However, virtually everyone
believes that they are unequal. It is generally held that most modern ciphers can
be cryptanalyzed in nondeterministic polynomial time. However, in practice it is
the deterministic polynomial-time algorithm that is the end goal of modern-day
cryptanalysis. Defining what it means to be a “computationally hard” problem
is a hard problem . One may say that problems in P are easy , and those not in
P are considered to be hard . However, there are problems that are regarded as
computationally easy, yet are not known to be in P . For instance, the Miller-
Rabin-Selfridge test is such a problem. It is in the class RP , called randomized