Mathematics and Statistics 320: Theory of Computation

Credits 3
Credit Type
Cross-Listed
Semester Offered
Fall
Faculty
Davis

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.