MATH 304 - Theory of Computability

Credit(s): 3
Lecture: 3
Non-Lecture: 0
This course covers the theoretical limits on what algorithms can and cannot compute. Topics include finite automata, regular languages, push-down automata, context-free languages, Turing machines, decidability, the structure of the classes of computable and uncomputable problems, and the relationships between computability and the logical limits of mathematics. Not offered on a regular basis.

Prerequisite(s): MATH 239.