ECCC-Report TR11-014https://eccc.weizmann.ac.il/report/2011/014Comments and Revisions published for TR11-014en-usThu, 31 Mar 2011 08:34:08 +0200
Revision 1
| Towards an axiomatic system for Kolmogorov complexity |
Antoine Taveneaux
https://eccc.weizmann.ac.il/report/2011/014#revision1In [She82], 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.
Thu, 31 Mar 2011 08:34:08 +0200https://eccc.weizmann.ac.il/report/2011/014#revision1
Paper TR11-014
| Towards an axiomatic system for Kolmogorov complexity |
Antoine Taveneaux
https://eccc.weizmann.ac.il/report/2011/014In \cite{shenpapier82}, 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.
Thu, 03 Feb 2011 15:23:42 +0200https://eccc.weizmann.ac.il/report/2011/014