2 papers
math.LO2013
The axiomatic power of Kolmogorov complexity
Laurent Bienvenu, Andrei Romashchenko, Alexander Shen +2
The famous Gödel incompleteness theorem states that for every consistent sufficiently rich formal theory T there exist true statements that are unprovable in T. Such statements wo…
cs.IT2011
Towards an axiomatic system for Kolmogorov complexity
Antoine Taveneaux
In [She82], it is shown that four basic functional properties are enough to characterize plain Kolmogorov complexity, hence obtaining an axiomatic characterization of this notion.…