There appears to be a loophole in Goedel Incompleteness Theorem. 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.) Similar problems and answers apply to other unsolvability results for tasks where required solutions are not unique, such as, 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 (apparently, never accepted by Hilbert). Its mathematical essence is the lack of total recursive extensions of universal partial recursive predicate.

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 r.e. sets of axioms cannot complete PA, the possibility of completion by other simple means remained open. In fact, it is easy to construct an r.e. theory R that, like PA, allows no consistent completion with r.e. axiom sets. Yet, it allows a recursive set of PAIRS of axioms such that random choice of one in each pair assures such completion with probability 99%.

The reference to randomized algorithms seems rather special. 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 laws: 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 the Hilbert-Goedel task of a consistent completion of a formal system is really possible for PA, as it is for an 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.