Preliminary Syllabus

Text:
Sipser, Michael, Introduction to the Theory of Computation, second edition, PWS, 2005.
(The first edition is now out of print.)

Course Objectives:

1. Introduce students to the classic results in theoretical computer science that classify problems according to the machines that can solve them and the resources required by those machines. This includes basic results relating to computable functions, decidability, and complexity theory.
2. Master basic proof techniques used in these results including induction, diagonalization, and reduction.
3. Illuminate the relationship between logic and computation.

Assumptions:

1. Students have been exposed to the concepts of regular expressions, context free grammars, and programming in a general purpose language. They have applied these concepts to solve problems such as lexical analysis, parsing, and code generation.
2. Students are familiar with discrete mathematics, including sets, sequences, induction and elementary graph theory.

Lectures: Subject to Change

1. Course Overview & Mechanics (9/27)
   • Review notation, set theory, proof, diagonalization
   • Assignments 0 and 1 are given at the first lecture
2. Review Finite Automata (9/29)
   • Definition, Closure properties, nondeterminism, regular expressions
3. Key Results for Finite Automata (10/4)
   • Equivalence of regular expressions and NFAs, Nonregular languages
4. Review Context Free Languages (10/6)
   • Context Free Grammars, PDAs
5. Non-context free languages (10/11)
   • Equivalence of PDAs/CFGs, Pumping lemma, applications
6. Church-Turing Hypothesis (10/13)
   • Introduction to Turing machines
   • Church-Turing hypothesis
7. Nondeterminism (10/18)
   • Multi-tape Turing machines
   • Nondeterministic Turing machines
8. The Halting Problem (10/20)
   • Decidability, the Halting problem
9. Reducibility (10/25)
   • Undecidable problems from language theory
10. Rice's Theorem (10/27)
    • Post Correspondence problem
    • Mapping reducibility, Rice's theorem
    • Mid-term review
11. Mid-term exam (11/1)
12. Time Complexity (11/3)
    • Time complexity, P, NP
    • Reading: Sections 7.1, 7.2, 7.3
13. NP Completeness (11/8)
14. NP Complete Problems (11/10)
    • Topics
    • Reading:
15. Space Complexity(11/15)
    • Savitch's theorem
    • PSPACE
    • Reading:
16. PSPACE Completeness (11/17)
    • Topics
17. Recursion theory (11/22)
    • Primitive recursive functions
    • Partial recursive functions
    • Kleene's T-predicate
18. No Class; Thanksgiving (11/24)
19. Acceptable computation systems (11/29)
20. Logic & Computability (12/1)
    • Incompleteness
    • Goedel's theorem
21. Final Exam: Monday, December 5, 10:15am - 12:05pm. [Corrected!]
    • Topics: Comprehensive, in-class exam.