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.
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.
This is subject to change as I realize what takes more or less time.
| No. | Date | Subject | Notes |
|---|---|---|---|
| 01 | Aug 21 | Introduction and DFAs | notes |
| 02 | Aug 23 | Nondeterminism | notes |
| 03 | Aug 28 | Regular Expressions | notes |
| 04 | Aug 30 | The Pumping Lemma | notes |
| Sep 06 | Exam 1 | ||
| 05 | Sep 11 | Context-Free Grammars | notes |
| 06 | Sep 13 | Syntactic Structures | notes |
| 07 | Sep 18 | Pushdown Automata | notes |
| 08 | Sep 20 | Equivalence of PDAs and CFGs | notes |
| 09 | Sep 25 | Pumping Lemma for CFLs | notes |
| Sep 27 | Exam 2 | ||
| 10 | Oct 02 | Turing Machines | notes |
| 11 | Oct 04 | Church-Turing Thesis | notes,slides, pre notes, required reading 1 , required reading 2, handout |
| 12 | Oct 11 | Turing-Completeness | notes,pre notes |
| 13 | Oct 16 | Countability | notes |
| 14 | Oct 18 | Foundations of Mathematics | notes |
| 15 | Oct 23 | Incompleteness and Undecidability | notes |
| 16 | Oct 25 | Art of Reduction | notes |
| 17 | Oct 30 | Post's Correspondence Problem & Rice's Theorem | notes |
| 18 | Nov 01 | Kolmogorov Complexity | notes |
| Nov 06 | Exam 3 | swapped with lecture 19 | |
| 19 | Nov 08 | Complexity Classes | notes |
| 20 | Nov 13 | In and around NP | notes |
| 21 | Nov 15 | In and around PSPACE | notes |
| 22 | Nov 20 | Relativization | notes |
| 23 | Nov 27 | Circuits | draft |
| 24 | Nov 29 | The Polynomial Hierarchy | draft |
| 25 | Dec 04 | Karp-Lipton Theorems | draft |
| Dec 08 | Final Exam |
Besides the notes we will publish this semester, I recommend you use the following two references:
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.
