Sumários

AP24 Redução

13 dezembro 2018, 11:30 • Maria Cristina De Sales Viana Serôdio Sernadas

Problema da consequência semântica em lógica proposicional e redução do problema da terminação de programas a este problema.

AP23 Complexidade de Kolmogorov

11 dezembro 2018, 11:00 • Maria Cristina De Sales Viana Serôdio Sernadas

Complexiddade de Kolmogorov de funções. Complexidade de Kolmogorov de conjuntos listáveis e de aplicação característica de conjunto decidível.

AT24 Complexidade de Kolmogorov

11 dezembro 2018, 09:30 • Maria Cristina De Sales Viana Serôdio Sernadas

Complexidade de Kolmogorov da aplicação constante, da propriedade smn, de usar mais oráculos, de usar um oráculo computavél, da composição com função eventualmente não computável.

AT23 Redutibilidade à Turing

6 dezembro 2018, 14:30 • Maria Cristina De Sales Viana Serôdio Sernadas

Redutibilidade à Turing. Propriedades básicas e comparação com a redutibilidade por aplicação. Graus de Turing. Introdução à complexidade
de Kolmogorov.

AP22 Máquinas de Turing

6 dezembro 2018, 11:30 • Maria Cristina De Sales Viana Serôdio Sernadas

Exemplos e agregação de funções computáveis à Turing.