then show how such a machine can be simulated with a standard Turing
machine.
3. Give a formal definition of a multihead-multitape Turing machine. Then
show how such a machine can be simulated by a standard Turing machine.
4. Give a formal definition of a Turing machine with a single tape but multiple
control units, each with a single read-write head. Show how such a machine
can be simulated with a multitape machine.
* 5. A queue automaton is an automaton in which the temporary storage is a
queue. Assume that such a machine is an on-line machine, that is, it has no
input file, with the string to be processed placed in the queue prior to the start
of the computation. Give a formal definition of such an automaton, then
investigate its power in relation to Turing machines.
* 6. Show that for every Turing machine there exists an equivalent standard
Turing machine with no more than six states.
* 7. Reduce the number of required states in Exercise 6 as far as you can.
(Hint:The smallest possible number is three.)
* 8. A counter is a stack with an alphabet of exactly two symbols, a stack start
symbol and a counter symbol. Only the counter symbol can be put on the
stack or removed from it. A counter automaton is a deterministic automaton
with one or more counters as storage. Show that any Turing machine can be
simulated using a counter automaton with four counters.
9.Show that every computation that can be done by a standard Turing machine
can be done by a multitape machine with a stay-option and at most two
states.
10. Write out a detailed program for the computation in Example 10.1.
10.3 Nondeterministic Turing Machines
While Turing's thesis makes it plausible that the specific tape structure is
immaterial to the power of the Turing machine, the same cannot be said of
nondeterminism. Since nondeterminism involves an element of choice and so
has a nonmechanistic flavor, an appeal to Turing's thesis is inappropriate. We
machine.
3. Give a formal definition of a multihead-multitape Turing machine. Then
show how such a machine can be simulated by a standard Turing machine.
4. Give a formal definition of a Turing machine with a single tape but multiple
control units, each with a single read-write head. Show how such a machine
can be simulated with a multitape machine.
* 5. A queue automaton is an automaton in which the temporary storage is a
queue. Assume that such a machine is an on-line machine, that is, it has no
input file, with the string to be processed placed in the queue prior to the start
of the computation. Give a formal definition of such an automaton, then
investigate its power in relation to Turing machines.
* 6. Show that for every Turing machine there exists an equivalent standard
Turing machine with no more than six states.
* 7. Reduce the number of required states in Exercise 6 as far as you can.
(Hint:The smallest possible number is three.)
* 8. A counter is a stack with an alphabet of exactly two symbols, a stack start
symbol and a counter symbol. Only the counter symbol can be put on the
stack or removed from it. A counter automaton is a deterministic automaton
with one or more counters as storage. Show that any Turing machine can be
simulated using a counter automaton with four counters.
9.Show that every computation that can be done by a standard Turing machine
can be done by a multitape machine with a stay-option and at most two
states.
10. Write out a detailed program for the computation in Example 10.1.
10.3 Nondeterministic Turing Machines
While Turing's thesis makes it plausible that the specific tape structure is
immaterial to the power of the Turing machine, the same cannot be said of
nondeterminism. Since nondeterminism involves an element of choice and so
has a nonmechanistic flavor, an appeal to Turing's thesis is inappropriate. We