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

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.