Note the unusual time

-------------------------------------------------------------------------

                   B O S T O N   U N I V E R S I T Y
                      Computer Science Department
                          C O L L O Q U I U M
                     Wednesday, November 13, 11:00 AM
                       (Coffee served at 10:45 AM)
                         Seminar Room / MCS 135

                         Forbidden Information 

                            Leonid A. Levin
                           Boston University

There appears to be a loophole in Godel 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 Godel 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.Godel 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-Godel 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 Godel Theorem
is, however, trickier to prove than the old one.

Web Site: http://www.cs.bu.edu/fac/lnd/expo/gdl.html

Host: Steve Homer 

-------------------------------------------------------------------------
For colloquium info, including directions, see
http://www.cs.bu.edu/colloquium
-------------------------------------------------------------------------