Ah, uma coisa: no teorema tipo Rice abaixo, até o domínio de P é indecidível.
On Tue, Feb 28, 2012 at 9:57 PM, Francisco Antonio Doria < famado...@gmail.com> wrote: > 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 > > -- 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
