Introduction to Theory of Computation

Catalog description

An introduction to the theoretical aspects of computation. The capabilities and limits of several computation models are considered including: partial recursive functions, Turing machines, finite state automata and formal languages. The implications of Church's thesis and unsolvable problems such as the halting problem are discussed. This course is taught largely at an undergraduate level. Graduate students will have additional course requirements/expectations. Prerequisite: CS 340 ; junior standing. Offered Spring - Even Numbered Years.