CRYPTOGRAPHIE MULTIVARIABLE
 

 

 

 

 

 

 

Pierre Vandeginste dans mensuel 420
daté juin 2008 -

Depuis vingt ans, on parle de la cryptographie multivariable comme d'un candidat bien placé à la succession du plus utilisé des algorithmes de cryptage : RSA. Mais son histoire est jalonnée d'attaques. On l'a cru morte plusieurs fois, elle a toujours su rebondir. Affaiblie, elle réagit encore...

Pendant près de vingt ans, on a vu en elle un successeur potentiel du célèbre algorithme RSA, peut-être la solution d'avenir de la cryptologie, celle qui nous sauverait quand les physiciens auront mis au point leur ordinateur quantique. Malgré son nom difficile à porter, la cryptographie multivariable était promise à un glorieux futur. Mais aujourd'hui de plus en plus de spécialistes de la science du secret lui prédisent un horizon limité, voire plus d'avenir du tout ! Voici la chronique mouvementée, tout en hauts et bas, de cette approche du chiffrement.
Un tournant dans l'histoire de la cryptographie se situe en 1994 quand l'Américain Peter Shor, des laboratoires ATT, propose un algorithme capable de factoriser - c'est-à-dire de décomposer en facteurs premiers - un nombre entier en un temps très raisonnable à l'aide d'un ordinateur quantique [1]. Dès lors, le petit monde de la cryptologie comprend que le fameux algorithme RSA, le plus utilisé dans le domaine, n'est pas immortel. Car un élément essentiel de sa cuirasse est précisément la difficulté de factoriser. Et l'ordinateur quantique, croit-on, craint-on à tort ou à raison, finira bien par arriver.

Cette menace, même hypothétique, oblige les spécialistes à s'interroger sur ce que va devenir la cryptographie à clé publique. D'autant qu'elle ne sert pas seulement à chiffrer des messages, mais également à résoudre un autre problème classique en cryptographie, la signature numérique. Ici, il ne s'agit plus de brouiller un message pour préserver sa confiden-tialité, mais de permettre au destinataire de vérifier qu'il provient bien de l'émetteur indiqué. Le message est alors chiffré par ce dernier à l'aide de sa clé secrète et déchiffré avec sa clé publique par le destinataire. En associant une « fonction de hachage » qui fournit un « résumé » compact d'un document à transmettre à certains schémas de cryptographie à clé publique, on obtient un procédé de signature électronique efficace, et qui démontre en plus l'intégrité du message, sa non-altération.

Système d'équations
La cryptographie s'est rendue indispensable dans notre société numérique. On comprend alors l'urgence d'en savoir plus sur ce qui pourrait bien détruire l'édifice : c'est ainsi que la « Post quantum Cryptography » devient un thème de recherche à part entière et fait l'objet de workshops réputés.
Par quoi donc remplacer RSA, puisqu'il est menacé ? Parmi les solutions envisagées, une a longtemps été présentée comme la plus prometteuse : la cryptographie multivariable. De quoi s'agit-il ? Essentiellement, cette nouvelle façon de chiffrer repose sur la résolution d'un système comportant de nombreuses équations contenant un grand nombre de variables. Voici un exemple simple avec trois variables, trois équations du second degré quadratiques :
y1 = x1 x1 + x1 x3 + x2 x3 + x3 x3
y2 = x1 x2 + x2 x2 + x3 x3
y3 = x1 x1 + x1 x2 + x2 x3 + x3 x3
Les xi représentent le message à chiffrer. Il est facile de calculer les yi. Mais il est en revanche beaucoup plus difficile de retrouver les xi, à partir des yi. Dans la pratique, on utilise jusqu'à une centaine d'équations souvent quadratiques portant sur une centaine de variables souvent binaires.
Quels sont les avantages de la cryptographie multivariable ? Tout d'abord, aucun algorithme quantique n'a jamais été proposé pour la démolir. Ensuite, elle présente l'avantage, en théorie en tout cas, de reposer sur un problème dit « NP-complet » lire « Le "pire des cas" chez les mathématiciens », p. 32, une classe de problèmes mathématiques réputés les plus « coriaces ». Enfin, elle vient enrichir la palette des algorithmes de cryptographie : utile et nécessaire en raison de besoins très variés en la matière. Télévision cryptée, transmissions militaires, cartes à puce, sécurisation des transactions sur Internet et protection des mots de passe sur un disque dur..., autant d'applications disparates qui demandent à être satisfaites. On exige ici des clés compactes, là des temps de calcul infimes, ailleurs, les deux à la fois.

Puissance limitée
La cryptographie multivariable est bien adaptée aux situations où l'on dispose d'une puissance de calcul limitée. Elle est particulièrement efficace pour le chiffrement et la vérification de signature en particulier. Cela parce que ses algorithmes manipulent des « petits » objets, typiquement des nombres codés sur 100 bits, contre 1 000 pour RSA.
1988, congrès européen de cryptographie Eurocrypt. Deux Japonais, Tsutomu Matsumoto et Hideki Imai, proposent un premier schéma exploitant le principe de cryptographie multivariable, qui restera connu sous le nom « Matsumoto-Imai » MI, ou encore sous le sigle C*. Dans leur approche, le degré des équations est, comme dans notre exemple, limité à deux : on a donc parlé à ce sujet de cryptographie multivariable quadratique MQ. Le schéma MI utilise tout d'abord une fonction Y = FX = Xe dans un corps* fini. Dans un second temps, il « enferme » cette fonction entre deux applications linéaires changements de variables T et S. On obtient ainsi la fonction de chiffrement T o F o S, dans laquelle T et S sont secrètes.

« Huile et vinaigre »
Le schéma MI tient bon sept ans. Jusqu'à ce qu'une équipe française entre dans la danse ! Jacques Patarin, à l'époque chez Bull CP8 mais actuellement au laboratoire Prism de l'université de Versailles, casse en 1995 le schéma « Matsumoto-Imai » [2]. Son papier, présenté la même année à Crypto, le congrès mondial du domaine, fait sensation.
Est-ce là la fin de la cryptographie multivariable ? Pas vraiment. Car dans la foulée de sa cryptanalyse victorieuse, J. Patarin a proposé de nouveaux schémas de cryptographie multivariable. À Eurocrypt 96, le Français présente un algorithme qui s'éloigne, en la généralisant le monôme devient un polynôme, de la proposition de Matsumoto et d'Imai : HFE « Hidden Field Equations ». Une approche particulièrement économe en temps de calcul... J. Patarin détient depuis lors un brevet sur HFE, qui a déjà subi de nombreuses attaques, mais qui résiste pour le moment.
Le chercheur poursuit en 1997 en proposant un algorithme de signature, très proche du schéma « Matsumoto-Imai ». Il le nomme « Oil and Vinegar » OV. Cela parce qu'il sépare les variables de son système d'équations en deux variétés : les hi pour « huile » et les vi pour « vinaigre ». Les équations OV comportent des produits « vinaigre »-« vinaigre » et « huile »-« vinaigre », mais pas de « huile »-« huile »...
Mais « Oil and Vinegar » va chuter. Au congrès Crypto 98, il est « cassé » par les Israéliens Adi Shamir et Aviad Kipnis. J. Patarin le répare aussitôt pour obtenir « Unbalanced Oil and Vinegar » avec cette fois beaucoup plus de variables « vinaigre » que d'« huile », qu'il publiera d'ailleurs avec Louis Goubin et Aviad Kipnis en 1999.

Deux ans plus tard, s'appuyant sur HFE, J. Patarin publie « SFLASH [3] », avec Nicolas Courtois et Louis Goubin, de l'université de Versailles. Il s'agit d'un algorithme de signature numérique très convaincant, notamment parce qu'il est remarquablement économe en puissance de calcul. Il connaîtra un vrai succès d'estime. La crédibilité de la cryptographie multivariable s'en trouve requinquée. L'initiative européenne « Nessie », visant à homologuer un certain nombre d'outils de cryptographie réputés fiables, étudie la candidature de SFLASH et finit par le sélectionner en 2003. L'une de ses grandes qualités : la puissance de calcul requise est aussi raisonnable pour calculer la signature que pour la vérifier, ce qui en fait une bonne solution pour les cartes à puce les moins chères. La cryptographie multivariable semble avoir enfin réussi à s'imposer, au moins dans cette niche de la signature dite « spartiate ».

Pression croissante
Un contretemps, pourtant, manque de gâcher la fête. Henri Gilbert, de France Télécom, a en effet publié lors d'Eurocrypt 2002 une attaque contre SFLASH. Celle-ci ne remet pas en question les fondements de l'algorithme mais oblige à réviser ses paramètres. Le « prix à payer » pour la grande rapidité de calcul de SFLASH est, à la base, la taille des clés publiques nécessaires. Elles sont en effet plus longues que celles de RSA qui font 1 024 bits : un sérieux inconvénient dans un environnement « spartiate » de carte à puce. Dans le SFLASH original, la clé avait été fixée à 2,2 kilo-octets. Pour contrer l'attaque, J. Patarin publie un SFLASH v2 dont la clé publique est portée à 15,4 kilo-octets. Grâce à quoi cette solution retrouve un niveau de sécurité appréciable. Il publiera même en 2003 une troisième version, SFLASH v3, dont la clé publique est portée à 112 kilo-octets. C'est un peu lourd pour une carte à puce économique actuelle, mais cela peut être acceptable pour une future génération de cartes. En tout cas, si la v2 venait à être menacée, la réponse serait prête.
2003, congrès Crypto, nouvelle attaque contre la cryptographie multivariable. Un assaut sur HFE, jugé sévère, est porté par les Français Jean-Charles Faugère et Antoine Joux. Le climat s'alourdit.
En 2005, encore un coup dur. Cette fois, l'attaque est lancée contre le schéma PMI « Perturbated Matsumoto-Imai », variation du thème lancé par Matsumoto et Imai. PMI a été introduit un an plus tôt par Jintai Ding, de l'université de Cincinnati. Dans le rôle des casseurs, une équipe de l'École normale supérieure ENS, dirigée par Jacques Stern avec Pierre-Alain Fouque et Louis Granboulan. Elle a adopté une stratégie d'attaque, dénommée « cryptanalyse différentielle ».
C'est presque la même équipe Vivien Dubois, P.-A. Fouque et J. Stern de l'ENS qui s'attaque ensuite à un SFLASH affaibli par des « paramètres modifiés ». Il s'agit là d'une démarche classique en cryptanalyse que de s'en prendre, dans un premier temps, à une version dégradée du schéma que l'on veut casser. Et ça marche ! Une première publication est acceptée pour Eurocrypt 2007 [4]. SFLASH est en train de tomber de son piédestal.
De passage à l'ENS, Adi Shamir le « S » de RSA, l'un des papes du domaine s'intéresse au sujet. Après avoir étudié les résultats obtenus, il estime que l'approche employée devrait également faire chuter SFLASH dans sa version normale. Peu de temps après, J. Stern trouve le point faible. Et fin novembre 2006, SFLASH lui-même est cassé. La technique employée démolit aussi bien les deux premières versions que la fameuse v3 qui devait prolonger l'existence du schéma. Ce travail va évidemment faire beaucoup de bruit à Crypto 2007

[5].

HFE résiste
« S'il n'y avait pas eu le précédent de PMI, nous n'aurions sans doute jamais songé à attaquer SFLASH, estime P.-A. Fouque. Ce premier succès aura servi de marchepied. Notre Graal, c'est désormais l'attaque contre HFE, qui résiste encore, malgré quelques assauts qui ont obligé à modifier ses paramètres. Il est déjà évident que certaines clés HFE sont faibles... »
Peut-on aller jusqu'à dire que la cryptographie multivariable est désormais « finie » ? Attention à ne pas jeter le bébé avec l'eau du bain... P.-A. Fouque admet qu'elle a « du plomb dans l'aile », mais, dans le même temps, estime qu'elle reste « très intéressante ». J. Patarin est, quant à lui, plus optimiste sur la survie de cette approche : « Adi Shamir pense que la base de la cryptographie multivariable est saine. Il essaie de casser HFE depuis un an, sans succès. »
Et si elle résiste à ce demi-dieu de la cryptographie... L'équipe de J. Patarin présentera bientôt à Pékin un nouveau schéma multivariable sur lequel il fonde de grands espoirs. Il n'en dit pas grand-chose, sauf le nom, qui fait saliver : « barre de chocolat ».

En deux mots À la fin des années 1980, deux Japonais proposent un type de cryptographie à clé publique, prometteur car efficace et peu gourmand en calculs. D'autres s'en inspirent, notamment en France, où est conçu un algorithme de signature numérique, SFLASH, qui connaîtra son heure de gloire. Mais la robustesse de ce que l'on appelle la cryptographie multivariable pose question. Elle n'a cessé de subir les assauts des cryptanalystes, ces « casseurs » de codes, et a fini par céder du terrain. Il reste aujourd'hui quelques algorithmes notamment celui dévoué au chiffrement, HFE, qui résiste tant bien que mal depuis une douzaine d'années.

[1] P. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, FOCS'94, IEEE, 1994. Révision : arXiv:quant-ph/9508027v2.
[2] J. Patarin, Crypto'95, p. 248, Springer-Verlag, 1995.
[3] J. Patarin et al., CT-RSA 2001, LNCS 2020, p. 298, Springer-Verlag, 2001.
[4] V. Dubois et al., LNCS 4515, p. 264, Springer-Verlag, 2007.
[5] V. Dubois et al., Crypto'07, LNCS 4622, p. 1, Springer-Verlag, 2007.

NOTES
*Un corps est un ensemble muni de deux lois de composition respectant un certain nombre de critères.

 

DOCUMENT   larecherche.fr    LIEN

 
 
 
  INTELLIGENCE ARTIFICIELLE
 

Course effrénée à l’intelligence artificielle
Juin 2016
Toujours plus puissants et plus « intelligents », les ordinateurs ne se réduisent plus à la simple exécution de tâches répétitives. Devenus irremplaçables dans les calculs et les opérations logiques, le traitement et la transmission d’informations,  la manipulation d’images, le pilotage de robots… ils sont aujourd’hui capables d’apprendre par eux-mêmes grâce à des réseaux de neurones artificiels calqués sur le cerveau humain.

Qu’est-ce que l’intelligence artificielle ?
L’intelligence artificielle (IA) est une discipline scientifique dont le but est de faire faire par une machine des tâches que l'homme accomplit en utilisant son intelligence.

Cette discipline est née en 1956 avec les travaux du mathématicien Alan Turing, qui s’intéressa à la « conscience » des machines. Il pensait que celles-ci seraient un jour capables de nous imiter (nous, les humains) et de dialoguer avec nous. Il était entre autre persuadé qu’un programme d’échecs serait capable de battre un champion du monde. Sa prophétie se réalisa en 1997 lorsque Kasparov fut battu par Deep Blue.

À l’origine des travaux de recherche, l’intelligence artificielle se fonde sur :

les mathématiques ;
les algorithmes, c’est-à-dire les programmes qu’un ordinateur exécute grâce à des langages de programmation ;
la sémantique, c’est-à-dire l’étude du langage et du sens des mots.

Depuis quelques années, l’IA puise de nouvelles sources d'inspiration dans le fonctionnement du cerveau humain. Le laboratoire  Google X, travaille sur les réseaux neuronaux artificiels profonds. Les chercheurs ont mis en place un réseau de plusieurs millions de neurones artificiels connectés à des milliers de processeurs, qui permet aux machines d’apprendre en partie par elles-mêmes.

Avec cette nouvelle capacité qu’ont les machines, l’avancement de l’IA progresse très rapidement. Les ordinateurs étaient capables :

de résoudre des problèmes mathématiques ;
d’analyser des données en vue de les modéliser : cartes météo, par exemple ;
de raisonner de manière logique : exemple des jeux de stratégie.
Ils peuvent désormais :

traduire des langues de manière automatique ;
reconnaître une voix : exemple des assistants vocaux comme Siri ou Cortana ;
comprendre la parole et le langage naturel, avec l'exemple des logiciels de dictée vocale : je parle et l’ordinateur écrit ce que je dis ;
reconnaître les formes, les visages, les images ;
acquérir des connaissances et apprendre par l’expérience : le système apprend par lui-même et progresse en permanence, exemple du robot Icub.

L’apprentissage en profondeur
L'objectif des chercheurs et des entreprises qui travaillent sur l’intelligence artificielle est que les logiciels puissent un jour comprendre toutes les données qu’un humain peut traiter. Il s'agit aussi bien de ce que l'humain perçoit (grâce aux informations que nos sens nous fournissent), que de la compréhension des données et du raisonnement.

Déjà, les assistants personnels intelligents - tels Siri, Cortana ou Google now - se pilotent et obéissent à la voix une fois que certaines informations nous concernant ont été entrées dans leur mémoire. Ils rendent des services pour gérer un agenda, créer des rappels, dicter un sms ou une recherche à effectuer sur le Web, lancer un itinéraire, trouver l’adresse d’un restaurant et répondre même à certaines questions. Siri est ainsi capable d’identifier un morceau de musique  et de nous donner son titre et le nom de son interprète grâce à son moteur de reconnaissance musicale.

Le géant américain Google dispose de milliards de données collectées par ses robots qui analysent en permanence les innombrables bases qui stockent des pages Web, des livres numérisés, des images et des vidéos ; celui lui permet, avec son projet "Google Brain", de poursuivre le développement d’une intelligence artificielle fondée sur l’apprentissage en profondeur des machines.

À l’instar du cerveau humain qui apprend à reconnaître une image et sait distinguer un chat d’un chien, ou sait faire la différence entre un « sot », un « seau » et un « saut »,  l’objectif de ce projet de recherche est d’améliorer la compréhension des machines pour que nous puissions un jour dialoguer avec elles en langage « naturel ». 


Zoom sur quelques projets de recherche en intelligence artificielle
Les machines sont aujourd’hui plus performantes que nous pour raisonner de manière logique : preuve en est le programme AlphaGo de Google qui a remporté 4 parties sur 5 contre un des meilleurs joueurs mondiaux de go en mars dernier. Cette victoire montre la puissance et la capacité d’apprentissage des programmes d’IA car le jeu de go propose un nombre incommensurable de combinaisons à explorer pour trouver la meilleure tactique.

Par ailleurs, le programme d’IA Deep Dream du même géant américain a pour but d’apprendre aux machines à générer de l’art et à développer la créativité des machines. On « nourrit » leur mémoire de milliards d’images pour leur apprendre à classifier des formes, des motifs, des couleurs. Une fois entraîné, le réseau de neurones est capable d’analyser et de distinguer des formes dans une image, puis par association de formes, il peut trouver des images similaires : lorsqu’on lui montre l’image d’un ciel avec des nuages, Deep Dream peut y voir des oiseaux, des anges, des arbres, des palais, et toute sorte d’images issues de l’imaginaire humain. Le programme imite ainsi notre capacité à reconnaître des visages, des corps ou des animaux dans des formes.


La Géode vue par le générateur Deep Dream
Depuis que le code source du projet est à disposition des développeurs, des milliers d’images ont été soumises à Deep Dream, qui a généré des images loufoques et psychédéliques, bourrées de têtes de chiens ou d’animaux étranges. Ces images produites par des machines font même l’objet d’un mouvement artistique appelé « inceptionisme » ! Ces machines, aussi intelligentes soient-elles, ne sont pourtant pas des artistes : les productions qu’elles génèrent sont issues de programmes et non pas de leur imagination et de leur sensibilité.

Il est clair que l’intelligence artificielle n’en est qu’à ces balbutiements et n’a pas fini de nous ébahir. Elle peut nous rendre bien des services et nous aider à vivre mieux. Mais gardons toujours à l’esprit qu’une intelligence froide et sans conscience peut nous conduire à notre perte. Alors, servons-nous de notre intelligence d’humain et  prenons le temps de cogiter la formule de Rabelais : « Science sans conscience n’est que ruine de l’âme ».

 

DOCUMENT       cite-sciences.fr        LIEN

 
 
 
  LES FLUIDES PERDENT LA MÉMOIRE
 


MATHÉMATIQUES
Les fluides perdent la mémoire


mathématiques - par Propos recueillis par Philippe Pajot dans mensuel n°454 daté juillet 2011 à la page 18 (592 mots) | Gratuit
L'étude statistique des fluides nécessite que les systèmes étudiés ne dépendent pas de leur état initial. Cette hypothèse est maintenant justifiée mathématiquement sur plusieurs équations utilisées par les physiciens pour décrire des systèmes réels.

Qu'est ce que l'hypothèse ergodique ?

M.H. Imaginée par Ludwig Boltzmann à la fin du XIXe siècle pour les besoins de la physique statistique naissante, cette hypothèse stipule que, dans un gaz que l'on laisse évoluer, l'état observé après un temps suffisamment long ne dépend pas de l'état de départ. Autrement dit, un système ergodique perd la mémoire de sa condition initiale. Mathématiquement, cela revient à remplacer les moyennes temporelles par des moyennes d'ensemble.

Cette hypothèse est-elle importante en physique ?

M.H. Elle est fondamentale lorsque l'on souhaite décrire statistiquement un système physique, et pas seulement les gaz. Partant d'un système dans un état précis et qui évolue de manière plus ou moins déterministe, l'hypothèse ergodique permet de le décrire de manière statistique, en termes d'évolution de probabilités de l'état du système. Les physiciens font souvent cette hypothèse de manière implicite, mais sans justification mathématique. Nos travaux ont apporté cette justification dans plusieurs domaines, notamment des situations de transition de phase dans des alliages.

À quels systèmes vous êtes-vous intéressé ?

M.H. Nous avons d'abord voulu justifier cette hypothèse fondamentale dans un modèle simplifié de turbulence dans un fluide. Partant d'un fluide où l'on injectait de l'énergie à une longueur fixe de manière stationnaire - comme si on le remuait avec une cuillère de taille donnée -, nous voulions vérifier à quelle condition le système était ergodique. Pour cela, nous avons étudié la turbulence à l'aide de l'équation de Navier-Stokes, l'équation de base qui décrit le mouvement d'un fluide. Il s'agit d'une équation dissipative que nous avons restreint à la géométrie la plus simple que l'on puisse imaginer : le fluide est confiné à la surface d'un tore un tore est équivalent à un rectangle dont les bords sont joints deux à deux.

Qu'avez-vous démontré ?

M.H. Nous avons pu démontrer, ce qu'on suspectait depuis longtemps, que de manière générique, le système est ergodique [1] .

La seule situation où l'ergodicité disparaît, c'est lorsque l'injection d'énergie le « forçage » est périodique avec une période plus petite que la taille du système. Ce résultat, publié en 2006, a été bien reçu, d'autant que, dans la communauté qui travaille sur les équations aux dérivées partielles stochastiques, d'autres groupes essayaient de l'obtenir.

Qu'est-ce qui vous a permis de débloquer la situation ?

M.H. Il nous fallait notamment comprendre comment la force qui maintient le système dans un état turbulent se transmet dans tout le système. La difficulté est qu'on a une évolution dans un espace de dimension infinie l'espace de fonction de l'équation et qu'en mélangeant on introduit du hasard dans un nombre fini de directions. Nous avons donc dû comprendre comment cet aléa se transmet aux autres directions et établir mathématiquement le critère d'ergodicité lire « Équations dissipatives », ci-dessus.

À quels autres systèmes avez-vous étendu ce résultat ?

M.H. D'abord à la sphère, et à des géométries différentes. Puis nous avons montré que d'autres équations aux dérivées partielles dissipatives sont ergodiques. Récemment, nous y sommes parvenus pour les équations d'Allen-Cahn, qui décrivent la dynamique des transitions de phase dans les alliages métalliques [2] . En revanche, il n'est pas question d'attaquer les équations de Navier-Stokes tridimensionnelles, car ces équations sont si mal connues qu'on ignore même si leur solution est unique. C'est l'un des « problèmes du millénaire », pour la résolution desquels l'institut Clay a promis un million de dollars.

Par Propos recueillis par Philippe Pajot

 

DOCUMENT      larecherche.fr     LIEN

 
 
 
  UN ORDINATEUR POURRA-T-IL RÉPONDRE À CETTE QUESTION ?
 


MATHÉMATIQUES
Un ordinateur pourra-t-il répondre à cette question ?


mathématiques - par Propos recueillis par Philippe Pajot dans mensuel n°449 daté février 2011 à la page 18 (632 mots) | Gratuit
Pour vérifier que des systèmes informatiques fonctionneront comme prévu, on ne peut pas tester leur nombre infini de configurations. Les informaticiens ont alors recours à la logique.

Pourquoi utilise-t-on la logique en informatique théorique ?

T.C. Il existe des questions auxquelles aucun ordinateur ne peut répondre, quelle que soit la manière dont il est programmé ou sa puissance. Partant de ce résultat fondamental, une partie de l'informatique théorique tente de déterminer quelles sont les questions que l'on peut résoudre, ce que l'on qualifie de décidable. La logique permet d'aborder ce problème. On se place dans un cadre d'un formalisme logique : un ensemble d'énoncés - des phrases mathématiques - qui peuvent être vrais ou non, et on cherche à programmer un ordinateur pour répondre aux énoncés.

Comment choisit-on ce formalisme logique ?

T.C. Il en existe beaucoup, élaborés dans le cadre d'autres questions mathématiques, mais la plupart de ces formalismes sont indécidables : aucun ordinateur ne peut dire si un énoncé donné du formalisme est vrai ou non. Cela oblige à utiliser des formalismes logiques assez simples. Je m'intéresse en particulier à la « logique monadique du second ordre », et ce qu'elle peut exprimer sur les suites de symboles par exemple des lettres, éventuellement de longueur infinie, ce que les informaticiens nomment des « mots », et possédant parfois des embranchements, les « arbres ».

Que peut-on montrer sur la logique monadique ?

T.C. Le résultat fondamental, établi en 1969, est que ce formalisme logique est décidable sur les mots et sur les arbres infinis. Cela signifie que, si on a un énoncé exprimé dans ce formalisme, un ordinateur est capable de dire s'il existe une séquence infinie de symboles pour laquelle l'énoncé est vrai. Par exemple, l'énoncé : un mot contient une infinité de lettres « a », une infinité de lettres « b », et entre deux lettres « a », il y a un nombre pair de lettres « b », est vrai sur le mot infini « abbabbabb »... De même, on saura dire s'il existe un arbre infini pour lequel un énoncé est vrai. Ce résultat a été démontré en établissant une équivalence entre logique et automates finis, des objets mathématiques conçus pour effectuer des calculs simples sur les mots ou sur les arbres. Il s'agit de machines abstraites dotées d'un nombre fini d'états. Un automate va commencer au début d'un mot, puis, lettre par lettre, va lire ce mot, son état évoluant à chaque étape. À la fin, l'automate répondra vrai ou faux. Sur les mots infinis, un automate pourra par exemple détecter l'apparition d'une infinité de lettres « a ». C'est en traduisant la logique monadique en automates équivalents que le résultat de décidabilité a été démontré.

Comment avez-vous étendu ce résultat ?

T.C. Ces questions sont à la frontière de ce qui est décidable. Ainsi, si on s'autorise une extension a priori mineure à la logique, on sort en général du domaine décidable : toute la théorie s'effondre. J'ai tenté d'étendre cette logique à un formalisme quantitatif. Au lieu de dire si un énoncé est vrai ou faux, ce formalisme permet de dire s'il est plus ou moins vrai. Cette logique permet de mesurer des choses, de compter. En montrant son équivalence avec de nouvelles formes d'automates, nous avons généralisé le résultat fondamental à cette nouvelle logique, sur les mots et sur les arbres les arbres finis pour l'instant [1] . Un aspect intéressant du cas des arbres finis est que sa démonstration utilise la théorie des jeux, une technique essentielle pour la démonstration du résultat de 1969 sur les arbres infinis voir encadré. Les jeux permettent de voir la vérité d'un énoncé logique comme un jeu au cours duquel l'un des joueurs va tenter de montrer que l'énoncé est vrai quand l'autre va essayer de le réfuter.

Par Propos recueillis par Philippe Pajot

 

DOCUMENT      larecherche.fr     LIEN

 
 
 
Page : [ 1 2 3 4 5 6 7 8 ] - Suivante
 
 
 


Accueil - Initiation musicale - Instruments - Solfège - Harmonie - Instruments - Vidéos - Nous contacter - Liens - Mentions légales /confidentialité

Initiation musicale Toulon

-

Cours de guitare Toulon

-

Initiation à la musique Toulon

-

Cours de musique Toulon

-

initiation piano Toulon

-

initiation saxophone Toulon

-
initiation flute Toulon
-

initiation guitare Toulon

Google