Section outline

  • ΔΕΥΤΕΡΑ

    • Διοικητικά - Διαδικαστικά
    • Problems, Algorithms and Languages. Decision and optimization problems.
    • Equivalence of Computational Models, Turing Machines.


    ΠΕΜΠΤΗ

    • Time and Space bounds, multiple strings, linear speedup, nondeterminism.
    • Equivalence of Computational Models, Turing Machines, Representation as string
    • The Universal Turing Machine, Simulation, Diagonalization The Halting Problem, Recursive and Recursive Enumerable Sets, Rice’s Theorem.

    Μπορείτε να διαβάσετε:
    -Ch.1,2,3 from [1]