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

Prévia do material em texto

Autoˆmatos e Computabilidade: Prova 3
1. (2 pontos) Escolha uma (e somente uma) das seguintes afirmac¸o˜es e prove que e´ verdadeira:
(a) A linguagemAMT = {〈M,w〉|M e´ uma MT que aceita a cadeia w} e´ indecid´ıvel. (Aten-
c¸a˜o: na sua prova na˜o utilize nenhuma reduc¸a˜o nem o Teorema da Recursa˜o).
Resposta: pa´ginas 188–190 do livro-texto.
(b) Se P e´ uma propriedade na˜o-trivial da linguagem de uma ma´quina de Turing, enta˜o P
e´ indecid´ıvel (Teorema de Rice).
Resposta: pa´ginas 226–227 do livro-texto (item 5.28).
(c) O conjunto de nu´meros reais no intervalo [0, 1] e´ inconta´vel.
Resposta: A prova e´ similar a` do Teorema 4.17 (pa´ginas 186–187) do livro-texto,
considerando somente nu´meros reais entre 0 e 1.
2. (5 pontos) Verdadeiro ou falso? Justifique suas respostas (na˜o e´ necessa´rio fazer provas
formais).
(a) Se a linguagem PARAMT = {〈M,w〉|M e´ uma MT que para sobre a cadeia w} fosse
decid´ıvel, enta˜o toda linguagem Turing-reconhec´ıvel seria decid´ıvel.
Resposta: Verdadeiro. Seja D a MT que decide PARAMT e R a MT que reconhece
uma outra linguagem L. Poderiamos decidir L com a MT:
S= “Sobre a cadeia de entrada w:
1. Rode D sobre 〈R,w〉. Se rejeita, rejeite.
2. Rode R sobre w. Se aceita, aceite; se rejeita, rejeite.
(b) Se a linguagem PARAMT fosse decid´ıvel, enta˜o todas as linguagens seriam decid´ıveis.
Resposta: Falso. O conjunto de todas as linguagens e´ inconta´vel. No entanto, o
conjunto das linguagens decid´ıveis na˜o pode ter tamanho maior que o conjunto de
MTs, que e´ conta´vel.
(c) Se uma linguagem e´ Turing-reconhec´ıvel e co-Turing-reconhec´ıvel, enta˜o e´ decid´ıvel.
Resposta: Verdadeiro. A prova esta´ na pa´gina 191 do livro-texto (Teorema 4.22).
(d) Existem linguagens que na˜o sa˜o Turing-reconhec´ıveis nem co-Turing-reconhec´ıveis.
(Fornec¸a um exemplo de tal linguagem, ou mostre que na˜o existe)
Resposta: Verdadeiro. A linguagem EQMT na˜o e´ Turing-reconhec´ıvel nem co-Turing-
reconhec´ıvel (Teorema 5.30 do livro-texto, na pa´gina 221)
(e) Existe um algoritmo para decidir a linguagem {〈M〉|M e´ uma MT e existe um AFD A
tal que L(M) = L(A)}
Resposta: Falso. Note que, se existe um AFD A tal que L(M) = L(A), enta˜o L(M)
e´ regular. Assim, a linguagem da afirmac¸a˜o e´ a linguagem REGULARMT, que e´ inde-
cid´ıvel pelo Teorema de Rice. Veja tambe´m o Teorema 5.3 do livro-texto, na pa´gina
201.
3. (1 ponto) O problema de determinar se um autoˆmato linearmente limitado M aceita uma
cadeia w e´ decid´ıvel ou indecid´ıvel? Prove sua resposta.
Resposta: O problema e´ decid´ıvel. A prova esta´ na pa´gina 205 do livro-texto (Teorema
5.9).
4. (1 ponto) Defina formalmente o que e´ uma func¸a˜o computa´vel (na˜o esquec¸a de indicar
domı´nio e contradomı´nio).
Resposta: pa´gina 218 do livro-texto (definic¸a˜o 5.20).
5. (1 ponto) Mostre que ≤m e´ uma relac¸a˜o transitiva.
Resposta: pa´gina 225 do livro-texto (resposta ao exerc´ıcio 5.6).