CSc I2200 Theory of Computability
Formulations of effective computability: Post machines. Turing-type models, recursive functions, and semi-Thue 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 recursively enumerable sets.
Contact Hours
3 hr./wk.