, préfixe ou non) est en revanche inadaptée pour caratériser l'aléatoire au sens de Schnorr. Ainsi, il existe des réels Schnorr aléatoires (pour la mesure de Lebesgue) dont l'expansion binaire a une complexité de Kolmogorov très petite, tandis que certains réels ont une expansion binaire de complexité de Kolmogorov préfixe quasi-maximale mais ne sont pas Schnorr-aléatoires
, Caractérisation de l'aléatoire par les jeux : imprédictibilité et stochasticité, Thèse de doctorat, 2008.
, On the Length of Programs for Computing Finite Binary Sequences, Journal of the ACM, vol.13, issue.4, pp.547-569, 1966.
DOI : 10.1145/321356.321363
, A Theory of Program Size Formally Identical to Information Theory, Journal of the ACM, vol.22, issue.3, pp.329-340, 1975.
DOI : 10.1145/321892.321894
, Algorithmic randomness and complexity. Springer, to appear. [For09] Lance Fortnow Computational complexity blog : A Kolmogorov complexity proof of the Lovász local lemma, 2009.
, Is randomness native to computer science ? Current Trends in Theoretical Computer Science, pp.141-179, 2004.
, Calculabilité, aléatoire et théorie ergodique sur les espaces métriques, Thèse de doctorat, 2008.
, An introduction to Kolmogorov complexity and its applications. Texts in Computer Science, 2008.
, The definition of random sequences, Information and Control, vol.9, issue.6, pp.602-619, 1966.
DOI : 10.1016/S0019-9958(66)80018-9
, A constructive proof of the Lov??sz local lemma, Proceedings of the 41st annual ACM symposium on Symposium on theory of computing, STOC '09, pp.343-350, 2009.
DOI : 10.1145/1536414.1536462
, Computability and randomness. Oxford Logic Guides, 2009.
, Randomness and ergodic theory : an algorithmic point of view, Thèse de doctorat, 2008.
, A formal theory of inductive inference. Part I, Information and Control, vol.7, issue.1, pp.1-22, 1964.
DOI : 10.1016/S0019-9958(64)90223-2
, Etude critique de la notion de collectif. Gauthiers-Villars, 1939.