Tem uma construção devida a Post (1944) que mostra como da indecidibilidade passamos à incompletude. Sempre me pareceu que indecidibilidade é o fenômeno mais básico, já que a obtemos num ambiente informal, por assim dizer, e o caminho contrário, a passagem da incompletude à indecidibilidade, requer algumas suposições extra.
Newton e eu procuramos a indecidibilidade aos sistemas caóticos, e isto decorre, quase imediatamente, para sistemas ergódicos, das construções de Richardson. Tentando fazer uma coisa mais geral, batemos nalgo que parecia impossível, uma expressão razoavelmente simples para a Halting Function na linguagem do cálculo. (A expressão é simples, mas deu o maior trabalho chegar lá.) Depois construimos expressões similares para infinitos graus de insolvabilidade, de modo a podermos tirar daí um teorema tipo Rice muito poderoso. Algo como (sem tecnicalidades): - Seja uma linguagem formal, ``clássica'' (whatever that might mean) que inclua ``bastante aritmética.'' Então se P é um predicado não trivial (existem x, y, x≠y tais que provamos P(x) e não-P(y)) para z qualquer no domínio de P, não há algoritmo geral que decida P(z). A dificuldade pode ser tão alta como quisermos. Estes resultados têm um caráter, digamos, absoluto, pois independem de sistemas axiomáticos, já que podemos fazer tudo na matemática intuitiva. O teorema de Tsuji é um corolário do resultado supra. -- fad ahhata alati, awienta Wilushati _______________________________________________ Logica-l mailing list Logica-l@dimap.ufrn.br http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
