SAVOIRS
Complexité de Kolmogorov
Kurt Godet
(1906-1978).
dent avec nos attentes : la complex ité
de Ko lmogorov de l'objet est grande (le
programme minimal est long) et sa profo ndeur logique est fa ible (le programme
minim al n ' a pas vra iment de calcul s à
mener) .
Pour ( ' instant , o n n 'a rencontré que des
objets de petite profondeur log ique. Ce
n 'est pas le cas des cent mille pre mières
décimales de :rt, qui constitue nt un objet
subtilement organi sé ! On sa it écrire des
programmes relati vement courts capables
d 'e ngendrer ces cent mille déc imales ,
et donc, cont ra ire me nt au cas où l'on
s' inté resse uniqu e me nt à v ing t déc ima les de :rt, ce n 'est plus le programme
« imprimer » qui est le plus court . Ces
prog ramm es co urts d o ivent ca lc ul e r
longte mps et ne produi sent leurs déc imales qu 'à petite vitesse (contrairement
à un programme « imprimer Ob »). Ce la
sig nifie que la profondeur log ique est
grande. Conformé ment à notre attente,
les ce nt mille premières déc ima les de :rt
ont une fa ibl e compl ex ité de Ko lmogoro v e t un e assez g rand e profond e ur
log ique de Bennett.
Co mme derni er exempl e, considéro ns
un mouton . Sa complex ité aléato ire est
grande car (par exemple) la ré partiti on
de la laine sur sa peau ne s uit pas un
motif parfa iteme nt réguli er. Sa pro fon -
de ur logique, e lle auss i, est grande car
on pourrait (en théorie) décrire le mouton , en donnant son génome et en demandant au programme de simuler le processus
de développement , ce qui prendrait beaucoup de te mps. Le mo uton est un objet
complexe , aussi bien en complex ité aléato ire qu 'en complex ité organi sée.
Croissance lente et indécidabilité
Les déve lo ppe me nt s math é matiqu es
que Be nnett a do nnés à ses idées sont
inté ressa nt s so us plu s ie urs as pec ts .
D'abo rd , il a mo ntré que, moyennant
une bo nne défi nition des ordinate urs de
référe nce, la définiti o n q u ' il pro pose
ne dé pe nd pratique me nt pas de l' ordinateur choisi : sa notion est donc (comme
cell e de la complex ité de Ko lmogorov)
stab le et g loba le ment in va ri ante q uand
on change la mac hine utili sée pour la
mes ure r. E ns ui te, il a mo ntré qu e la
notio n de profo nde ur log ique véri fie ce
qu ' il appelle une loi de croissance lente :
l'augmentation de la profonde ur ne peut
être que très le nte (o u encore : il n ' y a
qu ' une très fa ible proba bilité pour que.
du ra nt un court process us dynamique ,
un objet profo nd apparaisse spontanéme nt). Cec i confirm e que, face à un
obj et profo nd , o n do it considérer que
son ori g ine probable ne peut être qu ' un
lo ng ca lcul : un o bj et profo nd po rte
(implic ite ment) en lui la trace d ' un long
processus d 'é laboratio n.
Plus malheureuses sont les conséquences
des rés ultats d ' indéc id abilité de Gode l
(to uj ours e ux !) q ui , auss i bien po ur la
complex ité de Ko lmogorov que pour la
profonde ur log ique de Be nnett , montre nt que ca lcul e r avec ce rtitud e les
va le urs de ces de ux mes ures de complex ité est une tâche d' une extrême d i ffi c u lté, qui sera in fa isable de manière
exacte dès qu e l'on devra tra ite r des
objets no n tri viaux. Ce n 'est pe ut-être
pas surprenant, car on comprend bien que
face à un o bjet profo nd (pensons aux
déc imales de :rt entre la cent millième et
la de ux cent milliè me) il est di ffic il e de
déc ider entre les ex plicati ons « c'est un
o bjet de grande compl ex ité aléato ire»
Tangente Hors-série n°52. Mathématiques & informatique
Complexité de Kolmogorov
Kurt Godet
(1906-1978).
dent avec nos attentes : la complex ité
de Ko lmogorov de l'objet est grande (le
programme minimal est long) et sa profo ndeur logique est fa ible (le programme
minim al n ' a pas vra iment de calcul s à
mener) .
Pour ( ' instant , o n n 'a rencontré que des
objets de petite profondeur log ique. Ce
n 'est pas le cas des cent mille pre mières
décimales de :rt, qui constitue nt un objet
subtilement organi sé ! On sa it écrire des
programmes relati vement courts capables
d 'e ngendrer ces cent mille déc imales ,
et donc, cont ra ire me nt au cas où l'on
s' inté resse uniqu e me nt à v ing t déc ima les de :rt, ce n 'est plus le programme
« imprimer » qui est le plus court . Ces
prog ramm es co urts d o ivent ca lc ul e r
longte mps et ne produi sent leurs déc imales qu 'à petite vitesse (contrairement
à un programme « imprimer Ob »). Ce la
sig nifie que la profondeur log ique est
grande. Conformé ment à notre attente,
les ce nt mille premières déc ima les de :rt
ont une fa ibl e compl ex ité de Ko lmogoro v e t un e assez g rand e profond e ur
log ique de Bennett.
Co mme derni er exempl e, considéro ns
un mouton . Sa complex ité aléato ire est
grande car (par exemple) la ré partiti on
de la laine sur sa peau ne s uit pas un
motif parfa iteme nt réguli er. Sa pro fon -
de ur logique, e lle auss i, est grande car
on pourrait (en théorie) décrire le mouton , en donnant son génome et en demandant au programme de simuler le processus
de développement , ce qui prendrait beaucoup de te mps. Le mo uton est un objet
complexe , aussi bien en complex ité aléato ire qu 'en complex ité organi sée.
Croissance lente et indécidabilité
Les déve lo ppe me nt s math é matiqu es
que Be nnett a do nnés à ses idées sont
inté ressa nt s so us plu s ie urs as pec ts .
D'abo rd , il a mo ntré que, moyennant
une bo nne défi nition des ordinate urs de
référe nce, la définiti o n q u ' il pro pose
ne dé pe nd pratique me nt pas de l' ordinateur choisi : sa notion est donc (comme
cell e de la complex ité de Ko lmogorov)
stab le et g loba le ment in va ri ante q uand
on change la mac hine utili sée pour la
mes ure r. E ns ui te, il a mo ntré qu e la
notio n de profo nde ur log ique véri fie ce
qu ' il appelle une loi de croissance lente :
l'augmentation de la profonde ur ne peut
être que très le nte (o u encore : il n ' y a
qu ' une très fa ible proba bilité pour que.
du ra nt un court process us dynamique ,
un objet profo nd apparaisse spontanéme nt). Cec i confirm e que, face à un
obj et profo nd , o n do it considérer que
son ori g ine probable ne peut être qu ' un
lo ng ca lcul : un o bj et profo nd po rte
(implic ite ment) en lui la trace d ' un long
processus d 'é laboratio n.
Plus malheureuses sont les conséquences
des rés ultats d ' indéc id abilité de Gode l
(to uj ours e ux !) q ui , auss i bien po ur la
complex ité de Ko lmogorov que pour la
profonde ur log ique de Be nnett , montre nt que ca lcul e r avec ce rtitud e les
va le urs de ces de ux mes ures de complex ité est une tâche d' une extrême d i ffi c u lté, qui sera in fa isable de manière
exacte dès qu e l'on devra tra ite r des
objets no n tri viaux. Ce n 'est pe ut-être
pas surprenant, car on comprend bien que
face à un o bjet profo nd (pensons aux
déc imales de :rt entre la cent millième et
la de ux cent milliè me) il est di ffic il e de
déc ider entre les ex plicati ons « c'est un
o bjet de grande compl ex ité aléato ire»
Tangente Hors-série n°52. Mathématiques & informatique