5. Use Rice’s theorem to show that the following sets are not recursive. [See se

Question

5. Use Rice’s theorem to show that the following sets are not recursive.

[See section 6 for the definitions of the sets]

(a) TOT;

(b) EMPMTY;

(c) INF;

(d) FIN;

(e) MONOTONE;

(f) {y N | y(1) is a predicate}

P 97 Ex 5 : Computability,Complexity, and Languages by Davis, Sigal, Weyuker

Explanation / Answer

Diagonalization and reduction are two common techniques used to show that a given set is not r.e. These techniques are also commonly used to show that a given set is not recursive (i.e., not decidable). To illustrate how to use these two techniques, we consider a set Tot defined as follows: Tot = {hMi | M is a Turing Machine and M halts on any binary string}, where hMi represents a fixed binary encoding of M’s description and {0, 1} is M’s input alphabet. We can show that Tot is not r.e., nor is Tot Suppose for the sake of contradiction that Tot is r.e. It follows from Proposition 1 that there is a recursive function g such that Tot = range(g). This means that for any given binary string x, g(x) gives a binary encoding of a Turing machine that halts on anybinary string input y (including on input x itself). Denote this Turing machine by Mg(x) . We construct using diagonalization a recursive function f as follows: f(x) = ( 0, if Mg(x)(x) > 0 1, if Mg(x)(x) = 0 The function f is recursive because it is total. It follows from the construction that f(x) 6= Mg(x)(x) for any x. Let Mf be a Turing machine that computes f. Thus, Mf halts on any input. This implies that hMf i ? Tot and so there must be an x such that g(x) = hMf i. This means that Mg(x)(x) = Mf (x) = f(x), a contradiction. Thus, the assumption that Tot is r.e. is incorrect. This completes the proof. 2. g(0) = x0, g(x + 1) = ?1(x) if T(?1(x), a, ?2(x)), x0 otherwise. Since this type of argument is new, it is helpful to explain informally what g does. For every input x, the function g tries finitely many steps of a computation on input a of some partial recursive function. The computation is given by ?2(x), and the partial function is given by ?1(x). Since ?1 and ?2 are projection functions, when x ranges over N, both ?1(x) and ?2(x) also range over N. Such a process is called a dovetailing computation. It is infinite. For every input x, the function g tries finitely many steps of a computation on input a of some partial recursive function. The computation is given by ?2(x), and the partial function is given by ?1(x). Mf halts on any input. This implies that hMf i ? Tot and so there must be an x such that g(x) = hMf i. This means that Mg(x)(x) = Mf (x) = f(x), a contradiction.. It is finite as

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.