CS 334 Theory of Computation

Introduction to models of computation and their languages: finite-state machines, non-determinism, and regular languages, pushdown automata and context-free languages, and Turing Machines and recursively enumerable languages. The limits of computability: The Church-Turing thesis, decidable languages, reducibility, the halting problem, and the recursion theorem. Time and space complexity measures, intractable problems, and the P vs. NP question.

Credits

3

Prerequisite

CS 135 and CS 385

Distribution

Computer Science Program

Offered

Fall Semester Spring Semester