Posso construir explicitamente um conjunto X infinito de máquinas obviamente polinomiais no modelo standard para a aritmética tal que a sentença ``X é um conjunto de máquinas polinomiais'' é indecidível em ZFC suposto consistente. Isso vale para qquer extensão recursiva consistente de ZFC.
Tem muitos outros exemplos similares. On Wed, Feb 29, 2012 at 4:23 PM, julio cesar <[email protected]>wrote: > *não dá pra fazer teoria da computação em linguagens recursivas* > > > Como assim ? Seria possível explicitar isso melhor? > > Abraços, > Júlio César A. Custódio > > > ---------- Forwarded message ---------- > From: Francisco Antonio Doria <[email protected]> > Date: Tue, Feb 28, 2012 at 10:18 PM > Subject: Re: [Logica-l] Sobre alguns teoremas de indecidibilidade e > incompletude > To: Décio Krause <[email protected]> > > > 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 <[email protected] > >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 > > ------------------------------------------------------ > _______________________________________________ > Logica-l mailing list > [email protected] > http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l > -- fad ahhata alati, awienta Wilushati _______________________________________________ Logica-l mailing list [email protected] http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
