Exam questions from "Mathematical logic":

You will get a question chosen randomly from the following list.

  • (1) Syntax and semantics of first-order logic. The completeness theorem.

  • (2) Turing machines, partial recursive functions, recursive and r.e. sets. Universal Turing machine, the halting problem and its undecidability.

  • (3) Peano arithmetic PA and set theory ZFC and their incompleteness (Godel's First incompleteness theorem). Undecidability of predicate logic (Hilbert's Entscheidungsproblem).