Re: Re: [obm-l] Re: [obm-l] Provadores autom�ticos de Teorema

[Chicao Valadares <chicaovaladares@xxxxxxxxxxxx>]

adendo.....

> >O PROCEDIMENTO existe, por�m ele N�O P�RA
> > (problema
> > da parada da m�quina de Turing), da� ele n�o � um
> > ALGORITMO
> > geral para provar inconsist�ncia.  
> > O exemplo abaixo mostra isso ...
> 
> Agora fiquei na duvida entre o NAO PARAR e o NAO 
> EXISTIR pois:
> No exemplo,voce ja esta supondo que tal procedimento
> existe...
> Supondo, como vc,que tal procedimento
> existe,chamando
> tal procedimento de halt(Programa : w ) que recebe
> um
> programa como entrada, � facil construir um novo
> programa(PBugado) totalmente inconsistente...
> 
> PBugado(Programa : x){
> IF(Halt(x) == TRUE)
> THEN While(TRUE);
> ELSE Exit(); 
> }
> 
> Basta fazer a chamada  PBugado(Pbugado), a tao
> famosa
> autoreferencia... e observar que se PBugado
> parar(Halt
> vai acusar true) entao PBugado entra  em loop
> infinito
> que j� � uma contradi�ao...
> Se ele nao parar(vai para o ELSE) entao ele vai para
> instru�ao Exit() o que indica que ele vai parar, ou
> seja tambem � uma contradi�ao... 
> Portanto a suposi�ao de que Halt existe leva a uma
> contradi�ao..portanto ele nao existe....
> Correto???Errado??Ele EXISTE OU NAO EXISTE???
> acredito que o wikipedia ajude :
> http://en.wikipedia.org/wiki/Halting_problem

Busquei sobre indecibilidade em v�rios lugares p/
tirar essa d�vida(nao vou citar aqui � s� fazer a
busca por indecibilidade no google) e al�m do
wikipedia teve muitos outros lugares como em
http://www.ics.uci.edu/~eppstein/161/960312.html
(apesar de falar em numeros, � tudo equivalente)
que nao deixavam d�vidas em rela�ao a existencia do
procedimento...� uma questao at� de logica da prova
mesmo...se halt existe entao chegamos num absurdo,
logo halt nao existe.....observe que no meu exemplo, o
algoritmo nao p�ra assim como o seu :)

Valeu....

"O Bin�mio de Newton � t�o belo como a V�nus de Milo.
O que h� � pouca gente para dar por isso... "
Fernando Pessoa - Poesias de Alvaro Campos

_________________________________________________________________
As informa��es existentes nessa mensagem e no(s) arquivo(s) anexado(s) 
s�o
para uso restrito, sendo seu sigilo protegido por lei. Caso n�o seja
destinat�rio, saiba que leitura, divulga��o ou c�pia s�o proibidas. 
Favor
apagar as informa��es e notificar o remetente. O uso impr�prio ser� 
tratado
conforme as normas da empresa e a legisla��o em vigor. Agradecemos sua
colabora��o.


The information mentioned in this message and in the archives attached 
are
of restricted use, and its privacy is protected by law. If you are not 
the
addressee, be aware that reading, disclosure or copy are forbidden. 
Please
delete this information and notify the sender. Inappropriate use will 
be
tracted according to company's rules and valid laws. Thank you for your
cooperation.

__________________________________________________
Converse com seus amigos em tempo real com o Yahoo! Messenger 
http://br.download.yahoo.com/messenger/ 
=========================================================================
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
=========================================================================