Problem Solving in Automata, Languages, and Complexity

266 COMPUTABILITY THEORY

11. Show that there exist integers m and n such that VVm = VVn = K and
    mEKandn$K.


12. Use the recursion theorem to prove that the following sets are not re.:
    FIN, REC, REC.


13. Let f be the function defined in Example 5.40. Define f to be its
    inverse function: f (n) = (max x)[f (x) < - n]. Prove that f grows to
    infinity faster than any recursive function g. That is, for any recursive
    function g, there exists no such that f(n) > g(n) for all n > no. (The
    function f* is called the busy beaver function, which grows &en faster
    than the Ackermann function.)

5.6 Undecidable Problems

In Section 5.4, we used Rice’s theorem to establish many undecidability results

about partial recursive functions, r.e. sets and Turing machines. For instance,

the result that EMP is not recursive implies that the problem of determining

whether a given DTM A! halts on any input is undecidable. The application of

Rice’s theorem is, however, limited to the problems whose corresponding lan-

guages are index sets. In this section, we present some undecidability results

for problems involving Turing machines and grammars whose corresponding

languages are not index sets. Our main tool is the reducibility technique. We

first present a few simple examples using reductions from index sets.

Example 5.41 Show that the following problems are undecidable:
(a) Given a DTM M and a string y, determine whether M halts on some
input x which is greater than or equal to y.
(b) Given two DTM’s Mz and MY, determine whether they are equivalent
( i.e., whether they compute the same function).
(c) Given a DTM M, an input y and a state q; of M, determine whether
M ever enters state q; in the computation on input y.
(d) Given a DTM M, determine whether the computation of M( 111) con-
tains a configuration in which the tape contains a substring 000.

Proof. (a) We need to show that set Al = ((2, y) 1 MT halts on some input

2 > y} is not recursive. We reduce the problem EMP to it. We define g(x) =
(x:0). If x E EMP, then MS halts on some y > 0, and so (x, 0) E Al. If
x c EMP, then Mx does not halt on any y > 0, aid so (x,0) 4 Al. Therefore,
g is a reduction function for EMP sm. Al. -

(b) We need to show that A2 = {(x, y) 1 VVz = VV.} is not recursive. We

reduce the set EMP to it. Let M,, be a fixed DTM that does not halt on

any input. Define g(x) = (x,x0). Note th a t x E EMP if and only if MT is

equivalent to MxO, and so g is a reduction from EMP to AZ.