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).