(Fall 2023) CS 581 - Theory of computation


  • <2023-08-07 Mon> Welcome! Please stay tuned for updates.


  • Syllabus: PDF.
  • Instructor: Prof. Fang Song
  • Email: fsong “AT” pdx.edu. Start your email subject line with “f23-581”. Slack is preferred.
  • Lectures: TR 14:00 - 15:15 @ FAB 10
  • Office hours: T 15:20 (FAB 120-25). Book additioanal individual slots on youcanbookme (see details in Slack).
  • Google classroom: join with code sbdybav.
  • Overview: Computation is a familiar term to all computer scientists. But what is computation after all? What problems are computable (Computability), and how “efficient” can we compute them (Complexity)? This course will be investigating these fundamental questions.
  • Prerequisite: CS 311 or equivalent. You need to be familiar with the basics of computability theory, and be comfortable with reading and writing mathematical proofs.
  • Text: [S3] Michael Sipser. Introduction to the Theory of Computation, 3rd ed. Cengage Learning, 2012. Some topics will rely on lecture notes and additional readings. See Resource page for useful materials.