HomeAcademicsCourses → CS620

Theory of Computation (3 credits)

Functions computable by programs. Recursive functions and Turing machines; simulation and diagonalization. Universality and unsolvable problems. Kleene's hierarchy and the recursion theorem. Gregorczyk's hierarchy and Ackermann's function. Abstract complexity. Formal languages and classes of automata. Inherently difficult combinatorial problems.

Pre-requisites

CS310 and CS320L or permission of the instructor.


This page was last modified on June 08, 2007
© 2007 University of Massachusetts Boston

Template by OS Templates