Title: Arcane Information, Solving Relations, and Church Censorship

Speaker: Leonid A. Levin

Affiliations: Boston University, University of Heidelberg, Humboldt Foundation

Abstract:
The Church-Turing Thesis fails for problems that allow multiple answers:
many easily solvable problems allow only non-recursive solutions.
Its corrected version is: Physical and Mathematical Sequences Have
Little Common Information. This requires extending Kolmogorov's concept
of mutual information to infinite strings. This is tricky; the talk will
survey these and other related issues. Related Information can found at:
http://arxiv.org/abs/cs.CC/0203029.