Programa de Mestrado: Computação, Lógica e Teoria dos Conjuntos (2023)
Instituto de Matemática Pura e Aplicada |
19 videos |
Updated 2 years ago
Escola de Verão 2023
Professor: Felipe Gonçalves
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..
Redes Sociais do IMPA: linktr.ee/impabr
IMPA - Instituto de Matemática Pura e Aplicada ©
www.impa.br | impa.br/videos
Os direitos sobre todo o material deste canal pertencem ao Instituto de Matemática Pura e Aplicada, sendo vedada a utilização total ou parcial do conteúdo sem autorização prévia e por escrito do referido titular, salvo nas hipóteses previstas na legislação vigente.
The rights over all the material in this channel belong to the Instituto de Matemática Pura e Aplicada, and it is forbidden to use all or part of it without prior written authorization from the above mentioned holder, except in the cases prescribed in the current legislation.
