TOEVAL

Op het gebied van de algoritmische informatietheorie is de geschiedenis van wie-ontdekte-wat-waar-en-wanneer aan verhitte strijd en onjuiste informatie onderhevig. Vandaar dat ik hierbij enkele historische data en personen wil geven, als aanvulling op het interessante artikel van Rob van den Berg 'De wurgende omstrengeling van het toeval' (W&O, 5 juli) over het wiskundige begrip algoritmische complexiteit (ook wel Kolmogorov-complexiteit).

Het begrip Kolmogorov-complexiteit werd reeds in 1960 ontdekt door Ray Solomonoff in Cambridge (Massachusetts) als nevenproduct van het ontwikkelen van een universele machinale predictie- en leermethode. Marvin Minsky, de bekende goeroe van de Artificial Intelligence, verwees al in 1961 naar Solomonoffs werk. Solomonoff zelf publiceerde in 1964. Begin 1965 werd het begrip in meer precieze vorm opnieuw en onafhankelijk gepubliceerd door de grote wiskundige Andrei N. Kolmogorov in verband met het ontwikkelen van een formele definitie voor de informatie-inhoud en randomness van een individueel object.

Kolmogorov, die in de jaren dertig de waarschijnlijkheidsrekening grondvestte op de naar hem genoemde axioma's, wordt universeel beschouwd als Ruslands (en een van 's werelds) grootste wiskundigen van deze eeuw. Er zijn dan ook veel wiskundige begrippen en theorieën naar hem genoemd. G.J. Chaitin publiceerde het begrip voor de derde maal in twee artikelen in 1966 en 1969. Hij diende deze artikelen al eind 1965 ter publicatie in, toen hij student was aan het City College van de City University of New York. Hij was 18 jaar oud, en niet 15 zoals het W&O-artikel stelt. En Kolmogorov en Chaitin waren ook geen landgenoten.

Géén van de ontdekkers was in staat het verband aan te tonen tussen Kolmogorov-complexiteit en een formeel begrip van randomness (toevalligheid). Dit werd gedaan door de Zweedse wiskundige Per Martin-Loef, die in 1964-1965 een postdoctoraal jaar vervulde bij Kolmogorov in Moskou en deze 40 jaar oude kwestie oploste in termen van Kolmogorov-complexiteit. (Chaitin verwijst in zijn eerste artikelen naar Kolmogorovs en Martin-Loefs artikelen, die daar dus aan voorafgingen.)

Chaitin heeft de afgelopen jaren zeker de meeste publiciteit gegenereerd, maar hij heeft even zeker niet het vakgebied het meest vooruitgeholpen, zoals het W&O-artikel stelt. Oostblok-onderzoekers als L.A. Levin, P. Gacs, Ja. Barzdins, V.V.

Vyugin en anderen hebben veel meer gedaan en/of dezelfde resultaten eerder gepubliceerd, onder andere de in het W&O-artikel aan Chaitin toegeschreven versie van de Onvolledigheidsstelling van Gödel.