Exercícios sobre redutibilidade do 1º/2012

Prévia do material em texto

Autoˆmatos e Computabilidade – Teste 6
1. Considere o problema de se determinar se uma ma´quina de Turing T na˜o aceita nenhuma
cadeia w. Formule o problema como uma linguagem e prove que e´ indecid´ıvel.
Resposta: VMT = {〈T 〉|T e´ uma MT e L(T ) = ∅}. Prova: pa´ginas 200–201 do livro
texto.
2. Considere o problema de se determinar se uma ma´quina de Turing T aceita qualquer cadeia
w. Formule o problema como uma linguagem e prove que e´ indecid´ıvel.
Resposta: P = {〈T 〉|T e´ uma MT e L(T ) = Σ∗}. Prova: P satisfaz as duas condic¸o˜es
do teorema de Rice: (1) Podemos construir uma MT que rejeite qualquer cadeia, e outra
que aceite qualquer cadeia; logo, P e´ na˜o trivial. (2) Se duas MT reconhecem a mesma
linguagem, enta˜o ambas reconhecem Σ∗ ou nenhuma delas a reconhece. Em consequeˆncia,
o teorema de Rice diz que P e´ indecid´ıvel.
3. Considere o problema de se determinar se uma ma´quina de Turing T reconhece uma lin-
guagem regular. Formule o problema como uma linguagem e prove que e´ indecid´ıvel.
Resposta: REGULARMT = {〈T 〉|T e´ uma MT e L(T ) = e´ uma linguagem regu-
lar }. Prova: pa´ginas 201–202 do livro texto ou por aplicac¸a˜o do teorema de Rice:
REGULARMT satisfaz as duas condic¸o˜es do teorema. (1) Podemos construir uma MT
que reconhec¸a a linguagem na˜o regular {0n1n|n ≥ 0}, e outra que reconhec¸a a linguagem
regular Σ∗; logo, REGULARMT e´ na˜o trivial. (2) Se duas MT reconhecem a mesma
linguagem, enta˜o ambas reconhecem uma linguagem regular ou nenhuma delas reconhece
uma. Em consequeˆncia, o teorema de Rice diz que REGULARMT e´ indecid´ıvel.
4. Considere o problema de se determinar se um autoˆmato linearmente limitado A aceita uma
dada cadeia w. Formule o problema como uma linguagem e prove que e´ decid´ıvel.
Resposta: AALL = {〈A,w〉|A e´ um ALL que aceita a cadeia w}. Prova: pa´gina 205 do
livro texto.
5. Considere o problema de se determinar se duas grama´ticas livre-do-contexto geram a mesma
linguagem. Formule o problema como uma linguagem e prove que e´ indecid´ıvel.
Resposta: EQGLC = {〈G1, G2〉|G1 e G2 sa˜o GLCs e L(G1) = L(G2)}. Prova: Supo-
nha que EQGLC seja decid´ıvel. Constru´ımos, enta˜o, um decisor M para TODASGLC =
{〈G〉|G e´ uma GLC e L(G) = Σ∗}:
M = “Sobre a entrada 〈G〉, onde G e´ uma GLC:
1. Construa uma GLC G′ tal que L(G′) = Σ∗.
2. Rode o decisor para EQGLC sobre 〈G,G′〉.
3. Se o decisor aceita, aceite; se rejeita, rejeite.”
Como sabemos que TODASGLC e´ indecid´ıvel, concluimos que o decisor para EQGLC na˜o
existe e, portanto, esta linguagem e´ indecid´ıvel.
6. Considere o problema de se determinar se uma ma´quina de Turing T aceita uma cadeia de
entrada wR sempre que ela aceita w. Formule o problema como uma linguagem e prove que
e´ indecid´ıvel.
Resposta: L = {〈T 〉|T e´ uma MT que aceita wR sempre que ela aceita w}. Prova:
Suponha que L seja decid´ıvel. Constru´ımos, enta˜o, um decisor U para AMT = {〈M,w〉|M
e´ uma MT que aceita a cadeia w}:
U = “Sobre a entrada 〈M,w〉, onde M e´ uma MT e w e´ uma cadeia:
1. Construa uma a seguinte MT Mw.
Mw = “Sobre a entrada x:
1. Se x = 01 aceite.
2. Se x = 10, simule M sobre w. Se M aceita w, aceite; se M
rejeita w, rejeite.
3. Se x 6= 01 e x 6= 10 rejeite.
2. Rode o decisor para L sobre 〈Mw〉.
3. Se o decisor aceita, aceite; se rejeita, rejeite.”
Como sabemos que AMT e´ indecid´ıvel, concluimos que o decisor para L na˜o existe e,
portanto, esta linguagem e´ indecid´ıvel.
7. Considere o problema de se determinar se uma ma´quina de Turing T aceita a cadeia vazia
ε. Formule o problema como uma linguagem e prove que e´ indecid´ıvel.
Resposta: P = {〈T 〉|T e´ uma MT e ε ∈ L(T )}. Prova: P satisfaz as duas condic¸o˜es do
teorema de Rice: (1) Podemos construir uma MT que rejeite ε e outra que aceite ε; logo,
P e´ na˜o trivial. (2) Se duas MT reconhecem a mesma linguagem, enta˜o ambas aceitam
εou ambas rejeitam ε. Em consequeˆncia, o teorema de Rice diz que P e´ indecid´ıvel.
Tambe´m podemos usar reduc¸a˜o a partir de AMT = {〈M,w〉|M e´ uma MT que aceita a
cadeia w}: Suponha que P seja decid´ıvel. Constru´ımos, enta˜o, um decisor U para AMT:
U = “Sobre a entrada 〈M,w〉, onde M e´ uma MT e w e´ uma cadeia:
1. Construa uma a seguinte MT Mw.
Mw = “Sobre a entrada x:
1. Simule M sobre w. Se M aceita w, aceite; se M rejeita w, rejeite.”
2. Rode o decisor para P sobre 〈Mw〉.
3. Se o decisor aceita, aceite; se rejeita, rejeite.”
Note que Mw aceita ε (e, portanto, Mw ∈ P ) se e somente se M aceita w. Como sabemos
que AMT e´ indecid´ıvel, concluimos que o decisor para P na˜o existe e, portanto, esta
linguagem e´ indecid´ıvel.
8. Considere o problema de se determinar se uma ma´quina de Turing T para sobre uma dada
cadeia de entrada w. Formule o problema como uma linguagem e prove que e´ indecid´ıvel.
Resposta: PARAMT = {〈T,w〉|T e´ uma MT que para sobre a cadeia w}. Prova:
pa´ginas 198–199 do livro-texto.
9. Considere o problema de se determinar se duas ma´quinas de Turing reconhecem a mesma
linguagem. Formule o problema como uma linguagem e prove que e´ indecid´ıvel.
Resposta: EQMT = {〈T1, T2〉|T1 e T2 sa˜o MTs e L(T1) = L(T2)}. Prova: pa´gina 202
do livro-texto, ou reduc¸a˜o a partir de AMT = {〈M,w〉|M e´ uma MT que aceita a cadeia
w}: Suponha que EQMT seja decid´ıvel. Constru´ımos, enta˜o, um decisor U para AMT:
U = “Sobre a entrada 〈M,w〉, onde M e´ uma MT e w e´ uma cadeia:
1. Construa uma a seguinte MT M1.
M1 = “Sobre a entrada x:
1. Aceite.”
2. Construa uma a seguinte MT M2.
M1 = “Sobre a entrada x:
1. Simule M sobre w. Se M aceita w, aceite; se M rejeita w, rejeite.”
2. Rode o decisor para EQMT sobre 〈M1,M2〉.
3. Se o decisor aceita, aceite; se rejeita, rejeite.”
Note que L(M1) = Σ
∗, e L(M2) = L(M1) se e somente se M aceita w. Como sabemos
que AMT e´ indecid´ıvel, concluimos que o decisor para EQMT na˜o existe e, portanto, esta
linguagem e´ indecid´ıvel. .