CMSI 583 Home Page

CMSI 583 - Theory of Computation Home Page and Course Syllabus - fall, 2008

Brief contents

The goal is to become familiar with some of the main ideas in the theory of computation. After some preliminary mathematics (cardinality, proof techniques, alphabets, strings, and languages), we will talk about regular expressions and finite automata; context-free grammars, pushdown automata, and their relation to parsing; Turing machines, the Church-Turing hypothesis, problem reductions, undecidable problems and non-computable functions; intractability, P vs. NP, Cook's theorem, and NP-completeness.

You should be reasonably comfortable reading, and constructing some, formal proofs.

Hopcroft, Ullman, and Motwani. Introduction to Automata Theory, Languages, and Computation (3rd edition). Addison-Wesley, 2007.

Garey and Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, 1979. Classic introduction to NP-completeness, including an exhaustive appendix of NP-complete problems.

Crossley, Ash, Brickhill, Stillwell, and Williams. What is Mathematical Logic? Dover Publications, 1990. A skinny little book with six excellent lectures including an historical survey of the subject, completeness of the predicate calculus, model theory, Turing machines, Godel's theorems, and set theory.

Halmos. Naive Set Theory. Springer-Verlag, 1974. A(nother) skinny little book that develops the main ideas of set theory in twenty-five concise, very readable lectures.

Hey and Allen (eds.) The Feynman Lectures on Computation. Addison-Wesley, 1996. Computation from Feynman's typically unique, but not always easy-to-understand, point of view, including discussions of computability, coding and information theory, the thermodynamics of computing, and quantum mechanical computation.

Kohavi. Switching and Finite Automata Theory (2nd edition). McGraw-Hill, 1978. A well-known, highly-readable text that covers combinational logic, switching theory, and the theory of finite-state machines.

Kozen. Automata and Computability. Springer, 1997. An alternative to Hopcroft et al., organized as a sequence of lectures.

Linz. An Introduction to Formal Languages and Automata (third edition). D. C. Heath, 2001. This was once the textbook for CMSI 385, and is a slightly simplified version of the corresponding chapters of Hopcroft et al.

Minsky. Computation: Finite and Infinite Machines. Prentice-Hall, 1967. A classic, entertaining book that covers a lot of the course material from a slightly different angle.

Papadimitriou. Computational Complexity. Addison-Wesley, 1994. A comprehensive treatment of computability, logic, and complexity that picks up where (the textbook for) this course leaves off.

Sipser. Introduction to the Theory of Computation. PWS Publishing, 1997. Another former CMSI 385 text, covering virtually the same material as Hopcroft et al.

A set of highly recommended homework problems will be issued at each class, but it is generally not collected/graded. Typically, solutions are discussed, or distributed, at the next class meeting.

Revised: August 25, 2008