A gente tem que tomar muito cuidado com esses resultados de indecidibilidade e incompletude, porque frequentemente seu alcance é exagerado ou confundido. Por exemplo: o segundo teorema de incompletude de Gödel diz que (slight handwaving...) se PA é consistente, então a sentença de Gödel que diz da sua consistência não pode nem ser provada nem desprovada.
Ora, em 1995 Ken Kunen publicou um algoritmo que, trivialmente, prova Consis PA. Vou repetir: ***Um algoritmo que prova Consis PA***. Como pode? Outra coisa: é trivial (menos, menos, mas quase...) mostrar que, dado um conjunto finito de instâncias sendo investigadas para o Problema da Parada, ***existe*** um algoritmo que as decide. (Ênfase no ***existe***.) Mais complicado (mas factível) é explicitar tal (tais) algoritmo(s). Cumé qui podi??? ;-)))))
_______________________________________________ Logica-l mailing list [email protected] http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
