Description
Turing machines and other models of computability such as µ-recursive functions and random-access machines. Undecidability. Recursive and recursively enumerable sets. Church-Turing thesis. Resource-bounded complexity. Complexity comparisons among computational models. Reductions. Complete problems for complexity classes.
Learning Hours
120 (36 Lecture, 84 Private Study)
Prerequisite
Registration in a School of Computing Plan and a minimum grade of a C- (obtained in any term) or a 'Pass' (obtained in Winter 2020) in CISC 223.