Problema da Aceitação ATM PROBLEMA DA PARADA HALTTM Se ATM fosse decidivel …. qa <M,w> 0 11 0 String w Código de Máquina de Turing M qr Se M aceita w Se M não aceita w <M1> <M2> <M3> <M4> <M5> <M6> M1 M2 M3 M4 M5 M6 M8 …. qa qr qr qr qa qr qa qr qr qr qr qr qr qr qr qr qr qr qa qr qr qr qr qr qr qr qr qr qa qr qa qa qr qa qr qr qa qr qa qr qr qr …. …. …. …. …. …. qr qa qa qa qr qa …. …. …. …. …. …. …. …. Problema Diagonal Sim M Se M não aceita <M> Não Se M aceita <M> Código de Máquina de Turing Este teste produz uma resposta depois de um tempo finito, já que estamos supondo que ATM eh decidível ! Problema Diagonal seria Decídivel Maq = No input <M> faça • 1. Executa ATM em <M,M> • 2. Se ATM pára em qa, Maq pára em qr • 3. Se ATM pára em qr, Maq pára em qa Maq = Mk para algum k • Pergunta: Mk aceita < Mk > ? • Caso 1 : Se Mk aceita < Mk > Neste caso, Maq aceita <Maq>. Logo, pela definição de Maq, concluimos que Maq não aceita <Maq> Absurdo !! Maq = Mk para algum k • Caso 2 : Se Mk não aceita < Mk > Neste caso, Maq não aceita <Maq>. Logo, pela definição de Maq, concluimos que Maq aceita <Maq> Absurdo !! Problema HaltTM Sim <M,w> 0 11 0 String w Código de Máquina de Turing M Se M pára em w Não Se M não pára em w Se HaltTM fosse decidível … ATM seria decidível …. qa <M,w> H Se M pára em w qr Se M não pára em w Maq = No input <M,w> faça 1. Executa H em <M,w> 2. Se H pára em qa, executa M em w Se M pára em qa, Maq pára em qa Se M pára em qr, Maq pára em qr 3. Se H pára em qr, então Maq pára em qr Maq decide ATM !!! Absurdo, pois já provamos que ATM é indecidível