machine with
δ (q 1 ,a 1 ) = (q 1 ,a 1 ,R),
δ(q 1 ,a 2 ) = (q 3 ,a 1 ,L),
δ (q 3 ,a 1 ) = (q 2 ,a 2 ,L).
3. Sketch a Turing machine program that enumerates the set {0,1} + in proper
order.
4. What is the index of 0 i 1 j in Exercise 3?
5. Design a Turing machine that enumerates the following set in proper order.
L = {a n b n : n ≥ 1}.
6. For Example 10.3, find a function f (w) that gives for each w its index in the
proper ordering.
7. Show that the set of all triplets, (i,j,k) with i,j,k positive integers, is countable.
8. Suppose that S 1 and S 2 are countable sets. Show that then S 1 ∪ S 2 and S 1 ×
S 2 are also countable.
9. Show that the Cartesian product of a finite number of countable sets is
countable.
10.5 Linear Bounded Automata
While it is not possible to extend the power of the standard Turing machine by
complicating the tape structure, it is possible to limit it by restricting the way in
which the tape can be used. We have already seen an example of this with
pushdown automata. A pushdown automaton can be regarded as a
nondeterministic Turing machine with a tape that is restricted to being used like
a stack. We can also restrict the tape usage in other ways; for example, we might
permit only a finite part of the tape to be used as work space. It can be shown
that this leads us back to finite automata (see Exercise 3 at the end of this
section), so we need not pursue this. But there is a way of limiting tape use that
leads to a more interesting situation: We allow the machine to use only that part
of the tape occupied by the input. Thus, more space is available for long input
δ (q 1 ,a 1 ) = (q 1 ,a 1 ,R),
δ(q 1 ,a 2 ) = (q 3 ,a 1 ,L),
δ (q 3 ,a 1 ) = (q 2 ,a 2 ,L).
3. Sketch a Turing machine program that enumerates the set {0,1} + in proper
order.
4. What is the index of 0 i 1 j in Exercise 3?
5. Design a Turing machine that enumerates the following set in proper order.
L = {a n b n : n ≥ 1}.
6. For Example 10.3, find a function f (w) that gives for each w its index in the
proper ordering.
7. Show that the set of all triplets, (i,j,k) with i,j,k positive integers, is countable.
8. Suppose that S 1 and S 2 are countable sets. Show that then S 1 ∪ S 2 and S 1 ×
S 2 are also countable.
9. Show that the Cartesian product of a finite number of countable sets is
countable.
10.5 Linear Bounded Automata
While it is not possible to extend the power of the standard Turing machine by
complicating the tape structure, it is possible to limit it by restricting the way in
which the tape can be used. We have already seen an example of this with
pushdown automata. A pushdown automaton can be regarded as a
nondeterministic Turing machine with a tape that is restricted to being used like
a stack. We can also restrict the tape usage in other ways; for example, we might
permit only a finite part of the tape to be used as work space. It can be shown
that this leads us back to finite automata (see Exercise 3 at the end of this
section), so we need not pursue this. But there is a way of limiting tape use that
leads to a more interesting situation: We allow the machine to use only that part
of the tape occupied by the input. Thus, more space is available for long input