CS 4423 - Computability and Complexity Theory (3) SP

Rigorous introduction to theoretical foundations of computer science, addressing a number of interrelated topics and formally defining a computer, an algorithm and what is computable. Close reading of important theorems and proofs. Significant use of mathematical lemmas, corollaries, logical reasoning, inductive proofs, are used to introduce how to reason precisely about computation and prove mathematical theorems of computation such as Turing machines, undecidability, and computational complexity.

Prerequisites: CS 2233 and CS 3623 with grades of “C” or higher.