The Halting Problem

One often hears of the halting problem for Turing machines as a problem similar to L - one that is RE but not recursive. In fact, the original Turing machine of A. M. Turing accepted by halting, not by final state. We could define H{M) for TM M to be the set of inputs ю such that M halts given input w, regardless of whether or not M accepts w. Then, the halting problem is the set of pairs (M.w) such that w is in H{M). This problem/language is another example of one that is RE but not recursive.

is that the reduction of L to another problem P can be used to show there is no algorithm to solve P, regardless of whether or not P is RE. However, reduction of La to P is only possible if P is not RE, so L cannot be used to show undecidabiiity for those problems that are RE but not recursive. On the other hand, if we want to show a problem not to be RE, then only L(j can be used; L is useless since it is RE.

Theorem 9.6: is RE but not recursive.

PROOF: We just proved in Section 9.2.3 that Lu is RE. Suppose L were recursive. Then by Theorem 9.3, L-u, the complement of Lu, would also be recursive. However, if we have a TM M to accept L then we can construct a TM to accept Ld (by a method explained below). Since we already know that Ld is not RE, we have a contradiction of our assumption that Lu is recursive.

Copy

will w

M for

Hypo±etical algorithjn

M for L

Accept Reject

Accept Reject

Figure 9.6: Reduction of Ld to Lu

Suppose L{M) = L. As suggested by Fig. 9.6, we can modify TM M into a TM M that accepts Li as follows.

1. Given string w on its input, M changes the input to u;lllu. You may, as an exercise, write a TM program to do this step on a single tape. However, an easy argument that it can be done is to use a second tape to copy and then convert the two-tape TM to a one-tape TM.

2. M simulates M on the new input. If ш is in our enumeration, then M determines whether Mi accepts wt. Since M accepts Lu, it will accept if and only if does not accept tf,-; i.e., Wj is in Ld-

Thus, M accepts w if and only if w is in Lit. Since we know M cannot exist by Theorem 9.2, we conclude that Lu is not recursive. □

9.2.5 Exercises for Section 9.2

Exercise 9.2.1: Show that the halting problem, the set of {M,w) pairs such that M halts (with or without accepting) when given input ш is RE but not recursive. (See the box on The Halting Problem in Section 9.2.4.)

Exercise 9.2.2; In the box Why Recursive? in Section 9.2.1 we suggested that there was a notion of recursive function that competed with the Turing machine as a model for what can be computed. In this exercise, we shall explore an example of the recursive-function notation. A recursive function is a function F defined by a finite set of rules. Each rule specifies the value of the function F for certain arguments; the specification can use variables, nonnegative-integer constants, the successor (add one) function, the function F itself, and expressions built from these by composition of functions. For example, Ackermanns function is defined by the rules:

1. A(0,y) = 1 for any у > 0.

2. A(1,0) = 2.

3. A(a:,0)-a:-f2forx>2.

4. A{x + l,y + l) A{A{x,y + l),y) for any x > 0 and у > 0. Answer the following:

* a) Evaluate A(2,l).

! b) What function of x is A(a;,2)?

! c) Evaluate A(4,3).

Exercise 9.2.3: Informally describe multitape Turing machines that enumerate the following sets of integers, in the sense that started with blank tapes, it prints on one of its tapes 10*40*1 to represent the set {1,2,...}.

* a) The set of all perfect squares {i, 4,9,...}. b) The set of all primes {2,3,5,7,11,...}.

II с) The set of alU such that Mj accepts Wi. Hint: It is not possible to generate all these is in numerical order. The reason is that this language, which is Lrf, is RE but not recursive. In fact, a definition of the RE-but-not-recursive languages is that they can be enumerated, but not in numerical order. The trick to enumerating them at all is that we have to simulate all Mjs on Wi, but wc cannot allow any Mj to run forever, since it would preclude trying any other Mj for j ф i as soon as we encountered some Mi that does not halt on Wi. Thus, we need to operate in rounds, where in the fcth round we try only a limited set of Mis, and we do so for only a limited number of steps. Thus, each round can be completed in finite time. As long as for each TM Mi and for each number of steps s there is some round such that Mj wiU be simulated for at least s steps, then we shall eventually discover each M, that accepts Wi and enumerate г.

* Exercise 9.2.4: Let Xi, La,..., Lk be a coUection of languages over alphabet E such that:

1. For all i Ф 3, Li n Lj = 0; i.e., no string is in two of the languages.

2. Li и L2 и и Lf; ~ S*; i.e., every string is in one of the languages.

3. Each of the languages Li, for г - 1,2,..., is recursively enumerable. Prove that each of the languages is therefore recursive.

*! Exercise 9.2.5; Let L be recursively enumerable and let L be non-RE. Consider the language

L - {Ow I w is in L} U {Iw \ w is not in L}

Can you say for certain whether L or its complement are recursive, RE, or non-RE? Justify your answer.

! Exercise 9-2.6: We have not discussed closure properties of the recursive languages or the RE languages, other than our discussion of complementation in Section 9.2.2. Tell whether the recursive languages and/or the RE languages are closed under the following operations. You may give informal, but clear, constructions to show closure.

* a) Union.

b) Intersection.

c) Concatenation.

d) Kleene closure (star).

* e) Homomorphism.

f) Inverse homomorphism.