CSE 105Theory of Computability
An introduction to the mathematical theory of computability. Formal languages. Finite automata and regular expressions. Push-down automata and context-free languages. Computable or recursive functions: Turing machines, the halting problem. Undecidability.
Prerequisites
From the catalog: “CSE 12 and CSE 20 or MATH 109 or MATH 15A or MATH 31CH and CSE 21 or MATH 100A or MATH 103A or MATH 154 or MATH 158 or MATH 184 or MATH 188; restricted to CS25, CS26, CS27, CS29, EC26, and MA30 majors. Other students will be allowed as space permits.”