CSE 431: Theory of Computation
Winter, 2018
Instructor: James R. Lee (jrl@cs)
Office hours: TBD, CSE 640
TA : Yuqing Ai (yuqingai@cs)
Office hours: TBD
T Th 12-120pm EEB 037
Email and discussion:
Class email list: cse431a_wi18 [click link to sign up]
[archives]
Discussion board
Textbook:
-
Main text:
Introduction to the Theory of Computation (3rd ed)
Michael Sipser, PWS Publishing.
Lectures
| date | topic | media | reading |
| 4-Jan | Introduction Turing machines | pdf slides [epic Game of Life video] |
Sipser 3.1-3.3 |
| 9-Jan | Universality Decidability and the Halting Problem | Sipser 3.1-3.3, 4.1-4.2 |
Topics:
- Turing machines and the Church-Turing Thesis
- Decidability and the Halting Problem
- Reductions
- Time complexity
- P vs. NP
- NP-completeness and the Cook-Levin Theorem
- Space complexity
- Interactive proofs and IP=PSPACE
- Advanced topics
Related material:
- Scott Aaronson's Who can name the bigger number?
- Alan Turing's 1936 paper On computable numbers, with an application to the Entscheidungsproblem.
- A New Yorker article about Alan Turing.
- Hilbert's 23 problems (Problems 2 and 10 are of relevance to this course.)
- An interesting popular review of a book about Kurt Godel.
- A New Yorker article: "What were Einstein and Godel talking about?"
- The Algorithm: Idiom of Modern Science
- Logicomix: An epic search for truth