Ce qu'on appelle un problème est un ensemble de trois choses : des données, un algorithme, c'est-à-direun programme, une procédure pour résoudre ce problème et enfin un moyen pour exprimer cette solution.Ce qui nous intéresse alors est la complexité qu'on peut par exemple commencer par exprimer en temps de calcul.En voulant étudier le comportement d'un nuage de n points-masses vous deviez à chaque étape calculerpour chaque point l'attraction gravitationnelle exercée sur lui par tous les autres. Ainsi votre temps de calculcroissait comme le carré du nombre de points. C'est ce qu'on appelle un problème de type polynomial, où letemps de calcul croît comme une certaine puissance de l'ampleur du problème, de la quantité de données àtraiter, ce qui en l'occurrence ici se réduit au nombre des points. Dans ce cas, on peut toujours penser qu'enayant des ordinateurs de plus en plus puissants, des vitesses de calcul de plus en plus élevées, on pourrainéluctablement, un jour ou l'autre, être capable de maîtriser ces problèmes.qu'il existe des problèmes dits « non polynomiaux », où le temps de calcul se comporte de manièretotalement différente. Prenons par exemple le cas des problèmes « à temps exponentiel ». On en connaît descentaines où, quand on multiplie le nombre des données par dix, le temps de calcul passe d'un centièmede seconde à dix mille milliards de siècles. On sait aussi que ce type de problème échappe à tout espoir quipourrait être fondé sur l'accroissement des performances de la vitesse des ordinateurs.Je citerai le classique problème dit « du voyageur de commerce». On met n villes sur une carte ainsi quetoutes les routes qui les relient l'une à l'autre. On pose le problème de déterminer un trajet qui permette depasser par chacune d'entre elles et qui soit de longueur minimale. Or, par exemple, quand on atteint un nombrede mille villes, on est simplement incapable de traiter ce problème. La complexité présente différentesfacettes, différents « murs ». Dans le cas particulier du problème du voyageur de commerce, la situation esttelle qu'on ne dispose même pas d'algorithme, d'une méthode quelconque pour aborder le problème.
Je sais comme vous qu'au sommet de cette pyramide de la complexité se trouve une classe de problèmesdits «NP-complets», dont on a démontré qu'ils étaient tous de complexité équivalente. Le mathématicienCrook a même prouvé que s'il s'avérait possible d'en résoudre un seul, alors l'ensemble se comportaitcomme des dominos et qu'ils devenaient du coup tous solubles. Si vous résolvez un seul problème NPcomplet,la forteresse logique s'effondre comme un château de cartes. On a même donné à cette affaire unnom : c'est devenu « le problème du siècle ».
Je vais vous expliquer. SAT vient du mot anglais satis/easibility et k est simplement le nombre de variables du problème.Un problème k-SAT consiste simplement à savoir si une expression logique, booléenne, est vraieou fausse. Dans le problème du voyageur de commerce, le nombre de variables qui enconstituent les données est le nombre de villes. Appelons- le k. Nous avons donc k villes, plus tous les cheminspossibles qui les relient entre elles avec les kilométrages. On cherche à déterminer un trajet quipasse par chacune d'entre elles et qui soit de longueur minimale. n s'agit donc d'un problème d'extrema!.Imaginons que nous formulions maintenant le problème différemment, en posant la question : « Existet-il un trajet parcourant toutes les villes et qui fasse moins de 615 kilomètres ? » Cela devient un problèmelogique dont la réponse est soit oui, soit non, donc un problème k-SAT.«Existe-t-il un trajet passant par toutes les villes, faisant moins de 614 kilomètres?» Cela sera un nouveau problème k-SAT. Ainsi, en mettant en oeuvre cette procédure, cet algorithme,on se rapproche de la valeur minimale qui précédera la première réponse négative sur laquelle on tombera.
Qu'appelez-vous intelligence ?- La capacité de se reprogrammer. Les ordinateurs actuels en sont incapables.- lis peuvent pourtant modifier leur comportement en fonction des circonstances.- Uniquement en activant des sous-programmes préexistants, conçus par des hommes. Je vais essayerde vous situer les différents niveaux chez les êtres vivants. Le niveau zéro est le virus, mono-comportement,qui ne peut que donner à une bactérie l'ordre de fabriquer des clones de lui-même. li n'est d'ailleurs pasdit que les virus ne soient pas issus d'une dégénérescence d'une structure cellulaire. Dans le plancton ontrouve des êtres vivants, comme les radiolaires qui sont de simples boîtes noires. Ces êtres ne possèdent pas demémoire vive. La capacité de mémoriser, c'est-à-dire la mémoire vive, la « RAM », apparaît chez un êtrecomme l'oursin, qui ne peut pas changer de comportement mais est cependant capable de mémoriser un trajetconduisant à de la nourriture. Un logiciel de jeu d'échecs est un « oursin sophistiqué » qui fait illusion,c'est tout. L'intelligence c'est la capacité de faire émerger des comportements inédits comme peuvent le faireun chien ou un poulpe. Le recours à la technologie n'est qu'une démultiplication de cette intelligence.
« À propos de logique tétravalente, je crois que c'est plus qu'une logique à quatre états. On peut dire qu'une des applicationsserait une logique à quatre états, ou le développement d'une logique non classique plus fondamentale encore. C'est une entreprise plus vaste qui se cache derrière, avec beaucoup de travail en vue, peut-être pour des siècles de recherche logico-mathématique.»
C'est un terrible jeu d'apprenti sorcier, s'indigna Shandrah, et cela démontre la prétention imbécile des hommes de science. Quand les biologistes annoncent à son de trompe qu'ils ont achevé la cartographie du génome humain, c'est comme si des gens annonçaientqu'ils avaient enfin réussi à identifier tous les mots d'un dictionnaire, un à un, puis annonçaient leur intentionde faire de nouvelles phrases, de composer des textes, alors qu'ils ignorent la grammaire et la syntaxe de lalangue à laquelle ils s'attaquent. Je trouve que l'idée émise, dans un de vos échanges, par ce Windows 98ne manque pas de pertinence : et si le but de cette tentative était de montrer que l'ADN humain recèleun problème de type k-SAT? Cela pourrait au moins dissuader les généticiens de continuer leurs âneries.
Prenez, par exemple, celui de la stabilité d'un avion, qui relève d'un système d'équations différentiellesdu second ordre, couplées. Bien sûr, celles ci sont en assez petit nombre et, de nos jours, on arriveassez bien à traiter cette question grâce à la rapidité de nos calculateurs« digitaux». On procède par itérationssuccessives. On résout l'une des équations qui donne la fonction A(t), une grandeur qui dépend du temps,qui est, par exemple, l'angle d'incidence de l'appareil, puis on se sert de cette solution en l'injectant dans lesautres équations, partout où cette fonction est présente en s'en servant pour construire les fonctions-solutionsB(t), C(t) qui représentent d'autres grandeurs évoluant dans le temps. Et ainsi de suite. Le programme bouclejusqu'à ce que toutes ces solutions A(t), B(t), C(t), etc. soient compatibles entre elles. On a autant d'équationsque de fonctions inconnues. Si on en a six ou sept, ce qui est largement suffisant pour gérer la stabilité d'unavion, pas de problème. Mais si on devait faire face à un millier d'équations différentielles couplées, mettanten jeu un millier de fonctions différentes, évoluant selon le temps, ce serait une autre paire de manches.
Maintenant si j'appelle q(t) la valeur instantanée de la charge électrique du condensateur, tous les étudiantsen sciences ou les ingénieurs savent que ceci relève d'une équation différentielle du second ordrefaisant intervenir la dérivée première q'(t) de cette fonction et sa dérivée seconde q"(t). La dérivée premièreq'(t) représente la façon dont la charge électrique varie dans le temps, c'est-à-dire l'intensité l(t) du courantélectrique qui parcourt le circuit. Mais ce que vous ne voyez pas c'est que ce circuitoscillant constitue en soi une machine analogique permettant de résoudre des équations différentielles de ce type.Ainsi on peut construire la solution A(t), B(t), C(t), D(t) ... d'un système d'équations différentielles couplées, en temps réel. n n'y a pas de temps de calcul puisqu'il n'y a pas d'itérations. Ces calculateurs analogiques ont été utilisés dans les années 1960 pour étudier la dans les brumes du «secret-défense». Bien peu de gens savent qu'aujourd'hui pas mal de missiles sontpilotés par des systèmes de ce genre, dont le fameux Exocet. Ces calculateurs, très rustiques, sont moinssensibles aux impulsions électromagnétiques émises par les armes « E », devenues très à la mode ces temps ciet qui exigent que l'on blinde (on dit que l'on« durcisse ») tous les ordinateurs digitaux dont les processeurs grillent à la moindre surtension.
Il cocha ses hypothèses.- 1. Un scientifique travaillant pour les militaires et qui souhaite, à travers ce canal, faire sortir des infos àpropos de recherches auxquelles il est mêlé, en imputant cela à des extraterrestres.« 2. Des scientifiques militaires qui se livrent à une subtile manip en cherchant à activer des chercheurs civils, en les faisant travailler gratuitement et à leur insu sur des problèmes qu'ils n'ont pas résolus. - 3. Un extraterrestre qui tente d'entrer en contact en utilisant le net.« 4. Un extraterrestre qui effectue cette démarche en utilisant une interface protocolaire informatisée, c'està- dire un système d'intelligence artificielle.
« Comment acheminer tant d'informations quand on ne dispose que d'une ligne comportant un certain nombre de canaux nettement inférieur ? » Ce papier est au départ concentré sur une façon totalement originale de traiter, de compacter l'information en faisant apparaître ce que l'auteur appelle des « harmoniques ». L'image mentale commode est celle d'une couleur comme le « marron », comparée aux couleurs qui en fait la composent et qui imposent au minimum la présence de deux raies, de deux fréquences, l'une correspondant au rouge et l'autre au vert. Quand vous observez un décor vous avez sous les yeux un éventail des couleurs les plus complexes que vous identifiez chacune comme des « nuances colorées ». Ce que nous ne comprenions pas jusqu'ici c'était la façon dont le système perceptif humain s'y prenait pour transformer ces paquets de fréquences, ces nuances correspondant à un spectre compliqué, en quelque chose perçu comme une couleur, unique.Vous êtes habituée à fonctionner avec une logique divalente où il n'existe que deux « valeurs de vérité » :le vrai et le faux. Mentalement, vous excluez toute autre éventualité. C'est ce qu'Aristote avait énoncé en le nommant « principe du tiers exclu ». Autrement dit, une « proposition » ne peut être que vraie ou fausse, d'autres intermédiaires étant exclus a priori.
- Réfléchissez, s'il est vrai que je mens, alors cette proposition est un mensonge.- Donc vous ne mentez pas. Ouh là, là ! Mais alors, cette proposition est-elle vraie ou fausse?- Elle n'entre pas dans votre crible logique. Vous pouvez considérer cette assertion comme « vraie et fausse ». Vous avez donc, dans le simple langage courant,un exemple de logique à plus de deux valeurs de vérité.- Et à quoi pourrait ressembler une logique à quatrevaleurs de vérité ?- On a étudié des logiques tétravalentes basées sur quatre éventualités. Une proposition peut être vraie, fausse, vraie et fausse, vraie ou fausse.
- Ces logiques multivaluées sont intéressantes. Les notions de vrai et de faux sont, somme toute, purement conventionnelles. Imaginez, par exemple, un hôpital psychiatrique qui serait peuplé de psychiatres et de fous. Si un psychiatre rencontre un autre psychiatre il se dira : « Cet homme est dans le vrai. » Inversement, pour lui un fou a « tout faux ». Plus schématiquement, dans le point de vue logique du psychiatre, un autre psychiatre est « vrai » alors qu'unfou est «faux».
- Placez-vous maintenant dans le camp des fous. Entre eux ils se considèrent comme « vrais », « véridiques». En revanche, les psychiatres ont « tout faux »ou, dit plus simplement, ils sont « faux ». Cela introduitle concept de relativité du point de vue logique.
- Imaginez maintenant un hôpital qui soit peuplé par quatre populations : les psychiatres, les fous, les psychiatres devenus fous, les fous devenus psychiatres.- Essayez de considérer ces quatre populations vuesdu côté des psychiatres.- Essayons. Pour un psychiatre, un autre psychiatreest « vrai », un fou est « faux ». Mais à quoi correspondentdonc les deux autres types de pensionnaires ?- lls sont paradoxaux, de doxa, « la loi » et para, « à côté». lls sont en dehors de votre crible de classement.- Je veux bien, mais où est le progrès?- Adoptez maintenant le point de vue d'un psychiatredevenu fou.- Bon. Pour celui -là un autre psychiatre devenu fou sera « vrai ».-Exact.- Et un fou devenu psychiatre sera ... faux.- Tout à fait.- Si je comprends bien, ce sont les fous et les psychiatres qu'il ne parviendra plus à classer.- Vous avez tout compris. Vous avez deux souspopulations, d'un côté l'ensemble {«psychiatres» «fous»}, de l'autre l'ensemble {«psychiatres devenusfous» - «fous devenus psychiatres»}. À l'intérieur d'une même sous-population le vrai des uns est le faux des autres. Mais d'une sous-population à l'autre le décidabledes uns devient l'indécidable des autres, et vice versa. Le concept de relativité du point de vue logique prend tout son sens.- Est -ce à dire que la logique chromatique tourneautour de cela ?- Non, mais c'était pour vous faire sentir ce qui peut émerger d'une logique à plus de deux états. La logique chromatique possède aussi quatre états de vérité, mais ce serait un peu compliqué de vous l'expliquer. De plus cette approche a des aspects « kaléidoscopiques ».- Vous voyez bien qu'il y a quatre « points de vue logiques ». On passe de l'un à l'autre par une rotation de 90°.- Chaque point de vue correspond à ... une logique ?- Exactement. Vous obtenez donc un « générateur de logiques ». Le système sur lequel Sm ail m'a fait plancher possède la même propriété. Le vrai ou toute autre valeur de vérité y sont contingents. C'est la raison pour laquelle ces choses sont si difficile à appréhender. Quant à expliquer pourquoi tout cela permet de résoudredes problèmes plus rapidement, c'est encore une autre paire de manches.
