back to cs486-syllabus

CS486 - Teaching Material - Winter 2007

Lecture Contents

  1. 1/3/2007: Presentation of the course. Review on Languages, Automata and Grammars. Turing Machines. Deciders. Turing-recognizable languages and Turing-decidable languages.

  2. 1/8/2007: Turing Machines with multiple tracks. TMs with multiple tapes. Simulation of a TM with multiple tapes using a TM with multiple tracks and with quadratic slowdown. Nondeterministic TMs (NTMs). Simulation of an NTM with a DTM with multiple tapes and with exponential slowdown. Enumerators. Recursively enumerable languages. Equivalence between Recursively enumerable and Turing-recognizable languages.

  3. 1/10/2007: Simulation of a tyipical computer with a multitape TM. The tenth problem of Hilbert. The Church-Turing thesis.

  4. 1/17/2007: Simulation of a tyipical computer with a multitape TM with a cubic slowdown. Discussion on the complexity of performing arithmetic operations.

  5. 1/22/2007: The Halting Problem. Universal TMs. The pair function. Associating uniquely sequences of integers to integers. Goedelization of TMs. Data, TMs and Problems. Cantor's theorem and the diagonalization technique. Existence of non Turing-recognizable problems.

  6. 1/24/2007: Undecidability of the Halting Problem. Reductions.

  7. 1/29/2007: Reductions via computation histories. PDAs.

  8. 1/31/2007: PCP. Mapping reducibility. Rice's theorem.

  9. 2/5/2007: Preparation to the MT.

  10. 2/7/2007: MT1.

  11. 2/12/2007: Review of MT1. The Recursion theorem.

  12. 2/14/2007: More on the Recursion theorem: the fixed point version. Well-formed terms and well-formed formulas. Decidability of logical theories.

  13. 2/19/2007: A decidable theory.

  14. 2/21/2007: Undecidability of Th(N,+,*). Notion of syntatic proof. Hilbert's calculus: completeness and soundness.

  15. 2/26/2007: Goedel's incompleteness Theorem.

  16. 2/28/2007: MT2.

  17. 3/5/2007: Review of MT2. Introduction to computational complexity. The classes P and NP.

  18. 3/7/2007: NP-completeness. The P vs NP question. Cook's theorem.

  19. 3/12/2007: Proofs of NP-completeness. CNFSAT <=p 3SAT. 3SAT <=p IS.

Packages

  1. Self

Important Deadlines

  1. 2/5/2007: MT1. Postponed to 2/7/2007. Sample MT
  2. 2/28/2007: MT2: up to 6.2 (posted 2/21/07).

CSNS - Computer Science Network Services

Assignments and exams should be uploaded by the due date through the CSNS - Computer Science Network Services website. If you have never used this system before then follow the instructions for students.