We survey the Kolmogorov's approach to the notion of randomness through the Kolmogorov complexity theory. The original motivation of Kolmogorov was to give up a quantitative definition of information. In this theory, an object is randomness in the sense that it has a large information content. Afterwards, we present parts of the work of Martin-Lof, Schnorr, Chaitin and Levin which supply a mathematical notion of randomness throughout diverse theories from the the 60' up to recently.
Publié le : 2004-07-05
Classification:
Computer Science,
Information Theory,
Kolmogorov Complexity,
Randomness,
Logic,
[MATH.MATH-LO]Mathematics [math]/Logic [math.LO],
[INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO],
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]
@article{hal-00201576,
author = {Ferbus-Zanda, Marie and Grigorieff, Serge},
title = {Is Randomness "Native" to Computer Science?},
journal = {HAL},
volume = {2004},
number = {0},
year = {2004},
language = {en},
url = {http://dml.mathdoc.fr/item/hal-00201576}
}
Ferbus-Zanda, Marie; Grigorieff, Serge. Is Randomness "Native" to Computer Science?. HAL, Tome 2004 (2004) no. 0, . http://gdmltest.u-ga.fr/item/hal-00201576/