Information Technology Reference
In-Depth Information
between the real numbers and the natural numbers and that the real numbers
are not countably infinite.
How does this argument relate to Turing machines and computable num-
bers? We can obviously construct a machine to calculate the decimal expan-
sion of π by using one of the many algorithms for determining π. This just
requires a set of rules for adding, multiplying, and so on. However, because
π is an infinite decimal, the work of the machine would never end and the
machine would need an unlimited amount of working space on its tape. A
legitimate Turing machine must halt, so we need to set up the machine to
calculate each successive decimal place of π as a separate calculation. Each
number in the decimal expansion would then use only a finite amount of tape
and take some finite time for the machine to compute. So a Turing machine
for producing the decimal expansion of π to any number of decimal digits does
exist in this sense, although it would be a little complicated to set up. And we
can obviously do the same for a real number like the square root of two. The
real numbers that can be generated in this way Turing called “computable
numbers.”
In his paper Turing showed that the number of his machines was countable.
To see this, we specify any given Turing machine by the “quintuple” descrip-
tion of the machine as we see in our detailed discussion of the Parity Counter
Turing Machine at the end of this chapter. The quintuple description is just an
explicit labeling of the actions of the Turing machine in terms of five items: the
initial state and the symbol that is read plus the new state, the symbol written,
and the motion of the head to the left or right. The machine is specified by
a set of quintuples describing exactly what happens for each initial state and
symbol read. This set of quintuples may be written out as a binary string. The
resulting binary number can now be used to uniquely label the machine by a
one-to-one correspondence with the set of natural numbers. In principle then
we can now make a list with a natural number specifying each Turing machine
and the corresponding number the machine computes. The resulting infinite
list now includes every number that is computable! Turing now made use of
Cantor's diagonal slash method to add one to each of the computable numbers
on the diagonal as we did in the preceding text to generate a new real number.
In this way Turing showed that there are real numbers that are noncomput-
able. The details of Turing's proof are a bit more complicated, but this is the
basic argument that convinced Turing that the answer to Hilbert's third ques-
tion was “no.”
Universality and the Church-Turing thesis
Before we return to the Entscheidungsproblem , we need to look at another
marvelously original idea in Turing's paper - the Universal Turing Machine.
This is a Turing machine that can do anything that any specific, special-purpose
Turing machine can do, albeit more slowly and less efficiently. Suppose we have
a specific Turing machine T that acts on a tape t to produce its result. What
Turing showed was that it was possible to construct another Turing machine U
that, if we give it as input the specification of T and the tape t , will output the
result that machine T would have produced acting on tape t . The behavior of
Search WWH ::




Custom Search