Exercícios resolvidos sobre Redutibilidade - Lucero - UnB

Prévia do material em texto

Redutibilidade
Problemas indecid´ıveis da teoria de linguagens
1. 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.
2. 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.
3. 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.
4. Suponha que construimos uma lista de todas as descric¸o˜es de ma´quinas de Turing, e.g., em
ordem lexicogra´fica: 〈M1〉, 〈M2〉, . . . ,〈Mi〉, . . ., e uma lista de todas as cadeias: w1, w2, . . . , wi, . . ..
Suponha que ambas listas sa˜o computa´veis: para qualquer i, e´ poss´ıvel determinar 〈Mi〉
e wi; tambe´m, dada 〈M〉, e´ poss´ıvel determinar i tal que 〈Mi〉 = 〈M〉 e, similarmente,
dada w, e´ poss´ıvel determinar i tal que wi = w.
Ainda, suponha que a seguinte linguagem seja indecid´ıvel: Ld = {w| existe i para o qual
w = wi e Mi na˜o aceita wi}. Prove, enta˜o, que AMT = {〈M,w〉|M e´ uma MT que aceita
w} e´ indecid´ıdivel por reduc¸a˜o a partir de Ld ou Ld.
5. Prove que a linguagem L = {〈M〉|M aceita alguma cadeia w em, no ma´ximo, |w| passos}
e´ Turing-reconhec´ıvel.
6. Prove que EQGLC e´ co-Turing-reconhec´ıvel. Pode usar o fato de que AGLC e´ decid´ıvel.
7. Prove que TODASGLC e´ co-Turing-reconhec´ıvel. Pode usar o fato de que AGLC e´ decid´ıvel.
8. Considere esta afirmac¸a˜o: Toda linguagem infinita e´ indecid´ıvel. Prova: Seja w uma
cadeia e L uma linguagem infinita. Para determinar se w ∈ L, uma ma´quina de Turing
deve comparar w com cada uma das cadeias da linguagem. Se w ∈ L, em algum momento
a ma´quina de Turing aceita w e para. No entanto, se w /∈ L, a ma´quina de Turing deve
testar as infinitas cadeias de L e, consequentemente, na˜o ira´ parar nunca. Portanto, L e´
Turing-reconhec´ıvel, mas e´ indecid´ıvel. A afirmac¸a˜o e´ verdadeira ou falsa?
9. (a) A linguagem A = {〈M〉|M e´ uma ma´quina de Turing e L(M) e´ finita} e´ decid´ıvel
ou indecid´ıvel?
(b) A linguagem B = {〈M〉|M e´ uma ma´quina de Turing que dedide a linguagem A do
item (a)} e´ decid´ıvel ou indecid´ıvel?
10. Seja TUDOMT = {〈M〉|M e´ uma ma´quina de Turing e L(M) = Σ
∗}. Prove que TUDOMT
na˜o e´ decid´ıvel.
11. 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. Na˜o utilize o Teorema de Rice.
12. 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.
13. 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.
14. 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.
15. 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.
1
16. 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.
17. 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.
Um problema indecid´ıvel simples
18. Seja a ma´quina de Turing M :
q0 qaceita
⊔ → 0,D
com Σ = {0, 1} e Γ = {0, 1,⊔}, e a cadeia w = ε. A partir M e w, e usando o algoritmo
visto em aula, construa um conjunto de domino´s para o problema da correspondeˆncia de
Post modificado (PCPM) e mostre que existe um emparelhamento. Atenc¸a˜o: no conjunto
de domino´s, inclua todas as pec¸as que o algoritmo gera, mesmo aquelas que na˜o sera˜o
utilizadas no emparelhamento.
Redutibilidade por mapeamento
19. Suponha que A e´ Turing-reconhec´ıvel e que A ≤m A. Prove que A e´ decid´ıvel.
20. O conjunto de todas as func¸o˜es computa´veis f : Σ∗ → Σ∗ e´ conta´vel ou inconta´vel?
21. Em aula, para mostrar que a linguagem REGULARMT = {〈M〉|M e´ uma ma´quina de
Turing e L(M) e´ regular} e´ decid´ıvel, aplicamos uma reduc¸a˜o a partir de AMT. Se a
ma´quina R decide REGULARMT, enta˜o a seguinte ma´quina decide 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:
1. Se x tem a forma 0n1n, aceite.
2. Se x na˜o tem essa forma, rode M sobre w. Se M aceita, aceite.
2. Rode R sobre 〈N,w〉.
3. Se R aceita, aceite; se R rejeita, rejeite.”
Do ponto de vista da reduc¸a˜o por mapeamento, qual a func¸a˜o computa´vel f que faz a
reduc¸a˜o? Qual a ma´quina de Turing que computa f?
22. Prove que TUDOMT do Problema 10 na˜o e´ Turing-reconhec´ıvel.
23. O conjunto de func¸o˜es f : N → N e´ conta´vel ou inconta´vel?
24. Se A ≤m B e B ≤m A, enta˜o A = B?
25. PAREMT ≤m 0
∗
1
∗?
26. Diga se cada uma das seguintes afirmac¸o˜es e´ verdadeira ou falsa.
(a) Se L e´ decid´ıvel, LR pode na˜o ser decid´ıvel.
(b) Se L ⊆ {0}∗ enta˜o L e´ decid´ıvel.
(c) Se L ≤m {0
n
1
n|n ≥ 0}, enta˜o L e´ decid´ıvel.
2
(d) Existe uma MT U que recebe 〈M〉 como entrada e computa uma MT M ′ tal que,
sobre uma cadeia de entrada w, M ′ aceita w se e somente se M para sobre w.
(e) Se L e´ Turing-reconhec´ıvel e L′ ⊆ L enta˜o L′ tambe´m e´ Turing-reconhec´ıvel, porque
a MT que aceita cadeias de L tambe´m aceita cadeias de L′.
(f) A linguagem EQMT,AFD = {〈M〉|M e´ uma MT e existe um AFD D tal que L(M) =
L(D)} e´ decid´ıvel, pois todo AFD reconhece uma linguagem regular, e toda linguagem
regular e´ decid´ıvel.
27. Determine se cada uma das seguintes linguagens e´: (i) decid´ıvel, (ii) indecid´ıvel e Turing-
reconhec´ıvel, (iii) indecid´ıvel e co-Turing-reconhec´ıvel, ou (iv) nem Turing-reconhec´ıvel
nem co-Turing-reconhec´ıvel.
(a) L1 = {〈M〉|M e´ uma ma´quina de Turing que aceita alguma cadeia w ∈ 1
∗}.
(b) L2 = {〈M〉|M e´ uma ma´quina de Turing que na˜o aceita nenhum pal´ındromo}.
(c) L3 = {〈M〉|M e´ uma ma´quina de Turing que, sobre alguma entrada, para depois de
executar 42 passos}.
(d) L4 = {〈M〉|M e´ uma ma´quina de Turing que aceita a cadeia 01 e na˜o aceita a cadeia
10}.
(e) L5 = {〈M,w〉|M e´ um autoˆmato linearmente limitado que na˜o para sobre w}.
(f) L6 = {〈M〉|M e´ uma ma´quina de Turing e L(M) e´ reconhecida por uma ma´quina
de Turing que possui uma quantidade ı´mpar de estados}.
(g) L7 = {〈M〉|M e´ uma MT e L(M) e´ regular}.
(h) L8 = {〈M〉|M e´ uma MT e L(M) e´ Turing-reconhec´ıvel}.
(i) L9 = {〈M〉|M e´ uma MT que aceita alguma cadeia de comprimento maior ou igual
que |〈M〉| }.
(j) L10 = {〈M,N〉|M e N sa˜o MTs e L(M) ∩ L(N) 6= ∅}.
(k) L11 = {〈M〉|M e´ uma MT que na˜o aceita nenhuma cadeia de comprimento maior
que 10 caracteres}.
Respostas
1. 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.
2. 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 odecisor para L sobre 〈Mw〉.
3
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.
3. 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.
4. Suponha que AMT seja decid´ıvel. Enta˜o, existe uma MT R que decide AMT. Podemos
construir uma MT U que decide Ld, da seguinte forma:
U= “Sobre a entrada w:
1. Determine i tal que wi = w.
2. Compute 〈Mi〉.
3. Rode R sobre 〈Mi, wi〉.
4. Se R aceita, rejeite, e se rejeita, aceite.”
Como sabemos que Ld e´ indecid´ıvel, U na˜o pode existir, o que implica que AMT deve ser
indecid´ıvel.
5. A seguinte MT U reconhece L:
U= “Sobre a entrada 〈M〉:
1. Enumere cadeias w ∈ Σ∗.
2. Rode M sobre cada cadeia w por |w| passos.
2. Se M aceita, aceite.”
6. A seguinte ma´quina de Turing reconhece EQGLC:
U= “Sobre a entrada 〈G1, G2〉, onde G1 e G2 sa˜o grama´ticas livre-do-contexto:
1. Gere cadeias wi ∈ Σ
∗, onde i = 1, 2, . . ., em ordem lexicogra´fica. Para cada wi:
1. Teste se wi ∈ L(G1) e se wi ∈ L(G2), usando o decisor para AGLC.
2. Se o decisor aceita um dos testes e rejeita o outro, aceite.
7. A seguinte ma´quina de Turing reconhece TODASGLC:
U= “Sobre a entrada 〈G〉, onde G e´ uma grama´tica livre-do-contexto:
1. Gere cadeias wi ∈ Σ
∗, onde i = 1, 2, . . ., em ordem lexicogra´fica. Para cada wi:
1. Teste se wi ∈ L(G), usando o decisor para AGLC.
2. Se o decisor rejeita, aceite.
4
8. A afirmac¸a˜o e´ falsa. Por exemplo, a linguagem L = Σ∗ e´ uma linguagem infinita e e´
dec´ıdivel: uma ma´quina de Turing que aceita todas as cadeias sobre Σ decide L. E´
verdade que a ma´quina de Turing descrita na prova na˜o decide L, mas isso na˜o implica
que L seja indec´ıdivel. Para provar a indecidibilidade deveriamos mostrar que na˜o existe
uma ma´quina de Turing decisora.
9. (a) A 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 qualquer cadeias.
Enta˜o, 〈M1〉 /∈ A, 〈M2〉 ∈ A e, portanto, A e´ na˜o trivial. Tambe´m, se duas ma´quinas
M3 e M4 reconhecem a mesma linguagem, enta˜o ambas reconhecem uma linguagem
com infinitas cadeias e enta˜o 〈M3〉, 〈M4〉 ∈ A, ou ambas na˜o reconhecem tal lingua-
gem e enta˜o 〈M3〉, 〈M4〉 /∈ A. Assim, pelo Teorema de Rice, A e´ indecid´ıvel.
(b) A linguagem do item (a) e´ indecid´ıvel, portanto, B = ∅ e e´ decid´ıvel. A seguinte
ma´quina de Turing decide B:
F= “Sobre a entrada 〈M〉, onde M e´ uma ma´quina de Turing , rejeite.”
10. A linguagem TUDOMT 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 qual-
quer cadeias. Enta˜o, 〈M1〉 /∈ TUDOMT, 〈M2〉 ∈ TUDOMT e, portanto, A e´ na˜o trivial.
Tambe´m, se duas ma´quinas M3 e M4 reconhecem a mesma linguagem, enta˜o ambas re-
conhecem Σ∗ e enta˜o 〈M3〉, 〈M4〉 ∈ TUDOMT, ou ambas na˜o reconhecem Σ
∗ e enta˜o
〈M3〉, 〈M4〉 /∈ TUDOMT. Assim, pelo Teorema de Rice, TUDOMT e´ indecid´ıvel. Sabe-
mos, tambe´m, que se uma linguagem e´ indecid´ıvel, seu complemento tambe´m e´. Enta˜o,
TUDOMT e´ indecid´ıvel.
11. 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.
12. 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.
5
13. 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.
14. 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) = Σ
∗ seM aceita w, e L(Mw) = ∅ seM 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.
15. 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.
16. 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
6
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) seM 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.
17. 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.
18. O conjunto de domino´s e´
P =
{[
#
#q0 ⊔#
]
,
[
q0⊔
0qaceita
]
,
[
0
0
]
,
[
1
1
]
,
[⊔
⊔
]
,
[
#
#
]
,
[
#
⊔#
]
,
[
0qaceita
qaceita
]
,
[
qaceita0
qaceita
]
,
[
1qaceita
qaceita
]
,
[
qaceita1
qaceita
]
,
[
⊔qaceita
qaceita
]
,
[
qaceita⊔
qaceita
]
,
[
qaceita##
#
]}
O emparelhamento e´
[
#
#q0 ⊔#
] [
q0⊔
0qaceita
] [
#
#
] [
0qaceita
qaceita
] [
#
#
] [
qaceita##
#
]
19. Se A ≤m A, enta˜o A ≤m A. Pela reduc¸a˜o, se A e´ Turing-reconhec´ıvel, enta˜o A tambe´m e´
Turing-reconhec´ıvel. Se uma linguagem e seu complemento sa˜o Turing-reconec´ıveis, enta˜o
ela e´ decid´ıvel.
20. O conjunto de todas as func¸o˜es computa´veis e´ conta´vel. Por definic¸a˜o, uma func¸a˜o f
e´ computa´vel se existe uma ma´quina de Turing que, sobre a entrada w, escreve f(w)
na fita e´ para. Logo, toda func¸a˜o computa´vel esta´ asociada a uma ma´quina de Turing.
Sabemos que o conjunto de ma´quinas de Turing e´ conta´vel, pois cada ma´quina possui uma
descric¸a˜o finita que pode ser codificada como uma cadeia sobre um alfabeto, e o conjunto
de cadeias que sa˜o descric¸o˜es va´lidas de uma ma´quina de Turing pode ser enumerado em
ordem lexicogra´fica.
21. A func¸a˜o f : Σ∗ → Σ∗ e´ f(〈M,w〉) = 〈N〉, onde N e´ uma ma´quina de Turing tal que
L(N) e´ regular se e somente se M aceita w. A ma´quina de Turing que computa F e´
F= “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.
7
N : “Sobre a entrada x, onde x e´ uma cadeia:
1. Se x tem a forma 0n1n, aceite.
2. Se x na˜o tem essa forma, rode M sobre w. Se M aceita, aceite.
2. Deˆ como saida 〈N〉.”
22. Mostramos que AMT ≤m TUDOMT. A seguinte ma´quina de Turing computa uma func¸a˜o
redutora f :
F= “Sobre a entrada 〈M,w〉, onde M e´ uma ma´quina de Turing , e w uma
cadeia:
1. Construa a seguinte ma´quina de Turing.
N : “Sobre a entrada x, onde x e´ uma cadeia:
1. Rode M sobre w. Se M aceita, aceite.
2. Deˆ como saida 〈N〉.”
Note que, se M aceita w, L(N) = Σ∗, e se M na˜o aceita w, L(N) = ∅.
Se AMT ≤m TUDOMT, enta˜o AMT ≤m TUDOMT. Sabemos que AMT na˜o e´ Turing-
reconhec´ıvel, enta˜o TUDOMT tampouco e´.
23. Inconta´vel. Chame ao conjunto de F , e suponha que seja conta´vel. Nesse caso, e´ poss´ıvel
construir um lista infinita de func¸o˜es f1, f2, f3, . . . tal que toda func¸a˜o f ∈ F aparece
exatamente um vez nessa lista. Considere agora a func¸a˜o g : N → N definida por:
g(n) =
{
1, se fn(n) 6= 1,
0, se fn(n) = 1.
Claramente, g na˜o esta´ na lista de func¸o˜es, pois g(n) 6= fn(n) para todo n, o que contradiz
a afirmac¸a˜o de que e´ poss´ıvel listar todas as func¸o˜es em F .
24. Na˜o. Se uma linguagem L e´ tal que L ≤m L, enta˜o, pelas propriedades da reduc¸a˜o por
mapeamento, L ≤m L, no entanto, L 6= L. Como exemplo, considere L = 01
∗. A seguinte
ma´quina de Turing computa uma reduc¸a˜o f de L a L:
F= “Sobre a entrada w:
1. Se w tem a forma 01n, com n ≥ 0, deˆ 1 como sa´ıda; se na˜o, deˆ 0 como
sa´ıda.”
Assim, se w ∈ L enta˜o f(w) = 1 ∈ L, e se w /∈ L enta˜o f(w) = 0 /∈ L. Note que a mesma
ma´quina F computa uma reduc¸a˜o de L a L, pois se w ∈ L enta˜o f(w) = 0 ∈ L, e se
w /∈ L enta˜o f(w) = 1 /∈ L.
25. Na˜o. A linguagem 0∗1∗ e´ regular e, portanto, decid´ıvel. Se A ≤m B, e B e´ decid´ıvel,
enta˜o A tambe´m e´ decid´ıvel. No entanto, sabemos que PAREMT na˜o e´ decid´ıvel.
26. (a) Falso. Se existe uma MT M que decide L, podemos construir uma outra que decide
LR:
M ′= “Sobre a entrada w:
1. Obtenha wR invertindo w.
2. Rode M sobre wR.
3. Se M aceita, aceite; se rejeita, rejeite.”
(b) Falso. Podemos codificar qualquer linguagem indecid´ıvel, como AMT, usando o alfa-
beto una´rio {0}. Por exemplo, podemos codificar cadeias s ∈ Σ∗ na forma 0n, onde
n e´ a posic¸a˜o de s em uma lista de todas as cadeias sobre Σ em ordem lexicogra´fica.
Se Σ = {a, b}, enta˜o 〈a〉 = 0, 〈b〉 = 00, 〈aa〉 = 000, 〈ab〉 = 0000 etc.
8
(c) Falso. L = Σ∗ e´ regular e, portanto, Turing-reconhec´ıvel, mas AMT ⊆ L na˜o e´
Turing-reconec´ıvel.
(d) Verdadeiro. A linguagem A = {0n1n|n ≥ 0} e´ livre-do-contexto e, portanto, decid´ı-
vel. Se L se reduz a uma linguagem decid´ıvel, enta˜o L tambe´m e´ decid´ıvel.
(e) Verdadeiro. Por exemplo:
U= “Sobre a entrada 〈M〉:
1. Construa a seguinte MT M ′.
M ′: “Sobre a entrada w:
1. Rode M sobre w.
2. Se M para, aceite.”
2. Deˆ como sa´ıda 〈M ′〉.”
(f) Falso. L(D) e´ uma linguagem regular. Pelo teorema de Rice, o problema de se
determinar se uma MT aceita uma linguagem regular e´ indecid´ıvel.
27. (a) ii. L1 e´ uma propriedade na˜o-trivial da linguagem de uma ma´quina de Turing: se
M∅ e´ uma ma´quina de Turing que rejeita todas as cadeias e MΣ∗ e´ uma ma´quina que
aceita todas as cadeias, enta˜o 〈M∅〉 /∈ L1 e 〈MΣ∗〉 ∈ L1, e, portanto, L1 e´ na˜o-trivial.
Tambe´m, se duas ma´quinas M1 e M2 tem a mesma linguagem, enta˜o ambas aceitam
alguma cadeia w ∈ 1∗ ou nehuma das duas aceita uma cadeia w ∈ 1∗. No primeiro
caso, 〈M1〉, 〈M2〉 ∈ L1; no segundo caso, 〈M1〉, 〈M2〉 /∈ L1. Enta˜o, pelo Teorema de
Rice, L1 e´ indecid´ıvel.
Por outro lado, L1 e´ Turing-reconhec´ıvel. A seguinte ma´quina de Turing reconhece
L1:
R= “Sobre a entrada 〈M〉, onde M e´ uma ma´quina de Turing:
1. Enumere cadeias si ∈ 1
∗, em ordem lexicogra´fica. Para cada si:
2. Rode M sobre cada s1, s2, . . . , si por i passos. Se M aceita alguma
cadeia, aceite.”
(b) iii. L2 e´ uma propriedade na˜o-trivial da linguagem de uma ma´quina de Turing:
〈M∅〉 /∈ L2 e 〈MΣ∗〉 ∈ L2, onde M∅ e MΣ∗ sa˜o as ma´quinas definidas na resposta
a` questa˜o 5 (a), e, portanto, L2 e´ na˜o-trivial. Tambem, se duas ma´quinas M1 e
M2 tem a mesma linguagem, ambas aceitam algum pal´ındromo ou nenhuma das
duas aceita um pal´ındrmo. No primeiro caso, 〈M1〉, 〈M2〉 /∈ L2; no segundo caso,
〈M1〉, 〈M2〉 ∈ L2. Enta˜o, pelo Teorema de Rice, L2 e´ indecid´ıvel.
Por outro lado, L2 e´ co-Turing-reconhec´ıvel. A seguinte ma´quina de Turing reconhece
L2:
R= “Sobre a entrada 〈M〉, onde M e´ uma ma´quina de Turing:
1. Enumere pal´ındromos si ∈ Σ
∗, em ordem lexicogra´fica. Para
cada si:
2.Rode M sobre cada s1, s2, . . . , si por i passos. Se M aceita alguma
cadeia, aceite.”
(c) i. Se M para sobre w depois de executar 42 passos, enta˜o M so´ ira´ ler, no ma´ximo,
os primeiros 42 s´ımbolos de w. Enta˜o, podemos rodar M sobre todas as cadeias w
de comprimento menor ou igual a 42, e verificar se M para em 42 passos. A seguinte
ma´quina de Turing decide L3:
R= “Sobre a entrada 〈M〉, onde M e´ uma ma´quina de Turing:
1. Enumere todas as cadeias si ∈ Σ
∗, em ordem lexicogra´fica, de
9
comprimento |si| ≤ 42. Para cada cadeia si:
2. Rode M sobre si ate´ um ma´ximo de 42 passos. Se M
para (aceita ou rejeita) depois de excutar o 42o passo,
aceite.”
3. Se todas as cadeias si foram testadas sem sucesso, rejeite.
(d) iv. L4 na˜o e´ Turing-reconhec´ıvel. A seguinte ma´quina de Turing computa uma
reduc¸a˜o de AMT a L4:
F= “Sobre a entrada 〈M,w〉, onde M e´ uma ma´quina de Turing e w
uma cade´ia:
1. Construa a seguinte ma´quina de Turing.
Mw: “Sobre a entrada x, onde x e´ uma cadeia:
1. Se x = 01, aceite.
2. Se x 6= 01, rode M sobre w. Se M aceita, aceite.
2. Deˆ como saida 〈N〉.”
Note que, se M na˜o aceita w, enta˜o L(Mw) = {01} e, portanto, 〈Mw〉 ∈ L4; se M
aceita w, enta˜o L(Mw) = Σ
∗ e, portanto, 〈Mw〉 /∈ L4
Por outro lado, L4 na˜o e´ co-Turing-reconhec´ıvel. A seguinte ma´quina de Turing
computa uma reduc¸a˜o de AMT a L4 (ou, equivalentemente, de AMT a L4):
F= “Sobre a entrada 〈M,w〉, onde M e´ uma ma´quina de Turing e w
uma cade´ia:
1. Construa a seguinte ma´quina de Turing.
Mw: “Sobre a entrada x, onde x e´ uma cadeia:
1. Se x = 10, rejeite.
2. Se x 6= 10, rode M sobre w. Se M aceita, aceite.
2. Deˆ como saida 〈N〉.”
Note que, se M aceita w, enta˜o L(Mw) = Σ
∗ − {10} e, portanto, 〈Mw〉 ∈ L4; se M
na˜o aceita w, enta˜o L(Mw) = ∅ e, portanto, 〈Mw〉 /∈ L4.
(e) i. Lembre que um autoˆmato linearmente limitado tem exatamente qngn configura-
c¸o˜es diferentes, onde q e´ a quantidade de estados, g e´ a quantidade de s´ımbolos no
alfabeto de fita, e n e´ o comprimento da fita. A seguinte ma´quina de Turing decide
L5:
R= “Sobre a entrada 〈M,w〉, onde M e´ um autoˆmato linearmente limitado e
w uma cadeia:
1. Rode M sobre w por um ma´ximo de qngn passos. Se M para (aceita
ou rejeita) antes de completar qngn passos, rejeite.
2. Se M completou qngn passos e na˜o aceitou nem rejeitou w, aceite.”
(f) i. A linguagem de toda ma´quina de Turing satisfaz a propriedade descrita em L6.
Suponha uma ma´quina de Turing M qualquer. Podemos construir uma ma´quina de
Turing N equivalente que possua uma quantidade impar de estados: Se a quantidade
de estados de M e´ impar, enta˜o fazemos N = M . Se a quantidade de estados de M e´
par, construimos N adicionando um estado “inu´til” a M . Enta˜o, a seguinte ma´quina
de Turing decide L6:
R= “Sobre a entrada 〈M〉, onde M e´ uma ma´quina de Turing: aceite.”
(g) iv. L1 na˜o e´ decid´ıvel. Podemos aplicar o teorema de Rice; no entanto, e´ mais
conveniente mostrar que existe uma reduc¸a˜o AMT ≤m L1. A seguinte MT computa
essa reduc¸a˜o:
10
F= “Sobre a entrada 〈M,w〉, onde M e´ uma ma´quina de Turing e w uma
cadeia:
1. Construa a seguinte ma´quina de Turing.
Mw: “Sobre a entrada x, onde x e´ uma cadeia:
1. Se x tem a forma yy, para y ∈ Σ∗, aceite.
2. Se na˜o, rode M sobre w. Se M aceita w, aceite.
2. Deˆ como sa´ıda 〈Mw〉.”
L(Mw) e´ regular (Σ
∗) se e somente se M aceita w. Portanto, 〈Mw〉 ∈ L1 se e somente
se 〈M,w〉 ∈ AMT.
A mesma reduc¸a˜o prova que L1 na˜o e´ co-Turing-reconhec´ıvel, pois AMT ≤m L1.
Mostramos, agora, que L1 tampouco e´ Turing-reconhec´ıvel, com a reduc¸a˜o AMT ≤m
L1. A seguinte modificac¸a˜o da MT acima computa essa reduc¸a˜o:
F= “Sobre a entrada 〈M,w〉, onde M e´ uma ma´quina de Turing e w uma
cadeia:
1. Construa a seguinte ma´quina de Turing.
Mw: “Sobre a entrada x, onde x e´ uma cadeia:
1. Se x tem a forma yy, para y ∈ Σ∗, rode M sobre w. Se M aceita
w, aceite.
2. Deˆ como sa´ıda 〈Mw〉.”
Neste caso, L(Mw) e´ regular (∅) se e somente se M na˜o aceita w. Portanto, 〈Mw〉 ∈
L1 se e somente se 〈M,w〉 ∈ AMT.
(h) i. L2 e´ decid´ıvel pois, por definic¸a˜o, a linguagem de toda MT e´ Turing-reconhec´ıvel.
A seguinte MT decide L2:
D= “Sobre a entrada 〈M〉, onde M e´ uma MT, aceite.
(i) ii. L3 na˜o e´ decid´ıvel. A seguinte MT computa uma reduc¸a˜o AMT ≤m L3:
F= “Sobre a entrada 〈M,w〉, onde M e´ uma ma´quina de Turing e w uma
cadeia:
1. Construa a seguinte ma´quina de Turing.
Mw: “Sobre a entrada x, onde x e´ uma cadeia:
1. Se |x| ≥ |〈M〉|, rode M sobre w. Se aceita, aceite.
2. Deˆ como sa´ıda 〈Mw〉.”
L(Mw) aceita toda cadeia de comprimento maior ou igual que |〈M〉| se e somente se
M aceita w. Portanto, 〈Mw〉 ∈ L3 se e somente se 〈M,w〉 ∈ AMT .
Por outro lado, L3 e´ Turing-reconhec´ıvel. A seguinte MT a reconhece:
R= “Sobre a entrada 〈M〉, onde M e´ uma MT:
1. Gere cadeias si sobre Σ de comprimento |si| ≥ |〈M〉|, em ordem
lexicogra´fica. Para cada i = 1, 2, . . .:
2. Rode M por i passos sobre cada entrada s1, s2, . . . , si. Se M
aceita alguma cadeia, aceite.
(j) ii. L4 na˜o e´ decid´ıvel. A seguinte MT computa uma reduc¸a˜o VMT ≤m L4:
F= “Sobre a entrada 〈M〉, onde M e´ uma ma´quina de Turing:
1. Construa a seguinte ma´quina de Turing.
N : “Sobre a entrada x, onde x e´ uma cadeia, aceite.
2. Deˆ como sa´ıda 〈M,N〉.”
11
L(N) = Σ∗; assim, L(M)∩L(N) /∈ ∅ se e somente se L(M) /∈ ∅. Portanto, 〈M,N〉 ∈
L4 se e somente se 〈M〉 ∈ VMT
Por outro lado, L4 e´ Turing-reconhec´ıvel. A seguinte MT a reconhece:
R= “Sobre a entrada 〈M,N〉, onde M e N sa˜o MTs:
1. Gere cadeias si sobre Σ, em ordem lexicogra´fica.
Para cada i = 1, 2, . . .:
2. Rode M e N por i passos sobre cada entrada s1, s2, . . . , si. Se
ambas M e N aceitam a mesma cadeia, aceite.
(k) iii. L5 satisfaz o teorema de Rice: Se duas MTs possuem a mesma linguagem, enta˜o
ambas pertencem a L5 ou nenhuma delas pertence. Ale´m disso, podemos construir
uma MT M∅ que na˜o aceita nenhuma cadeia, e outra MΣ∗ que aceita todas. Assim,
M∅ ∈ L5 e MΣ∗ /∈ L5. Portanto, L5 e´ uma propriedade na˜o-trivial da linguagem de
uma MT. Conclu´ımos, enta˜o, que L5 e´ indecid´ıvel.
Por outro lado, L5 e´ co-Turing-reconhec´ıvel. A seguinte MT reconhece L5:
R= “Sobre a entrada 〈M〉, onde M e´ uma MT:
1. Gere cadeias si sobre Σ, de comprimento maior que 10 caracteres,
em ordem lexicogra´fica. Para cada i = 1, 2, . . .:
2. Rode M por i passos sobre cada entrada s1, s2, . . . , si. Se M
aceita alguma cadeia, aceite.
12