Restricted models of computation: finite automata and pushdown automata. Grammars and their relation to automata. Closure properties and pumping lemmas. Turing machines and the Church-Turing thesis. Limits of computation: uncomputable functions, undecidable problems.

Usually Offered:	Offered in Fall of 2002-03
Credit:	3 hours (class)
Prerequisite:	CS 381 or MA 453
University Catalog:	CS 483
Schedule:	Fall 2002 Instructor: Greg Frederickson
Syllabi:	Canonical