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

Sub-field: THEORY