Problema da Aceita çã o A TM

Problema da AceitaProblema da Aceitaçãoo AATMTM

PROBLEMA DA PARADA PROBLEMA DA PARADA HALTHALTTMTM

Se ASe ATMTM fosse decidivel fosse decidivel …. ….

0 1 1 0

Código deMááquina de TuringM

String w

qa

qr

Se M aceita w

Se M não aceita w<M,w>

M1M1 qaqa qrqr qrqr qrqr qaqa qrqr ……..

M2M2 qaqa qrqr qrqr qrqr qrqr qrqr ……..

M3M3 qrqr qrqr qrqr qrqr qrqr qrqr ……..

M4M4 qaqa qrqr qrqr qrqr qrqr qrqr ……..

M5M5 qrqr qrqr qrqr qrqr qaqa qrqr ……..

M6M6 qaqa qaqa qrqr qaqa qrqr qrqr ……..

M8M8 qaqa qrqr qaqa qrqr qrqr qrqr ……..

…….. …….. …….. …….. …….. …….. …….. ……..

<M1> <M2> <M3><M4><M5> <M6>

qrqr qaqa qaqa qqaaqaqa qrqr

M

Sim

Se M não aceita <M>

Se M aceita <M>

Não

Código de Máquina de Turing

Problema DiagonalProblema Diagonal

Este teste produz uma resposta depois de um tempofinito, já que estamos supondoque ATM eh decidível !

Problema Diagonal Problema Diagonal seriaseria DecídivelDecídivel

MaqMaq = No input <M> faça = No input <M> faça

• 1. Executa A1. Executa ATMTM em <M,M> em <M,M>

• 2. Se A2. Se ATMTM pára em q pára em qaa, , MaqMaq pára em q pára em qrr

• 3. Se A3. Se ATMTM pára em q pára em qrr, , MaqMaq pára em q pára em qaa

Maq = MMaq = Mkk para algum k para algum k

• Pergunta: MPergunta: Mkk aceita < M aceita < Mkk > ? > ?

•Caso 1 : Se M Se Mkk aceita < M aceita < Mkk > >

Neste caso, Maq aceita <Maq>. Neste caso, Maq aceita <Maq>.

Logo, pela definição de Maq, Logo, pela definição de Maq, concluimos que Maq não aceita <Maq>concluimos que Maq não aceita <Maq>

Absurdo !!Absurdo !!

Maq = MMaq = Mkk para algum k para algum k

• Caso 2 :Caso 2 : Se MSe Mkk não aceita < M não aceita < Mkk > >

Neste caso, Maq não aceita <Maq>. Neste caso, Maq não aceita <Maq>.

Logo, pela definição de Maq, Logo, pela definição de Maq, concluimos que Maq aceita <Maq>concluimos que Maq aceita <Maq>

Absurdo !!Absurdo !!

Problema HaltProblema HaltTMTM

0 1 1 0

Código deMáquina de TuringM

String w

Sim

Não

Se M pára em w

Se M não pára em w

<M,w>

Se HaltSe HaltTMTM fosse decidível … fosse decidível … AATMTM seria decidível …. seria decidível ….

<M,w>

qa

qr

Se M pára em w

H

Se M não pára em w

Maq = No input <M,w> faça1. 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