Remerciez-le!

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

Les Métamorphoses du calcul Pour plus de livres rejoignez nous sur Heights-book

Les Métamorphoses du calcul Pour plus de livres rejoignez nous sur Heights-book.blogspot.com Gilles Dowek Les étalllorphoses du calcul Une étonnante histoire de mathématiques Copyright © Le Pommier, 2007 Tous droits réservés ISBN 2-7465-0324-3 239 rue Saint-Jacques 75005 Paris www.editions-lepommier.fr À Gérard Huet Merci à Pablo Arrighi, Sophie Bancquart, Jacques Deschamps, Joëlle Fouéré, Sophie Le Callennec, Guiseppe Longo, Alexandre Miquel, Thierry Paul et Benjamin Werner, qui ont bien voulu relire certaines parties de ce livre. Sommaire Les mathématiques à la conquête de nouveaux espaces ..... 9 Première partie: une origine ancienne 1. De la préhistoire des mathématiques aux mathématiques grecques ......................... 15 2. Deux mille ans de calcul ............................. 29 Deuxième partie: l'âge classique 3. La logique des prédicats ............................. 49 4. Du problème de la décision au théorème de Church ..... 67 5. La thèse de Church ................................. 83 6. Une tentative de donner sa place au calcul en mathématiques: le lambda-calcul ................. 103 7. La constructivité ................................... 109 8. Les démonstrations constructives et les algorithmes .... 121 Troisième partie: la crise de la méthode axiomatique 9. La théorie intuitionniste des types ................... 131 10. La démonstration automatique ..................... 141 11. La vérification des démonstrations .................. 155 12. Des nouvelles du terrain ........................... 163 13. Les instruments ................................... 181 14. En finir avec1es axiomes? .......................... 195 Au terme de ce périple... . ............................ 199 Annexes Repères biographiques ............................... 205 Bibliographie ........................................ 215 Index ............................................... 221 INTRODUCTION Les mathématiques à la conquête de nouveaux espaces On l'a beaucoup dit, le siècle qui vient de s'achever a été le véritable âge d'or des mathématiques: les mathématiques se sont davantage développées au cours du XX" siècle que pendant l'ensemble des siècles qui l'ont précédé. Il est probable, cepen- dant, que le siècle qui s'ouvre sera tout aussi exceptionnel pour les mathématiques: un siècle au cours duquel elles se métamor- phoseront autant, si ce n'est davantage, qu'au XX" siècle. L'un des signes qui nous invitent à le penser est une transformation pro- gressive, depuis le début des années soixante-dix, de ce qui constitue le socle même de la méthode mathématique: la notion de démonstration. Et cette transformation remet sur le devant de la scène un concept mathématique ancien, mais quelque peu négligé: celui de calcul. L'idée que le calcul puisse être la clé d'une révolution peut sembler paradoxale. Les algorithmes qui permettent, par exemple, d'effectuer des additions et des multiplications sont souvent perçus comme une partie élémentaire du savoir mathé- matique, et effectuer ces calculs est souvent perçu comme une activité peu créative et ennuyeuse. Les mathématiciens ne sont 9 LES MÉTAMORPHOSES DU CALCUL eux-mêmes pas sans préjugés à l'égard du calcul, comme René Thom qui déclarait: « Une grande partie de mes affirmations relève de la pure spéculation; on pourra sans doute les traiter de rêveries. J'accepte la qualification. [ ... ] Au moment où tant de savants calculent de par le monde, n'est-il pas souhaitable que d'aucuns, s'ils le peuvent, rêvent? » Tenter de faire rêver avec le calcul constitue donc sans doute un défi. .. Ce préjugé à l'encontre du calcul se retrouve malheureu- sement jusque dans la définition même de la notion de démons- tration mathématique. Depuis Euclide, on définit, en effet, une démonstration comme un raisonnement, construit à l'aide d'axiomes et de règles de déduction. Mais résoudre un problème mathématique demande-t-il uniquement de construire un rai- sonnement? La pratique des mathématiques ne nous a-t-elle pas plutôt appris que cela demande une subtile articulation d'étapes de raisonnement et d'étapes de calcul? En se restreignant au rai- sonnement, la méthode axiomatique propose sans doute une vision restreinte des mathématiques. Et c'est précisément par la critique de cette méthode axiomatique trop restrictive que le cal- cul réapparaît dans les mathématiques. Plusieurs travaux, non toujours connectés les uns aux autres, remettent progressive- ment en cause cette prééminence du raisonnement sur le calcul, pour proposer une vision plus équilibrée dans laquelle l'un et l'autre jouent des rôles complémentaires. Cette révolution, qui nous amène à repenser les rapports entre le raisonnement et le calcul, nous pousse également à repenser le dialogue entre les mathématiques et les sciences de la nature, telles la physique ou la biologie, en particulier la vieille question de la déraisonnable efficacité des mathématiques dans 10 INTRODUCTION ces sciences, ainsi qu'une question plus récente relative à la forme logique des théories de la nature. Elle éclaire également d'une lumière nouvelle certains concepts philosophiques, comme ceux de jugement analytique et synthétique. Elle nous amène aussi à nous interroger sur les liens entre les mathéma- tiques et l'informatique, et sur la singularité des mathématiques, qui semblent l'unique science à ne pas utiliser d'instruments. Enfin - et c'est certainement le plus intéressant -, elle nous laisse entrevoir de nouvelles manières de résoudre des pro- blèmes mathématiques, qui s'affranchissent des limites arbi- traires que la technologie du passé a imposées à la taille des démonstrations: les mathématiques sont peut-être en train de partir à la conquête d'espaces jusqu'alors inaccessibles. Naturellement, cette crise de la méthode axiomatique n'est pas sortie de rien. Elle était annoncée, depuis la première moitié du xxe siècle, par des signes précurseurs, en particulier par le développement de deux théories qui, sans remettre en cause la méthode axiomatique, ont contribué à redonner une certaine place au calcul au sein de l'édifice mathématique: la théorie de la calculabilité et la théorie de la constructivité. Ce récit de la crise de la méthode axiomatique sera donc précédé d'une histoire de ces deux notions. Mais, auparavant, partons à la recherche des origines de cette notion de calcul, dans la lointaine Antiquité, et intéressons-nous à 1'« invention» des mathématiques par les Grecs. 1 Une origine ancienne CHAPITRE 1 De la préhistoire des mathématiques aux mathématiques grecques Le récit de l'histoire des mathématiques commence souvent en Grèce au ye siècle avant notre ère, quand Pythagore, d'un côté, Thalès et Anaximandre, de l'autre, ont fondé les deux principales branches des mathématiques antiques: l'arithmétique et la géo- métrie. La fondation de l'arithmétique et de la géométrie consti- tue, certes, une révolution majeure dans l'histoire des mathématiques. Cependant, le récit ainsi commencé occulte une période importante que l'on peut appeler la ~ préhistoire» des mathématiques. Les hommes n'ont, en effet, pas attendu le ye siècle avant notre ère pour tenter de résoudre les problèmes mathématiques, surtout les problèmes mathématiques concrets, qui se posaient à eux. Les comptables et les arpenteurs L'une des plus anciennes traces d'activité « mathématique» consiste en une tablette trouvée en Mésopotamie qui date de 2500 avant notre ère. Elle présente le calcul du nombre de per- sonnes auxquelles on peut donner 7 mesures de grain, en pui- 15 LES MÉTAMORPHOSES DU CALCUL sant dans un grenier qui en contient 1152000. Sans surprise, le résultat, 164571 personnes, s'obtient en divisant 1152000 par 7. Les comptables mésopotamiens savaient donc faire des divi- sions, bien avant la « naissance» de l'arithmétique. il est même vraisemblable, quoiqu'il soit difficile d'avoir des certitudes en ce domaine, que l'écriture ait été inventée précisément pour tenir des livres de comptes et que les chiffres soient, de ce fait, anté- rieurs aux lettres. Même si certains ont du mal à l'admettre, nous devons probablement l'ensemble de la culture écrite à la bien peu romantique profession de comptable. Outre des multiplications et des divisions, les comptables mésopotamiens et égyptiens savaient effectuer de nombreux autres calculs, comme résoudre certaines équations du second degré. Et les arpenteurs savaient calculer les aires de rectangles, de triangles, de disques ... L'irruption de l'infini Ces techniques développées par les comptables et les arpen- teurs constituent donc une préhistoire de l'arithmétique et de la géométrie. Que s'est--il donc passé de si spécial en Grèce, au ye siècle avant notre ère, pour justifier que l'on fasse démarrer l'histoire à ce moment et non à un autre? Pour tenter de le comprendre, prenons l'exemple d'un problème résolu par un disciple de Pythagore dont le nom ne nous est pas parvenu: trouver un triangle rectangle et isocèle dont les trois côtés mesurent un nombre entier d'unités, disons un nombre entier de mètres. Comme le triangle est isocèle, ses deux petits côtés ont la même longueur, appelons-la x, et appelons y la longueur du 16 UNE ORIGINE ANCIENNE grand côté, l'hypoténuse. Comme le triangle est rectangle, le nombre y2 est, d'après le théorème de Pythagore, égal à x2 + x2• Le problème se ramène donc à celui de trouver deux nombres entiers x et y tels que 2 x x2 soit égal à f. Essayons toutes les pos- sibilités dans lesquelles les nombres x et y sont inférieurs à 4: x y 2xx2 y2 1 1 2 1 1 2 2 4 1 3 2 9 1 4 2 16 2 1 8 1 2 2 8 4 2 3 8 9 2 4 8 16 3 1 18 3 2 18 4 3 3 18 9 3 4 18 16 4 1 32 1 4 2 32 4 4 3 32 9 4 4 32 16 Dans tous ces cas, le nombre 2 x x2 uploads/Litterature/ les-metamorphoses-du-calcul-par-www-heights-book-blogspot-com-pdf.pdf