Exercícios sobre redutibilidade do 1º/2014

Prévia do material em texto

Autoˆmatos e Computabilidade – Teste 6
1. Seja L = {〈M〉 | M e´ uma MT que aceita a cadeia vazia}. Usando uma reduc¸a˜o a partir de
AMT, prove que L e´ indecid´ıvel. Na˜o utilize o Teorema de Rice.
Resposta: Suponha L decid´ıvel, e seja R uma ma´quina de Turing que a decide. 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. Se x 6= ε, rejeite.
2. Simule 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) = {ε} se M aceita w, e L(Mw) = ∅ se M na˜o aceita w. Enta˜o 〈Mw〉 ∈ L se
e somente se 〈M,w〉 ∈ AMT. No entanto, sabemos que AMT e indecid´ıvel, o que causa uma
contradic¸a˜o. A contradic¸a˜o implica que a ma´quina de Turing S na˜o pode ser constru´ıda.
Conclu´ımos, enta˜o, que R na˜o existe e L e´ indecid´ıvel.
2. Seja L = {〈M〉 | M e´ uma MT que aceita exatamente uma cadeia (e na˜o mais que uma)}.
Usando uma reduc¸a˜o a partir de AMT, prove que L e´ indecid´ıvel. Na˜o utilize o Teorema de
Rice.
Resposta: Suponha L decid´ıvel, e seja R uma ma´quina de Turing que a decide. 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. Se x 6= abbabab, rejeite.
2. Simule 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) = {abbabab} se M aceita w, e L(Mw) = ∅ se M na˜o aceita w. Enta˜o
〈Mw〉 ∈ L se e somente se 〈M,w〉 ∈ AMT. No entanto, sabemos que AMT e indecid´ıvel, o
que causa uma contradic¸a˜o. A contradic¸a˜o implica que a ma´quina de Turing S na˜o pode
ser constru´ıda. Conclu´ımos, enta˜o, que R na˜o existe e L e´ indecid´ıvel.