Section outline

  • December 12th, Tuesday (12:30-14:30)

    Undecidability

    • Diagonalization language \( L_d \)
    • Properties of recursive languages
    • Properties of RE languages
    • Universal Language \( L_u \)
    • Universal TM \( U \)
    • \( L_u \) is in RE
    • \( L_u \) is not in REC (\(L_d \leq_m \overline{L_u}\))
    • Halting problem for a TM on a given input

    References

    • Hopcroft et al., chapter 9