9
Problema da Aceita Problema da Aceitaçã o o A A TM TM PROBLEMA DA PARADA PROBLEMA DA PARADA HALT HALT TM TM

Problema da Aceita çã o A TM

  • 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

Page 1: Problema da Aceita çã o  A TM

Problema da AceitaProblema da Aceitaçãoo AATMTM

PROBLEMA DA PARADA PROBLEMA DA PARADA HALTHALTTMTM

Page 2: Problema da Aceita çã o  A TM

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>

Page 3: Problema da Aceita çã o  A TM

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

Page 4: Problema da Aceita çã o  A TM

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 !

Page 5: Problema da Aceita çã o  A TM

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

Page 6: Problema da Aceita çã o  A TM

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 !!

Page 7: Problema da Aceita çã o  A TM

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 !!

Page 8: Problema da Aceita çã o  A TM

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>

Page 9: Problema da Aceita çã o  A TM

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