Recursive and Primitive Recursive Functions, Turing Machines. Equivalence Between Several Models, Church's Thesis, Universal Machine, Undecidable Problems, Deterministic and Nondeterministic Machines, The Class P and Np-completeness, Cook's Theorem.

Faculty: Computer Science
|Undergraduate Studies |Graduate Studies

Pre-required courses

234247 - Algorithms 1

Course with no extra credit

46002 - Design and Analysis of Algorithms 97447 - Intro. to Computability and Complexity 106843 - Theory of Computation C 214912 - Computational Models For Teachers

Course with no extra credit (contained)

94250 - Introduction to Computability

Semestrial Information