Teorema de Rice

50 %
50 %
Information about Teorema de Rice
Education

Published on March 20, 2014

Author: yuripassos58

Source: slideshare.net

Description

Aula sobre o teorema de Rice

Teorema de Rice Yuri Tavares dos Passos

Prévia ● Antes de começar, pesquisem sobre o seguintes problemas: – Le = {Mi | L(Mi ) = ∅} – Lne = {Mi | L(Mi ) ≠ ∅} E responda se eles são RE, não-RE ou decidíveis.

Propriedade ● Uma propriedade de uma linguagem RE é um conjunto de linguagens RE ● Exemplo: A propriedade de uma linguagem ser CFL é o conjunto de todas as linguagens CFLs.

Propriedade trivial ● Uma propriedade é dita trivial se: – Ela é vazia. – Ela corresponde a um conjunto de linguagens RE. ● Observe que {∅} é diferente de ∅. ● Se P é uma propriedade das linguagens RE, podemos dizer que LP é a linguagem das MTs que aceitam alguma linguagem de P. – LP = {Mi | L(Mi ) ∈ P} ● Ou seja, LP possui os códigos de MTs que aceitam alguma linguagem de P.

Teorema de Rice ● Toda propriedade não-trivial das linguagens RE é indecidível. ● Prova: Considere P uma propriedade não-trivial que não possui a linguagem vazia ∅. ● Como ela não possui vazio e não é vazio, deve existir uma linguagem L dentro dela. ● Considere que existe uma máquina ML que aceita esta linguagem.

Prova ● ML possui um código que está em LP . ● Considere também que exista uma MT MP que reconhece a propriedade P. ● Vamos descrever um algoritmo que constrói M', uma MT que aceita a seguinte linguagem: L(M ' )={L M aceita w ∅ M não aceita w

x Mw Aceitar ML Aceitar Aceitar M' Algoritmo que gera a MT M'

Prova ● Veja que se M' aceita x, como x ∈ L, então M' é uma MT, cujo código está em LP . ● Chame o algoritmo que gera M' de algorimto A. ● Usando A, podemos criar uma redução de LU para o teste da propriedade P como mostra a figura que segue.

Redução de LU para P M111w A M' MP Aceitar Aceitar Rejeitar Rejeitar

Prova ● Mas, o algoritmo de construção de M' é uma redução de LU a P. ● Sabemos que LU é indecidível, logo P também é. ● Falta tratar o caso em que vazio pertence a P. Mas, sabemos que o teste para linguagem vazio é não-RE.

Add a comment

Related presentations

Related pages

Teorema de Rice – Wikipédia, a enciclopédia livre

Na teoria da computação, o teorema de Rice afirma que, para qualquer propriedade não-trivial de funções parciais, não existe um método geral e ...
Read more

Rice's theorem - Wikipedia, the free encyclopedia

In computability theory, Rice's theorem states that, for any non-trivial property of partial functions, no general and effective method can decide whether ...
Read more

Teorema de Rice - Wikipedia, la enciclopedia libre

Introducción. Otra forma de expresar el teorema de Rice que es más útil en la teoría de la computación dice que: Sea un conjunto de lenguajes no ...
Read more

Teorema di Rice - Wikipedia

Nella logica matematica, nella teoria della calcolabilità e nell'informatica teorica, il teorema di Rice costituisce un importante risultato nella teoria ...
Read more

Teorema de Rice - Departamento de Computación

Teorema 1.1 (Rice) Ninguna subclase propia no vacía de funciones recursivas puede ser recursiva. En otras palabras, si existen tales que y entonces ...
Read more

Teorema de Rice - Pastebin.com

Pastebin PRO Accounts SPRING SPECIAL! For a limited time only get 40% discount on a LIFETIME PRO account! Offer Ends Soon!
Read more

Teorema de Rice - Education - Discover, share, present ...

Teorema de Rice Mestrado em Ciência da Computação Profa. Sandra de Amo. Slide 1 Teorema de Rice Mestrado em Ciência da Computação Profa.
Read more

Rices theorem - Example Problems

Rices theorem. From Example Problems. Jump to: navigation, search. ... Satz von Rice fr:Théorème de Rice it:Teorema di Rice he:משפט ...
Read more

Teorema da Rita | Aqui a Rita vai falar sobre o que lhe ...

Teorema da Rita Aqui a Rita vai falar sobre o que lhe apetecer, até porque o estaminé é dela! Menu. Procurar. Skip to content. Início; Sobre; Procurar por:
Read more