Topics include models of computation: finite-state machines, stack machines, Turing machines, Church's thesis; computability theory: halting problem and unsolvability, introductory recursion theory; complexity theory: complexity measures, time and space hierarchy, NP-complete problems.
