Elements of Complexity Theory - A Classical Introduction to Cryptography: Applications for Communications Security - page 216

Although real computers have a finite memory and not an infinite tape, Turing
machines are better models than finite automata since the microprocessor is very close
to a finite automaton and the memory is virtually infinite from the microprocessor point
of view! However, the access model of the memory is not so relevant since we do not
need to scan all the memory in order to reach the end.

8.2 Ability Frontiers

8.2.1 Standard Computational Models

The Church hypothesis consists of considering that all computable languages over

are precisely those that are accepted by some Turing machine. We can even show that
adding extra characters in the alphabet does not extend the computational power of
Turing machines. We can thus consider that all computable languages over are those

that are accepted by some Turing machine with the same alphabet. Languages over a
larger alphabet can always be encoded with this alphabet.

When the underlying finite automaton is not deterministic, we obtain a nondeter-
ministic Turing machine . We say that a language L is accepted by a nondeterministic
Turing machine M if for any word x ,wehave x

L if and only if there exists a running
of M on x which eventually halts. As we transformed nondeterministic finite automata
into deterministic ones, we can represent nondeterministic Turing machines as deter-
ministic Turing machines with two tapes: one regular tape and one read-only tape on
which we only move to the right. We use this tape as an additional input which is used
in order to decide what is the next state. In simpler words it is interesting to consider
a nondeterministic algorithm on input x as a deterministic algorithm on inputs x and
r . The input r is sometimes called a witness for x being in L . Hence we say that L is
accepted by a nondeterministic Turing machine M if for any word x ,wehave x

∈

∈ L if

and only if there exists a witness r such that M ( x , r ) eventually halts.

One special case of nondeterministic Turing machines is probabilistic Turing ma-
chines . Here we consider that the new state of the Turing machine is decided at random,
and we consider the probability that the Turing machine halts. Equivalently, we consider
r as being a random input, following a given distribution.

Obviously, nondeterministic Turing machines do not extend the notion of com-
putability. Indeed, we can simulate acceptance by a nondeterministic Turing machine
by doing an exhaustive search on the random input r with a deterministic Turing ma-
chine. The crucial difference, as will be noticed later, is about the complexity.

8.2.2 Beyond Computability

It is fairly easy to show the limits of computability by proving that there exist languages
which are not computable. This can be made by a standard set theory argument.