Which problems can be solved computationally? Which cannot? Why? We can prove that computers can perform certain computations and not others. This course will investigate which ones, and why. Topics will include formal models of computation such as finite state automata, push-down automata, and Turing machines, as well as formal languages such as context-free grammars and regular expressions. May be elected as Computer Science 320, and must be elected as Computer Science 320 to apply toward the total credit requirement in Computer Science.
Prerequisites
Computer Science/Mathematics 220; or Mathematics 260.