par Jean-Paul Delahaye

Quae, c/o Inra, RD 10, 78026 Versailles cedex, mai 2009
76 p. en 12 × 19, 8,50 €, ISBN : 978-2-7592-0320-8

Cette petite brochure contient le texte d’une conférence-débat organisée par le groupe Sciences en questions (Inra) le 19 octobre 2006 pour un public de bio-statisticiens ; le texte lui-même occupe 36 pages et la discussion 27.

L’auteur, spécialiste d’algorithmique qui a déjà publié deux livres et de nombreux articles sur le sujet, et militant de la promotion de la culture scientifique, souhaite articuler son exposé autour des questions suivantes :

• Qu’est-ce que la complexité ?
• Y a-t-il un concept précis derrière ce mot ?
• Que nous disent les mathématiques sur de possibles définitions formelles ?
• Quelles sont les conséquences et les applications du travail de définition théorique ?

Le mot complexe recouvre deux idées éloignées : d’une part, il signifie sans ordre, sans régularité, aléatoire, chaotique, et d’autre part organisé, structuré, ajustant des éléments. Ceci conduit à distinguer pour une suite finie de chiffres la complexité aléatoire (celles obtenues par tirages successifs indépendants) de la complexité organisée (celle des premières décimales de p) ; peut-on les mesurer ?

Pour la première, la réponse a été apportée en 1965, simultanément et indépendamment par Kolmogorov et Chaitin : La complexité de Chaitin-Kolmogorov, K(s) , d’une suite binaire finie s est la longueur du plus court programme qui engendre s (programme minimal de s) ; le calcul de K(s) se heurte à l’indécidabilité de l’arrêt d’un programme (Turing 1936), mais les algorithmes de compression de données donnent des majorations intéressantes.

En 1988, le physicien Ch. Bennett définit la profondeur logique de s : P(s) comme le temps de calcul du programme minimal de s et propose l’identification avec la complexité organisée.

La discussion comporte une vingtaine de questions qui permettent à l’auteur de détailler certains points ; en voici quelques unes :

• Peut-on évaluer la (faible) complexité d’une très longue suite pseudo aléatoire sans connaître l’algorithme qui l’engendre ?
• Est-il possible de créer une suite aléatoire de façon informatique ?
• La suite des décimales de $\pi$ passe-t-elle tous les tests ?
• Comment définir la complexité d’une image bruitée ?
• Dans la description des réseaux de régulation, il y a à la fois une certaine régularité mais une grande part d’aléatoire dans les réactions individuelles.
• Est-ce que les algorithmes actuels de compression permettent d’approcher une représentation de l’évolution du génome ?
• Les concepts évoqués sont-ils pertinents pour parler de l’évolution de la vie sur terre ?
• Êtes-vous d’accord avec l’idée métaphysique que tout est algorithme ?

L’ouvrage rend donc compte d’un très riche débat qu’un professeur pourra aborder avec des élèves qui se posent des questions sur l’utilisation de la touche random de leur calculatrice ou dans un travail interdisciplinaire avec des informaticiens, des biologistes, des logiciens et des philosophes.

Les qualités pédagogiques manifestées par l’auteur, tant dans l’exposé que dans l’habileté à répondre à des questions difficiles et encore ouvertes, rendent la lecture de bout en bout agréable.

Une bibliographie présentant des travaux s’étalant sur une cinquantaine d’années permet au lecteur d’approfondir certains points.