Section outline

  • November 24th, Friday (12:30-14:30)

    Turing Machine

    • General ideas about Turing Machine (TM)
    • Mathematical definition of TM
    • Instantaneous description of a TM
    • Computation of a TM
    • Example of computation of a TM
    • Graphical representation of the transition function of a TM
    • TM with output
    • Language accepted by a TM

    References

    • Hopcroft et al., chapter 8