An introduction to the mathematical theory of computability. Formal languages. Finite automata and regular expression. Push-down automata and context-free languages. Computable or recursive functions: Turing machines, the halting problem. Undecidability.
This course gives a precise definition of the notion of an algorithm as well as developing a theory of automata and formal languages. The course stresses the understanding of the basic concepts and constructions.
CSE 12, CSE 15L, CSE 21 or Math 154 or Math 184A or Math 100A or Math 103A; restricted to SO, JR, SR standing. Graduate students will be allowed as space permits. Please see Prerequisites page.
Credit not offered for both Math 166 and CSE 105. Equivalent to Math 166.
Three sections per year.