Mar 29, 2024  
2015-2016 Graduate Catalog 
    
2015-2016 Graduate Catalog [ARCHIVED CATALOG]

CS 620 Theory of Computation


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.

Prerequisite(s): CS 320L

3 Credit(s)