Undecidability and Incompleteness

4 Units.

Introduction to the formal theory of effective processes, including recursive functions, Turing machines, Church's thesis, and proofs of Göedel's incompleteness theorem for arithmetic, and Church's undecidability theorem for first-order logic.