COSI 130A — Introduction to the Theory of Computation
[ sn ]Prerequisite: COSI 29a. May not be taken for credit by students who took COSI 30a in prior years.
Formal treatment of models of computation: finite automata and regular languages, pushdown automata and context-free languages, Turing machines, and recursive enumerability. Church's thesis and the invariance thesis. Halting problem and undecidability, Rice's theorem, recursion theorem. Usually offered every year.
Mr. Mairson