HackerPapers

arXiv:chao-dyn/9407009nlin.CD

The Limits of Mathematics---Fourth Version

G. J. Chaitin

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

Abstract

This is yet another version of the course notes in chao-dyn/9407003. Here we use m-expressions more aggressively to further reduce the constants in our information-theoretic incompleteness theorems. Our main theorems are: 1) an N-bit formal axiomatic system cannot enable one to exhibit any specific object with program-size complexity greater than N+c, 2) an N-bit formal axiomatic system cannot enable one to determine more than N+c' scattered bits of the halting probability Omega. In chao-dyn/9407003, c = 2359 bits and c' = 7581 bits. In chao-dyn/9407005, c = 1127 bits and c' = 3689 bits. In chao-dyn/9407006, c = 994 bits and c' = 3192 bits. And in this version, c = 735 bits and c' = 2933 bits.

arXiv comments
231 pages, LaTeX, ignore numerous Overfull hbox too wide errors
Journal reference
DOI
Subjects
nlin.CDChaotic Dynamics

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Sep 2010 to Sep 2010.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. Book review: The Limits of Mathematics by Gregory Chaitin 1 comment

    • Chaitin’s website about the book, which seems to include the full contents (in HMTL format): http://www.cs.auckland.ac.nz/~chaitin/lm.html A PDF draft from 1994 at Arxiv: http://arxiv.org/abs/chao-dyn/9407009 Some other links about the book (putting these here to save people…

      jacobolusView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.