Exercícios sobre redutibilidade do 1º/2013

Prévia do material em texto

Autoˆmatos e Computabilidade – Teste 6
Usando uma reduc¸a˜o a partir de AMT, prove que a linguagem {〈M〉|M e´ uma ma´quina de Turing
e L(M) e´ uma linguagem infinita} e´ indecid´ıvel. Explique claramente a reduc¸a˜o. Na˜o utilize o
Teorema de Rice.
Resposta: Chame a` linguagem dada de INFMT, e suponha que e´ decid´ıvel. Seja R uma
ma´quina de Turing que decide INFMT. E´ poss´ıvel construir, enta˜o, o seguinte decisor para
AMT:
S= “Sobre a entrada 〈M,w〉, onde M e´ uma ma´quina de Turing e w e´ uma cadeia:
1. Construa a seguinte ma´quina de Turing.
Mw: “Sobre a entrada x:
1. Rode M sobre w. Se M aceita, aceite; se rejeita, rejeite.
2. Rode R sobre 〈Mw〉.
3. Se R aceita, aceite; se R rejeita, rejeite.
Note que L(Mw) = Σ
∗ e, portanto, infinita, se M aceita w; e L(Mw) = ∅ e, portanto, finita, se
M na˜o aceita w. Se R aceita 〈Mw〉, enta˜o L(Mw) e´ infinita e 〈M,w〉 ∈ AMT; se R rejeita 〈Mw〉,
enta˜o L(Mw) e´ finita e 〈M,w〉 /∈ AMT. Como sabemos que AMT e indecid´ıvel, a ma´quina de
Turing S na˜o pode ser constru´ıda. Conclu´ımos, enta˜o, que R na˜o existe e INFMT e´ indecid´ıvel.
Usando uma reduc¸a˜o a partir de PARAMT, prove que existe uma ma´quina de Turing M para a
qual a linguagem {w|M para sobre a entrada w} e´ indecid´ıvel. Explique claramente a reduc¸a˜o.
Resposta: Fac¸a HM = {w|M para sobre a entrada w}, e suponha que e´ decid´ıvel para
qualquer ma´quina de Turing M . E´ poss´ıvel construir, enta˜o, o seguinte decisor para PARAMT:
S= “Sobre a entrada 〈M,w〉, onde M e´ uma ma´quina de Turing e w e´ uma cadeia:
1. Construa a ma´quina de Turing RM que decide HM .
2. Rode RM sobre w.
3. Se RM aceita, aceite; se RM rejeita, rejeite.
Se RM aceita w, enta˜o M para sobre w e, portanto, 〈M,w〉 ∈ PARAMT; se RM rejeita w,
enta˜o M na˜o para sobre w e, portanto, 〈M,w〉 /∈ PARAMT. Como sabemos que PARAMT
e indecid´ıvel, a ma´quina de Turing S na˜o pode ser constru´ıda. Conclu´ımos, enta˜o, que a
suposic¸a˜o de que HM e´ decid´ıvel para qualquer ma´quina de Turing e´ falsa, e portanto, deve
existir uma ma´quina M para a qual HM e´ indecid´ıvel.