Course Catalog

all > GRAD > CS

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.

Pre Requisites: Pre-req = CS 320L

Offered in:

2017 Fall

Section Class Number Schedule/Time Instructor Location
01 6017 TuTh
4:00 - 5:15 pm
Pomplun,Marc Y02-2120
Session: Regular
Class Dates: 09/05/2017 - 12/13/2017
Capacity: 50
Enrolled: 27
Status: Open
Credits: 3/3
Class Notes:
Pre Requisites: Pre-req = CS 320L
Course Attributes: