Upload
imaran
View
18
Download
0
Embed Size (px)
DESCRIPTION
Problema da Aceita çã o A TM. PROBLEMA DA PARADA HALT TM. Se A TM fosse decidivel …. q a. Se M aceita w. . q r. Se M não aceita w. 0. 1. 1. 0. String w. Código de M á quina de Turing M. . . . . . . qr. qa. qa. qr. qa. q a. - PowerPoint PPT Presentation
Citation preview
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