Les Actualités / Pierre Wolper ou l’intelligence de la simplicité au service de la science inf

Pierre Wolper ou l’intelligence de la simplicité au service de la science informatique

Professeur ordinaire et vice-recteur à la recherche de l’Université de Liège, membre de l’Académie royale de Belgique depuis 2009, éminent spécialiste en science informatique dont il est docteur de Stanford University aux États-Unis, lauréat en 2000 du prix Gödel, du prix Kanellakis Theory and Practice Award en 2005, et auteur de nombreux articles marquants dans la sphère de la computer science mais également d’un livre consacré à l’introduction à la calculabilité servant de base à son enseignement,
Pierre Wolper impressionne immédiatement par la clarté et la simplicité de ses propos qui pourtant touchent à des domaines fort complexes : ceux de la mise en forme de procédures, de programmes, visant à être compris par la machine. Son regard clair, son bureau épuré du Sart Tilman près de Liège et son langage pointu mais accessible témoignent de cet état d’esprit d’un scientifique qui a les pieds sur terre mais la tête surtout bien faite. Le professeur Wolper nous a reçu avec une grande disponibilité afin de nous parler de cette énorme galaxie pleine de data et de bits où il excelle, celle de l’informatique.



Professeur Wolper, comment voyez-vous l’évolution prochaine des sciences informatiques ? Et, en particulier, les développements, semble-t-il inéluctables, d’internet ?

Ce qu’internet a vraiment changé, c’est la disponibilité et l’accès à l’information. La taille et la vitesse augmentent mais depuis longtemps nous sommes arrivés à un point où l’accumulation de masses d’informations est tout à fait extraordinaire. On appelle cela le big data ! Pensons par exemple aux séquenceurs rapides en génétique pour lire le génome. Ce n’est plus un génome que l’on séquence, mais celui de centaines, voire de milliers d’individus. Toutes ces données sont accumulées, mais elles peuvent aussi être échangées et surtout analysées, ce qui ouvre la possibilité de découvertes qui peuvent être surprenantes.

On se pose toujours la question de savoir si, en informatique, on va avoir des systèmes intelligents ? On se fait, je pense, beaucoup d’idées exagérées sur ce qu’est l’intelligence. En définitive, nous croyons en tant qu’humain être plus intelligents que nous ne le sommes vraiment ! Car lorsqu’on regarde ce qu’il est possible de faire, on s’aperçoit qu’en accumulant l’information, on arrive à faire beaucoup de choses considérées comme intelligentes. D’ailleurs, dans notre vie quotidienne, on fait peu de raisonnements. En tant que chercheurs, on en fait plus que la moyenne bien entendu (rires) ! Mais, lorsque vous vous levez le matin, vous ne raisonnez pas beaucoup. Nos comportements sont finalement très simples. Avec des méthodes relativement simples qui manipulent suffisamment d’informations, on peut déjà faire énormément !

Une objection est que les mathématiques nous disent qu’il y a des problèmes insolubles par les méthodes informatiques, mais cela ne concerne que les situations où le nombre d’ensembles de données différents que l’on pourrait avoir à traiter est infini. Or, nous travaillons toujours avec des données de taille limitée. C’est évidemment aussi le cas pour un être humain.

Si, par exemple, nous estimons la capacité nécessaire pour notre mémoire, l’informaticien aura vite fait de déterminer une limite au nombre de bits ! Aussi, l’évolution ne nous a certainement pas rendus capables d’absorber et de traiter davantage que ce à quoi nous sommes exposés au cours d’une vie elle aussi finie, par nos sens, le flux visuel étant le plus important. L’information que nous traitons a toujours une taille bien inférieure à celle du film complet de notre vie. Donc, avec de grosses quantités de données, et des méthodes relativement simples, on peut arriver à de très bons résultats. On le voit très bien avec la traduction automatique, cela donne des résultats qui permettent de comprendre l’essentiel. C’est la révolution de l’informatique actuelle. Les voitures autonomes roulent bel et bien ! Les conducteurs humains seront vite considérés comme bien trop dangereux (rires) ! On peut aussi, dans ce cadre, penser au diagnostic médical où internet permet de rassembler toute la connaissance, notamment sur les symptômes détectés pour différentes maladies, bien au-delà de ce que le médecin peut faire à lui tout seul ! Ainsi, on assimile du reste souvent l’intelligence à quelque chose qu’on ne comprend pas tout à fait. L’exemple des échecs est éloquent ! Tout cela est transposable dans des programmes ! On se rendra compte tôt ou tard que tout ce que nous faisons ne nécessite pas une intelligence extraordinaire. Nous ne sommes, in fine, qu’un système de traitement de l’information. Et les progrès en robotique vont nous étonner, avec des mécanismes relativement simples !

Pourriez-vous retracer votre parcours académique et scientifique ? Et, en amont, nous dessiner la genèse des lignes de force principales des problématiques que vous mettez en avant et traitez ? Autrement dit, comment devient-on spécialiste d’une science, il faut bien le dire, un peu particulière : la science informatique ?

Oui, et d’ailleurs, l’appellation science informatique fait débat dans certains milieux. N’est-ce pas seulement une technique se demande-t-on ? Mais, justement, je pourrais mettre en évidence l’aspect scientifique de l’informatique et dans quel sens il s’agit effectivement d’une science.

Mais commençons par mon parcours. J’ai été formé à l’Université de Liège comme ingénieur spécialisé en électricité et plus particulièrement en électronique. À ce titre, j’ai eu des cours d’informatique. Sujet qui m’a interpellé et d’une certaine façon fasciné car j’y voyais beaucoup de possibilités. Surtout que cela ouvrait un monde logique et virtuel où à partir d’idées on pouvait rapidement créer quelque chose d’utile. En effet, lorsqu’on crée un programme, on génère une sorte d’objet mathématique qui permet de traiter des informations et d’en tirer des conséquences. Dans ce cadre, j’avais fait un mémoire lié au problème du langage naturel, domaine que j’ai abandonné par la suite du reste. Il s’agissait de formuler en langage naturel des concepts qui avaient été formalisés sous forme d’expressions logiques. J’ai donc développé un certain intérêt pour la logique et la représentation de la connaissance de façon générale. Puis, j’ai poursuivi mon parcours académique en allant à Stanford University pour y faire un doctorat pendant lequel j’ai été obligé de suivre un nombre de cours et d’approfondir mes connaissances notamment dans le domaine de l’informatique proprement dite mais aussi dans celui de la logique. Je me suis alors intéressé à l’utilisation de la logique dans le contexte du raisonnement au sujet de programmes.

Mais, dans le fond, qu’est-ce qu’un programme ?

Le programme est un texte qui est opérationnalisé par un ordinateur et qui permet de réaliser un calcul, un traitement de l’information. Et, la question était : est-ce que ces programmes que l’on crée font ce que nous souhaitons qu’ils fassent ? Cela peut paraître évident mais tout utilisateur de l’informatique sait que les programmes ne font pas toujours ce qu’il souhaite.

En effet, ils ne nous obéissent pas toujours !

Oui, et dans la plupart des cas ce n’est pas dramatique mais dans certains contextes plus précis comme par exemple lorsqu’un système informatique contrôle un système physique, cela peut devenir beaucoup plus gênant et créer des dégâts ! On le voit bien lors des jours de grandes affluences lorsque les systèmes de paiements s’arrêtent ! Ou encore en aéronautique ! D’ailleurs, je lisais aussi récemment que l’on envisageait d’automatiser le transport maritime avec des bateaux sans équipage. Mieux vaut qu’il n’y ait pas d’erreurs de programmation.

J’ai donc commencé à m’intéresser à l’usage du formalisme logique pour raisonner au sujet de programmes avec l’objectif d’automatiser ces raisonnements. En logique, suivant la nature du formalisme, on a ou on n’a pas de méthodes algorithmiques qui permettent de décider certaines propriétés des formules. Je me suis donc naturellement intéressé à certaines formes particulières de logique qui permettaient un raisonnement automatisé. La logique est alors utilisée pour décrire les propriétés et le comportement souhaité du programme. Et cela n’est pas toujours simple. Car, dès que vous avez quelque chose de complexe, que doit faire le programme ? Surtout ne pas se retrouver dans une situation qui deviendrait dangereuse à un moment de son exécution. On peut aussi spécifier qu’il va réagir dans un certain délai. Je suis donc parti d’un formalisme qui était la logique temporelle, initialement développée pour formaliser des questions relatives à l’usage des temps du langage, mais en gardant l’essentiel et en épurant cette logique. Ma tâche a donc été de travailler à partir de formules de logiques temporelles. Que peut-on faire ? Un des outils que j’ai utilisé par la suite dans mes recherches pour cette question est la correspondance qui existe entre les formules de logique temporelle et un autre formalisme qui est celui des automates finis.

Pourriez-vous préciser de quoi il s’agit avec les automates finis ?

Un automate fini est en fait une forme très simple de programme. En définitive, c’est un langage de programmation extrêmement simplifié où l’on parle simplement d’états et d’actions. On le représente souvent sous la forme d’un graphe où les états sont les nœuds du graphe et les actions permettent de changer d’état.

Ce qui a guidé mes travaux, c’est qu’il est possible à partir d’un formalisme logique de construire un automate fini qui représente la même information mais qui a l’avantage d’être manipulable algorithmiquement.

Plus précisément, qu’est-ce que cela veut dire ‘être manipulable algorithmiquement’ ?

Cela veut dire que l’on peut écrire un programme qui analyse ou modifie l’information. C’est beaucoup plus facile au niveau des automates. Cela m’a amené à proposer d’utiliser cette correspondance de façon systématique lorsqu’on souhaitait mettre au point des méthodes d’analyse de programme, par exemple par rapport à des spécifications exprimées en logique temporelle. Cela a été le thème central d’une série d’articles que j’ai publiés. En fait, j’ai proposé une approche par la théorie des automates pour la solution de tel ou tel problème. Elle s’est avérée un concept particulièrement utile, même s’il a été critiqué au début. Mais le gros avantage de passer par les automates était que l’on se trouvait dans un contexte beaucoup plus simple. Et donc qu’une série de questions algorithmiques étaient beaucoup plus faciles à résoudre. J’ai continué mes recherches chez Bell Labs près de New York où je travaillais avec des gens qui construisaient des systèmes d’analyse et de vérification. Au départ, ils n’avaient pas inclus la possibilité d’utiliser des spécifications de logiques temporelles dans leur système. Mais avec le passage par les automates, cette possibilité devenait plus facile à introduire dans les systèmes qu’ils construisaient. La mise en œuvre pratique était donc devenue plus facile.

Vous avez donc vu la mise en œuvre concrète de vos automates ?

Oui, dans certains domaines, c’est exploité ! Et aussi dans la conception des circuits. Car lorsque vous construisez un circuit ou un processeur, s’il y a une erreur c’est extrêmement gênant. Il n’y a pas de mise à jour comme pour les logiciels ! Et la complexité est telle qu’elle est souvent, bien supérieure à celle des programmes d’il y a 30 ans. Malheureusement, aujourd’hui, la plupart des circuits comportent des erreurs !

Voulez-vous dire que vos recherches ont modifié la conception des circuits ?

Certaines de mes idées ont été intégrées dans des outils utilisés par les fabricants de semi-conducteurs. Il s’agit de vérifier que ce qui est conçu correspond bien à ce que l’on souhaite. En fait, c’est détecter un maximum d’erreurs potentielles.

C’est ici qu’intervient ce que vous apportez avec la logique temporelle ?

La logique temporelle permet de spécifier les conditions de séquencement d’actions ou le fait que certaines situations vont ne jamais arriver ou fatalement arriver.

Ici, à Liège, j’ai poursuivi mes travaux avec des doctorants qui ont eu notamment des parcours tout à fait intéressants dans cette optique de l’utilisation des automates. En définitive, j’ai toujours gardé à l’esprit que je dois aboutir à des algorithmes et à des solutions simples. Souvent, ce qui est proposé dans mon domaine est horriblement compliqué. Mes lignes directrices les plus importantes en matière de recherches ont toujours été de trouver les solutions les plus simples possibles, et d’arriver par-là à des choses parfois étonnantes. Et l’avantage de faire des choses simples, c’est qu’elles sont généralement comprises ! Et donc plus facilement exploitées !

Et mieux applicables, j’imagine ?

Exactement ! Lorsqu’on doit réaliser un système informatique, écrire des programmes – ce qui n’est déjà pas une tâche facile – plus les concepts à mettre en œuvre sont simples, plus c’est facile à faire ! Il faut arriver à des représentations suffisamment simples pour que leur transcription sous forme algorithmique soit faisable et fiable.

La gageure étant que la simplicité rejoigne la complexité de ce qui est à faire !

Ce qu’il faut, c’est traiter des choses complexes mais avec des méthodes relativement simples.

Et en 2000, vous recevez le prix Gödel pour tout cela !

Oui, c’était pour cette idée de passage et d’utilisation de formules de logique temporelle vers les automates. Et aussi en 2005, dans le domaine des applications, le prix Kanellakis Theory and Practice Award, partagé avec le co-auteur avec lequel j’ai beaucoup travaillé, Moshe Vardi, ainsi que Robert Kurshan et Gérard Holzmann, ce dernier étant maintenant à la Nasa, exploitant les idées sur lesquelles nous avons travaillé. Petite anecdote amusante : lorsque je proposais à ce dernier une solution, il répondait que ce n’était pas possible, que cela ne fonctionnait pas ! Puis, dans un second temps, que ce n’était pas pratique ni utilisable même si c’était juste ! Et, un an après, il commençait à implémenter ma solution dans son système !

Aussi, nous avons eu une controverse au sujet d’une technique de compaction d’informations lorsque l’on essaie de générer les états, tous les comportements possibles d’un programme. Il faut être efficace et lui, avait un système qui faisait très bien ce travail. Je pensais néanmoins qu’il y avait moyen de faire mieux ! Et finalement, il a adopté mon approche. Ce qui est somme toute assez amusant ! C’est le plaisir de la recherche ! Surtout qu’à partir d’idées et de concepts assez théoriques, on arrive à des choses tout à fait pratiques ! J’ai d’ailleurs un doctorant qui travaillait justement sur l’amélioration de l’efficacité de l’analyse des états et qui maintenant est employé chez Microsoft près de Seattle où il est très apprécié car il a mis au point des techniques qui trouvent des erreurs ! Cela fait évidemment gagner beaucoup d’argent car les erreurs, cela coûte très cher ! Pensons à toutes les mises à jour sur Windows ! Il ne cherche du reste que les erreurs qui valent un million de dollars !

Que pensez-vous des limites de l’informatique ? Et donc, d’une certaine façon, celles de la calculabilité dont vous êtes devenu le chantre ? Y a-t-il, autrement dit, du non-calculable et qu’est-ce que cela induit pour ce qu’on appelle la science informatique ?

Le concept de calculabilité, c’est simplement de se poser la question de savoir si pour un problème il existe ou non une solution algorithmique. Or, il n’y a pas de solution algorithmique pour tout problème. La question se définit d’un point de vue mathématique de façon directe. On a un ensemble d’objets mathématiques et on doit distinguer deux catégories, qui ont des propriétés différentes. Mais peut-on faire cela avec un algorithme ? Imaginons que les objets soient des nombres. Et je veux distinguer deux catégories de nombres, les pairs et les impairs. Pour cela, on a un algorithme. Mais il y a des propriétés pour lesquelles on n’a pas d’algorithme ! La raison fondamentale, et presque évidente, c’est simplement qu’il y a plus de problèmes que d’algorithmes ! Si vous prenez l’ensemble dénombrable des nombres naturels, le problème, ce sont les sous-ensembles de cet ensemble, car l’ensemble des sous-ensembles est non-dénombrable. C’est dans les deux cas un ensemble infini, mais le non-dénombrable est en quelque sorte plus grand que le dénombrable. Les algorithmes et les programmes qui les concrétisent sont des objets de taille finie et donc, le nombre de programmes est dénombrable. Par contre, l’ensemble des problèmes est non-dénombrable et il existe par conséquent une large infinité de problèmes pour lesquels il n’y a pas d’algorithmes. À partir de là, on peut démontrer que certains problèmes tout à fait concrets n’ont pas de solutions algorithmiques. Et notamment les questions qui s’intéressent aux propriétés des programmes eux-mêmes ! Questions auxquelles je m’intéresse dans mes travaux. Un programme avec une caractéristique donnée à l’entrée va-t-il l’exécuter jusqu’à la sortie et s’arrêter ou va-t-il tourner indéfiniment ? Un problème aussi simple que cela n’est pas décidable. On peut se demander si on n’est pas un peu fou de travailler sur des questions qui ne sont pas décidables ? Mais, la théorie de la calculabilité nous indique l’absence de solution parfaite, c’est-à-dire applicable dans absolument tous les cas. Si je veux savoir si un programme s’arrête, je veux pouvoir le faire pour n’importe quel programme. Mais le problème pratique n’est pas celui-là. On peut n’être intéressé que par certains types de programmes, ou simplement accepter que l’on n’aura pas nécessairement la réponse. Donc, la non-calculabilité ne veut pas dire l’impossibilité de traitement informatique, seulement l’impossibilité de traitement informatique parfait.

Avez-vous le rêve de faire disparaître cette indécidabilité ?

L’indécidabilité est tout simplement un fait mathématique. Elle ne disparaîtra pas, c’est la différence entre le dénombrable et le non-dénombrable. Mais comme je suis quand même ingénieur, j’ai un point de vue très pragmatique. Même si l’indécidabilité exclut des solutions algorithmiques parfaites, cela n’empêche pas qu’on puisse traiter énormément de choses. Bien sûr, on est confronté à des problèmes indécidables mais cela ne m’empêche pas de travailler ! On a généralement tendance à surestimer ce qu’il faut faire pour arriver à des résultats efficaces et concrètement utilisables. Et, à l’opposé, ce n’est pas parce qu’un problème est décidable que l’on a une solution algorithmique utilisable en pratique. Par exemple, dans un ensemble fini, toute question est décidable ! Mais si l’ensemble est de très grande taille, cela ne permet pas forcément d’aboutir à une solution pratique. Paradoxalement, passer à un contexte infini permet parfois même de simplifier ! Imaginons que je travaille sur des nombres naturels et que je les représente par 32 bits, 64 bits ou davantage. Je dois toujours savoir que je travaille dans ce contexte, par exemple 64 bits. Je dois donc dans tout mon système de raisonnement tenir compte de cette contrainte. Mais, on peut aussi considérer que les nombres n’ont pas de limite à leur taille. Et on va pouvoir travailler avec des représentations plus simples. Dans ce contexte, on peut d’ailleurs arriver à représenter des ensembles de nombres par des automates finis, sujet sur lequel j’ai aussi travaillé.

Un moment très agréable dans ma carrière a été de se rendre compte que les automates qui représentaient certains ensembles avaient des propriétés particulières où des algorithmes plus simples arrivaient à les manipuler. Et de réaliser un système permettant de mettre cela en œuvre.

La recherche informatique peut paraître un peu magique car on part de représentations mathématiques complexes, et puis on arrive à quelque chose qui peut résoudre des problèmes concrets.

Propos recueillis par Robert Alexander

Quelques orientations bibliographiques :

Moshe Y. Vardi et Pierre Wolper, « Reasoning about infinite computations », Information and Computation, Boston, MA, Academic Press, vol. 115, no 1, 1994, p. 1-37 : lauréat du prix Gödel.
Moshe Vardi et Pierre Wolper, « An Automata-Theoretic Approach to Automatic Program Verification », dans Proceedings of the First Symposium on Logic in Computer Science, Cambridge,‎ 1986, p. 322-331 : lauréat du prix LICS test-of-time 1996.
Patrice Godefroid et Pierre Wolper, « A partial approach to model checking », dans Proceedings of the Sixth Symposium on Logic in Computer Science, Amsterdam,‎ 1991, p. 406-415 : lauréat du prix LICS test-of-time 2011.
Pierre Wolper, Introduction à la calculabilité : cours et exercices corrigés, Paris, Dunod,‎ 2006.

Zoom

 

Top