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 212 (Mathematical Foundations of Computer Science) 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