Catalog Description: This course gives an introduction to the mathematical foundations of computation. The course will look at Turing machines, universal computation, the Church-Turing thesis, the halting problem and general undecidability, Rice’s theorem, the recursion theorem, efficient computation models, time and space (memory) bounds, deterministic and nondeterministic computation and their relationships, the P versus NP problem and hard problems for NP and beyond.
Note: This course will replace Math 374 (Theory of Computability and Turing Machines) which is listed as a recommended way to fulfill the undergraduate theory breadth requirement in CS but hasn’t been taught in several years. The Math department is happy to give it up.
Required Textbook: Computability and Complexity Theory by Steve Homer and Alan Selman
Course Goals: A firm background in the basic principles of theoretical computer science with a particular understanding of undecidability and intractability, the theoretical limitations of computation.
Prerequisites: EECS 310 (Discrete Mathematics) or permission of instructor.
Detailed Course Topics:
-
Alphabets, Strings, Languages and Classes
-
Turing Machines
-
Multiple Tapes and RAMs
-
Nondeterministic
-
Church-Turing Thesis
-
-
Computability Theory
-
Decision Problems
-
Computable and Computably Enumerable Sets
-
Universal Turing Machines
-
Undecidability
-
Halting Problem
-
Rice’s Theorem
-
-
Recursion Theorem
-
-
Complexity Theory
-
Time and Space (memory)
-
Multiple Tapes and RAMs
-
Nondeterministic
-
-
DTIME, DSPACE, NTIME, NSPACE
-
Basic relationships
-
Savitch’s Theorem
-
Nondeterministic Space closed under complement
-
-
Time and Space Hierarchies
-
The P versus NP problem
-
Definitions of P and NP
-
Robustness of definitions
-
NP-completeness of Satisfiability and other problem
-
Implications of NP-completeness and how to handle it
-
-
Beyond NP
-
PSPACE
-
Exponential-Time
-
Provably Intractable Problems
-
-
-
Other Models of Efficient Computation
-
Brief discussion of probabilistic, parallel and quantum computation
-
-
Grading:
-
Weekly homework assignments (33%)
-
Midterm Exam (33%)
-
Final Exam (34%)
Course Objectives: When a student completes this course, he/she should be able to prove that various computational problems are undecidable or NP-complete and understand the implications of those results.
