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

Prévia do material em texto

Autoˆmatos e Computabilidade: Prova 3
1. (1 ponto) O conjunto de todas as func¸o˜es computa´veis f : Σ∗ → Σ∗ e´ conta´vel ou inconta´vel?
Prove sua resposta.
Resposta: 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.
2. (1 ponto) 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? Justifique sua resposta.
Resposta: 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.
3. (1 ponto) 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?
Resposta: 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.
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〉.”
4. (a) (1 ponto) A linguagem A = {〈M〉|M e´ uma ma´quina de Turing e L(M) e´ finita} e´
decid´ıvel ou indecid´ıvel? Prove sua resposta.
Resposta: 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 qual-
quer 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 reco-
nhecem tal linguagem e enta˜o 〈M3〉, 〈M4〉 /∈ A. Assim, pelo Teorema de Rice, A e´
indecid´ıvel.
(b) (1 ponto) 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? Prove sua resposta.
Resposta: 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.”
5. Seja TUDOMT = {〈M〉|M e´ uma ma´quina de Turing e L(M) = Σ
∗}.
(a) (1,5 pontos) Mostre que TUDOMT na˜o e´ decid´ıvel.
Resposta: A linguagem TUDOMT satisfaz as condic¸o˜es do Teorema de Rice. Pode-
mos construir uma ma´quina de Turing M1 que na˜o aceite nenhuma cadeia, e outra
M2 que aceite qualquer cadeias. Enta˜o, 〈M1〉 /∈ TUDOMT, 〈M2〉 ∈ TUDOMT e, por-
tanto, A e´ na˜o trivial. Tambe´m, se duas ma´quinas M3 e M4 reconhecem a mesma
linguagem, enta˜o ambas reconhecem Σ∗ 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. Sabemos, tambe´m, que se uma linguagem e´ indecid´ıvel, seu
complemento tambe´m e´. Enta˜o, TUDOMT e´ indecid´ıvel.
(b) (1,5 pontos) Prove que TUDOMT na˜o e´ Turing-reconhec´ıvel.
Resposta: 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´.
Notem que esta reposta tambe´m responde a questa˜o 5 (a), pois se uma linguagem
na˜o e´ Turing-reconhec´ıvel, tampouco e´ decid´ıvel.
6. (2 pontos) Seja T uma ma´quina de Turing que computa uma func¸a˜o t : Σ∗ × Σ∗ → Σ∗. O
Teorema da Recursa˜o diz que existe uma ma´quina de Turing R que computa uma func¸a˜o
r : Σ∗ → Σ∗ tal que, para toda cadeia w ∈ Σ∗, r(w) = t(〈R〉,w). Explique como construir
R.
Resposta: R e´ construida pela concatenac¸a˜o de treˆs ma´quinas, R = ABT . Seja Px
uma ma´quina que, sobre uma entrada w, escreve x na fita a` esquerda de w e usando um
separador #. Enta˜o, fazemos
(a) A = P 〈BT 〉: A escreve 〈BT 〉 na fita, a` esquerda da cadeia de entrada w e usando
o separador #. Assim, sobre a entrada w, A produz a sa´ıda 〈BT 〉#w e passa o
controle a B.
(b) B e´ uma ma´quina que, sobre uma entrada x#w, computa Px e escreve 〈Px〉 na
fita a` esquerda da entrada. Assim, sobre a entrada 〈BT 〉#w, B produz a sa´ıda
〈P〈BT 〉〉〈BT 〉#w e passa o controle a T . Sendo que A = P 〈BT 〉, e 〈A〉〈BT 〉 =
〈ABT 〉, enta˜o a sa´ıda de B e´ 〈ABT 〉#w. Ainda, R = ABT , enta˜o a sa´ıda de B e´
〈R〉#w.
(c) Finalmente, T opera sobre a entrada 〈R〉#w.