Mathematisches Kolloquium

The Church-Turing Thesis tells which problems are solvable (with unlimited computing resources). Its standard formulation fails for problems with multiple allowed answers: many easily solvable problems have only non-recursive solutions. Its corrected version is: ``Sequences We Can Generate Have No Significant Mutual Information with Those We Can Define Mathematically.'' The catch is to say what is information. Extending Kolmogorov's mutual information concept to infinite sequences is tricky ! Details available on-line: http://arxiv.org/abs/cs.CC/0203029. (Earlier versions: FOCS-02; Bull.Symb.Logic 10/1, Symb.Logic Assoc. 2003 meeting plenary addresses.)

Donnerstag, den 18. November 2010 um 17:15 Uhr, in INF 288, HS 2 Donnerstag, den 18. November 2010 at 17:15, in INF 288, HS 2