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

Prévia do material em texto

Autoˆmatos e Computabilidade: Prova 3
1. Diga se cada uma das seguintes afirmac¸o˜es e´ verdadeira ou falsa. Justifique sua resposta.
(a) Se L e´ decid´ıvel, LR pode ser ou na˜o ser decid´ıvel. (LR e´ o reverso da linguagem L.)
Resposta: Falso. Se existe uma MT M que decide L, podemos construir uma
outra que decide M ′:
M ′= “Sobre a entrada w:
1. Obtenha wR invertindo w.
2. Rode M sobre wR.
3. Se M aceita, aceite; se rejeita, rejeite.”
(b) Se L ⊆ {0}∗ enta˜o L e´ decid´ıvel.
Resposta: Falso. Podemos codificar qualquer linguagem indecid´ıvel, como AMT,
usando o alfabeto 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.
(c) Se L ≤m {0n1n|n ≥ 0}, enta˜o L e´ decid´ıvel.
Resposta: 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.
(d) 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′.
Resposta: Falso. L = Σ∗ e´ regular e, portanto, Turing-reconhec´ıvel, mas AMT ⊆ L
na˜o e´ Turing-reconec´ıvel.
(e) 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.
Resposta: 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) 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.
Resposta: Falso. L(D) e´ uma linguagem regular. Pelo teorema de Rice, o pro-
blema de se determinar se uma MT aceita uma linguagem regular e´ indecid´ıvel.
2. Suponha que A e´ Turing-reconhec´ıvel e que A ≤m A. Prove que A e´ decid´ıvel.
Resposta: 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.
3. 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.
Resposta: 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.
4. (2 pontos) Prove que a linguagem L = {〈M〉|M aceita alguma cadeia w em, no ma´ximo, |w|
passos} e´ Turing-reconhec´ıvel.
Resposta: 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.”
5. (1 ponto) Como visto em aula, e´ poss´ıvel construir uma ma´quina de Turing AUTO que imprime
sua pro´pria descric¸a˜o, concatenando duas ma´quinas de Turing A e B. Descreva as ma´quinas A e
B.
Resposta: A MT A = P〈B〉 ignora sua entrada e escreve 〈B〉 na fita:
A= “Sobre qualquer entrada:
1. Apague a entrada.
2. Escreva 〈B〉 na fita.
3. Pare.”
A MT B, sobre a entrada w, computa Pw, e escreve 〈Pw〉 na frente de w:
B= “Sobre a entrada w:
1. Compute Pw.
2. Insira 〈Pw〉 na fita, na frente de w.
3. Pare.”
Assim a concatenac¸a˜o de A e B (AB) produz como resultado 〈A〉〈B〉 = 〈AB〉