Information Technology Reference
In-Depth Information
computers today?
Although Turing Machines may seem particularly mundane,
they are important in the theory of computation for several reasons.
First, because they can be defined precisely and their processing can
be described rigorously, it is possible to prove various results about
them. In particular, several variations of Turing Machines have
been proven to have the same power. That is, whatever can be
solved with one of these machines can also be solved on the others.
Through theory, we can show that Turing Machines with the fol
lowing capabilities can solve exactly the same problems:
A Turing Machine with a tape extending infinitely far in both
directions (an infinite twoway tape)
A Turing Machine with a tape extending infinitely far in only
one direction (an infinite oneway tape)
A Turing Machine with several oneway tapes
A Turing Machine with an infinite oneway tape and just the
symbols 0, 1, and space
A Turing Machine with several twoway tapes and an ex
tended alphabet of tape symbols
These results indicate that adding tape capabilities or extending
alphabets does not change what computers can solve. For example,
although we may be more comfortable with numbers in decimal no
tation, Turing Machines that process decimal numbers cannot solve
problems beyond those solvable by Turing Machines based on bi
nary numbers.
Further, additional theory allows us to prove that Turing
Machines have exactly the same power as the basic computer we
discussed at the start of this chapter (with a CPU, main memory,
and storage device). It may seem that today's computers are much
more sophisticated than the historical Turing Machines; however,
research shows that any problem that can be solved with one of to
day's computers also could be solved with a Turing Machine. And,
conversely, any problem that can be solved with a Turing Machine
can be solved with one of the basic computers we described earlier.
