Undergraduate Catalog 2015-2016
CSC 484 Theory of Computation
4 hours; 4 credits
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.
Up one level
Click arrowheads to expand or collapse contents