O
Chapter 10
Other Models of
Turing Machines
ur definition of a standard Turing machine is not the only possible
one; there are alternative definitions that could serve equally well.
The conclusions we can draw about the power of a Turing machine
are largely independent of the specific structure chosen for it. In this
chapter we look at several variations, showing that the standard
Turing machine is equivalent, in a sense we will define, to other, more
complicated models.
If we accept Turing's thesis, we expect that complicating the standard Turing
machine by giving it a more complex storage device will not have any effect on
the power of the automaton. Any computation that can be performed on such a
new arrangement will still fall under the category of a mechanical computation
and, therefore, can be done by a standard model. It is nevertheless instructive to
study more complex models, if for no other reason than that an explicit
demonstration of the expected result will demonstrate the power of the Turing
machine and thereby increase our confidence in Turing's thesis. Many variations
on the basic model of Definition 9.1 are possible. For example, we can consider
Turing machines with more than one tape or with tapes that extend in several
dimensions. We will consider variants that will be useful in subsequent
discussions.
We also look at nondeterministic Turing machines and show that they are no
more powerful than deterministic ones. This is unexpected, since Turing's thesis
covers only mechanical computations and does not address the clever guessing
implicit in nondeterminism. Another issue that is not immediately resolved by
Turing's thesis is that of one machine executing different programs at different
times. This leads to the idea of a “reprogrammable” or “universal” Turing
machine.
Chapter 10
Other Models of
Turing Machines
ur definition of a standard Turing machine is not the only possible
one; there are alternative definitions that could serve equally well.
The conclusions we can draw about the power of a Turing machine
are largely independent of the specific structure chosen for it. In this
chapter we look at several variations, showing that the standard
Turing machine is equivalent, in a sense we will define, to other, more
complicated models.
If we accept Turing's thesis, we expect that complicating the standard Turing
machine by giving it a more complex storage device will not have any effect on
the power of the automaton. Any computation that can be performed on such a
new arrangement will still fall under the category of a mechanical computation
and, therefore, can be done by a standard model. It is nevertheless instructive to
study more complex models, if for no other reason than that an explicit
demonstration of the expected result will demonstrate the power of the Turing
machine and thereby increase our confidence in Turing's thesis. Many variations
on the basic model of Definition 9.1 are possible. For example, we can consider
Turing machines with more than one tape or with tapes that extend in several
dimensions. We will consider variants that will be useful in subsequent
discussions.
We also look at nondeterministic Turing machines and show that they are no
more powerful than deterministic ones. This is unexpected, since Turing's thesis
covers only mechanical computations and does not address the clever guessing
implicit in nondeterminism. Another issue that is not immediately resolved by
Turing's thesis is that of one machine executing different programs at different
times. This leads to the idea of a “reprogrammable” or “universal” Turing
machine.