Explain the fundamental difference between the ” Halts on the n’th transition problem” from Example 11.5.2 and the ”Halting Problem” that makes the former decidable and the latter undecidable. 6. Prove that there is no algorithm that determines whether an arbitrary Turing machine prints the symbol 1 on three consecutive transitions when run with a blank tape.

Explain the fundamental difference between the ” Halts on the n’th transition problem” from Example 11.5.2 and the ”Halting Problem” that makes the former decidable and the latter undecidable. 6. Prove that there is no algorithm that determines whether an arbitrary Turing machine prints the symbol 1 on three consecutive transitions when run with a blank tape.

Please remember that in any Turing machine description you should give a description of
the tape (where the inputs are and how the tape is being used) and you should identify the
high-level function of sets of states (eg states q, through qj copies the input, qk through q;
increments the counter, and so on.) I also encourage you to use Turing machine macros where
appropriate.

1. Construct a two-tape Turing machine with input alphabet {a, b} that accepts strings with

the same number of a’s and b’s. The computation with input u should take no more than
2 * length(u) -+- 3 transitions.

2. Construct a ’I1rning machine that reduces the language L to Q. In each case the alphabet

of L is {w, y) and the alphabet of Q is {a, b}:
(a) L = (my? and Q = (aa)*
(b) L=:1:*y”‘ and Q=alb
(c) L = {xiyixih’ Z O} and Q = aibili 2 0}

3. Construct a Turing machine that decides whether a string over {0, 1}* is the encoding of
a non-deterministic Turing machine. What would be required to change this to a machine
that decides whether the input is the representation of a deterministic Turing machine.

4. The universal machine introduced in Section 11.5 was designed to simulate the actions of
Turing machines that accepts by halting. Consequently, the representation scheme R(M)
did not encode accepting states.

(a) Extend the representation of R(iM) of a Turing machine M to explicitly encode the
accepting states of M.

(b) Design a universal machine U f that accepts input of the form R(M)w if the machine
114 accepts input w by final state.

5. Explain the fundamental difference between the ” Halts on the n’th transition problem”
from Example 11.5.2 and the ”Halting Problem” that makes the former decidable and
the latter undecidable.

6. Prove that there is no algorithm that determines whether an arbitrary Turing machine
prints the symbol 1 on three consecutive transitions when run with a blank tape.
7. Use Rice’s theorem to show that the following properties of recursively enumerable lan-
guages are undecidable:
(a) L(M) = E’“
(b) L is infinite.
8. Let g : id, h = p?) + pg”, and let f be defined from g and h by primitive recursion.
(a) Compute the values f (3, O), f (3, 1), f (3, 2).
(b) Give a closed form (nonrecursive) definition of the function f.
9. Let g(:1:, y, 2) be a primitive recursive flmction. Show that each of the following functions
is primitive recursive.
(a) flab?!) Z 9017, 14,93)
(b) f(37,y, Z, 2) = g(£r,y, £13)
(0) f(:v) = 9(1,2,x)
10. Show that gcd(:c, y) : the greatest common divisor of a: and y is primitive recursive.