Computability

Catalog description

Sheperdson-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.