instructions in the set. This would undoubtedly tax our patience, but it ought to
be possible in principle if our hypothesis is correct. Still, while every success in
this direction would strengthen our conviction of the truth of the hypothesis, it
would not lead to a proof. The difficulty lies in the fact that we don't know
exactly what is meant by “a typical digital computer” and that we have no means
for making a precise definition.
We can also approach the problem from the other side. We might try to find
some procedure for which we can write a computer program, but for which we
can show that no Turing machine can exist. If this were possible, we would have
a basis for rejecting the hypothesis. But no one has yet been able to produce a
counterexample; the fact that all such tries have been unsuccessful must be taken
as circumstantial evidence that it cannot be done. Every indication is that Turing
machines are in principle as powerful as any computer.
Arguments of this type led A. M. Turing and others in the mid-1930s to the
celebrated conjecture called the Turing thesis. This hypothesis states that any
computation that can be carried out by mechanical means can be performed by
some Turing machine.
This is a sweeping statement, so it is important to keep in mind what Turing's
thesis is. It is not something that can be proved. To do so, we would have to
define precisely the term “mechanical means.” This would require some other
abstract model and leave us no further ahead than before. The Turing thesis is
more properly viewed as a definition of what constitutes a mechanical
computation: A computation is mechanical if and only if it can be performed by
some Turing machine.
If we take this attitude and regard the Turing thesis simply as a definition, we
raise the question as to whether this definition is sufficiently broad. Is it farreaching enough to cover everything we now do (and conceivably might do in
the future) with computers? An unequivocal “yes” is not possible, but the
evidence in its favor is very strong. Some arguments for accepting the Turing
thesis as the definition of a mechanical computation are
1. Anything that can be done on any existing digital computer can also be done
by a Turing machine.
2. No one has yet been able to suggest a problem, solvable by what we
intuitively consider an algorithm, for which a Turing machine program
cannot be written.
3. Alternative models have been proposed for mechanical computation, but
be possible in principle if our hypothesis is correct. Still, while every success in
this direction would strengthen our conviction of the truth of the hypothesis, it
would not lead to a proof. The difficulty lies in the fact that we don't know
exactly what is meant by “a typical digital computer” and that we have no means
for making a precise definition.
We can also approach the problem from the other side. We might try to find
some procedure for which we can write a computer program, but for which we
can show that no Turing machine can exist. If this were possible, we would have
a basis for rejecting the hypothesis. But no one has yet been able to produce a
counterexample; the fact that all such tries have been unsuccessful must be taken
as circumstantial evidence that it cannot be done. Every indication is that Turing
machines are in principle as powerful as any computer.
Arguments of this type led A. M. Turing and others in the mid-1930s to the
celebrated conjecture called the Turing thesis. This hypothesis states that any
computation that can be carried out by mechanical means can be performed by
some Turing machine.
This is a sweeping statement, so it is important to keep in mind what Turing's
thesis is. It is not something that can be proved. To do so, we would have to
define precisely the term “mechanical means.” This would require some other
abstract model and leave us no further ahead than before. The Turing thesis is
more properly viewed as a definition of what constitutes a mechanical
computation: A computation is mechanical if and only if it can be performed by
some Turing machine.
If we take this attitude and regard the Turing thesis simply as a definition, we
raise the question as to whether this definition is sufficiently broad. Is it farreaching enough to cover everything we now do (and conceivably might do in
the future) with computers? An unequivocal “yes” is not possible, but the
evidence in its favor is very strong. Some arguments for accepting the Turing
thesis as the definition of a mechanical computation are
1. Anything that can be done on any existing digital computer can also be done
by a Turing machine.
2. No one has yet been able to suggest a problem, solvable by what we
intuitively consider an algorithm, for which a Turing machine program
cannot be written.
3. Alternative models have been proposed for mechanical computation, but