CS4510 Automata and Complexity

Summer 2023 3:30-5:40PM TR in ES&T (Ford) Room L1255


Course Information

This course answers two main questions:

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 a computation? What even is a computer? Are all problems solvable? We will explore several models of computation and explore their 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.

Other schools may call a version this course something like "Great Ideas in Computer Science". I like to think of it like, a kind of finale to your CS degree. This is the course where you will learn why computer science gets to be called a science.

This course has a lot of preqs, 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. We will follow the book very closely, and the places we differ from the book will be explicitly mentioned.


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 three exams. They are open note and open book, but not open internet. You will also have ten problem sets. Your tentative exam dates are:

Jun 06 Exam 1

Jun 30 Exam 2

Jul 27 Exam 3


This is subject to change as I realize what takes more or less time. Summer pacing is usually weird. We will split each class into two sections, each one hour, with a ten minute break in between. I will record lectures and post them.



Day Title
May 16 01A Introduction
May 16 01B Deterministic Finite Automata
May 18 02A Nondeterminism
May 18 02B Powerset Construction
May 23 03A Regular Expressions
May 23 03B The Pumping Lemma
May 25 04A Context Free Grammars
May 25 04B Closure
May 30 05A Syntactic Structures
May 30 05B Chomsky Normal Form
Jun 01 06A Pushdown Automata
Jun 01 06B Each CFG has a PDA
Jun 06 07A Each PDA has a CFG
Jun 06 07B Non Context-Free Languages
Jun 08 08A Turing Machines
Jun 08 08B The Church-Turing Thesis
Jun 13 09A Simulation evidence
Jun 13 09B Turing-Completeness
Jun 15 10A Countability
Jun 15 10B Diagonalization
Jun 20 11A A Crisis in Geometry
Jun 20 11B Russell's Paradox
Jun 22 12A Godel Incompleteness
Jun 22 12B The Halting Problem
Jun 27 13A The Art of Reduction
Jun 27 13B Rice's Theorem and PCP
Jun 29 14A Kleene's Recursion Theorem
Jun 29 14B Kolmogorov Complexity
Jul 06 15A P
Jul 06 15B NP
Jul 11 16A Cook-Levin Theorem
Jul 11 16B Ladner's Theorem
Jul 13 17A Savitch's Theorem
Jul 13 17B PSPACE-completeness
Jul 18 18A Hierarchy Theorems
Jul 18 18B The Relativization Barrier
Jul 20 19A Advice
Jul 20 19B Circuits
Jul 25 20A The Polynomial Hierarchy
Jul 25 20B Karp-Lipton Theorem

Statement of Intent for Classroom Inclusivity

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.