Course Descriptions

16:198:539 Theory of Computation (3)

Mathematical theory of computing machines. Computable functions, recursive and recursively enumerable sets, recursion and fixed-point theorems, abstract complexity and complexity theoretic analogues of aspects of recursive-function theory, algorithmic (Kolmogoroff) complexity theory.
Allender. Prerequisite: 16:198:509 or equivalent.