Theory of Computation

Catalog description

Effective computability of functions and sets in terms of Turing machines and other computational models. Universal machines and examples of unsolvable problems. The Church-Turing thesis and formal proofs of the equivalence of Turing machines, systems of recursion equations, and other models of computation. Mathematical properties of the classes of recursive functions. Recursive and recursively enumerable sets.