Forbidden Information. Leonid A. Levin.

[JACM, 60(2), 2013, . Earlier extended abstract appears in FOCS-2002 and also in abstracts of plenary talks of the 2003 annual meeting of Assoc. of Symbolic Logic. Below is a brief summary.]

Abstract: Goedel Incompleteness Theorem leaves open a way around it, vaguely perceived for a long time but not clearly identified. (Thus, Goedel believed informal arguments can answer any math question.) Closing this loophole does not seem obvious and involves Kolmogorov complexity. (This is unrelated to, well studied before, complexity quantifications of the usual Goedel effects.) Consider extensions U of the universal partial recursive predicate (or, say, Peano Arithmetic). I prove that any U either leaves an n-bit input (statement) unresolved or contains nearly all information about the n-bit prefix of any r.e. real (which is n bits for some r.e. reals). I argue that creating significant information about a SPECIFIC math sequence is impossible regardless of the methods used. Similar problems and answers apply to other unsolvability results for tasks allowing non-unique solutions, e.g. non-recursive tilings.

D.Hilbert asked if the formal arithmetic (PA: consisting of logic and algebraic axioms and an infinite family of Induction Axioms) can be consistently extended to a complete theory. The question was somewhat vague since an obvious answer was "yes": just add to PA axioms (assumed consistent) a maximal consistent set, clearly existing albeit hard to find. K.Goedel formalized this question as existence among such extensions of recursively enumerable ones and gave it a negative answer. Its mathematical essence is the absence of total recursive extensions of universal partial recursive predicate. This negative answer apparently was never accepted by Hilbert, and Goedel himself had reservations:

"Namely, it turns out that in the systematic establishment of the axioms of mathematics, new axioms, which do not follow by formal logic from those previously established, again and again become evident. It is not at all excluded by the negative results mentioned earlier that nevertheless every clearly posed mathematical yes-or-no question is solvable in this way. For it is just this becoming evident of more and more new axioms on the basis of the meaning of the primitive notions that a machine cannot imitate." (Goedel. 1961 "The modern development ...")

As is well known, [Barzdin 69, Jockusch, Soare 72], the absence of algorithmic solutions is no obstacle when the requirements do not make a solution unique. A notable example is generating strings of linear Kolmogorov complexity, e.g., those that cannot be compressed to half their length. Algorithms fail, but a set of dice does a perfect job! Thus, while enumerable sets of axioms cannot complete PA, completion by other realistic means remained an open possibility: one can so construct an enumerable theory R that, like PA, allows no consistent completion with enumerable axiom sets. Yet, R allows a recursive set of pairs of axioms such that random choice of one in each pair assures such completion with probability 99%. This cannot be done for PA itself. In fact, [Stephan 06] shows that any Martin-Lof random sequence that computes (i.e. allows computing from it) a consistent completion of PA also computes the Halting Problem H; and by [DeLeeuw, Moore, Shannon, Shapiro, 56], only a recursive sequence (which H is not) can be computed with a positive probability by randomized algorithms.

Of course, Goedel did not envision Math axioms to be chosen at random :-). But for arbitrary, not random, PA completions the reduction arguments do not work: only a recursive predicate can be computed from all consistent completions of PA.

However, the impossibility of a task can be formulated more generically. In 1965 Kolmogorov defined a concept of mutual Information in two finite strings. It can be refined and extended to infinite sequences, so that it satisfies conservation inequalities: cannot be increased by deterministic algorithms or in random processes or with any combinations of both. In fact, it seems reasonable to assume that no physically realizable process can increase information about a specific sequence.

In this framework one can ask if non-mechanical means could really enable the Hilbert-Goedel task of consistent completion for PA (as they do for the artificial system R just mentioned). A negative answer follows from the existence of a specific sequence that has infinite mutual information with ALL total extensions of a universal partial recursive predicate. It plays a role of a password: no substantial information about it can be guessed, no matter what methods are allowed. This "robust" version of Incompleteness Theorem is, however, trickier to prove than the old one.