[Busec] Colloquium: Leonid Levin - Wed Nov 16 11AM

Sharon Goldberg goldbe at cs.bu.edu
Tue Nov 8 22:41:28 EST 2011

Hi group,

I'm very excited to be hosting Leonid Levin's colloquium here at BU
next Wednesday, 11AM.  Abstract below. I hope to see all of you there!


               Colloquium: Wed, Nov. 16, 11am.
      BU-MCS, Hariri Institute, 111 Cummington St., 1st floor.

                 Leonid A. Levin, Boston University.
            Occam vs. Solomonoff, or Turing vs. Assange.

Our notion of computation changed dramatically. We never computed
on Turing machines, but even von Neumann model is losing touch.
 Our computations run on large networks, involving all sorts of users
with mismatched interests and many other hard-to-model factors. What
information cannot be generated by Turing Machines but can by Wikipedia?

Starting from a specific, though surprising, result (based on ideas
of Vereshchagin, Vitanyi, Betke, Samuel Epstein, extended by speaker),
I mention related earlier results and proceed to discuss the thesis they
all depend on: a revision of the computability concept (NOT model-based,
as I cannot model Wikipedia without (insulting or) amusing its editors :-)

First example: Inductive Inference (passive learning) extrapolates known
data to unknown domains. It has two popular (conflicting) philosophies:
 The Occam Razor (adhered to by Minimum Description Length community)
suggests focusing on the simplest objects consistent with known data.
 But Solomonoff and his followers take a probabilistic view: the
simplest objects EACH have the highest universal probability 2^{-K(x)},
but their combined universal probability may still be negligible
compared to the COMBINED probability of complicated objects in the set.

It turns out this could not happen, except as a purely mathematical
construction. Any finite set D that has combined probability of all its
members significantly (by >log factor) higher than universal probability
of its single simplest element, has high information about the Halting
Problem H (I call H "Turing's Password" :-). And there are NO WAYS
to generate D with significant Kolmogorov Information I(D:H) about H.

Another example concerns Goedel's belief that the Math community
can circumvent his incompleteness theorem by the informal process
of choosing consistently new axioms. One may be confused how to even
address such a vague hope. But it is refuted by proving that any
consistent extension of Peano Arithmetic that resolves all n-bit
questions has ~n bits of information about the Halting Problem.

More on-line in: http://arxiv.org/abs/1107.1458
and appendix of: http://arxiv.org/abs/cs/0203029

Host: Sharon Goldberg.

Sharon Goldberg
Computer Science, Boston University

More information about the Busec mailing list