Exercícios sobre decidibilidade do 2º/2013

Prévia do material em texto

Autoˆmatos e Computabilidade – Teste 6
1. Seja B = {〈M〉 | M e´ uma MT e L(M) conte´m pelo menos duas cadeias}. Usando uma
reduc¸a˜o a partir de AMT, prove que B e´ indecid´ıvel. Na˜o utilize o Teorema de Rice.
Resposta: Suponha B decid´ıvel, e seja R uma ma´quina de Turing que a decide. E´ poss´ıvel
construir, enta˜o, o seguinte decisor para AMT:
D= “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 = 0, aceite.
2. Se 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) = {0, 1} se M aceita w, e L(Mw) = {0} se M na˜o aceita w. Enta˜o
〈Mw〉 ∈ B se e somente se 〈M,w〉 ∈ AMT. Como sabemos que AMT e indecid´ıvel, a ma´quina
de Turing D na˜o pode ser constru´ıda. Conclu´ımos, enta˜o, que R na˜o existe e B e´ indecid´ıvel.
2. Seja B = {〈M〉 | M e´ uma MT e L(M) e´ finita}. Usando uma reduc¸a˜o a partir de AMT,
prove que B e´ indecid´ıvel. Na˜o utilize o Teorema de Rice.
Resposta: Suponha B decid´ıvel, e seja R uma ma´quina de Turing que a decide. E´ poss´ıvel
construir, enta˜o, o seguinte decisor para AMT:
D= “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, rejeite; se R rejeita, aceite.
Note que L(Mw) = Σ
∗ se M aceita w, e L(Mw) = ∅ se M na˜o aceita w. Enta˜o 〈Mw〉 ∈ B
se e somente se 〈M,w〉 /∈ AMT. Como sabemos que AMT e indecid´ıvel, a ma´quina de Turing
D na˜o pode ser constru´ıda. Conclu´ımos, enta˜o, que R na˜o existe e B e´ indecid´ıvel.
3. Seja B = {〈M〉 | M e´ uma MT e L(M) e´ livre-do-contexto}. Usando uma reduc¸a˜o a partir
de AMT, prove que B e´ indecid´ıvel. Na˜o utilize o Teorema de Rice.
Resposta: Suponha B decid´ıvel, e seja R uma ma´quina de Turing que a decide. E´ poss´ıvel
construir, enta˜o, o seguinte decisor para AMT:
D= “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 = yy, onde y ∈ Σ∗, aceite.
2. Se x 6= yy, onde y ∈ Σ∗, 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) = Σ
∗ (que e´ livre-do-contexto) se M aceita w, e L(Mw) = { yy‖ y ∈
Σ∗} (que na˜o e´ livre-do-contexto) se M na˜o aceita w. Enta˜o 〈Mw〉 ∈ B se e somente se
〈M,w〉 ∈ AMT. Como sabemos que AMT e indecid´ıvel, a ma´quina de Turing D na˜o pode
ser constru´ıda. Conclu´ımos, enta˜o, que R na˜o existe e B e´ indecid´ıvel.
4. Seja B = {〈M〉 | M e´ uma MT e L(M) na˜o e´ livre-do-contexto}. Usando uma reduc¸a˜o a
partir de AMT, prove que B e´ indecid´ıvel. Na˜o utilize o Teorema de Rice.
Resposta: Suponha B decid´ıvel, e seja R uma ma´quina de Turing que a decide. E´ poss´ıvel
construir, enta˜o, o seguinte decisor para AMT:
D= “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 = yy, onde y ∈ Σ∗, 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) = { yy‖, y ∈ Σ∗} (que na˜o e´ livre-do-contexto) (que e´ livre-do-contexto)
se M aceita w, e L(Mw) = ∅ (que e´ livre-do-contexto) se M na˜o aceita w. Enta˜o 〈Mw〉 ∈ B
se e somente se 〈M,w〉 ∈ AMT. Como sabemos que AMT e indecid´ıvel, a ma´quina de Turing
D na˜o pode ser constru´ıda. Conclu´ımos, enta˜o, que R na˜o existe e B e´ indecid´ıvel.
5. Seja B = {〈M〉 | M e´ uma MT que decide uma linguagem}. Usando uma reduc¸a˜o a partir
de PARAMT, prove que B e´ indecid´ıvel.
Resposta: Suponha B decid´ıvel, e seja R uma ma´quina de Turing que a decide. E´ poss´ıvel
construir, enta˜o, o seguinte decisor para PARAMT:
D= “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= w, aceite.
2. Se x = w, 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, se M para sobre w, enta˜o Mw para sobre sobre qualquer entrada , e se Mw na˜o
para sobre w, enta˜o Mw na˜o para sobre a entrada x = w. Enta˜o 〈Mw〉 ∈ B se e somente
se 〈M,w〉 ∈ PARAMT. Como sabemos que PARAMT e indecid´ıvel, a ma´quina de Turing D
na˜o pode ser constru´ıda. Conclu´ımos, enta˜o, que R na˜o existe e B e´ indecid´ıvel.