Lecture 21 (Rice’s Theorem), 11/15/17

Concepts, definitions (in italics):

·         Mapping reduction:  return the output of whatever we reduced to.

o    Written A <=m B

o    Reducing function takes input to A to input to B

·         Usefulness of mapping reductions: can use them for recognizers (and not just deciders)

o    If A mapping-reduces to B (A <=m B) and B is recognizable then A is recognizable

o    If A mapping-reduces to B and A is not recognizable then B is not recognizable

·         Saw mapping from a to reg, non-mapping from a to e,

·         Mapping reduction from A-TM to the complement of EQ-TM (p.238)

o    Cannot create by combining ones we saw (a to e, e to eq) - why?

o    Same as from complement A=TM to eq-tm

·         Corollary 1: EQTM is not recognizable

·         Mapping reduction from A-TM to EQ-TM (i.e. complement-ATM to complement-EQ-TM (p.238)

·         An interesting TM problem is a language P where:

·         Examples of interesting TM problems: ETM, REGTM

·         Rice's theorem: all interesting TM problems are not decidable

·         Applying Rice's theorem to L: 1) show that L is an interesting TM problem; 2) it follows that L is not decidable.

·         Implications for software engineering: there are many software tools that cannot be constructed perfectly to work on all possible programs -- they may be useful, but there is always some input (program) out there on which they will fail.

·         Post Correspondence Problem (PCP)

o    Example of an undecidable problem that seems to be unrelated to TMs

·         Can simulate Turing machines using dominos

·         ATM mapping-reduces to PCP

Reading:

·         Chapter 5.2 up to theorem 5.15; Chapter 5.3

·         Rice’s theorem is defined in problem 5.28; the proof is below

Skills:

Notes:

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

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

2) Let M1 be some TM that rejects everything (its language is empty).
case 1: If M1 is not in P, let M2 be some TM in P;
case 2: if M1 is in P, let M2 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 ATM-DECIDER to P-DECIDER:

ATM-DECIDER(M,w)
{
1. Create M3 as follows

M3(X) {
      run M on w
      if M accepts, run M3 on X
      else reject
      }

2. BOOL b = P-DECIDER(M2)
3. if
M1 is in P // case 1
    return !b
else // if
M1 is in not P, case 2
    return b

}

Here is the table

 

ATM  decider
should

What is L(M3)?

What will P_decider (M3) do?

ATM  decider
returns

 

M accept w

ACCEPT

same
as L(M2)

If M2 is in P
(and M1 is not in P)
it will ACCEPT
else R
EJECT

ACCEPTS

 

M does not
accept w

REJECT

empty
(same
as L(M1))

If M2 is in P
(and M1 is not in P)
it will ACCEPT
else REJECT

REJECTS

 

This table shows that we have a valid reduction from ATM  to P. Since ATM  is not decidable, so is P.