2021-2022 Catalog

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

Credits

4 units

Cross Listed Courses

MATH 352

Prerequisite

Math 210, COMP 149, or permission of instructor

Core Requirements Met

  • Mathematics/Science