Indecidibilidade de A_TM
27 Novembro 2019, 09:30 • André Souto
Prova que N, Z e Q, conjunto das máquinas de Turing e de todas as strings são enumeráveis.
Prova que R e que o conjunto das sequências infinitas não é enumerável.
Prova que A_TM é indecidível.
Consequências da indecidibilidade de A_TM.
Estudar a secção 4.2 do Sipser.