Sumários
T21_24
20 Maio 2019, 10:00 • Mário Jorge Edmundo
Relações efectivamente enumeráveis (versão informal); Q-semi-decidibilidade; relações efectivamente enumeráveis (versão formal), efectivamente enumerável e existe, efectivamente enumerável é imagem de função efectivamente computáveis, teorema da negação. Nota sobre recursivamente enumerável. Teorias, axiomas e decidibilidade, teorias com axiomas decidíveis são efectivamente enumeráveis, teorias completas com axiomas decidíveis são decidíveis. Exemplos.
T21_23
17 Maio 2019, 10:30 • Mário Jorge Edmundo
Linguagens efectivamente numeráveis, números de Godel; fórmulas são efectivamente decidíveis, substituição é efectivamente computável, substituibilidade é efectivamente decidível; demonstrações são efectivamente decidíveis. Nota sobre a aritmétização da sintaxe e recursividade.
T21_22
13 Maio 2019, 10:00 • Mário Jorge Edmundo
Função beta de Godel, sequências, definição por casos, recursão, recursão primitiva, exemplos. Funções recursivas primitivas, funções recursivas, função de Ackermann, exemplos de funções recursivas primitivas, relações recursivas e recursivas primitivas.
T21_21
10 Maio 2019, 10:30 • Mário Jorge Edmundo
Fórmulas decididas correctamente por Q, fecho para conectivos e quantificadores limitados; relações efectivamente decidíveis, funções efectivamente computáveis; tese de Church-Turing. Exemplos de funções efectivamente computáveis: funções básicas, composição, minimização, adição, multiplicação.