CSc 42200 - Computability


Shepherdson-Sturgis machines. Elements of recursive function theory. The equivalence of the class of computable and recursive functions. Church’s thesis; other models of computation: Post machines, Turing machines, semi-Thue systems, etc. Unsolvable problems and introduction to their classification. Subrecursive formalism.
Prereq.: CSc 22000, CSc 30400. 3 hr./wk.; 3 cr.