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).