Enabling javascript will improve the functionality of this page. skip to content
Lehman College

Catalog search

Catalog links

print page

CMP 685: Computability Theory.

4 hours, 4 credits. Mathematical formulation of computability theory and abstract machine theory. Finite-state machines and Turing machines; Church's Thesis; recursive functions and recursively enumerable sets; unsolvability and the halting problem.

Last modified: 8/4/2015