SAVOIRS
Complexité de Kolmogorov
Charles Henry Bennett
(né en 1943).
so rte de « te mps de décompress io n »
car le prog ramme minim al est la fo rme
comprimée la meilleure de l' objet numéri sé, e t exéc ute r ce progra mme mini -
ma l c'est décompresse r l'in fo rmat io n
compressée de ma niè re ex trê me da ns
le prog ramm e minim a l. Ce te mps de
ca lcu 1, Be nn e tt l'a ppe ll e profondeur
logique de l'obje t numé riqu e.
La profondeur logique de Bennett n'a été
proposée que dans les années l 980 , car
l' idée la plu s te nta nte po ur définir le
contenu en calcul d' un objet est de mimer
la définiti o n de la compl ex ité de Ko lmogoro v e t do nc de définir le conte nu
e n calcul d ' un obje t numé rique comme
« le temps de calcul du programme le plus
rapide capable de produire l'objet numériqu e ». Ce tte définiti o n na ture ll e ne
marc he pas : e n effet , ce te mps minimal de calcul est to ujo urs do nné par le
prog ramme« imprime r Ob » o ù Ob est
l'obje t numé ri sé auque l o n s' inté resse.
Cette remarque est d 'ailleurs bie n connue
des prog ramme urs, qui save nt tous que
le programme le plus ra pide pour o btenir les vingt pre miè res décima les de n
est le programme
« imprime r 14 159265358979323846 » .
La définiti o n nature ll e du conte nu e n
calc ul pa r le te mps minim al de calcul
d ' un objet n 'a do nc pas de sens et ne
mesure rien . C'est cette di fficulté d ' une
définiti o n te ntante mais ino pérante que
Be nnett a surmontée e n fa isant réfé rence
au programme minimal. Sa définiti o n ,
qu ' il ne faut pas confo ndre avec celle envisagée e n te rmes de progra mme « le plus
ra pide » , est vra ime nt q ue le contenu en
ca lc ul (o u profo nd e ur log iqu e) d'u n
o bjet numé rique O b do it être co nsidé ré
co mme « le tem ps de ca lc ul d u programme minimal (en taill e) de Ob » . Un
o bjet « profond » ,c ' est-à-d ire aya nt une
grande profonde ur log ique, est un objet
do nt l'o ri g ine la plu s probab le es t un
lo ng ca lc ul. C'est un objet qui conti e nt
des redo nda nces parfo is profo ndément
cachées. Po ur teste r s i la défi niti on de
Be nne tt corres po nd bi e n à notre atte nte
intuiti ve, co nsidéro ns di vers exe mples.
Un bloc de cristal possède clairement une
fa ibl e compl ex ité a léato ire (pui squ ' il
n'est pas du tout aléatoire !) et une fa ible
co mpl ex ité e n o rga ni sati o n (pui squ e
son o rgani sati o n est une s imple répétiti o n). En utili sa nt les défi niti o ns fo rme ll es, o n constate que, confo rm é me nt
à cette intuiti o n , la compl ex ité de Kolmogorov est petite puisque le programme
minima l po ur décrire la vers io n numéri sée du bl oc de c ri stal est court , et que
sa profo nde ur log ique a uss i est petite ,
pui sque le progra mme minim al est un
progra mme d ' itérati o ns é lé me nta ires
du ge nre « mill e fo is de suite, re produire le moti f de base du c ri sta l » , qui
' exécute ra pide me nt.
Comme de uxiè me exemple, preno ns un
litre de gaz (s upposé numé ri sé avec une
préc isio n de l' o rdre du milli o niè me de
millimètre par exemple). C'est un o bjet
qui possède une très grande complex ité
a léato ire . Les mo léc ul es du gaz sont
ré pa11ies au hasard , o n ne pe ut ri e n fa ire
de mi e ux po ur déc rire le litre de gaz
qu ' utiliser un programme du type « imprime r Ob » . Il n 'y a pas o u très pe u de
racco urc is poss ibles dans la description.
La compl ex ité o rga ni sée est fa ibl e (le
programme minimal « imprimer Ob » ne
fa it pas de ca lcul s subtil s). À no uveau.
les définiti o ns mathé matiques s'accorTangente Hors-série n°52. Mathématiques & informatique
Complexité de Kolmogorov
Charles Henry Bennett
(né en 1943).
so rte de « te mps de décompress io n »
car le prog ramme minim al est la fo rme
comprimée la meilleure de l' objet numéri sé, e t exéc ute r ce progra mme mini -
ma l c'est décompresse r l'in fo rmat io n
compressée de ma niè re ex trê me da ns
le prog ramm e minim a l. Ce te mps de
ca lcu 1, Be nn e tt l'a ppe ll e profondeur
logique de l'obje t numé riqu e.
La profondeur logique de Bennett n'a été
proposée que dans les années l 980 , car
l' idée la plu s te nta nte po ur définir le
contenu en calcul d' un objet est de mimer
la définiti o n de la compl ex ité de Ko lmogoro v e t do nc de définir le conte nu
e n calcul d ' un obje t numé rique comme
« le temps de calcul du programme le plus
rapide capable de produire l'objet numériqu e ». Ce tte définiti o n na ture ll e ne
marc he pas : e n effet , ce te mps minimal de calcul est to ujo urs do nné par le
prog ramme« imprime r Ob » o ù Ob est
l'obje t numé ri sé auque l o n s' inté resse.
Cette remarque est d 'ailleurs bie n connue
des prog ramme urs, qui save nt tous que
le programme le plus ra pide pour o btenir les vingt pre miè res décima les de n
est le programme
« imprime r 14 159265358979323846 » .
La définiti o n nature ll e du conte nu e n
calc ul pa r le te mps minim al de calcul
d ' un objet n 'a do nc pas de sens et ne
mesure rien . C'est cette di fficulté d ' une
définiti o n te ntante mais ino pérante que
Be nnett a surmontée e n fa isant réfé rence
au programme minimal. Sa définiti o n ,
qu ' il ne faut pas confo ndre avec celle envisagée e n te rmes de progra mme « le plus
ra pide » , est vra ime nt q ue le contenu en
ca lc ul (o u profo nd e ur log iqu e) d'u n
o bjet numé rique O b do it être co nsidé ré
co mme « le tem ps de ca lc ul d u programme minimal (en taill e) de Ob » . Un
o bjet « profond » ,c ' est-à-d ire aya nt une
grande profonde ur log ique, est un objet
do nt l'o ri g ine la plu s probab le es t un
lo ng ca lc ul. C'est un objet qui conti e nt
des redo nda nces parfo is profo ndément
cachées. Po ur teste r s i la défi niti on de
Be nne tt corres po nd bi e n à notre atte nte
intuiti ve, co nsidéro ns di vers exe mples.
Un bloc de cristal possède clairement une
fa ibl e compl ex ité a léato ire (pui squ ' il
n'est pas du tout aléatoire !) et une fa ible
co mpl ex ité e n o rga ni sati o n (pui squ e
son o rgani sati o n est une s imple répétiti o n). En utili sa nt les défi niti o ns fo rme ll es, o n constate que, confo rm é me nt
à cette intuiti o n , la compl ex ité de Kolmogorov est petite puisque le programme
minima l po ur décrire la vers io n numéri sée du bl oc de c ri stal est court , et que
sa profo nde ur log ique a uss i est petite ,
pui sque le progra mme minim al est un
progra mme d ' itérati o ns é lé me nta ires
du ge nre « mill e fo is de suite, re produire le moti f de base du c ri sta l » , qui
' exécute ra pide me nt.
Comme de uxiè me exemple, preno ns un
litre de gaz (s upposé numé ri sé avec une
préc isio n de l' o rdre du milli o niè me de
millimètre par exemple). C'est un o bjet
qui possède une très grande complex ité
a léato ire . Les mo léc ul es du gaz sont
ré pa11ies au hasard , o n ne pe ut ri e n fa ire
de mi e ux po ur déc rire le litre de gaz
qu ' utiliser un programme du type « imprime r Ob » . Il n 'y a pas o u très pe u de
racco urc is poss ibles dans la description.
La compl ex ité o rga ni sée est fa ibl e (le
programme minimal « imprimer Ob » ne
fa it pas de ca lcul s subtil s). À no uveau.
les définiti o ns mathé matiques s'accorTangente Hors-série n°52. Mathématiques & informatique