Theory of Computation
Overview
Subject area
CSC
Catalog Number
484
Course Title
Theory of Computation
Department(s)
Description
The notion of an algorithm. Primitive recursive and partial recursive functions. Turing machines and other models of computation. Markov algorithms. Church thesis. Godel numberings and unsolvability results. Halting problem. Post correspondence problem. Recursive and recursively enumerable sets. Concepts from formal language theory.
Typically Offered
Fall, Spring
Academic Career
Undergraduate
Liberal Arts
No
Credits
Minimum Units
4
Maximum Units
4
Academic Progress Units
4
Repeat For Credit
No
Components
Name
Lecture
Hours
4
Requisites
023467