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

Prévia do material em texto

Autoˆmatos e Computabilidade: Prova 3
1. O conjunto de func¸o˜es f : N → N e´ conta´vel ou inconta´vel?
Resposta: inconta´vel. Chame ao conjunto de F , e suponha que seja conta´vel. Nesse
caso, e´ poss´ıvel construir um lista infinita de func¸o˜es f1, f2, f3, . . . tal que toda func¸a˜o
f ∈ F aparece exatamente um vez nessa lista. Considere agora a func¸a˜o g : N → N
definida por:
g(n) =
{
1, se fn(n) 6= 1,
0, se fn(n) = 1.
Claramente, g na˜o esta´ na lista de func¸o˜es, pois g(n) 6= fn(n) para todo n, o que contradiz
a afirmac¸a˜o de que e´ poss´ıvel listar todas as func¸o˜es em F .
2. Defina, formalmente, o que significa dizer que uma linguagem A e´ redut´ıvel por mapeamento
a uma linguagem B.
Resposta: A e´ redutivel por mapeamento a B se existe uma func¸a˜o computa´vel f :
Σ∗ → Σ∗ tal que w ∈ A⇔ f(w) ∈ B.
3. Se A ≤m B e B ≤m A, enta˜o A = B?
Resposta: Na˜o. Se uma linguagem L e´ tal que L ≤m L, enta˜o, pelas propriedades
da reduc¸a˜o por mapeamento, L ≤m L, no entanto, L 6= L. Como exemplo, considere
L = 01∗. A seguinte ma´quina de Turing computa uma reduc¸a˜o f de L a L:
F= “Sobre a entrada w:
1. Se w tem a forma 01n, com n ≥ 0, deˆ 1 como sa´ıda; se na˜o, deˆ 0 como
sa´ıda.”
Assim, se w ∈ L enta˜o f(w) = 1 ∈ L, e se w /∈ L enta˜o f(w) = 0 /∈ L. Note que a
mesma ma´quina F computa uma reduc¸a˜o de L a L, pois se w ∈ L enta˜o f(w) = 0 ∈ L,
e se w /∈ L enta˜o f(w) = 1 /∈ L.
4. PAREMT ≤m 0∗1∗?
Resposta: Na˜o. A linguagem 0∗1∗ e´ regular e, portanto, decid´ıvel. Se A ≤m B, e
B e´ decid´ıvel, enta˜o A tambe´m e´ decid´ıvel. No entanto, sabemos que PAREMT na˜o e´
decid´ıvel.
5. Determine se cada uma das seguintes linguagens e´: (i) decid´ıvel, (ii) indecid´ıvel e Turing-
reconhec´ıvel, (iii) indecid´ıvel e co-Turing-reconhec´ıvel, ou (iv) nem Turing-reconhec´ıvel nem
co-Turing-reconhec´ıvel.
(a) L1 = {〈M〉|M e´ uma ma´quina de Turing que aceita alguma cadeia w ∈ 1∗}.
Resposta: ii.
– L1 e´ uma propriedade na˜o-trivial da linguagem de uma ma´quina de Turing:
se M∅ e´ uma ma´quina de Turing que rejeita todas as cadeias e MΣ∗ e´ uma
ma´quina que aceita todas as cadeias, enta˜o 〈M∅〉 /∈ L1 e 〈MΣ∗〉 ∈ L1, e,
portanto, L1 e´ na˜o-trivial. Tambe´m, se duas ma´quinas M1 e M2 tem a mesma
linguagem, enta˜o ambas aceitam alguma cadeia w ∈ 1∗ ou nehuma das duas
aceita uma cadeia w ∈ 1∗. No primeiro caso, 〈M1〉, 〈M2〉 ∈ L1; no segundo
caso, 〈M1〉, 〈M2〉 /∈ L1. Enta˜o, pelo Teorema de Rice, L1 e´ indecid´ıvel.
– L1 e´ Turing-reconhec´ıvel. A seguinte ma´quina de Turing reconhece L1:
R= “Sobre a entrada 〈M〉, onde M e´ uma ma´quina de Turing:
1. Enumere cadeias si ∈ 1∗, em ordem lexicogra´fica. Para cada si:
2. Rode M sobre si. Se M aceita, aceite.”
(b) L2 = {〈M〉|M e´ uma ma´quina de Turing que na˜o aceita nenhum pal´ındromo}.
Resposta: iii.
– L2 e´ uma propriedade na˜o-trivial da linguagem de uma ma´quina de Turing:
〈M∅〉 /∈ L2 e 〈MΣ∗〉 ∈ L2, onde M∅ e MΣ∗ sa˜o as ma´quinas definidas na resposta
a` questa˜o 5 (a), e, portanto, L2 e´ na˜o-trivial. Tambem, se duas ma´quinas M1
e M2 tem a mesma linguagem, ambas aceitam algum pal´ındromo ou nenhuma
das duas aceita um pal´ındrmo. No primeiro caso, 〈M1〉, 〈M2〉 /∈ L2; no segundo
caso, 〈M1〉, 〈M2〉 ∈ L2. Enta˜o, pelo Teorema de Rice, L2 e´ indecid´ıvel.
– L2 e´ co-Turing-reconhec´ıvel. A seguinte ma´quina de Turing reconhece L2:
R= “Sobre a entrada 〈M〉, onde M e´ uma ma´quina de Turing:
1. Enumere pal´ındromos si ∈ Σ∗, em ordem lexicogra´fica. Para
cada si:
2. Rode M sobre si. Se M aceita, aceite.”
(c) L3 = {〈M〉|M e´ uma ma´quina de Turing que, sobre alguma entrada, para depois de
executar 42 passos}.
Resposta: i.
– Se M para sobre w depois de executar 42 passos, enta˜o M so´ ira´ ler, no
ma´ximo, os primeiros 42 s´ımbolos de w. Enta˜o, podemos rodar M sobre todas
as cadeias w de comprimento menor ou igual a 42, e verificar se M para em
42 passos. A seguinte ma´quina de Turing decide L3:
R= “Sobre a entrada 〈M〉, onde M e´ uma ma´quina de Turing:
1. Enumere todas as cadeias si ∈ Σ∗, em ordem lexicogra´fica, de
comprimento |si| ≤ 42. Para cada cadeia si:
2. Rode M sobre si ate´ um ma´ximo de 42 passos. Se M
para (aceita ou rejeita) depois de excutar o 42o passo,
aceite.”
3. Se todas as cadeias si foram testadas sem sucesso, rejeite.
(d) L4 = {〈M〉|M e´ uma ma´quina de Turing que aceita a cadeia 01 e na˜o aceita a cadeia
10}.
Resposta: iv.
– L4 na˜o e´ Turing-reconhec´ıvel. A seguinte ma´quina de Turing computa uma
reduc¸a˜o de AMT a L4:
F= “Sobre a entrada 〈M,w〉, onde M e´ uma ma´quina de Turing e w
uma cade´ia:
1. Construa a seguinte ma´quina de Turing.
Mw: “Sobre a entrada x, onde x e´ uma cadeia:
1. Se x = 01, aceite.
2. Se x 6= 01, rode M sobre w. Se M aceita, aceite.
2. Deˆ como saida 〈N〉.”
Note que, se M na˜o aceita w, enta˜o L(Mw) = {01} e, portanto, 〈Mw〉 ∈ L4;
se M aceita w, enta˜o L(Mw) = Σ
∗ e, portanto, 〈Mw〉 /∈ L4
– L4 na˜o e´ co-Turing-reconhec´ıvel. A seguinte ma´quina de Turing computa uma
reduc¸a˜o de AMT a L4 (ou, equivalentemente, de AMT a L4):
F= “Sobre a entrada 〈M,w〉, onde M e´ uma ma´quina de Turing e w
uma cade´ia:
1. Construa a seguinte ma´quina de Turing.
Mw: “Sobre a entrada x, onde x e´ uma cadeia:
1. Se x = 10, rejeite.
2. Se x 6= 10, rode M sobre w. Se M aceita, aceite.
2. Deˆ como saida 〈N〉.”
Note que, se M aceita w, enta˜o L(Mw) = Σ
∗ − {10} e, portanto, 〈Mw〉 ∈ L4;
se M na˜o aceita w, enta˜o L(Mw) = ∅ e, portanto, 〈Mw〉 /∈ L4.
(e) L5 = {〈M,w〉|M e´ um autoˆmato linearmente limitado que na˜o para sobre w}.
Resposta: i. Lembre que um autoˆmato linearmente limitado tem exatamente
qngn configurac¸o˜es diferentes, onde q e´ a quantidade de estados, g e´ a quantidade
de s´ımbolos no alfabeto de fita, e n e´ o comprimento da fita. A seguinte ma´quina
de Turing decide L5:
R= “Sobre a entrada 〈M,w〉, onde M e´ um autoˆmato linearmente limitado e
w uma cadeia:
1. Rode M sobre w por um ma´ximo de qngn passos. Se M para (aceita
ou rejeita) antes de completar qngn passos, rejeite.
2. Se M completou qngn passos e na˜o aceitou nem rejeitou w, aceite.”
(f) L6 = {〈M〉|M e´ uma ma´quina de Turing e L(M) e´ reconhecida por uma ma´quina de
Turing que possui uma quantidade ı´mpar de estados}.
Resposta: i. A linguagem de toda ma´quina de Turing satisfaz a propriedade
descrita em L6. Suponha uma ma´quina de Turing M qualquer. Podemos construir
uma ma´quina de Turing N equivalente que possua uma quantidade impar de estados:
Se a quantidade de estados de M e´ impar, enta˜o fazemos N = M . Se a quantidade
de estados de M e´ par, construimos N adicionando um estado “inu´til” a M . Enta˜o,
a seguinte ma´quina de Turing decide L6:
R= “Sobre a entrada 〈M〉, onde M e´ uma ma´quina de Turing: aceite.”