[Busec] Leonid Levin talk tomorrow 11AM in Hariri Institute

Sharon Goldberg goldbe at cs.bu.edu
Tue Nov 15 16:46:47 EST 2011

Hi All,

I'm very excited to be hosting Leonid Levin's talk tomorrow at 11AM.
Hope to see you all there! Abstract below.



             Colloquium: Wed. Nov. 16, 11am - 12pm
   Boston University, 111 Cummington St., MCS-180, Hariri Institute

              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 models like von Neumann's are losing touch.
Our computations run on large networks, involve all sorts of users with
mismatched interests, many other hard-to-model factors. What information
that Turing Machines cannot generate, Wikipedia can? What it cannot?

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 betting on the simplest environments 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 in 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.

An earlier 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

Sharon Goldberg
Computer Science, Boston University

More information about the Busec mailing list