AULA 17

19 Abril 2017, 11:30 • Fernando Ferreira

Problemas indecidíveis. Os exemplos de K, de H (o problema da paragem: "halting problem") e menção de outros problemas. M-redutibilidade. O teorema da parametrização (ou teorema smn). Demonstração de que K é m-redutível a H e que, consequemente, H não é decidível. O teorema da recursão. Uso do teorema da recursão para mostrar que a função de Ackermann é recursiva.