Towards an axiomatic system for Kolmogorov complexity

Por • 4 feb, 2011 • Sección: Filosofía

Antoine Taveneaux

Abstract: In \cite{shenpaper82}, it is shown that four basic functional properties are enough to characterize plain Kolmogorov complexity, hence obtaining an axiomatic characterization of this notion. In this paper, we try to extend this work, both by looking at alternative axiomatic systems for plain complexity and by considering potential axiomatic systems for other types of complexity. First we show that the axiomatic system given by Shen cannot be weakened (at least in any natural way). We then give an analogue of Shen’s axiomatic system for conditional complexity. In a the second part of the paper, we look at prefix-free complexity and try to construct an axiomatic system for it. We show however that the natural analogues of Shen’s axiomatic systems fails to characterize prefix-free complexity. The Kolmogorov complexity concept have been introduced independently byKolmogorov (in [Kol65]) and Chaitin, the aim of the theory of Kolmogorov complexity is to quantify the amount of “information” contained in finite objects,such as binary strings. This idea can use to try to give an answer to the philosophical question “what does it mean for a single real number to be random?”Kolmogorov complexity theory has also had a key role in computability theory. The basic definition of Kolmogorov complexity involves Turing machines. However, most of the work done in computability theory use computable functions as the basic object, not Turing machines. Therefore, it would be interesting to give an axiomatic system characterizing Kolmogorov complexity only via its functional properties. This would give us another point of view on thisconcept and to get a better understanding of the fundamental properties for this notion. And of course, as with any axiomatic system, we want the axiomatic system to be minimal, i.e. to contain no superfluous axiom.

Post to Twitter

Etiquetado con: , , , , , , ,

Escribe un comentario