Scribe:Nathan TranDate:May 6th, 2003

5.4 –Undecidable Problems

  • Halting Problems (revisit)
  • Reductions
  • Problems on r.e. sets w/ non-trivial properties: Rice’s Theorem

Universal Turing Machine

Encoding of TM’s: <M>

Halting Problem:

K = {<M> | M is a TM and M halts on the input <M>}

(K is denoted by H in the text-book)

Theorem: K is undecidable, but K is Turing acceptable.

Let HALT = {<M<X> | M is a TM and M halts on the input x}

- We could also use <M,x> to denote <M<x>.

- We also use H to denote HALT.

We’ll show that H is undecidable. We’re going to use “reduction” to prove this result.

Reduction:

Suppose we have two languages A and B. If there is a Turing-computable function f

(i.e., f can be computed by a TM M on all inputs & M always halts)

Such that iff f(x) B, then we say that A is reducible to B, written as B

Proposition 1: If B and B is decidable, then A is decidable.

Proof: Assume that B via a reduction f, then we know that f is Turing-computable, and iff f(x) B. If B is decidable, then a DTM that decides B.

i.e., on any input always halts and

- If x B, then accepts x

- If x B, then rejects x

Let be a TM that computes f. Construct a DTM to decide A as follows:

(x) = ((x))

This means on any input x, first simulates on x. Then, simulates on the output f(x) of on x.

- Since on any input x always halts, and on any input always halts, we know

that on any input will always halt.

- Since has two halting states, and , will also have two halting states.

Now x, if xA, then f(x) B. Hence, accepts f(x).

-Since (x) = f(x), we have: if xA, then accepts (x)

This means that accepts x. Similarly, if x A, then f(x) B. Hence, rejects f(x). This means that rejects x. Thus, decides A, so A is decidable.

Corollary. If B and A is not decidable, then B is not decidable. (End Proposition)

Now we’re ready to show that:

H = { <M<x> | M is a TM & halts on x } is not decidable by reducing to H.

We can construct this reduction as follows:

On any instance <M> of , define f(<M>) = <M<M>

Then it’s easy to see that f is Turing-computable (a machine that duplicates its input).

And we have:

<M>: <M> iff M is a TM & M halts on <M>

iff <M<M>H

iff f(<M>) H

Hence, we know that H. Thus, H is not decidable. (End Halting Problem)

Proposition 2: If A B and B is Turing-acceptable, then A is Turing-acceptable.

Proof:Since A B, there is a Turing-computable reduction f, s.t. iff f(x)B.

Let be a DTM that computes f. This means that on any input x, always halts and produces f(x) as its output.

Assume that B is Turing-acceptable. Then, there is a DTM , s.t. B = L(). This means that for all input x, if xB, then on x halts, and x B, then on x never halts.

Now we construct an acceptor for A as follows:

(x) = ((x))

On any input x, if xA, then f(x)B. Hence,on the input f(x) halts.

Since f(x) = (x), halts on (x). Thus, if xA, then on x halts. On the other hand, if xA, then f(x)B. Hence, on the input f(x) never halts. This implies that on x never halts. Thus, is indeed an acceptor for A. So A is Turing-acceptable.

Corollary. If A B and A is not recursively enumerable( same as Turing-acceptable), then B is not recursively enumerable. (End Proposition)

- This means that we have a way to show that a language is not Turing-acceptable.

For instance, we know that is not Turing-acceptable (H is Turing-acceptable, but is not decidable).

If we can reduce to a language L, then L is not Turing-acceptable.

Proposition 3: A B iff . (Proof by Def.)(End Proposition)

Example:

Let L = {<> | and are TM’s and L() L()

Then L is not Turing-acceptable.

Proof:Reduce H to as follows:

Construct a reduction f, s.t. on instance (input) of H <M<x>, f outputs two TM’s and ,

where accepts everything:

i.e., L() = ,

and on input w, will first simulate halts on w:

i.e., if M on x halts, then L()= .

This means that f(<M<x>) = <> and <M<x>H,

Iff L() = & L () =

Iff <

Hence, H . Hence, H L.

This implies that L is not Turing-acceptable. (End Example)

Problems on r.e. sets w/ non-trivial properties: Rice’s Theorem:

We’ll call a set of r.e. sets a property. E.g.,

Non-Trivial Properties:

{Ø} is the property of r.e. sets “being empty”

{} is the property of “being full”

{regular languages} is the property of “being regular”

For any given property P, we can look at a language

= { <M> | M is a TM & L(M)P}

E.g.,

E = {<M> | M is a TM & L(M) = Ø }

F = {<M> | M is a TM & L(M) = }

R = { <M> | M is a TM & L(M) is regular }

- All of these languages are not decidable.

Say a property P is trivial if p = Ø or p contains all r.e. sets.

Rice’s Theroux:For any non-trivial property P, is not decidable.

- As a direct application of Rice’s Theorem, we know that E, F, R are not decidable.