Computer & Information Science Department   Polytechnic University

ATTENTION: THIS WEB SITE HAS MOVED. The pages you are looking at are no longer being maintained. Please go to http://www.poly.edu/cis/ to visit the new site of the Department of Computer and Information Science at Polytechnic University.

CS675 - Theory of computation

Computability and decidability. Computable and primitive recursive functions. The Halting Problem. Recursively enumerable sets. Relationships between languages, grammars, and machines. Solvable and unsolvable linguistic questions.

Prerequisites: CS600 or permission of instructor