Information-theoretic Incompleteness

We propose an improved definition of the complexity of a formal axiomatic system: this is now taken to be the minimum size of a selfdelimiting program for enumerating the set of theorems of the formal system. Using this new definition, we show (a) that no formal system of complexity n can exhibit a specific object with complexity greater than n + c, and (b) that a formal system of complexity n can determine at most n + c scattered bits of the halting probability# .Wealsopresent a short, self-contained proof of (b)