COSC 5120 - Theory Of Computation

Credits: 3
Models of computation, the Church-Turing thesis, computable functions, decidable and enumerable sets, unsolvable problems, correctness of programs, and complexity of computation. The theory of computation provides precise answers to the fundamental questions of computer science: Which problems can be solved by machine computation and which can be solved using a reasonable amount of computer resources.

Prerequisite: COSC 4100.