---------- Forwarded message ---------- From: Francisco Antonio Doria <famado...@gmail.com> Date: Tue, Feb 28, 2012 at 10:18 PM Subject: Re: [Logica-l] Sobre alguns teoremas de indecidibilidade e incompletude To: Décio Krause <deciokra...@gmail.com>
Teoria informal como p.e. no livro do Rogers - não dá pra fazer teoria da computação em linguagens recursivas. On Tue, Feb 28, 2012 at 10:15 PM, Décio Krause <deciokra...@gmail.com>wrote: > Sim, Dória, independente de sistemas axiomáticos em particular, mas sim de > que sua linguagem seja recursiva, etc, como nas condições do teorema de > Gödel. Assim, concordo que, independentemene se uma formulação particular, > o seu resultado se aplique, mas as condições do Teorema devem ser > cumpridas. Está errado isso? Em uma "teoria" informal, nem sabemos direito > qual a sua linguagem, regras de formação, etc. Como aplicar o teorema? > Seria bacana, pelo menos para min, esclarecer isso. > Abraços > D > > > > ------------------------------------------------------ > Décio Krause > Departamento de Filosofia > Universidade Federal de Santa Catarina > 88040-900 Florianópolis - SC - Brasil > http://www.cfh.ufsc.br/~dkrause > ------------------------------------------------------ > > Em 28/02/2012, às 21:57, Francisco Antonio Doria <famado...@gmail.com> > escreveu: > > > 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 > -- 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
