Jul 04, 2025  
2018-2019 Graduate Catalog 
    
2018-2019 Graduate Catalog [ARCHIVED CATALOG]

CS 620 - Theory of Computation


3 Credit(s)

Description:
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.

Enrollment Requirements:
: CS 220

013111:1