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 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.
This is subject to change as I realize what takes more or less time.
|Jan 23.||The Pumping Lemma||notes|
|Jan 25.||Context Free Grammars||notes|
|Jan 30.||Syntactic Structures||notes|
|Feb 01.||Exam 1 Review|
|Feb 06.||Exam 1|
|Feb 08.||Pushdown Automata||notes|
|Feb 13.||Equivalence of PDAs and CFGs||notes|
|Feb 15.||Pumping Lemma for CFLs||notes|
|Feb 20.||Turing Machines||notes|
|Feb 22.||Church-Turing Thesis||notes,handout,many books|
|Feb 27.||Countability||notes,pre notes|
|Mar 01.||Exam 2 Review|
|Mar 06.||Exam 2|
|Mar 08.||Foundations of Mathematics||notes,logicomix1,logicomix2,pre notes|
|Mar 13.||Undecidability by Reduction||notes,pre notes|
|Mar 15.||Post's Correspondence Problem||notes,pre notes|
|Mar 27.||Kolmogorov Complexity||notes,pre_notes|
|Mar 29.||Complexity Classes||notes,pre notes|
|Apr 03.||Cook-Levin Theorem||notes,pre notes|
|Apr 05.||Exam 3 Review|
|Apr 10.||Exam 3|
|Apr 12.||Savitch's Theorem||notes,pre notes|
|Apr 17.||Relativization||notes,pre notes,blog|
|Apr 24.||The Polynomial Hierarchy||notes,pre_notes|
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.