Section outline

  • December 12th, Thursday (08:30-10: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)

    References

    • Hopcroft et al., chapter 9