CS486 - Teaching Material - Winter 2005

Lecture Contents

1. 1/3/2005: Presentation of the course. Review on Languages, Automata and Grammars. Introduction to Pushdown Automata.

   Textbook: chapter 2.1



2. 1/5/2005: Pushdown automata. Instantaneous descriptions. Construction of a PDA that accepts a language generated by a given CFG.

   Textbook: chapter 2.2



3. 1/10/2005: Equivalence between CFGs and PDAs: construction of a CFG that generates a CFL accepted by a given PDA.

   Textbook: chapter 2.2



4. 1/12/2005: Chomsky Normal Form. Pumping Lemma for CFLs. Deterministic CFLs.

   Textbook: chapter 2.3 (end of part I).



5. 1/19/2005: Turing Machines. Configurations. Graphical descriptions. Turing-recognizable languages and Turing-decidable languages. Examples.

   Textbook: chapter 3.1



6. 1/24/2005: Variants of Turing Machines: multi-track, multi-tape and nondeterministic TM's.

   Textbook: chapter 3.2



7. 1/24/2005: Simulation of an NTM with a multi-track 2-tape DTM.

   Textbook: chapter 3.2



8. 1/31/2005: The Church-Turing thesis. Decidable languages.

   Textbook: chapter 3.3, 4.1




2/2/2005: Midterm1.


9. 2/7/2005: Languages and Turing machines. Cantor's theorem.

   Textbook: chapter 4.2.



10. 2/9/2005: The Halting problem.

    Textbook: chapter 4.2.



11. 2/14/2005: Reducibility.

    Textbook: chapter 5.1.



12. 2/16/2005: Rice's theorem.

    Textbook: chapter 5.1.



13. 2/21/2005: Reductions via Computation Histories.

    Textbook: chapter 5.1.



14. 2/23/2005: Mapping Reducibility.

    Textbook: chapter 5.3.
    

15. 2/28/2005: Codifying uniquely pairs of integers into integers. Goedel numbers. A program that prints its own source code. Preparation to the midterm examination.

    Textbook: chapter 6.1.




3/2/2005: Midterm 2.


16. 3/7/2005: Review of the midterm examination. The recursion theorem.

    Textbook: chapter 6.1, 6.2.



17. 3/9/2005: Decidability of logical theories. Goedel's incompleteness theorem. Sketch of the proof.

    Textbook: chapter 6.2.

Important Deadlines

• Midterm 1: Wednesday, February 2, 2005. Material to Cover: chapter 2 and chapter 3 (all).
  1. Topics: closure properties of CF languages, Pumping Lemma and Generalized Pumping Lemma, Design of PDAs and TMs, Equivalence of variants of TMs, Enumerators, Decidability.
  
  
  2. Exercises: 2.18-c, 3.8-b, 3.9, 3.10, 3.17.
  
  
• Midterm 2: Wednesday, March 2, 2005. Material to Cover: chapter 4 and chapter 5 (all except 5.2).
  1. Topics: Diagonalization. Decidable and Turing-recognizable languages. Rice's theorem. LBA. Computable functions and mapping reducibility.


• Final: Monday, March 14, 2005. Material to Cover: chapter 4, chapter 5 (all except 5.2), chapter 6.1.
  1. Topics: Diagonalization. Decidable and Turing-recognizable languages. Rice's theorem. LBA. Computable functions and mapping reducibility. Recursion Theorem.