Section outline

  • ΔΕΥΤΕΡΑ

    • Turing machines with multiple strings, linear speedup, nondeterminism.
    • Equivalence of Computational Models, Turing Machines, Representation as strings.
    • Computability & Undecidability: The Universal Turing Machine, Simulation, Diagonalization

    ΠΕΜΠΤΗ

    • Complexity Classes: Complexity Measures, Time and Space Classes, Hierarchy Theorems, Gap Theorem.

    Προτεινόμενη Μελέτη:
    -Ch.1,2 από το [1]
    -Ch.3: p. 57-63 από τo [1]
    -Ch. 7: p.139-146 από το [1]
    - Ch.1 από το [2]