CS620: Theory of Computation
Credits: 3
Catalog 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.
Current & Upcoming Offerings
2025-2026
Fall 2025 1 section
| Section | Schedule / Time | Instructor | Location |
|---|---|---|---|
| 01 |
TuTh
|
TBA |
TBA
|
Prerequisites
- CS220/CS320L/MATH320L
Graduate course in theory of computation for graduate students covering computability, automata, and formal language theory.