Reduction Proofs and Rice’s Theorem

Return to List of Lectures

Previous Lecture

• Misc
  • REU Talk
    • Stephanie Allen re identifying social groups in economic need
    • Wednesday April 6th, 3:30 pm
    • South 328
    • Snacks
    • Usual extra credit for write-ups
• Questions?
• Reduction Proof Examples
  • Do L(M1) and L(M2) have at least one string in common? (I.e., is their intersection nonempty?)
    • Proof 1
      • Assume R decides whether L(M1) and L(M2) have a nonempty intersection
      • Reduce from A_TM
      • To decide A_TM, on input M, w…
        

        construct M2 w/ input x
            if x = w accept
            otherwise reject
        run R( M, M2 )   { M and M2 can have a string in common only if both accept w}
        if R accepts, accept
        otherwise reject

    • Proof 2
      • Assume R decides whether L(M1) and L(M2) have a nonempty intersection
      • Decide A_TM on input M, w as…
        

        construct M2 with input x as
            {L(M2) = Σ* if M accepts w, ∅ otherwise}
            run M on w
            if M accepts, accept
            otherwise reject
        let M3 be a Turing machine that accepts at least 1 string
        run R on M2 and M3
        if R accepts, accept, otherwise reject

  • Does program P print “I love reductions” when run on input w?
    • Assume R decides “does P(w) print ‘I love…’”
    • Solve A_PROGRAM for P w/ input x as
      • (A_PROGRAM asks whether P run on w returns true)
        

        construct P2(y) as
            if P(x)
                print “I love reductions”
            end
        run R on P2
        if R accepts, accept
        otherwise reject

    • Technically, things this runs need to be versions known to never print “I love reductions”
• Rice’s Theorem
  • If P is a nontrivial property of a Turing machine’s language (and only of the language, not of the underlying machine), then the set { ⟨M⟩ | L(M) has property P } is undecidable.
    • “Nontrivial” means some languages have the property and some do not (and all languages either have the property or don’t)
  • Proof
    • Case 1: ∅ does not have property P
      • Reduce from HALT_TM
      • Assume R decides if L(M) has property P
      • Decide HALT_TM w/ input M and w as
        

        let L(T), where T is a Turing machine, have property P
        construct M2 w/ input x
            run M on w
            run T on x, accept iff T does
        run R on M2
        if R accepts, accept
        otherwise reject

    • Case 2: ∅ has property P
      • Reduce from HALT_TM
      • Assume R decides if L(M) has property P
      • Decide HALT_TM w/ input M and w as
        

        let L(T), where T is a Turing machine, not have property P
        construct M2 w/ input x
            run M on w
            run T on x, accept iff T does
        run R on M2
        if R accepts, reject
        otherwise accept

• Problem Set
  • Handout
• Next
  • Computation histories
  • Read “Reductions via Computation Histories” in section 5.1
    • Bottom of page 220 through page 226

Next Lecture