to the modified machine, with configurations q 0 w and q f w. This would give
us a solution of the halting problem.
13. Take a universal Turing machine and let it simulate computations on an
empty tape. Whenever the simulated computations halt, accept the Turing
machine being simulated. The universal Turing machine is therefore an
accepter for all Turing machines that halt when applied to a blank tape. The
set is therefore recursively enumerable.
Suppose now the set were recursive. There would then exist an algorithm A
that lists all Turing machines that halt on a blank tape input in some order
of increasing lengths of the program. See if the original Turing machine is
amongst the Turing machines generated by A. Since the length of the
original program is fixed, the comparison will stop when this length is
exceeded. Thus, we have a solution to the blank tape halting problem.
16. If the specific instances of the problem are p 1 , p 2 ,…, p n , we construct a
Turing machine that behaves as follows:
Whatever the truth values of the various instances are, there is always some
Turing machine that gives the right answer. Remember that it is not
necessary to know what that Turing machine is, only to guarantee that it
exists.
Section 12.2
3. Suppose we had an algorithm to decide whether or not
. We
could then construct a machine M 2 such that
and apply the
algorithm. Then
if and only if
. But this
contradicts Theorem 12.3, since we can construct M1 from any given
grammar G.
6. If we take L(G 2 ) = Σ * , the problem becomes the question of Theorem 12.3
and is therefore undecidable.