Exercícios sobre decidibilidade do 2º/2012

Prévia do material em texto

Autoˆmatos e Computabilidade – Teste 5
Prove que a linguagem T = {〈M〉|M e´ uma ma´quina de Turing que para sobre todas as cadeias
w ∈ Σ∗} e´ indecid´ıvel.
Resposta: Suponha que T e´ decid´ıvel, e que R e´ um decisor para T . Podemos construir,
enta˜o, o seguinte decisor para AMT:
U= “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, onde x e´ uma cadeia:
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 L(Mw) = Σ
∗ se e somente se M aceita w. Como sabemos que AMT e indecid´ıvel,
a ma´quina de Turing U na˜o pode ser constru´ıda. Conclu´ımos, enta˜o, que R na˜o existe e T e´
indecid´ıvel.
Prove que a linguagem T = {〈M,σ〉|M e´ uma ma´quina de Turing e existe pelo menos uma cadeia
de entrada para a qual M , em algum momento, escreve o s´ımbolo σ na fita} e´ indecid´ıvel.
Resposta: Suponha que T e´ decid´ıvel, e que R e´ um decisor para T . Podemos construir,
enta˜o, o seguinte decisor para AMT:
U= “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, onde x e´ uma cadeia:
1. Ignore a entrada.
2. Rode M sobre w. Se M aceita, escreva σ na fita, onde σ e´ um s´ımbolo
que na˜o pertence ao alfabeto de M .
2. Rode R sobre 〈Mw,σ〉.
3. Se R aceita, aceite; se R rejeita, rejeite.
Note que Mw escreve σ na fita, para qualquer entrada x, se e somente se M aceita w. Como
sabemos que AMT e indecid´ıvel, a ma´quina de Turing U na˜o pode ser constru´ıda. Conclu´ımos,
enta˜o, que R na˜o existe e T e´ indecid´ıvel.
Prove que a linguagem T = {〈M〉|M e´ uma ma´quina de Turing que aceita pelo menos duas
cadeias} e´ indecid´ıvel.
Resposta: T satisfaz as condic¸o˜es do Teorema de Rice. Podemos construir uma ma´quina de
Turing M1 que na˜o aceite nenhuma cadeia, e outra M2 que aceite duas cadeias. Enta˜o, 〈M1〉 /∈
T , 〈M2〉 ∈ T e, portanto, T e´ na˜o trivial. Tambe´m, se duas ma´quinas M3 e M4 reconhecem a
mesma linguagem, enta˜o ambas reconhecem uma linguagem com duas ou mais cadeias e enta˜o
〈M3〉, 〈M4〉 ∈ T , ou ambas na˜o reconhecem tal linguagem e enta˜o 〈M3〉, 〈M4〉 /∈ T . Assim, pelo
Teorema de Rice, T e´ indecid´ıvel.
Prove que a linguagem T = {〈M,w〉|M e´ uma ma´quina de Turing que aceita w em mais de 3
passos} e´ indecid´ıvel.
Resposta: Suponha que T e´ decid´ıvel, e que R e´ um decisor para T . Podemos construir,
enta˜o, o seguinte decisor para AMT:
U= “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.
N : “Sobre a entrada x, onde x e´ uma cadeia:
2. Desloque a cabec¸a duas posic¸o˜es a` direita e logo 2 posic¸o˜es a` esquerda.
3. Rode M sobre x. Se M aceita, aceite; se rejeita, rejeite.
2. Rode R sobre 〈N,w〉.
3. Se R aceita, aceite; se R rejeita, rejeite.
Note que N aceita w em mais de 3 passos se e somente se M aceita w. Como sabemos que
AMT e indecid´ıvel, a ma´quina de Turing U na˜o pode ser constru´ıda. Conclu´ımos, enta˜o, que
R na˜o existe e T e´ indecid´ıvel.
Considere a linguagem T = {〈M〉|M e´ uma ma´quina de Turing e L(M) e´ uma linguagem Turing-
reconhec´ıvel}. Um aluno propo˜e a seguinte demonstrac¸a˜o de que T e´ indecid´ıvel: a propriedade
“L e´ uma linguagem Turing-reconhec´ıvel” e´ na˜o-trivial, pois existem linguagens que sa˜o Turing-
reconhec´ıveis e outras que na˜o. O Teorema de Rice afirma que o problema de determinar se a
linguagem de uma ma´quina de Turing tem uma certa propriedade na˜o-trivial e´ indecid´ıvel. Assim,
T e´ indecid´ıvel.
No entanto, T e´ decid´ıvel!
1. O que esta´ errado na demonstrac¸a˜o do aluno?
Resposta: A propriedade“L e´ uma linguagem Turing-reconhec´ıvel”se refere a` linguagem
de uma ma´quina de Turing. Toda linguagem de uma ma´quina de Turing e´, por definic¸a˜o,
Turing-reconhec´ıvel. Assim, T conte´m todas as descric¸o˜es de ma´quinas de Turing e,
portanto, e´ trivial. Consequentemente, e o Teorema de Rice na˜o pode ser aplicado.
2. Fornec¸a uma ma´quina de Turing que decide T .
Resposta:
S= “Sobre a entrada < M >: aceite.”