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.