CMSC 415: Theory of computation

Fall 2018

Prof. Blaheta

Welcome to CMSC 415! Computation theory is an exploration of the question of what it even means for something to be computable. Some of the earliest results that can now be identified as computer science—at the time seen as mathematical or philosophical facts—are in the area of theory of computation. Other areas of theory are questions that remain open after more than a half-century of work. In this course, we will ask some of these questions and develop an appreciation and understanding of the answers that the early computer scientists produced for them.

The textbook for this course is Michael Sipser, Introduction to the theory of computation. Either 2nd or 3rd edition is fine. (2e: ISBN 978-0-534-95097-2; 3e: ISBN 978-1133-18779-0)

This course meets TR at 9:30am, in Ruffner 352.

Resources

Homework

Classroom stuff