Section outline

  • December 4th, Wednesday (10:30-12:30)

    Turing Machine

    • Multi-stack TM
    • TM and modern computers

    Undecidability

    • String indexing
    • TM encoding
    • TM indexing
    • Diagonalization language \( L_d \)
    • The TM / string infinite table

    Exercises

    • Minimization of DFA (exercise from final exam of February 13th, 2019)

    References

    • Hopcroft et al., chapter 8
    • Hopcroft et al., chapter 9