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