b. 1944
Paul Vitányi is a Dutch computer scientist at CWI Amsterdam best known for co-authoring, with Ming Li, the definitive textbook on Kolmogorov complexity and algorithmic information theory. His research explores the mathematical foundations of information, randomness, and computation, with significant implications for philosophy of mathematics and the limits of formal systems. He has contributed to debates on the nature of a priori knowledge by situating classical logical results within a computational framework.
Co-authored 'An Introduction to Kolmogorov Complexity and Its Applications' (with Ming Li), the standard reference in the field
Co-developed the normalized compression distance (NCD) as a parameter-free similarity metric
Extended Kolmogorov complexity to quantum information theory
Applied minimum description length (MDL) principles to machine learning and statistical inference
Contributed formal analysis connecting computational undecidability and Gödelian incompleteness
The semantics of a formal system rich enough to contain elementary mathematics cannot be fully defined in terms of mathematical functions within that same system.
claimThere is a fundamental tension between treating logical knowledge as a priori and the computational intractability of deciding logical validity.