CSCI 361(F) Theory of Computation (Same as Mathematics 361) (Q)

Formal models of computation such as finite state automata, recursive functions, formal grammars and Turing machines will be studied. These models will be used to provide a mathematical basis for the study of computability. Applications to compiler design and computational undecidability will also be covered. Format: lecture. Evaluation will be based on weekly problem sets, a midterm examination, and a final examination. Prerequisites: Computer Science 256 or both a 300-level Mathematics course and permission of instructor. Enrollment limit: 30 (expected: 25).