The theory of general purpose programming systems. Recursive and partial-recursive functions; recursive and recursively enumerable sets. The Church-Turing thesis. The recursion theorem, Rogers' translation theorem, Rice's undecidability theorem. The general theory of computational complexity: there are no general solutions to natural optimization problems. Complexity for specific models of computation: the polynomial complexity classes P, NP, and PSPACE; NP-hard and PSPACE-hard problems, inherently exponential problems.

Usually Offered:	Spring Not offered in 2007-08
Credit:	3 hours (class)
Prerequisite:	CS 483
University Catalog:	CS 584