Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Logique, informatique et paradoxes par Jean-Paul Delahaye POUR LA [SCIENCE 1 (D

Logique, informatique et paradoxes par Jean-Paul Delahaye POUR LA [SCIENCE 1 (DIFFUSION BELINJ 8, rue Férou 75006 Paris Le code de la propriété intellectuelle autorise DANGER .<les copies ou reproductions strictement réservées à l'usage privé du copiste et non destinées à une utilisation collective* (article PHoToCoPlllAGE L, 122-5) ; il autorise également les courtes TUE LE LIVRE citations effectuées dans un but d'exemple et [O] d'illustration. En revanche, *toute représentation ou reproduction intégrale ou partielle, sans le consentement de l'auteur ou de ses ayants droit ou ayants cause, est illiciten (article L. 122-4). Cette représentation ou reproduction, par quelque procédé que ce soit, sans autorisation de l'éditeur ou du Centre français de l'exploitation du droit de copie (3, rue Hautefeuille, 75006 Paris), constituerait donc une contrefaçon sanctionnée par les articles 425 et suivants du Code pénal. O Pour La Science 1987 à 1993 ISBN 2-9029-1894-1 ISSN 0224-5159 Table des matières Préface Calculabilité et machines de Turing L'indécidabilité en mathématiques et en physique Gode1 Machines, prédictions et fin du monde Le désordre total existe-t-il ? La cryptographie quantique Chaînage avant et déduction logique Vote inconscient Complexités Thermodynamique et informatique théorique L'inférence inductive Les virus L'altruisme récompensé L'altruisme perfectionné Algorithmes et preuves probabilistes IP=PSPACE Les automates Les hyperensembles Longueur d'une démonstration Le réalisme en mathématiques et en physique Bibliographie Préface a logique est un domaine paradoxalement paradoxal. Alors qu'on prétend y détermi- ner les règles à respecter pour ne pas tom- ber dans des paradoxes, c'est là qu'on en ren- contre le plus grand nombre. Et l'on ne sait pas toujours les éliminer. Cet affrontement direct avec ce aui fait le plus peur à un être rationnel (la contradiction), cette volonté de traquer l'imprécision et l'incohé- rence ont cependant conduit le logicien à dévelop- per des armes et des techniques qui se révèlent utiles dans d'autres domaines. Ainsi la logique a donné aux mathématiciens le langage formalisé de la théorie des ensembles, qui les met à l'abri des paradoxes (du moins jusqu'à présent) et qui, même s'il est trop étroit pour poser tous les pro- blèmes que les logiciens aiment se poser, est bien assez large pour l'usage pratique des mathémati- ciens (N. Bourbaki, le célèbre mathématicien français polycéphale, s'en contente). La représentation des informations, la mani- pulation symbolique des connaissances, les rap- ports que les vérités entretiennent constituent le domaine de la logique ; il n'est pas étonnant que, lorsqu'il s'agit de construire des machines à mani- puler de l'information, de la connaissance et des vérités, la logique ait son mot à dire. C'est telle- ment vrai que les logiciens avaient pensé aux ordi- nateurs avant même que les ingénieurs ne s'y met- tent. Alan Turing, en 1936, introduisait le concept de calculateur élémentaire (aujourd'hui appelé machine de Tzu-ing), qui n'est rien d'autre que la version abstraite de l'ordinateur. Depuis, logique, informatique et paradoxes s'entremêlent, enrichissant notre compréhension du monde de l'abstrait tout en produisant une connaissance concrète qui s'applique partout et de mieux en mieux. Comme la physique l'a mon- tré depuis belle lurette, l'abstrait et le concret ne sont jamais opposés, mais au service l'un de l'autre. C'est en informatique que les théories mathématiques les plus difficiles s'appliquent le mieux et le d u s radement. et c'est en étudiant les techniques qu'elle rencontre que l'informatique stimule et féconde les théories mathématiques et physiques. Grâce à une série de courts chapitres indé- pendants, que nous avons cherché à rendre attrayants, vous entrerez dans le monde mer- veilleux et fascinant : - de l'indécidabilité (aussi puissantes que soient les machines futures, nous savons déjà qu'elles ne pourront pas tout faire) ; - des paradoxes de la prédiction (qui devraient nous troubler si nous les prenions au sérieux) ; - de l'aléatoire absolu (défini il y a seulement quelques années) ; - de la déduction logique (qu'on n'a jamais fini de comprendre et qui est au centre des travaux de l'intelligence artificielle) ; - de l'induction mécanique (qui mathématise certaines questions philosophiques et leur donne quelquefois des réponses inattendues) ; - de la cryptographie quantique (qui permet ce qu'on croyait impossible et est sur le point de s'appliquer) ; - des hyperensembles (dont chacun d'eux est un paradoxe à lui tout seul et qui pourtant s'organi- sent en une théorie étonnamment cohérente) ; - d'une théorie des stratégies (dont les conclu- sions définissent une morale du comportement social, et éclairent certains aspects de la théorie de l'évolution) ; - des êtres semi-vivants (que sont les virus informatiques et qu'un résultat d'indécidabilité protège contre une élimination définitive) ; - de la complexité des objets et des algorithmes (qu'il faut maîtriser par exemple pour connaître les nombres premiers) ; - des systèmes formels (dont les théorèmes de Gode1 justifient l'importance et expliquent des limites) ; et de bien d'autres découvertes récentes qui renouvellent nos conce~tions fondamentales du monde, et nous montrent un univers où l'esprit tente de comprendre l'esprit, de le recréer et de s'en amuser. Jean-Paul DELAHAYE Calculabilité et machines de Turing Pour de nombreux problèmes, il néxiste pas d'algorithme de résolution. L'indécidabilité provient de difficultés mathématiques insurmontables. Q u'est-ce qu'une méthode de calcul? Jusque dans les années 1930, les mathématiciens l'ignoraient. La faculté étonnante des mathématiques à transformer leurs méthodes et leurs techniques en objets d'études mathématiques les rapproche de la philosophie et est souvent l'occasion d'introduire de nouveaux concepts et de formuler de nouveaux résultats. Cette faculté dr(autoréflexivité» permet, par exemple, d'étudier des objets qui sont eux-mêmes les théories mathématiques. La partie des mathématiques qui se consacre à ce travail est la logique mathématique ; parmi ses notions, il y a celles d'algorithme, de fonction calculable, de décidabilité des problèmes et des énoncés. Grâce aux travaux des logiciens, les mathé- maticiens savent précisément ce qu'est une méthode de calcul ; ils savent assez précisément quels problèmes ces méthodes peuvent traiter et, mieux encore, ils savent que certains problèmes n'auront jamais de solution. Ces problèmes pour lesquels on démontre qu'il n'existe aucune méthode de résolution sont appelés problèmes (<indécidables». Dans les années 1930, les premiers exemples de tels pro- blèmes semblaient artificiels, mais on a rapide- ment découvert que des problèmes simples sont de ce type. Notamment, en informatique, de nom- breuses questions naturelles sont indécidables. Est-il utile de savoir qu'un problème est indécidable? Certainement : si un problème est indécidable, il ne faut plus perdre son temps à en chercher une solution, et il est préférable de chercher un problème dérivé du premier mais plus simple, dont on doit ensuite déterminer la décidabilité. Alors qu'ils exploraient la nature du calcul, les logiciens découvrirent la notion d'énoncé indé- cidable, encore nommé énoncé indécidable de Godel. Kurt Godel, en 1931, démontra le premier théorème important à leur sujet : ce sont des énoncés impossibles à démontrer, ainsi que leur négation. Eindécidabilité d'un énoncé est tou- jours relative à un système de démonstrations (OU système formel) ; elle ne doit pas être confon- due avec l'indécidabilité d'un problème qui, elle, est absolue. Nous verrons les liens entre ces deux notions. De l'algorithme à l'indécidabilité La notion informelle d'algorithme est ancienne : une recette de cuisine, un jeu d'ins- tructions pour réaliser un tricot, un procédé élé- mentaire pour additionner deux nombres sont des algorithmes (le mot vient du nom d'un mathé- maticien persan du Ixe siècle, Al Khwarizmi). Tels des Monsieur Jourdain, les mathémati- ciens recherchaient et élaboraient des algo- rithmes bien avant que le concept ne soit bien défini. Au début du siècle, encore, ils ne soup- tonnaient pas que l'on pourrait préciser la notion. Le dixième problème de David Hilbert, formulé avec 23 autres lors du Congrès interna- tional des mathématiciens, à Paris, en 1900, se réfère implicitement à la notion d'algorithme. Hilbert demandait que l'on recherche une méthode générale indiquant quelles équations diophantiennes ont des solutions (dans ces équations, les coefficients sont des nombres entiers, et l'on cherche des solutions en nombres entiers). Il aurait sans doute aimé CALCULABILITE ET MACHINES DE TURING 9 savoir que ce pro- blème est indéci- dable, comme cela fut démontré p a r J u r i Vladimirovic Matj a- sevich e n 1970. Le travail d'iden- tification et de formu- lation de l a notion d'algorithme fut effec- tué en plusieurs étapes, entre 1931 et 1936, par Alonzo Church, Stephen Kleene, Alan Turing et Godel. Ils introdui- sirent plusieurs clas- ses de fonctions, dont ils montrèrent en- suite qu'elles coïnci- daient, et qui se révé- lèrent être la classe des fonctions calcu- lables : une fonction est calculable s'il existe une façon de la décrire qui permette effectivement d'en calculer toutes les valeurs. La définition précise de la notion de fonction calculable fixe celle d'algo- rithme. Depuis les années 1930, on a étudié la décidabilité de nom- breux problèmes, et l'on a parfois découvert que des problèmes d'apparence simple étaient indécidables ; inversement on a trouvé des algorithmes à des problèmes qui étaient jusqu'alors res- tés ouverts. Chaque année, des dizaines de tels résultats sont éta- blis dans de nombreux domaines des mathé- uploads/Philosophie/ logique-que-et-paradoxes.pdf