Theory of Computation

Identifier
COMS 5310
Professor(s)
Jack Lutz

Last Updated: Spring 2025

  1. Credits and contact hours: 3 credits, 3 contact hours
  2. Textbook title, author, and year: Introduction to the Theory of Computation (Third Edition), Michael Sipser, 2013
  3. Other supplemental materials: Course lectures

Specific course information

  1. Brief description of the content of the course: A systematic study of the fundamental models and analytical methods of theoretical computer science. Computability, the Church-Turing thesis, decidable and undecidable problems. Computational resources such as time, space, and nonuniformity. Complexity classes, computational intractability and completeness. Selected topics from randomness, algorithmic information theory, and logic.
  2. Prerequisites or co-requisites: COMS 3310 or an equivalent in which you wrote many proofs
  3. Required, elective, or selected elective? Selected Elective