Baixe o app para aproveitar ainda mais
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).
Compartilhar