Lecture 23 (More undecidability), 4/17/06

Concepts, definitions (in italics):

• HALT_TM is not decidable (by reduction from A_TM)
• Mapping reduction: return the output of whatever we reduced to.
• If there is a mapping reduction from A to B:

1)      If B is recognizable, so is A        
2)      If A is not recognizable, so is B

• A_TM is the one problem we already know to be non-recognizable.
• EQ_TM is not recognizable (by mapping reduction from A_TM)
• EQ_TM is not co-recognizable; equivalently, EQ_TM is not recognizable (by mapping reduction from A_TM)
• An interesting Turing Machine problem P is a language where:

  • Each element of P is a TM description

  • P is not trivial.  That is, there exist TMs in P, and there exist TMs not in P
    (in other words, there exist M1, M2 such that M1ÎP, but M2ÏP)

  • Whenever L(M1) = L(M2) then either both ΠP or neither Î P

  (see another definition in problem 5.22)

• Examples of interesting TM problems: E_TM, REGULAR_TM
• Rice's theorem: all interesting TM problems are not decidable
• Applying Rice's theorem to L: show that L is an interesting TM problem; it follows that L is not decidable.
• Other undecidable problems: Post Correspondence Problem, Unbounded Tiling Problem (see PDF slides in Links section of web site)

Reading:

• Chapter 5.2 pp. 199-200 (including the high-level discussion of proof of Theorem 5.15, but not the details)
• Chapter 5.3 (For a mapping reduction from A to B, the textbook shows only how to convert inputs to A into inputs to B, without actually showing how A would call B)
• Chapter 5.3 Theorem 5.30
• Note: notes below provide more details than the textbook, please read them carefully
• Post Correspondence Problem, Tiling Problem (see PDF slides in Links section of course web site)

Skills:

• Know new definitions, understand new concepts.
• What is the difference between HALT_TM and A_TM?
• Understand the proof of Rice's theorem.
• Be able to apply Rice's theorem: to which languages does it apply?
• Be able to prove that EQ_TM is nether recognizable nor co-recognizable
• Understand why it would not work to prove that EQ_TM is not co-recognizable by taking the algorithm for proving that EQ_TM is not recognizable and returning the complement of what we used to return.

Notes:

Some problem is (not) co-recognizable == its complement is (not) recognizable.

If a problem A is not decidable, it is possible that A is co-recognizable, and that it is recognizable, but not both.

Can use mapping reductions to prove (by contradiction) that something is not recognizable.

A mapping reduction from L1 to L2 is the same as a mapping reduction from the complement of L1 to the complement of L2

Mapping reduction from ATM to EQ_TM to show that EQ_TM is not recognizable.

ATM  Recognizer (M,w)
{
1)  create M₁, M₂ as follows

M₁(x) {
      Reject x;                                        
      }

M₂(X) {
      Simulate M on w
      If M accepts w, we accept x; otherwise, we do not
      }

2) return EQ_TM -recognizer (M₁,M₂)
}
 

	ATM  recognizer should return	L(M1)	L(M2)	EQTM recognizer
M accepts w	Reject or loop	Ø	∑*	Reject or loop
M does not accept w	Accept	Ø	Ø	Accept

• Mapping reduction from ATM to EQTM to show that EQTM is not recognizable
  
  A_TM-Recognizer (M,w)
  {
  1) create M1, M2 as follows                         

      M1(X) {
            Accept x;       
            }                                                         

      M2(X) {
            Simulate M on w                                                 
            If M accepts w, we accept X
            }

   2) return EQ_TM-recognizer (M1,M2)
   }

  	ATM  recognizer should return	L(M1)	L(M2)	EQTM recognizer
  M accepts w	Reject or  Loop	∑*	∑*	Reject or loop
  M does not accept w	Accept	∑*	Ø	Accept

• Proof of Rice's theorem (by contradiction):

  1) Suppose P is decidable, i.e. there exists a valid P-DECIDER algorithm.

  2) Let M-empty be some TM that rejects everything (its language is empty).
  case 1: If M-empty is not in P, let M₀ be some TM in P;
  case 2: if M-empty is in P, let M₀ be some TM not in P
  (as P is non-trivial there must be one in either case).

  3) Here is a valid reduction from A_TM-DECIDER to P-DECIDER:

A_TM-DECIDER(M,w)
{
1. Create M₁ as follows

M₁(X) {
      run M on w
      if M accepts, run M₀ on X
      else reject (or loop)
      }

2. return P-DECIDER(M₁) if M-empty is not in P,
or its negation if M-empty is in P
}

Here is a table for the case when M-empty is not in P; the table for the case when M-empty is in P will reverse accepts and rejects in the 4th column, but be the same otherwise.

	ATM  decider should return	L(M1)	P_decider (M1)
M accept w	Accept	same as L(M0)	Accept M1 (because it accepts M0, and L(M1) = L(M0))
M not accept w	Reject	Ø, same as L(Mempty)	Reject M1 (because it rejects Mempty and L(M1) = L(Mempty))

4)  This is a valid mapping reduction from ATM  to P. Since ATM  is not decidable, so is P.

Big conclusion: there are many software tools that cannot be constructed perfectly -- they may be useful, but there is always some input (program) out there on which they will fail.