Title: Arcane Information, Solving Relations, and Church Censorship
Speaker: Leonid A. Levin, Boston University, University of Heidelberg, Humboldt Foundation
Date: Wednesday, September 22, 2010 11:00-12:00pm
Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ
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.