Theory of Computation
Course #: CS 620, Class #: 4555, Section #: 01
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.
Prerequisites
CS 220
Course Details
Date / Time
9/8/26 - 12/11/26
MoWe 4p.m. – 5:15p.m.
Location
McCormack M02-0404
Credits
3
Session
Regular Academic Session
Class Dates
9/8/2026 - 12/11/2026
Location
McCormack M02-0404
Enrolled / Capacity
13 / 30
Status
Open