, KS(xjy) qui code x, c'est--a-dire tel que hx ? y i = x. Soit la machine pr eexe P qui sur une entr ee hxx htt y ii lit exactement t bits de x et fait le calcul de hx 1 : : : x t y i. Cette machine est une machine pr eexe, qui calcule x sur l'entr ee hx ? hKS(xjy) y ii. D'apr es le th eor eme fondamental, KS(xjy) > KP(xjKS(xjy) y ):s o i tx ? un mot dont la longueur est
, KS(xjy) > minfii KP(xjii y) 6 ig : A v ec le r esultat pr ec edent, on a montr e que KP(xjKS(x) y ) 6 KS(xjy) + O(1). Donc KS(xjy) e s t dans l'ensemble des fii KP
, xjii y) 6 i, a l o r s KS(xjy) 6 i + O(1). C'est suusant pour la preuve. Soit x ?(i) le plus petit programme pour la description pr eexe de x sachant i et y. P ar hypoth ese, l(x ?(i) ) n ; f(n) est major e par 2 n;f(n) , donc la mesure de V m est major ee par 2 ;f(n) , ce qui est bien plus petit que 2, KS(xjy) 6 minfii KP(xjii y) 6 ig : la premi ere etape est de prouver que si KP
Il existe une constante positive c telle que KS(! 1:n ) > n;c pour une innnit e d e n si et seulement si il existe une constante positive c telle que KL(! 1:n ) > n ,
, Si il existe une constante c telle que KS(! 1:n ) > n;c pour une innnit e de n, a l o r s ! est
, L'ensemble des ! 2 , tel qu'il existe c et une innnit e d e n tel que KS(! 1:n ) > n
,
, :n ) > n ; c. Le sens de l'implication est le seul a prouver, l'autre d ecoulant de la proposition 3. On utilise une m ethode de padding. O n c herche une description de l'objet, et on se sert de 0 exc edentaires pour coder d'autres informations. Un description de ! 1:n peut ^ etre une description optimale du plus petit programme x ? d ecrivant ! 1:n sachant n, Ce petit lemme permet en fait de renforcer les enonc es suivants on utilisera alors dans la preuve la condition KL, vol.1
, 1:n ) par c + c 1 + 2 l(n ; KS(! 1:n jn)) pour tous les n tels que KS(! 1:n ) > n ; c. On a donc A 6 c + c 1 + 2 l(A)
, Un -test s equentiel universel est d eeni par une fonction approximable par au-dessous . Il est alors facile de voir que pour = la mesure de Lebesgue
Information and Randomness, an Algorithmic Perspective, 1993. ,
A theory of program size formally identical to information theory, J. Assoc. Comput. Mach, vol.22, pp.329-340, 1975. ,
On the symmetry of algorithmic information, Soviet Math. Dokl, vol.15, pp.1477-1480, 1974. ,
Komplexitt at und Zuff alligkeit, J.W. Goethe Universitt at, 1978. ,
Information Theory and Reliable Communication. W iley, 1968. ,
Laws of information conservation (non-growth) and aspects of the foundation of probability theory, Soviet Math. Dokl, vol.10, pp.206-210, 1974. ,
Various measures of complexity for nite objects (axiomatic description), Soviet Math. Dokl, vol.17, pp.522-526, 1976. ,
An Introduction to Kolmogorov Complexity and its Applications, 1993. ,
The deenition of random sequences, Inform. Contr, vol.9, pp.602-619, 1966. ,
Complexity oscillations in innnite binary sequences, vol.19, pp.223-230, 1971. ,
Mathematical metaphysics of randomness, Institute of New Technologies, 1996. ,
The mathematical theory of communication, 279{423, 623{656, 1948. ,
Kolmogorov complexity: Recent research i n m o s c o w, MFCS'96, 1996. ,
Can an individual sequence of zeros and ones be random?, Russian Math. Surveys, vol.25, issue.1, pp.121-189, 1990. ,
Relations between varieties of Kolmogorov complexities, 1993. ,
Relations between varieties of Kolmogorov complexities, Mathematical Systems Theory, pp.271-291, 1993. ,
Kolmogorov Complexity and Computational Complexity, 1992. ,
The complexity of nite objects and the development of the concepts of information and randomness by means of the theory of algorithms, Russian Math. Surveys, vol.25, issue.6, pp.83-124, 1970. ,