Section outline

  • November 27th, Wednesday (10:30-12: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
    • Language accepted by a TM that always halts
    • Recursive languages (REC) and recursively enumerable languages (RE)
    • Decision problems and associated languages (see chapter 1, section 1.5.4)

    References

    • Hopcroft et al., chapter 8