Computação, Lógica e Teoria dos Conjuntos

Formal Languages: Automata, Nondeterminism, Context free grammars, Chomsky normal form.
Register Machines: FRACTRAN, Minsky and Turing Machines, Partial recursive functions, Universality.
Decidability, The Halting Problem.
Algorithmic Complexity: Basic examples, P vs NP, NP-completeness.
First-Order Logic: Consistency, Completeness, Compactness, Model Theory, Undecidability, Gödel.
Incompleteness Theorems, Basics of second order logic.
Set Theory: Integers, Rationals, Reals, Cardinal, Ordinals, Surreals, well-ordering, transfinite induction.
ZFC set theory, the axiom of choice, the continuum Hypothesis.

Referências:
M. Sipser, Introduction to the Theory of Computation, 3rd Edition.
C. Papadimitriou, Computational Complexity: A Modern Approach.
H. B. Enderton, A Mathematical Introduction to Logic, 2nd Edition.
R. Weber, Computability theory.
K. Ciesielski, Set Theory For the Working Mathematician.