Mathematical Logic II

4 credits

Theory of computation and recursive function theory, Church’s thesis, computability and undecidability. Feasible computability and complexity. Peano arithmetic and the incompleteness theorems, nonstandard models. Prerequisites: MATH 260A or consent of instructor.