CSCI 663 - Theory of Computation

Fall or Spring 3 Prerequisite(s): Finite Automata and a strong mathematical background.

An in depth study of Turing machines and the equivalent computational models such as recursive function theory and lambda calculus. Church’s thesis and incompleteness results. Computational complexity including NP-completeness.