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

Prévia do material em texto

Autoˆmatos e Computabilidade: Prova 3
1. Diga se cada uma das seguintes linguagens e´ (I) decid´ıvel, (II) indecid´ıvel mas Turing-
reconhec´ıvel ou (III) na˜o-Turing-reconhec´ıvel. Prove (formalmente) sua resposta. No caso
(I), sua resposta deve incluir uma descric¸a˜o da ma´quina de Turing que decide a linguagem;
no caso (II), deve incluir uma descric¸a˜o da ma´quina de Turing que reconhece a linguagem.
Pode utilizar qualquer teorema ou propriedade vista em aula.
(a) (2 pontos) L1 = {〈M〉|M e´ uma MT e L(M) e´ conta´vel}
Resposta: I. Toda linguagem e´ conta´vel. A seguinte MT decide L1:
D= “Sobre a entrada 〈M〉, onde M e´ uma MT:
1. Aceite.”
Note que o teorema de Rice na˜o se aplica porque L1 e´ trivial.
(b) (2 pontos) L2 = {〈M〉|M e´ uma MT e L(M) e´ finita}
Resposta: III. L2 na˜o e´ Turing-reconhec´ıvel porque AMT ≤m L2. A seguinte MT
computa essa reduc¸a˜o:
D= “Sobre a entrada 〈M,w〉, onde M e´ uma MT e w uma cadeia:
1. Construa a seguinte MT:
Mw= “Sobre a cadeia de entrada x:
1. Rode M sobre w. Se aceita, aceite; se rejeita, rejeite.”
2. Apague a fita, escreva 〈Mw〉 e pare.”
Note que L(Mw) = Σ
∗ se M aceita w, e L(Mw) = ∅ se M na˜o aceita w. Enta˜o, L(Mw)
e´ finita se e somente se M na˜o aceita w.
(c) (2 pontos) L3 = {〈M,w〉|M e´ um autoˆmato linearmente limitado (ALL) que para so-
bre a cadeia w}
Resposta: I. A seguinte MT decide L3:
D= “Sobre a entrada 〈M,w〉, onde M e´ uma 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 , n e´ o comprimento de sua fita e g e´ a quantidade de
s´ımbolos de seu alfabeto de fita.
2. Se M parou, aceite. Se atingiu a quantidade ma´xima de passos e na˜o
parou, rejeite.”
(d) (2 pontos) L4 = {〈M〉|M e´ uma MT e ε ∈ L(M)}
Resposta: II. L4 na˜o e´ decid´ıvel porque AMT ≤m L4. A seguinte MT computa essa
reduc¸a˜o:
D= “Sobre a entrada 〈M,w〉, onde M e´ uma MT e w uma cadeia:
1. Construa a seguinte MT:
Mw= “Sobre a cadeia de entrada x:
1. Rode M sobre w. Se aceita, aceite; se rejeita, rejeite.”
2. Apague a fita, escreva 〈Mw〉 e pare.”
Note que L(Mw) = Σ
∗ se M aceita w, e L(Mw) = ∅ se M na˜o aceita w. Enta˜o,
ε ∈ L(Mw) se e somente se M aceita w.
L4 e´ Turing-reconhec´ıvel porque a seguinte MT a reconhece:
D= “Sobre a entrada 〈M〉, onde M e´ uma MT:
1. Rode M sobre ε. Se aceita, aceite; se rejeita, rejeite.”
2. (1 ponto) A seguinte afirmac¸a˜o e´ verdadeira ou falsa? Justifique brevemente sua reposta:
Se A e´ Turing-reconhec´ıvel e A ≤m A, enta˜o A e´ decid´ıvel.
Resposta: A afirmac¸a˜o e´ verdadeira. Se A ≤m A, enta˜o A ≤m A e A tambe´m e´ Turing-
reconhec´ıvel. Se A e´ Turing-reconhec´ıvel e co-Turing-reconhec´ıvel, enta˜o e´ decid´ıvel.
3. (1 ponto) Defina formalmente o que e´ uma func¸a˜o computa´vel. Na˜o esquec¸a de definir
domı´nio e contradomı´nio.
Resposta: Uma func¸a˜o f : Σ∗ → Σ∗ e´ computa´vel se existe uma ma´quina de Turing que,
sobre toda entrada w ∈ Σ∗, para com f(w) na fita.