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

Prévia do material em texto

Autoˆmatos e Computabilidade: Prova 3
1. (3 pontos) Prove que a linguagem AMT = {〈M,w〉|M e´ uma MT que aceita a cadeia w} e´
indecid´ıvel. Dica: Suponha AMT decid´ıvel e obtenha uma contradic¸a˜o. Na˜o utilize nenhuma
reduc¸a˜o.
Resposta: Teorema 4.11 e pa´ginas 188-189 do livro-texto. Suponha AMT decid´ıvel
e seja H a MT decisora. Enta˜o, podemos construir a seguinte MT D:
D= “Sobre a entrada 〈M〉, onde M e´ uma MT:
1. Rode H sobre 〈M, 〈M〉〉.
2. Se H aceita, rejeite; se H rejeita, aceite.
A MT D aceita uma entrada 〈M〉 se e somente se M na˜o aceita seua pro´pria descric¸a˜o
〈M〉. Agora, se rodamos D sobre sua pro´pria descric¸a˜o 〈D〉, obtemos que D aceita 〈D〉 se
e somente se D na˜o aceita 〈D〉. Esta e´, obviamente, uma contradic¸a˜o, o que implica que
AMT na˜o e´ decid´ıvel.
2. (2 pontos) A quais das seguintes linguagens e´ poss´ıvel aplicar o Teorema de Rice para provar
indecidibilidade? Justifique brevemente suas respostas.
Resposta: Em cada caso, devemos verificar se as condic¸o˜es para o Teorema de Rice sa˜o
satisfeitas. Essas condic¸o˜es esta˜o enunciadas no Problema 5.28 do livro-texto: a lin-
guagem dada deve ser um propriedade da linguagem de uma MT, e deve-ser na˜o-trivial.
(a) VMT = {〈M〉|M e´ uma MT e L(M) = ∅}
Resposta: Sim e´ poss´ıvel. Se duas MTs possuem a mesma linguagem, essa linguagem
e´ vazia, em cujo caso ambas MT pertencem a VMT, ou na˜o e´ vazia, em cujo caso
nenhuma das MT pertence a VMT. Enta˜o, VMT e´ uma propriedade da linguagem de
uma MT. Tambe´m, podemos construir uma MTM1 que aceite qualquer entrada e uma
MT M2 que na˜o aceite nenhuma. Assim, M1 /∈ VMT e M2 ∈ VMT e, portanto, VMT e´
na˜o-trivial
(b) EQMT = {〈M1,M2〉|M1,M2 sa˜o MTs e L(M1) = L(M2)}
Resposta: Na˜o e´ poss´ıvel, pois EQMT conte´m descric¸o˜es de pares de MTs (em vez de
MTs individuais).
(c) LMEQ = {〈M〉|M e´ uma MT e L(M) = EQMT}
Resposta: Na˜o e´ poss´ıvel, pois EQMT na˜o e´ Turing-reconhec´ıvel e enta˜o LMEQ = ∅
(i.e., LMEQ e´ trivial).
(d) LM6 = {〈M〉|M e´ uma MT que aceita ε em exatamente um passo}
Resposta: Na˜o e´ poss´ıvel, pois LM6 na˜o e´ uma propriedade da linguagem de uma
ma´quina de Turing. Duas MTs podem ter a mesma linguagem L com ε ∈ L; no
entanto, uma delas pode aceitar ε em um passo e a outra em dois passos. Enta˜o, a
primeira MT ira´ pertencer LM6 em quanto que a segunda MT na˜o.
3. (2 pontos) Usando reduc¸a˜o por mapeamento, prove que a linguagem
COMPMT = {〈M1,M2〉|M1,M2 sa˜o MTs e L(M1) = L(M2)}
e´ indecid´ıvel.
Resposta: A prova e´ similar a` do exemplo 5.26 do livro-texto, trocando M1 por uma
MT que aceita todas as cadeias. A seguinte MT computa uma reduc¸a˜o de VMT a COMPMT:
F= “Sobre a entrada 〈M〉, onde M e´ uma ma´quina de Turing:
1. Construa a seguinte ma´quina de Turing.
M1: “Sobre a entrada x, onde x e´ uma cadeia,aceite.
2. Escreva 〈M,M1〉 na fita e pare.”
L(M1) = Σ
∗ e, portanto, L(M1) = ∅. Enta˜o, L(M) = ∅ se e somente se L(M) = L(M1).
Portanto, 〈M〉 ∈ VMT se e somente se 〈M,M1〉 ∈ COMPMT.
4. (2 pontos) A linguagem L5 = {〈M,w〉|M e´ um ALL (autoˆmato linearmente limitado) que
na˜o para sobre a cadeia w} e´ decid´ıvel ou indecid´ıvel? Prove sua resposta.
Resposta: L5 e´ decid´ıvel. A prova e´ similar a` do Teorema 5.9 do livro-texto, e a
seguinte MT decide L5:
F= “Sobre a entrada 〈M,w〉, onde M e´ um ALL e w uma cadeia:
1. Rode M sobre w por um ma´ximo de qngn passos, onde q e´ a quantidade de
estados de M , g e´ a quantidade de s´ımbolos no seu alfabeto de fita, e n e´ o
comprimento da sua fita.
2. Se M parou (aceitou ou rejeitou w), rejeite; se na˜o parou, aceite.”
5. (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: Definic¸a˜o 5.17 do livro-texto: Uma func¸a˜o computa´vel e´ uma func¸a˜o
f : Σ∗ → Σ∗ para a qual existe uma MT que, sobre toda entrada w, para com exatamente
f(w) sobre sua fita.