Sumários
T_10a
29 Novembro 2022, 11:30 • Mário Jorge Edmundo
Linguagens efectivamente numeráveis; números de Godel; fórmulas são decidíveis; substituição é computável; substituibilidade é decidível; demonstrações são decidíveis; segunda nota sobre a recursividade; teorema da negação; terceira nota sobre a recursividade (relações decidíveis e funções computáveis são recursivas); semi-decidibilidade e existe; computavelmente enumerável e semi-decidível.
T_9b
23 Novembro 2022, 15:00 • Mário Jorge Edmundo
Aula dedicada à discussão de exercícios (videoconferência no Zoom).
T_9a
22 Novembro 2022, 11:30 • Mário Jorge Edmundo
Exemplos de relações decidíveis e funções computáveis: funções básicas; adição e multiplicação; composição; definição por casos; minimização; minimização limitada; subtração; pair, left, right; a função beta de Godel; sequências; recursão; recursão primitiva. Funções recursivas primitivas; funções recursivas; relações recursivas (res. recursivas primitivas); primeira nota sobre a recursividade.
T_8b
16 Novembro 2022, 15:00 • Mário Jorge Edmundo
Aula dedicada à discussão de exercícios (videoconferência no Zoom).
T_8a
15 Novembro 2022, 11:30 • Mário Jorge Edmundo
Relações decidíveis e funções computáveis. Tese de Church-Turing. A teoria Q de Robinson, termos fechados e variáveis limitadas por termos fechados e Q. Fórmulas decididas correctamente por Q. Fecho para conectivos e quantificadores limitados. Fórmulas Delta0; Q decide correctamente fórmulas Delta0. Conjuntos e funções definíveis. Relações Q-decidíveis e funções Q-computáveis. Relações semi-decidíveis e funções semi-computáveis. Fórmulas semi-decididas correctamente por Q. Relações Q-semi-decidíveis e funções Q-semi-computáveis.