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