Section 9.4 Turing Machines
771
concept of an algorithm. Figure 9.22 illustrates what has been done; here solid
lines represent mathematical proofs and dashed lines correspond to the Church–
Turing thesis. The dates indicate when the various models were proposed.
Computable by
algorithm
Turing
1936
Markov
1954
Church, Kleene
Late 1930s
Post
Early 1940s
Smullyan
1961
figure 9.22
The Church–Turing thesis is now widely accepted as a working tool by researchers dealing with computational procedures. If, in a research paper, a method
is set forth for computing a function and the method intuitively seems to be an
algorithm, then the Church–Turing thesis is invoked and the function is declared
to be Turing computable (or one of the names associated with one of the equivalent formulations of Turing computability). This invocation means that the author
presumably could, if pressed, produce a Turing machine to compute the function,
but again, the Church–Turing thesis is so universally accepted that no one bothers
with these details anymore.
Although the Church–Turing thesis is stated in terms of number-theoretic
functions, it can be interpreted more broadly. Any algorithm in which a finite set
of symbols is manipulated can be translated into a number-theoretic function by
a suitable encoding of the symbols as nonnegative integers, much as input to a
real computer is encoded and stored in binary form. Thus, by the Church–Turing
thesis we can say that if there is an algorithm to do a symbol manipulation task,
there is a Turing machine to do it.
By accepting the Church–Turing thesis, we have accepted the Turing machine
as the ultimate model of a computational procedure. Turing machine capabilities
exceed those of any actual computer, which, after all, does not have the unlimited tape storage of a Turing machine. It is remarkable that Turing proposed this
concept in 1936, well before the advent of the modern computer.
Decision Problems and uncomputability
We have spent quite a bit of time discussing what Turing machines can do. By
the Church–Turing thesis, they can do a great deal indeed, although not very efficiently. It is even more important, however, to consider what Turing machines
cannot do. Because a Turing machine’s abilities to perform tasks exceed those of
an actual computer, if we find something no Turing machine can do, then a real
computer cannot do it either. In fact, by invoking the Church–Turing thesis, no
algorithm exists to do it, and the task is not computable. The type of task we have
in mind here is generally that of determining the truth value of each of a number
of related statements.
771
concept of an algorithm. Figure 9.22 illustrates what has been done; here solid
lines represent mathematical proofs and dashed lines correspond to the Church–
Turing thesis. The dates indicate when the various models were proposed.
Computable by
algorithm
Turing
1936
Markov
1954
Church, Kleene
Late 1930s
Post
Early 1940s
Smullyan
1961
figure 9.22
The Church–Turing thesis is now widely accepted as a working tool by researchers dealing with computational procedures. If, in a research paper, a method
is set forth for computing a function and the method intuitively seems to be an
algorithm, then the Church–Turing thesis is invoked and the function is declared
to be Turing computable (or one of the names associated with one of the equivalent formulations of Turing computability). This invocation means that the author
presumably could, if pressed, produce a Turing machine to compute the function,
but again, the Church–Turing thesis is so universally accepted that no one bothers
with these details anymore.
Although the Church–Turing thesis is stated in terms of number-theoretic
functions, it can be interpreted more broadly. Any algorithm in which a finite set
of symbols is manipulated can be translated into a number-theoretic function by
a suitable encoding of the symbols as nonnegative integers, much as input to a
real computer is encoded and stored in binary form. Thus, by the Church–Turing
thesis we can say that if there is an algorithm to do a symbol manipulation task,
there is a Turing machine to do it.
By accepting the Church–Turing thesis, we have accepted the Turing machine
as the ultimate model of a computational procedure. Turing machine capabilities
exceed those of any actual computer, which, after all, does not have the unlimited tape storage of a Turing machine. It is remarkable that Turing proposed this
concept in 1936, well before the advent of the modern computer.
Decision Problems and uncomputability
We have spent quite a bit of time discussing what Turing machines can do. By
the Church–Turing thesis, they can do a great deal indeed, although not very efficiently. It is even more important, however, to consider what Turing machines
cannot do. Because a Turing machine’s abilities to perform tasks exceed those of
an actual computer, if we find something no Turing machine can do, then a real
computer cannot do it either. In fact, by invoking the Church–Turing thesis, no
algorithm exists to do it, and the task is not computable. The type of task we have
in mind here is generally that of determining the truth value of each of a number
of related statements.