Complexités et calcul : dessin et mathématiques

Les histoires (car ce sont bien de vraies histoires …) que le chercheur chilien en mathématiques et sciences de l’informatique, Éric Golès*, nous racontera à propos de la complexité, ont au moins deux versants : l’un lié aux aspect classiques de la complexité en informatique, sur les limites de la calculabilité, ce que l’on peut ou ne peut pas calculer sur un ordinateur ; et l’autre lié à la complexité comme émergence inattendue de la dynamique (ou du fonctionnement) d’un système composé d’un grand nombre d’unités simples.

La première histoire est associée à l’indécidabilité du problème de l’arrêt d’un ordinateur (une machine de Turing). Bien qu’en apparence nos ordinateurs modernes sont faciles à éteindre, il est en fait très complexe pour un ordinateur, même des plus récents, de savoir quand toutes ses tâches sont terminées. Une analogie peut être faite avec un peintre qui reproduirait sur son tableau un modèle en mouvement permanent. Comment ce peintre va décider que son œuvre est finie et qu’il peut s’arrêter de peindre ?

La seconde histoire parle des dessins que le chercheur faisait lui-même pour passer le temps lors de longues réunions. La question dans ce cas est pourquoi était-il en train de dessiner précisément ces dessins. Cette interrogation a trouvé une réponse grâce aux systèmes complexes et a abouti à un petit théorème qu’il tâchera de nous expliquer.

Enfin, la troisième histoire est en relation avec un artiste plasticien qui voulait mettre des formules mathématiques dans ses œuvres de très grande taille. Le problème rencontré concernait le transport par avion de ces œuvres et la nécessité de trouver un moyen de plier les toiles sans les abîmer ; cette question a conduit le chercheur à résoudre le problème de pliage et de pavage des toiles de l’artiste.