SEMINAR: The Mysterious Thesis

Leonid Levin Boston University Presented by the Department of Computer Science and Engineering in cooperation with the Louisville Chapter of the IEEE Computer Society.
When Sep 21, 2018
from 03:00 PM to 05:00 PM
Where Duthie 117
Add event to calendarvCal

Gödel’s Incompleteness Theorem leaves open a way around it, vaguely perceived for a long time but not clearly identified. (Thus, Gödel believed informal arguments can answer any math question.) Closing this loophole does not seem obvious and involves Kolmogorov complexity. (This is unrelated to, well studied before, complexity quantifications of the usual Gödel effects.) Consider extensions U of the universal partial recursive predicate (or, say, Peano Arithmetic). I prove that any U either leaves an n-bit input (statement) unresolved or contains nearly all information about the n-bit prefix of any r.e. real (which is n bits for some r.e. reals). I argue that creating significant information about a SPECIFIC math sequence is impossible regardless of the methods used. I will discuss other implications of these extended Church-Turing Thesis for unsolvability issues of tasks that allow non-unique solutions.

Leonid Levin is known for his work in randomness in computing, algorithmic complexity and intractability, average-case complexity, foundations of mathematics and computer science, algorithmic probability, theory of computation, and information theory. He obtained his master's degree at Moscow University in 1970 where he studied under Andrey Kolmogorov, and his PhD from MIT in 1979. He and Stephen Cook independently discovered the existence of NP-complete problems.

Levin is a faculty at Boston University and a Fellow of The American Academy of Arts and Sciences. He worked at Moscow University, Inst. of Problems of Information Transmission of the Soviet Academy of Sciences, MIT, Berkeley, CalTech, Hebrew University, Inst. des Hautes Etudes Scientifiques (France), Heidelberg University (Germany). In recognition of his contribution to science he was awarded medals, prizes, fellowships, e.g., 2012 ACM/IEEE Knuth Prize, 2010 Humboldt Prize, 2004 Kolmogorov Medal, 2003 Outstanding Paper Prize of Soc. Industrial and Applied Math, 2001 Clay Math Inst. Fellowship, 1993 Guggenheim Fellowship, invited to address major forums, such as, e.g., the International Congress of Mathematicians, etc.