è 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. --- [EMAIL PROTECTED] 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 =========================================================================