Graduate Catalog 2014-2015
CSC 722 Computability
3 hours; 3 credits
Formulations of effective computability: Sheperdson-Sturgis machines. Turing type models, recursive functions and semiThue systems. The equivalence of the various formulations. Church’s Thesis. Fundamental theorems of computability: Universal Machines, S-M-N, and Recursion theorem. Unsolvable problems. Recursive and r.e. sets.
Up one level
Click arrowheads to expand or collapse contents