This course answers two main questions:
What are the fundamental limits of computation?
What makes some problems easy, and others hard?
The first question is the study of the area of Computability theory. Most of its questions are solved, which is what makes this subject fun. We are concerned with such extremal, almost philosophical questions. What even is computation? What even is a computer? Are all problems solvable? We will explore several models of computation and explore their relative power, and weaknesses.
The second question is the study of Complexity theory. Most of its questions are unsolved. This subject does not have a happy ending (and perhaps won’t, in our lifetimes) but this contrast is what makes it interesting. We may not know how to solve certain questions, but ironically, we know a lot about how hard these questions are.
I like to think of this course as a finale to your CS degree. It is simultaneously the most important and least important course you will take. It is the least important as it doesn’t develop any single technical skill. It is the most important, as it develops your ability to conceptualize and theorize. This is the course where you will learn why computer science gets to be called a science. It puts the rest of your degree into context.
This course has a lot of pre-reqs, some of which I would disagree should be a requirement. All you really need is good proof skills, like those found CS2050. If you think you might be rusty, please refresh chapter zero of the Sipser book.
The book for the course is Introduction to the Theory of Computation by Michael Sipser. It is an excellent textbook, can’t count how many times I’ve read it. The notes and lectures for the course are the authoritative reference, but it is expected you follow along with Sipser’s book. Later on, I may reference the Arora-Barak and Li-Vitanyi books.
In order to accomodate students who wish to take this course fully remote, I have decided to make all assignments take home. The tradeoff here is that the difficulty will increase. You will have four exams. They are open note and open book, but not open internet. You will also have ten problem sets. Your tentative exam dates are:
May 29 Exam 1
Jun 12 Exam 2
Jul 10 Exam 3
Aug 05 Exam 4
This is subject to change as I realize what takes more or less time.
| No. | Date | Lecture |
|---|---|---|
| L01A | May 18 | Introduction |
| L01B | May 18 | Deterministic Finite Automata |
| L02A | May 20 | Nondeterminism |
| L02B | May 20 | Powerset Construction |
| L03A | May 27 | Regular Expressions |
| L03B | May 27 | The Pumping Lemma |
| L04A | Jun 01 | Context-Free Grammars |
| L04B | Jun 01 | Regular Grammars and Closure |
| L05A | Jun 03 | Syntactic Structures |
| L05B | Jun 03 | Chomsky Normal Form |
| L06A | Jun 08 | Pushdown Automata |
| L06B | Jun 08 | Equivalence of PDAs and CFGs |
| L07A | Jun 10 | Pumping Context-Free Languages |
| L07B | Jun 10 | Parikh’s Theorem |
| L08A | Jun 15 | Turing Machines |
| L08B | Jun 15 | The Church-Turing Thesis slides, required reading1, required reading 2, required reading 3 |
| L09A | Jun 17 | CTT as a falsifiable hypothesis |
| L09B | Jun 17 | Turing-completeness |
| L10A | Jun 22 | Countability |
| L10B | Jun 22 | Diagonalization |
| L11A | Jun 24 | Foundations of Mathematics |
| L11B | Jun 24 | Russell’s Paradox |
| L12A | Jun 29 | Godel’s Incompleteness Theorems |
| L12B | Jun 29 | The Halting Problem |
| L13A | Jul 01 | The Art of Reduction |
| L13B | Jul 01 | Post’s Correspondence Problem |
| L14A | Jul 06 | Recursion and Truth |
| L14B | Jul 06 | Kolmogorov Complexity |
| L15A | Jul 08 | Computational Complexity |
| L15B | Jul 08 | Nondeterministic Polynomial Time |
| L16A | Jul 13 | Cook-Levin Theorem |
| L16B | Jul 13 | Ladner’s Theorem |
| L17A | Jul 15 | Savitch’s Theorem |
| L17B | Jul 15 | PSPACE-completeness |
| L18A | Jul 20 | Hierarchy Theorems |
| L18B | Jul 20 | Relativization |
| L19A | Jul 22 | Circuit Complexity |
| L19B | Jul 22 | Circuit Lower Bounds |
| L20A | Jul 27 | Polynomial Time Hierarchy |
| L20B | Jul 27 | Karp-Lipton Theorems |
Besides the notes we will publish this semester, I recommend you use the following two references:
Submission of any work not your own will result on a zero on the assignment to a report to OSI, which may incur further sanctions.
As a member of the Georgia Tech community, I am committed to creating a learning environment in which all of my students feel safe and included. Because we are individuals with varying needs, I am reliant on your feedback to achieve this goal. To that end, I invite you to enter into dialogue with me about the things I can stop, start, and continue doing to make my classroom an environment in which every student feels valued and can engage actively in our learning community.