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.
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. RECOMMENDED CISC 365.