[Dmbu-l] BUCS Colloquium Speaker: Leonid Levin on Occam vs. Solomonoff, or Turing vs. Assange [Wednesday 11/16 @ 11:00 am in MCS 180, Hariri Institute Seminar Room] (fwd)

Evimaria Terzi evimaria at cs.bu.edu
Mon Nov 14 18:30:39 EST 2011

Hi all,

I would suggest that we go to this talk instead of having our regular DB 
meeting at 12. 


"Everything should be made as simple as possible, but no simpler"
(A. Einstein)

---------- Forwarded message ----------
Date: Mon, 14 Nov 2011 09:46:19 -0500
From: BU CS Colloquium <bucscolloquium at gmail.com>
To:  <colloq-l at cs.bu.edu>
Subject: BUCS Colloquium Speaker: Leonid Levin on Occam vs. Solomonoff,
    or Turing vs. Assange [Wednesday 11/16 @ 11:00 am in MCS 180,
    Hariri Institute Seminar Room]

Boston University -- Computer Science Department

*C O L L O Q U I U M*

Wednesday, November 16, 2011
11:00 AM - 12:30 PM
MCS 180
Hariri Institute Seminar Room

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

*Abstract*: 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

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:

*Host: *Sharon Goldberg

More information about the Dmbu-l mailing list