CSE 431: Introduction to the Theory of Computation
Winter, 2025
Paul Beame
Lectures MWF 10:30-11:20.Office hours: MWF 11:20-11:50 and W 3:00-3:50
Office: CSE 668, Phone 206-543-5114.
Discussion board:
We will use the Ed discussion board. This is the right place to ask any questions about the course. We will happily answer questions from lecture or about general concepts. We also will answer clarifications about homework (e.g. correcting typos). You are encouraged to answer each other’s questions on the message board as well. If you have a question that might reveal your approach to a homework problem, you must ask the question privately. For accommodations and other private questions, you can ask privately on Ed or email the instructor directly. Only you and the course staff can see a private question on Ed.Homework submission is via Gradescope.
Canvas
We will only use Canvas for Panopto lecture capture and for the release of homework solutions.
Textbook:
Michael Sipser, Introduction to the Theory of Computation.Any of the first, international, second or third editions will work. Earlier editions are less than one quarter the cost of the third edition online. Although the numbering of almost everything in the first and international editions is different from the others, the content is mostly unchanged except for some corrections and new and solved problems in each subsequent edition. The third edition has an extra section 2.4 on deterministic context-free languages that we won't cover anyway. See errata links from Sipser's book page for lists of errors and corrections.
Review Reading:
- Review Sipser text: Chapter 0
- Review Sipser text: Chapter 1
- If you did not take CSE 311 and have not seen finite state machines, you should skim Chapter 1 of Sipser's text to get a sense of the material covered there.
Lectures
| Date | Topic | Materials | Reading (Sipser) |
| Mon, Jan 6 | Introduction. Prehistory of computing |
Infinity & Computation | Chapter 3 (first part 3.3) |
| Wed, Jan 8 | Turing Machines | Turing & Post Handout | |
| Fri, Jan 10 | Turing Machines definition & operation | Notes #1 | Section 3.1 |
| Mon, Jan 13 | Turing Machine diagrams k-tapes ≡ 1-tape |
Notes #1 | Section 3.1-3.2 |
| Wed, Jan 15 | Finish k-tapes ≡ 1-tape NTMs, NTM≡ TM |
Notes #1 | Section 3.2 |
| Fri, Jan 17 | TM enumerators L, L' T-rec → L Decidable Church-Turing Thesis |
Notes #1 | Section 3.2-3.3 |
| Mon, Jan 20 | HOLIDAY | ||
| Wed, Jan 22 | Decidable properties of machines & grammars Universal TM: ATM is T-rec |
Notes #2 | Section 4.1-4.2 |
| Fri, Jan 24 | Undecidability, Mapping Reductions | Notes #2 | Sections 4.2, 5.3 |
| Mon, Jan 27 | Undecidability of HALTTM, ETM, TM Equivalence | Notes #3 | Sections 5.3, 5.1 |
| Wed, Jan 29 | REGULARTM, IRREGULARTM, Rice's Theorem | Rice's Theorem Proof Notes #3 |
Section 5.1 |
| Fri, Jan 31 | Undecibability via computation histories Linear Bounded Automata, ALBA, INTERCFG, ALLCFG | Notes #3 | Section 5.1 |
| Mon, Feb 3 | Godel Incompleteness | Notes #4 | Chapter 6 |
| Wed, Feb 5 | CFGs, PDAs, Turing Chomsky Normal Form, ACFG decidable Pumping Lemma for CFGs |
Notes #4 Chomsky Normal Form |
Skim Chapter 3 |
| Fri, Feb 7 | Time Complexity for TMs, NTMs P, NP, Examples |
Notes #4 | Chapter 7 |
| Mon, Feb 10 | CFLs in P, NP & Verifiers, SAT | Notes #5 CKY Algorithm |
Sections 7.2-7.3 |
| Wed, Feb 12 | Polynomial-time reductions, NP-complete, NP-hard, Cook-Levin Theorem, Circuit-SAT |
Notes #5 | Section 7.4, 9.3 |
| Fri, Feb 14 | Midterm | ||
| Mon, Feb 17 | HOLIDAY | ||
| Wed, Feb 19 | CIRCUIT-SAT is NP-complete, Most functions require large circuits | Sipser 9.3 | |
| Fri, Feb 21 | |||
| Mon, Feb 24 | |||
| Wed, Feb 26 | |||
| Fri, Feb 28 | |||
| Mon, Mar 3 | |||
| Wed, Mar 5 | |||
| Fri, Mar 7 | |||
| Mon, Mar 10 | |||
| Wed, Mar 12 | |||
| Fri, Mar 14 |
| TA | Office hours | Room | |
| Matthew Shang | Mondays 3:30-4:20 | Gates 153 | |
| Wednesdays 1:30-2:20 | Gates 153 | ||
| Michael Whitmeyer | Tuesdays 2:30-3:20 | Allen 220 | |
| Thursdays 9:30-10:20 | Gates 153 | ||
Homework:
Before starting on homework, please review our homework policy Submission is online in Gradescope. Extra credit problem solutions need to be uploaded separately from the regular problems.
- Homework 1 (Due: Thursday, Jan 23, 11:59 pm. Latex source).
- Homework 2 (Due: Thursday, Jan 30, 11:59 pm. Latex source).
- Homework 3 (Due: Thursday, Feb 6, 11:59 pm. Latex source).
- Homework 4 (Due: Thursday, Feb 20, 11:59 pm. Latex source).
- Homework 5 (Due: Thursday, Feb 27, 11:59 pm. Latex source).
Exams:
- Midterm exam:
Friday, Feb 14 in class. Closed book and closed notes. It will cover the material we have discussed through last Friday, Jan 31, as well as everything covered on (non-extra credit) homework up to HW3. There will be a review session on Zoom on Wednesday, Feb 12 starting at 4:30 p.m. Please bring your questions to ask. Here is a sample midterm and as well as solutions. - Final exam:
The final exam will be in our regular classroom at the time listed in the official exam schedule which is 8:30-10:20 am, Monday March 17.
Grading Scheme:
The grading scheme below is subject to change depending on our ability to have in-person exams this term.
| Homework | 45-55% + Extra Credit |
| Midterm | 15-20% |
| Final Exam | 30-35% |
Further reading
- Hilbert's 23 Problems (See, especially, problems 2 and 10.)
- David Hilbert Bio
- Kurt Gödel Bio
- Alonzo Church Bio
- Alan Turing Bio
- Extensive material on advanced topics in computational complexity is available in Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak. A page containing a draft of the book is available here: