EECS 335  Introduction to the Theory of Computation
CATALOG DESCRIPTION: This course gives an introduction to the mathematical foundations of computation. The course will look at Turing machines, universal computation, the ChurchTuring 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

ChurchTuring 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

NPcompleteness of Satisfiability and other problem

Implications of NPcompleteness and how to handle it


Beyond NP

PSPACE

ExponentialTime

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 NPcomplete and understand the implications of those results.