There appears to be a loophole in Goedel Incompleteness Theorem. It was 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.) I consider extensions U of the universal partial recursive predicate (or, say, Peano Arithmetic). I prove that any U either leaves unresolved an n-bit input (statement) 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 can be consistently extended to a complete theory. The question was somewhat vague since an obvious answer was "yes": just add to the axioms of Peano Arithmetic (PA) 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 lack 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, 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 a possibility. In fact, it is easy to construct an enumerable theory R that, like PA, allows no consistent completion with enumerable axiom sets. Yet, Barzdin, Jockusch, Soare showed that this theory (though not PA itself) allows a recursive set of PAIRS of axioms such that random choice of one in each pair assures such completion with probability 99%.
Of course, Goedel's remark envisioned more sophisticated ways to choose axioms :-). 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.