Academics

Course Catalog

GRAD > CS > 620

Theory of Computation

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.

Offered in:

2016 Fall

Section Class Number Schedule/Time Instructor Location
01 5859 TuTh
04:00 PM - 05:15 PM
Pomplun,Marc W01-0006
Session: Regular Academic Session
Class Dates: 09/06/2016 - 12/14/2016
Capacity: 70
Enrolled: 60
Status: Open
Credits: 3/3
Class Notes:
Pre Requisites: Pre-req = CS 320L
Course Attributes:

2016 Spring

Section Class Number Schedule/Time Instructor Location
01 14027 MW
07:00 PM - 08:15 PM
Simovici,Dan W01-0053
Session: Regular Academic Session
Class Dates: 01/25/2016 - 05/11/2016
Capacity: 25
Enrolled: 19
Status: Open
Credits: 3/3
Class Notes:
Pre Requisites: Pre-req = CS 320L
Course Attributes: