Problema da terminação e redutibilidade

25 Novembro 2020, 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 5.3 do livro do Sipser.

A aula foi dada em regime síncrono não presencial com transmissão via Zoom.