SAVOIRS
par Jean-Paul Delahaye
Complexité de Kolmogorou
et profondeur logique de Bennett
Pour mesurer la complexité d 'un objet numérique, s elon que
l'on considère son contenu en informations, ou son contenu
en structures, deux notions très différentes sont obtenues. À
l'origine de ces outils se trouvent les travaux du mathématicien
Andreï Kolmogorov.
Andreï Nikolaïevitch Kolmogorov (1903-1987),
photogr aphié pa r Pa ul Halmos en 1965 .
L
es tentatives de mathé matisati o n
d es n o ti o n s n a ture ll es de
« s impl e » e t de « co mpl exe »
n 'ont abo uti à des résultats inté ressants
que de puis que lques années, g râce à la
théori e a lgorithmique de l' informati o n
proposée par A ndreï Ko lmogorov e n
1965. C harles Bennett a depuis donné un
sens mathématique à une distinction tout
auss i nature lle e t impo rtante , ma is q ui
j usqu 'à présent écha ppa it à la forma lisati o n , la di stin ctio n e ntre ce q ui est
« complexe car a léato ire » (co mme un
gaz o u un tas de caillo ux) et ce qu i est
« co mpl exe ca r t rès o rga nisé o u très
structuré » (comme une puce info rmatique ou un être vivant). Ces deux concepts
- comp lex ité de Ko lm ogorov et profo nde ur logi que de Be nnett - concerne nt to utes les scie nces.
Que signifie « complexe » ?
Co mpl exe pe ut vo ul o ir dire « lo ng à
décrire e n déta il » o u « ri c he e n structures et subti lement o rganisé ». Les deux
idées que sont le « conte nu e n in fo rmati o ns » et le « conte nu en structu res »
sont re lati ve me nt indépe ndantes. « Une
a llée rectil igne e mpie rrée » est d iffic ile
à décrire e nti è re me nt dans le déta i 1, car
il faut indiquer l'emplacement et la fo1 m e
de chaque caillo u. Pourtant e lle est fac ile
à décrire po ur ce qui est de sa struc ture
généra le , pui sque seul e sa for me géoTangente Hors-série n°52. Mathématiques & informatique
par Jean-Paul Delahaye
Complexité de Kolmogorou
et profondeur logique de Bennett
Pour mesurer la complexité d 'un objet numérique, s elon que
l'on considère son contenu en informations, ou son contenu
en structures, deux notions très différentes sont obtenues. À
l'origine de ces outils se trouvent les travaux du mathématicien
Andreï Kolmogorov.
Andreï Nikolaïevitch Kolmogorov (1903-1987),
photogr aphié pa r Pa ul Halmos en 1965 .
L
es tentatives de mathé matisati o n
d es n o ti o n s n a ture ll es de
« s impl e » e t de « co mpl exe »
n 'ont abo uti à des résultats inté ressants
que de puis que lques années, g râce à la
théori e a lgorithmique de l' informati o n
proposée par A ndreï Ko lmogorov e n
1965. C harles Bennett a depuis donné un
sens mathématique à une distinction tout
auss i nature lle e t impo rtante , ma is q ui
j usqu 'à présent écha ppa it à la forma lisati o n , la di stin ctio n e ntre ce q ui est
« complexe car a léato ire » (co mme un
gaz o u un tas de caillo ux) et ce qu i est
« co mpl exe ca r t rès o rga nisé o u très
structuré » (comme une puce info rmatique ou un être vivant). Ces deux concepts
- comp lex ité de Ko lm ogorov et profo nde ur logi que de Be nnett - concerne nt to utes les scie nces.
Que signifie « complexe » ?
Co mpl exe pe ut vo ul o ir dire « lo ng à
décrire e n déta il » o u « ri c he e n structures et subti lement o rganisé ». Les deux
idées que sont le « conte nu e n in fo rmati o ns » et le « conte nu en structu res »
sont re lati ve me nt indépe ndantes. « Une
a llée rectil igne e mpie rrée » est d iffic ile
à décrire e nti è re me nt dans le déta i 1, car
il faut indiquer l'emplacement et la fo1 m e
de chaque caillo u. Pourtant e lle est fac ile
à décrire po ur ce qui est de sa struc ture
généra le , pui sque seul e sa for me géoTangente Hors-série n°52. Mathématiques & informatique