2017-2018 Catalog

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.


4 units


MATH 210 or permission of instructor

Core Requirements Met

  • Mathematics/Science