Semester Hours:3Periodically
An advanced approach to automata, computability, and complexity, with an emphasis on computability. Topics include: regular and context-free languages; decidable and undecidable problems; reducibility; recursive function theory; consideration of time and space measures on computation; completeness; hierarchy theorems; discussion of Turing machines; the halting problem and other undecidable problems.
Prerequisite(s)/Course Notes: Course open to graduate students in computer science, others need permission from computer science graduate director.