Theory of Computation
COSC 39, Winter 2021
About the course
Computers, capable of performing universal computations and simulating other computers, is one of the greatest achievements of human civilization. One of the key components is the ability to abstract and formalize computation itself as a concrete mathematical object, called the Turing machine. Surprisingly, such definition is sufficiently robust that any attempts to formalize computation end up arriving at definitions provably equivalent to Turing machines, which encapsulate all the physical computing devices known to human beings.
While the whole discipline has been growing explosively for the past several decades, many important questions regarding the fundamental principle of computation remain unanswered; this includes the P versus NP, one of the Millennium Prize Problems that resists all attempts to be solved despite serious attempts from the most brilliant minds.
In this course we will study computation through the abstract lenses of Turing machines (including their variations), the benefit of knowing computations from a theoretical perspective, and how they relate to the rest of computer science.
Course objectives
At the end of the course, the students are expected to be able to:
Conceptually:
- Treat programs as abstract objects
- Understand the relation between machine models and languages classes
- Have a concrete mental picture of nondeterminism
- Explain and interpret the importance of universal computation
- Explain formally and informally why the P versus NP problem is (un)important to the modern study of computation
- Describe how reductions create relationship between languages
Skill-wise:
- Construct convincing and rigorous mathematical arguments
- Formally define problems and algorithms
- Explain and utilize the equivalence between three models of regular languages
- Compare the power of different machine models using reductions
- Describe and prove some basic properties about P and NP
- Demonstrate NP-hardness by performing reductions correctly
Prerequisite
A proof-based course like COSC 30: Discrete Mathematics or equivalent is required as prerequisite. Alternatively, students with reasonable mathematical background and maturity, in particular the ability to follow arguments of a proof, are welcome to take the course with instructor’s permission.
We will hand out homework 0 in the first week to give the students an idea of the background knowledge and skills expected.
Related courses
-
COSC 40 Computational Complexity: This is the sequel of COSC 39. The theory of computational complexity aims at studying and classifying computational problems using reductions based on their difficulties — the various resources needed to solve the problem. Connections between problems help us to identify central problems of study, whose breakthrough often comes with development of new insights and techniques.
-
COSC 31 Algorithms: This is the flip side of COSC 39. Algorithms are ubiquitous in computer science; this course focuses on the design and analysis of (mostly classical) algorithms, with similar emphasis on the development of rigorous and unambiguous ways of communicating ideas. Both courses will prepare you for a similar skill set that is necessary for any future career related to computer science. Unlike COSC 39 and 40, the goal of algorithms is to actually solve the problems (at least with lots of simplifying assumptions).
Textbook and references
There is no required textbook. We will use the following book and lecture notes as our main reference:
-
Michael Sipser, Introduction to the Theory of Computation. Either the 2nd or 3rd edition is fine.
-
Jeff Erickson, Models of Computation
We will also use a mix of books and class notes listed below as references. Additional relevant reading materials will be linked on the course webpage each week.
-
Scott Aaronson, Quantum Computing since Democritus
-
Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach
-
Michael Garey and David Johnson, Computers and Intractability
-
John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation (1st edition)
-
Cristopher Moore and Stephan Mertens, The Nature of Computation
-
Christos Papadimitriou, Computational Complexity
Final grades
The final grading will be based on the following factors (the tentative percentages are included):
- Working sessions (10%)
- Assignments (30%)
- Midterms (20% each)
- Final exam (20%)
Because we have a small-size class, I would prefer to talk to each of you and set up concrete goals after reviewing your submission to Homework 0. At the middle of the term we will review the goals together and revise them if necessary. At the end of the term
the grades will be assigned based on the predetermined goals.
Related Courses
Here is an (vastly incomplete) list of similar/related courses offered by other instructors.
-
H. Conrad Cunningham, Models of Computation, Dec 2015
-
Margaret Fleck and Sariel Har-Peled, Models of Computation, May 2009
-
Jean Gallier, Introduction to the Theory of Computation, Dec 2017
-
Michael Levet, Theory of Computation, Aug 2019
-
Anil Maheshwari and Michiel Smid, Introduction to Theory of Computation, Apr 2019
-
Sriram Sankaranarayanan, Introduction to the Theory of Computation, Fall 2015
-
Michael Sipser, Introduction to the Theory of Computation, Fall 2020
-
Robert Tarjan, Theory of Computation, Fall 2012
-
Luca Trevisan, Computability and Complexity, Fall 2005
-
Jeffrey D. Ullman, Introduction to Automata and Complexity Theory, Spring 2010