none of them is more powerful than the Turing machine model.
These arguments are circumstantial, and Turing's thesis cannot be proved by
them. In spite of its plausibility, Turing's thesis is still an assumption. But
viewing Turing's thesis simply as an arbitrary definition misses an important
point. In some sense, Turing's thesis plays the same role in computer science as
do the basis laws of physics and chemistry. Classical physics, for example, is
based largely on Newton's laws of motion. Although we call them laws, they do
not have logical necessity; rather, they are plausible models that explain much of
the physical world. We accept them because the conclusions we draw from them
agree with our experience and our observations. Such laws cannot be proved to
be true, although they can possibly be invalidated. If an experimental result
contradicts a conclusion based on the laws, we might begin to question their
validity. On the other hand, repeated failure to invalidate a lawstrengthens our
confidence in it. This is the situation for Turing's thesis, so we have some reason
for considering it a basic lawof computer science. The conclusions we draw
from it agree with what we know about real computers, and so far, all attempts to
invalidate it have failed. There is always the possibility that someone will come
up with another definition that will account for some subtle situations not
covered by Turing machines but which still fall within the range of our intuitive
notion of mechanical computation. In such an eventuality, some of our
subsequent discussions would have to be modified significantly. However, the
likelihood of this happening seems to be very small.
Having accepted Turing's thesis, we are in a position to give a precise
definition of an algorithm.
Definition 9.5
An algorithm for a function f : D →R is a Turing machine M, which given
as input any d ∈ D on its tape, eventually halts with the correct answer f (d) ∈ R
on its tape. Specifically, we can require that
for all d ∈ D.
Identifying an algorithm with a Turing machine program allows us to prove
rigorously such claims as “there exists an algorithm…” or “there is no algorithm.
These arguments are circumstantial, and Turing's thesis cannot be proved by
them. In spite of its plausibility, Turing's thesis is still an assumption. But
viewing Turing's thesis simply as an arbitrary definition misses an important
point. In some sense, Turing's thesis plays the same role in computer science as
do the basis laws of physics and chemistry. Classical physics, for example, is
based largely on Newton's laws of motion. Although we call them laws, they do
not have logical necessity; rather, they are plausible models that explain much of
the physical world. We accept them because the conclusions we draw from them
agree with our experience and our observations. Such laws cannot be proved to
be true, although they can possibly be invalidated. If an experimental result
contradicts a conclusion based on the laws, we might begin to question their
validity. On the other hand, repeated failure to invalidate a lawstrengthens our
confidence in it. This is the situation for Turing's thesis, so we have some reason
for considering it a basic lawof computer science. The conclusions we draw
from it agree with what we know about real computers, and so far, all attempts to
invalidate it have failed. There is always the possibility that someone will come
up with another definition that will account for some subtle situations not
covered by Turing machines but which still fall within the range of our intuitive
notion of mechanical computation. In such an eventuality, some of our
subsequent discussions would have to be modified significantly. However, the
likelihood of this happening seems to be very small.
Having accepted Turing's thesis, we are in a position to give a precise
definition of an algorithm.
Definition 9.5
An algorithm for a function f : D →R is a Turing machine M, which given
as input any d ∈ D on its tape, eventually halts with the correct answer f (d) ∈ R
on its tape. Specifically, we can require that
for all d ∈ D.
Identifying an algorithm with a Turing machine program allows us to prove
rigorously such claims as “there exists an algorithm…” or “there is no algorithm.