[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [obm-l] Indecidibilidade -PARTE I
è muito mais facil compreender esse problema pela
otica do teorema da parada das maquinas de Turing, ja
que uma prova,nada mais é que mu algoritmo.Uma boa
explanaçao sobre isso pode ser vista em:
http://en.wikipedia.org/wiki/Halt_problem
A proposiçao indecidivel nada mais é que a funçao
trouble , que é um algoritmo.Em teoria da computaçao,
se trabalha com problemas de decisao.Problemas de
decisao sao aqueles cuja PERGUNTA crucial é se uma
dada entrada pertence ou não(é soluçao) a uma dada
linguagem.Voce fornece uma entrada para a maquina e
ela diz se aquela entrada pertence ou nao a linguagem.
Todos os problemas podem ser reduzidos a um problema
de decisao.Voce poderia transformar o problema do
calculo de uma integral,perguntando somente se uma
dada entrada é integral de uma dada funçao ou
não.Perceba a diferença, nao há o desenvolvimento ate
se achar a resposta, simplesmente fornece-se uma
suposta resposta e pergunta-se se é integral ou não.
Linguagens DECIDIVEIS sao as linguagens interpretadas
pela maquina de Turing que dizem sim e param se a
entrada pertence a linguagem , e dizem nao e param se
a entrada nao pertence a linguagem.O importante aqui é
que elas sempre PARAM,num tempo finito, nem que leve a
idade do universo para parar.
Linguagens SEMIDECIDIVEIS é o mesmo conceito da
DECIDIVEL com o diferencial que , se a entrada não
pertence a linguagem, entra em loop infinito, ou seja,
NAO PARA.Seria como entrar com uma soluçao falsa para
a integral e a maquina entrar em loop infinito, isso
só aconteceria se as linguagens das integrais fossem
semidecidiveis.Existem problemas assim???Se DECIDIVEIS
= SEMIDECIDIVEIS nao existem coisas do tipo.O conceito
de Indecidivel, nao é o caso em que nao para nós casos
em que a entrada pertence ou nao,simplesmente
refere-se a algo que nao dá para fazer.
O que nao se sabia era se DECIDIVEIS = SEMIDECIDIVEIS,
que foi a contribuiçao da ideia de Turing.Bem para se
provar isto basta que provar que DECIDIVEIS esta
contido nos SEMIDECIDIVEIS E QUE SEMIDECIDIVEIS esta
contido nos DECIDIVEIS => DECIDIVEIS = SEMIDECIDIVEIS.
Para provar a primeira, basta pegar uma maquina que le
uma linguagem decidivel qualquer e fazer uma
modificação, quando a entrada nao pertencer a
linguagem,faça ela entrar em loop,assim reduzir ela a
uma semidecidivel,que é o suficiente.Portanto
DECIDIVEIS esta contido nos SEMIDECIDIVEIS.
Para provar a segunda , teriamos que arrumar um
mecanismo de reduzir um problema SEMIDECIDIVEL a um
problema DECIDIVEL.Como????Ai é que entra o pulo do
gato, fica para a parte II.
Ate mais.
--- ronaldogandhi@ig.com.br escreveu: > >Desculpe, mas
acho que esta sua explicação do que é
> uma
> >questão indecidível confunde mais do que esclarece.
>
>
> Tem toda razão, eu preciso ler mais sobre isso.
> Mas nada que um bom professor (como vc) não
> possa esclarecer. Fiz uma pesquisa no Google e
> encontrei essa mensagem sua bastante interessante:
>
>
>
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.200008/msg00240.html
>
>
>
>
> >
> >Uma proposição é indecidível quando nem ela nem a
> sua negação
> >seguem dos axiomas da teoria (que podem ser dados
> explicita
> >ou implicitamente). Mas uma proposição é algo
> claro, sem
> >autoreferências explícitas, como no seu exemplo.
> >
>
> Pelo que eu entendi, abaixo
> vc deu um exemplo abaixo de uma proposição que é
> indecidível em PA mas que é decidível
> e verdadeira em ZFC:
>
>
> >Um exemplo de afirmativa sobre naturais verdadeira
> em ZFC
> >mas não demonstrável em PA é uma versão do teorema
> de Ramsey.
> >Teorema de Ramsey finito forte:
> >Dados naturais n, m e l então existe N tal que se X
> =
> >{0,1,2,...,N-1} e |Y| = m então toda função f:
> X^[n] -> Y
> >admite um subconjunto homogêneo Z relativamente
> grande
> >com pelo menos l elementos.
> > O teorema de Ramsey forte acima não pode ser
> demonstrado
> >na aritmética de Peano apesar de ser facilmente
> >demonstrável fazendo uso de conjuntos infinitos.
>
>
>
> Essa é frase 'G' que você citou no e-mail
> anterior, certo? Vc também citou a hipótese do
> Contínum que não é demonstrável em ZFC:
>
> >A hipótese do contínuo diz que se X é um
> subconjunto
> >infinito de R então ou existe uma bijeção entre X e
>
> > N ou entre X e R. Ela é um exemplo de proposição
> >indecidível em ZFC: isto significa que com os
> axiomas
> >de ZFC não é possível
> >nem demonstrar nem refutar a hipótese do contínuo.
>
> A dúvida apareceu é se existe algum sistema no
> qual
> a hipótese do contínum seja demonstrável. Se não é
> possível demonstrá-la nem em PA e
> nem em ZFC, existe algum outro sistema no qual
> ela seja demonstrável?
> Ou teríamos que considerá-la verdadeira (axioma)
> e construir outro sistema a partir dela?
> Desculpe se isto estiver indo meio off-topic...
> ou dizendo bobagens. Eu realmente tenho muitas
> dúvidas...
>
>
> >Para isso é preciso 'emular' a lógica
> >dentro da aritmética, um processo um pouco
> trabalhoso.
>
> Vou dar uma olhada no livro de Gödel para tentar
> entender como isso é feito... parece interessante.
>
> []s
> Ronaldo L. Alonso
>
>
_________________________________________________________
> Voce quer um iGMail protegido contra vírus e spams?
> Clique aqui: http://www.igmailseguro.ig.com.br
> Ofertas imperdíveis! Link:
> http://www.americanas.com.br/ig/
>
>
=========================================================================
> Instruções para entrar na lista, sair da lista e
> usar a lista em
> http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
>
=========================================================================
______________________________________________________________________
Yahoo! Mail - O melhor e-mail do Brasil! Abra sua conta agora:
http://br.yahoo.com/info/mail.html
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================