CS 6800 - Advanced Theory of Computation

The theory of computation emphasizing equivalent models of computation, properties of recursively enumerable languages, computability (decidability and semi-decidability), recursive and partial recursive functions, and complexity. The Chomsky hierarchy is also reviewed and some of the more advanced topics (than those covered in the prerequisite) are addressed. Students are expected to read research papers and complete a semester project.

Prerequisites/Corequisites: Prerequisite: CS 5800, a grade of “B” or better is required to satisfy any course prerequisite.

Credits: 3 hours

Restrictions This course is restricted to the following: masters and doctorates in computer science, masters in electrical engineering, and doctorates in mathematics.
Notes: Open to graduate students only.