Section outline

  • December 12th, Friday (10:30-12:30)

    Undecidability

    • Properties \( \cal P\) of RE languages and associated languages \( L_\cal P\)
    • Rice's theorem
    • Discussion
    • Definition of Post's correspondence problem (PCP)
    • Example
    • PCP is not recursive (no proof)

    Exercises

    • Let \(L_{ev}\) be the language of all strings in \(\{0,1\}^\ast\) with even length. Define \({\cal P} = \{ L \; | \; L \in {\rm RE}, \; L_{ev} \subsetneq L \} \) and define \( L_{\cal P} = \{ \mathsf{enc}(M) \; | \; L(M) \in {\cal P} \} \). Is \(L_{\cal P}\) a recursive language? (exercise from final exam of January 22nd, 2019)

    References

    • Hopcroft et al., chapter 9