MATH 352 Computability and Complexity

The logical foundation of the notion of a computable function underlying the workings of modern computers. Representation of the informal mathematical idea of calculability by canonical proxies: "general recursive functions" "Turing computable functions." Discussion of Church's Thesis which asserts the adequacy of these representations. Survey of decidable and undecidable problems.