Indecidibilidade de A_TM
3 Dezembro 2019, 09:30 • André Souto
Consequências da indecidibilidade de A_TM.
O problema da terminação e a sua indecidibilidade.
Noção de função computável.
Exemplos.
Noção de redução por mapeamento entre linguagens.
Resultados sobre linguagens redutíveis por mapeamento.
Exemplos.
Prova que o complementar de A_TM não é Turing reconhecível.
Prova que EQ_TM e o seu complementar não são Turing reconhecíveis.
Estudar a secção 4.2 e o capítulo 5 do Sipser.