Randomness & Complexity, from Leibniz to Chaitin

Por • 21 sep, 2018 • Sección: Leyes

Cristian S. Calude

During its history of more than 40 years, AIT knew a significant variation in terminology. In particular, the main measures of complexity studied in AIT were called Solomonoff-Kolmogorov-Chaitin complexity, Kolmogorov-Chaitin complexity, Kolmogorov complexity, Chaitin complexity, algorithmic complexity, program-size complexity, etc. Solovay’s handwritten notes [22]3 , introduced and used the terms Chaitin complexity and Chaitin machine.4 The book [21] promoted the name Kolmogorov complexity for both AIT and its main complexity.5 The main contribution shared by AIT founding fathers in the mid 1960s was the new type of complexity—which is invariant up to an additive constant—and, with it, a new way to reason about computation. Founding fathers’ subsequent contributions varied considerably. Solomonoff’s main interest and results are related to inductive inference, see [19]. Kolmogorov’s main contributions to AIT were mainly indirect6—through the works of his students, P. Martin-Lof, L. Levin, V. Uspenskij.7 Chaitin’s contributions—spanning over four decades—on plain and program-size complexity, algorithmic randomness (finite and infinite sequences), applications to Godel incompleteness, and concrete versions of AIT (hands-on programming), are central for the field. One can appreciate their lasting impact by inspecting the forthcoming monograph [17] which also includes the boom of results obtained in the last decade (due in part to the renaissance of Recursion Theory focussed on AIT)


Post to Twitter

Escribe un comentario