3ª Prova de Autômatos e Computabilidade - 2º/2013 - Lucero - UnB

Prévia do material em texto

Autoˆmatos e Computabilidade: Prova 3
1. Classifique cada uma das seguintes linguagens como (I) decid´ıvel, (II) indecid´ıvel mas
Turing-reconhec´ıvel, (III) na˜o Turing-reconhec´ıvel mas co-Turing-reconhec´ıvel, (IV) nem
Turing-reconhec´ıvel nem co-Turing-reconhec´ıvel. Prove todas suas respostas. Pode citar
qualquer teorema visto em aula. Para descrever ma´quinas de Turing, utilize o formato
M= “Sobre a cadeia de entrada . . .:
1....
2....
...
(a) L1 = {〈M〉|M e´ uma MT e L(M) e´ regular}.
Resposta: 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 seguinteMT 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 ∈ Σ∗, 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. Mos-
tramos, 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.
(b) L2 = {〈M〉|M e´ uma MT e L(M) e´ Turing-reconhec´ıvel}.
Resposta: 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.
(c) L3 = {〈M〉|M e´ uma MT que aceita alguma cadeia de comprimento maior ou igual
que |〈M〉| }.
Resposta: 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.
(d) L4 = {〈M,N〉|M e N sa˜o MTs e L(M) ∩ L(N) 6= ∅}.
Resposta: 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〉.”
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.
(e) L5 = {〈M〉|M e´ uma MT que na˜o aceita nenhuma cadeia de comprimento maior que
10 caracteres}.
Resposta: III. L5 satisfaz o teorema de Rice: Se duas MTs possuem a mesma lingua-
gem, 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.
2. A unia˜o de infinitas linguagens decid´ıveis e´ decid´ıvel? Prove sua resposta.
Resposta: na˜o necessariamente. A unia˜o de infinitas linguagens decid´ıveis pode ser
tanto decid´ıvel quanto indecid´ıvel. Toda linguagem finita e´ regular e, portanto, decid´ıvel.
Enta˜o, a linguagem Σ∗, que e´ regular e decid´ıvel, e´ a unia˜o de infinitas linguagens finitas e
decid´ıveis Li, cada uma das quais conte´m uma u´nica cadeia wi ∈ Σ
∗. No entanto, podemos
fazer uma afirmac¸a˜o similar sobre a linguagem AMT, que sabemos que e´ indecid´ıvel. AMT e´
a unia˜o de infinitas linguagens finitas e decid´ıveis Li, cada uma das quais conte´m uma u´nica
cadeia 〈Mi, wj〉 onde Mi e´ uma MT que aceita a cadeia wj.
3. E´ poss´ıvel enumerar todas as ma´quinas de Turing M que aceitam sua pro´pria descric¸a˜o
〈M〉?
Resposta: Sim. A linguagem L = {〈M〉|M e´ uma MT que aceita 〈M〉} e´ Turing-
reconhec´ıvel. A seguinte MT a reconhece:
R= “Sobre a entrada 〈M〉, onde M e´ uma MT:
1. Rode M sobre 〈M〉. Se aceita, aceite; se rejeita, rejeite.
Sabemos que toda linguagem Turing-reconhec´ıvel e´ enumera´vel.