ONT Forbidden Information
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
> Subj: New York Logic Colloquium - February
> Date: Mon, 3 Feb 2003 13:30:32 -0500
> From: Joel David Hamkins <...>
>
> New York Logic Colloquium
> A monthly event in logic at the CUNY Graduate Center, 365 Fifth Avenue
>
> http://nylogic.org/Colloquium
>
> Thursday, February 6, 2003 4:15 pm GC 9206 (Joint talk with GC CS Colloquium)
> Professor Leonid Levin (Boston University)
> Forbidden Information
>
> Abstract. 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.
>
> The talk will be followed by a wine and cheese reception.
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o