In spite of the descriptive nature of these examples, it is not too farfetched to
conjecture that Turing machines, while rather primitive in principle, can be
combined in many ways to make them quite powerful. Our examples were not
general and detailed enough for us to claim that we have proved anything, but it
should be plausible at this point that Turing machines can do some quite
complicated things.
EXERCISES
1. Write out the complete solution to Example 9.14.
2. Establish a convention for representing positive and negative integers in
unary notation. With your convention, sketch the construction of a subtracter
for computing x - y.
3. Using adders, subtracters, comparers, copiers, or multipliers, draw block
diagrams for Turing machines that compute the functions
(a) f (n)= n(n+ 1),
(b) f (n)= n 5 ,
(c) f (n)= 2 n
(d) f (n)= n!,
(e) f (n)= n n! ,
for all positive integers n.
4. Use a block diagram to sketch the implementation of a function f defined for
all w 1 , w 2 , w 3 {1} + by
f (w 1 ,w 2 ,w 3 )= i,