Select the desired Level or Schedule Type to find available classes for the course. |

CS 7805 - Theory of Computation |

Examines formal models of computation, notions of undecidability, and basic complexity theory. Models of computation include finite state automata, pushdown automata, and Turing machines. Discusses the properties of regular sets and context-free languages. Also covers partial recursive functions, primitive recursive functions, recursively enumerable sets, Turing decidability, and unsolvable problems. Discusses the concept of reductions, time and space complexity classes, and the polynomial-time hierarchy. Prereq. CS 7800; computer science PhD students only.
4.000 Credit hours 4.000 Lecture hours Levels: Graduate Schedule Types: Lecture Computer Science Department Course Attributes: GSCS Computer & Info Science Restrictions: Must be enrolled in one of the following Programs: PhD Computer Science Must be enrolled in one of the following Levels: Graduate Must be enrolled in one of the following Colleges: Khoury Coll of Comp Sciences Prerequisites: Graduate level CS 7800 Minimum Grade of C- |

Return to Previous | New Search |