Outro problema que tem é que o conjunto das máquinas polinomiais varia, de teoria em teoria. E ele usa um construtivismo radical, baseado em máquinas polinomiais.
2011/9/29 Francisco Antonio Doria <[email protected]> > Sim! No caso do Kunen, o algoritmo é todo primitivo recursivo, exceto numa > passagem que corresponde à indução transfinita. E que é simplesmente o uso > de uma função não p.r. Muito interessante. > > > 2011/9/29 Rodrigo Freire <[email protected]> > >> Obrigado, mas a análise não é só minha. O Terence Tao já viu isso antes, e >> eu identifiquei o problema junto com um colega (que já escreveu para o >> Nelson). >> >> Não conheço especificamente o algoritmo do Kunen, mas conheço outro >> algoritmo para a mesma coisa (a consistência de Peano). >> Esses algoritmos não são primitivos recursivos. >> >> Mas tudo bem, não importa. A afirmação do Nelson não é que alguma teoria T >> não prova que uma função primitiva recursiva é total. Isso de fato existe, >> teorias mais fracas que PRA. A afirmação do Nelson é que superexponenciação >> não é total, e não apenas que alguma teoria não prova isso. É essa afirmação >> mais forte que não sei o que quer dizer. >> >> A propósito, para localizar bem o erro do Nelson no livro: >> >> página 37, linha 8 de baixo para cima. O que segue sobre o \mu está >> errado. Em particular, está errado que \mu >= l_1, que seria a contradição. >> >> >> Abraço >> Rodrigo >> >> >> >> >> >> >> 2011/9/28 Francisco Antonio Doria <[email protected]> >> >>> Gostei da tua análise; te cumprimento por ela, mas tem um ponto de que >>> discordo: >>> >>> *não acho que exista a mais remota possibilidade de >>> Nelson ter provado o que ele afirma, que alguma função primitiva >>> recursiva >>> não é total. Afinal, o que faz o algoritmo que calcula a função em termos >>> dos valores anteriores? * >>> >>> O que a gente vê intuitivamente, nesse caso ou em casos similares, não é >>> necessariamente o que se prova. Vc conhece o algoritmo de Kunen para provar >>> Paris-Harrington? A gente vê que o algoritmo converge, mas PA não... >>> >>> 2011/9/28 Rodrigo Freire <[email protected]> >>> >>>> Li, junto com um colega, uma parte do manuscrito do Nelson. >>>> Identificamos o >>>> erro que o Terence Tao apontou: no livro ocorre na página 37 na parte de >>>> aritmetização do teorema de Chaitin e da prova de Kritchman e Raz. >>>> >>>> O problema é que a cada subteoria de Q* corresponde um l diferente na >>>> aritmetização do teorema de Chaitin, e o Nelson está usando sempre o >>>> mesmo l >>>> da teoria Q*. >>>> >>>> A descrição de Nelson da sua construção na seção "The plan" usa apenas >>>> resultados conhecidos de lógica e generalidades de teoria da >>>> complexidade. >>>> Ele poderia tentar mostrar como fica a construção se substituir PRA por >>>> ZFC >>>> e Q por PA, o que facilitaria bastante a codificação. Afinal, é um >>>> corolário >>>> do que ele propõe (e um corolário bem mais modesto) que ZFC provaria que >>>> PA >>>> é inconsistente. Ele tenta usar o fato que Q* prova a consistência de >>>> suas >>>> subteorias finitas para tentar tirar alguma inconsistência. PA e ZFC >>>> provam >>>> que suas subteorias finitas são consistentes, a construção parece não >>>> ter >>>> nada de especial em relação a Q*. Além disso ele usa que PRA prova a >>>> consistência de Q. Claro que ZFC também prova a consistencia de PA. Acho >>>> que >>>> seria útil ver nesse caso "modesto" como fica a prova. >>>> >>>> Para deixar bem claro, não acho que exista a mais remota possibilidade >>>> de >>>> Nelson ter provado o que ele afirma, que alguma função primitiva >>>> recursiva >>>> não é total. Afinal, o que faz o algoritmo que calcula a função em >>>> termos >>>> dos valores anteriores? Essa afirmação não me parece inteligível. >>>> >>>> Obs: Vi que o Nelson escreveu na lista fom, supostamente respondendo o >>>> comentário do Terence Tao. Não acho que ele tenha respondido >>>> satisfatoriamente. Parece que o Terence Tao não se expressou muito bem >>>> falando de "complexidade da teoria", o que Nelson diz que não está >>>> definido. >>>> No entanto, parece claro que Tao se referia ao l que é um para cada >>>> teoria. >>>> >>>> Abraço >>>> Rodrigo >>>> _______________________________________________ >>>> Logica-l mailing list >>>> [email protected] >>>> http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l >>>> >>> >>> >>> >>> -- >>> fad >>> >>> ahhata alati, awienta Wilushati >>> >>> >> > > > -- > fad > > ahhata alati, awienta Wilushati > > -- fad ahhata alati, awienta Wilushati _______________________________________________ Logica-l mailing list [email protected] http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
