Alguma coisa tá complicada na comunicação. O que, em princípio, bloqueia algoritmos para resolver o problema da parada é que existem algoritmos parciais; algoritmos que entram em loop infinito.
Agora: cada caso onde o algoritmo diverge no modelo standard é dada por uma sentença ∏1. Logo, se PA for sound, ou PA prova essa sentença x, ou PA + x a prova, no caso trivialmente. A teoria PA + x é uma teoria que inclui os teoremas de PA, tem sua mesma linguagem, e a mesma ``força de prova.'' Não dá pra enumerar instâncias finitas, pois há algoritmos onde os pontos de divergência são em número infinito. 2009/6/5 Newton José Vieira <[email protected]> > Dória e amigos, > > Entendi perfeitamente que estava falando do problema da parada. > > Seja P um conjunto finito de programas e E um conjunto finito de entradas > possíveis para programas. Então o problema de determinar se o programa p > pára se sua entrada for x, para qualquer par (p,x) em P x E é *obviamente* > decidível: se P x E tem n elementos, existem 2^n tabelas de n respostas > sim/não, apenas uma delas com todas as respostas corretas e cada uma das > restantes 2^n-1 tabelas com alguma resposta incorreta. Assim, dos 2^n > algoritmos baseados no uso das tabelas para resolver o problema, apenas um é > correto; os outros 2^n-1 são incorretos. O algoritmo correto existe, mesmo > que não se saiba qual é. Costumo brincar com os alunos que o seguinte > problema é decidível (supondo que a resposta só possa ser sim ou não): *Deus > existe?* . Como ele tem apenas uma instância, existem 21=2 algoritmos: > A1: retorne sim. > A2: retorne não. > Embora não saibamos qual, um deles é o correto! > > Em resumo: qualquer problema de decisão constituído de um conjunto finito > de instâncias (incluindo qualquer subconjunto finito de instâncias do > problema da parada) é decidível. Ou seja, o fato de um subconjunto *finito* > de instâncias do problema da parada ser decidível não depende do fato de que > ele seja constituído de instâncias do *problema da parada*! > > Peço desculpas se não fui claro da outra vez ou se continuo sem entender o > que disse... > > Newton. > > Francisco Antonio Doria escreveu: > >> Não, é o halting problem, em ciência da computação, para meaquinas de >> Turing. Decidir onde há divergências é a questão. O teorema de Turing é: >> >> Para uma máquina de Turing qualquer, e um input arbitrário, não há um >> algoritmo geral que decida se a máquina para ou não. >> >> 2009/6/4 Newton José Vieira <[email protected] <mailto: >> [email protected]>> >> >> Prezado Dória, >> >> Tenho ficado encucado com o que disse, lendo e relendo para ver >> onde é que entendi errado... Para mim é óbvio que todo problema de >> decisão com conjunto finito de instâncias é decidível (se n é o >> número de instâncias, um algoritmo para o problema é aquele que >> consulta a tabela de respostas corretas dentre as 2^n tabelas >> possíveis). Você acha que isso é pouco percebido em geral ou quiz >> dizer alguma outra coisa? >> >> Newton. >> >> Francisco Antonio Doria escreveu: >> >> Não existe nenhum algoritmo capaz de resolver todas as >> instâncias do Problema da Parada, mas - fato pouco percebido - >> é que, dado um conjunto finito de tais instâncias, podemos >> nesse caso particular escrever sempre um algoritmo que resolva >> o problema específico. Não dá é para fazer um algoritmo >> global; entre outras coisas porque a complexidade >> computacional cresce sem limite. >> >> ------------------------------------------------------------------------ >> >> >> >> _______________________________________________ >> Logica-l mailing list >> [email protected] <mailto:[email protected]> >> http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l >> >> >> -- You don't really understand something if you only understand it >> in >> one way. >> Marvin Minsky >> >> >> > > -- > You don't really understand something if you only understand it in one way. > Marvin Minsky > >
_______________________________________________ Logica-l mailing list [email protected] http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
