, 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

!. Soit, 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

. Preuve,

, :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

C. Calude, Information and Randomness, an Algorithmic Perspective, 1993.

G. J. Chaitin, A theory of program size formally identical to information theory, J. Assoc. Comput. Mach, vol.22, pp.329-340, 1975.

P. Acs, On the symmetry of algorithmic information, Soviet Math. Dokl, vol.15, pp.1477-1480, 1974.

P. Acs, Komplexitt at und Zuff alligkeit, J.W. Goethe Universitt at, 1978.

R. G. Gallager, Information Theory and Reliable Communication. W iley, 1968.

L. A. Levin, Laws of information conservation (non-growth) and aspects of the foundation of probability theory, Soviet Math. Dokl, vol.10, pp.206-210, 1974.

L. A. Levin, Various measures of complexity for nite objects (axiomatic description), Soviet Math. Dokl, vol.17, pp.522-526, 1976.

M. Li and P. , An Introduction to Kolmogorov Complexity and its Applications, 1993.

P. and M. Of, The deenition of random sequences, Inform. Contr, vol.9, pp.602-619, 1966.

P. and M. Of, Complexity oscillations in innnite binary sequences, vol.19, pp.223-230, 1971.

A. A. Muchnik, A. L. Semenov, and V. A. Uspensky, Mathematical metaphysics of randomness, Institute of New Technologies, 1996.

C. E. Shannon, The mathematical theory of communication, 279{423, 623{656, 1948.

V. A. Uspensky, Kolmogorov complexity: Recent research i n m o s c o w, MFCS'96, 1996.

V. A. Uspensky, A. L. Semenov, A. Kh, and . Shen, Can an individual sequence of zeros and ones be random?, Russian Math. Surveys, vol.25, issue.1, pp.121-189, 1990.

V. A. Uspensky, A. Kh, and . Shen, Relations between varieties of Kolmogorov complexities, 1993.

V. A. Uspensky, A. Kh, and . Shen, Relations between varieties of Kolmogorov complexities, Mathematical Systems Theory, pp.271-291, 1993.

O. Watanabe, Kolmogorov Complexity and Computational Complexity, 1992.

A. K. Zvonkin and L. A. Levin, 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.