Remerciez-le!

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

Université Paris 1 Panthéon-Sorbonne M1 - Logique - LoPhiSC Alberto Naibo Calcu

Université Paris 1 Panthéon-Sorbonne M1 - Logique - LoPhiSC Alberto Naibo Calculabilité Introduction Aux origines de la théorie de la calculabilité : la pensée comme calcul La théorie de la calculabilité, en tant que branche de la logique-mathématique visant à donner un traitement logico-formel de la notion intuitive et informelle de procédure mécanique (ou procédure eﬀective ou encore, algorithmique), est une théorie relativement récente. 1 On peut notamment faire remonter sa naissance entre les années vingt et trente du 20ème siècle, d’abord avec les travaux de T. Skolem, D. Hilbert et W. Ackermann, et ensuite avec les développements techniques et conceptuels entrepris par K. Gödel, S.C. Kleene, A. Church, A. Turing, mais aussi par E. Post, J. Herbrand et R. Péter. 2 Toutefois, d’un point de vue plus général, le cœur de la théorie de la calculabilité prend ses racines dans un problème philosophique traditionnel, comme celui de la possibilité de concevoir la pensée – ou au moins une partie (des opérations) de la pensée, tel que le raisonnement 3 (déductif) – à un calcul. Ce problème était notamment déjà au centre des réﬂexions de philosophes comme T. Hobbes 4 et G.W. Leibniz 5 (cf. Parrochia 1992 ; Chevalier 2016, p. 15-20). L’idée, plus précisément, était que si le raisonnement pouvait être réduit à un calcul algébrique de sommes et soustractions sur les concepts ou sur les noms (ou plus généralement, sur les termes) désignant ces concepts (calculus ratiocinator), on pourrait alors espérer de pouvoir décider, de manière purement mécanique, de la correction d’un raisonnement, sans qu’il soit nécessaire de faire appel à des formes d’intuition ou d’ingéniosité quelconques. En ce sens, si le raisonnement était réduit à un calcul, il n’y aurait pas de possibilité d’avoir de « trous épistémiques » : n’importe qui pourrait, à tout moment, comprendre et 1. Nous verrons plus tard que les procédures mécaniques que nous allons étudier sont des procédures de type fonctionnel (voir la Remarque p. 10). 2. Pour approfondir l’histoire de la théorie de la calculabilité voir Adams (2011), Mosconi (1998) et Soare (1999). 3. Le raisonnement s’oppose ici à d’autres parties, ou opérations, de la pensée, comme l’intuition. 4. Léviathan (1651), partie I, chap. 5 (trad. fr. F. Tricaud) : A partir de ce qui vient d’être dit, on peut déﬁnir la raison, c’est-à-dire déterminer la signiﬁcation de ce mot en tant qu’il désigne une faculté de l’esprit. En eﬀet, la raison, en ce sens, n’est rien d’autre que le calcul, c’est-à-dire l’addition et la soustraction de noms généraux admis pour noter ou signiﬁer nos pensées : je parle de noter quand nous calculons à part nous-mêmes ; et de signiﬁer quand nous démontrons notre calcul à autrui. De corpore (1655), chap. I, partie I, § 2 : Per Ratiocinationem autem intelligo computationem. Computare vero est plurium rerum simul addi- tatrum summam colligere, vel unâ re ad aliâ detractâ cognoscere residuum. Ratiocinari igitur idem est quod addere et subtrahere, vel si quis adjungat his multiplicare et dividere, non abnuam, cum multipli- catio idem sit quod aequalium additio, divisio quod aequalium, quoties ﬁeri potest, substractio. Recidit itaque ratiocinatio omnis ad duas operationes animi, additionem et substractionem. 5. Voir Dissertatio de arte combinatoria (1666). 1 vériﬁer la correction d’un raisonnement simplement en suivant de manière « aveugle » un ensemble de règles de calcul ﬁxées au préalable. Et même si on ne connaissait pas tous les termes en jeu – à savoir leur signiﬁcation –, on pourrait néanmoins vériﬁer que la combinaison de ces termes respecte les règles données. Ces règles doivent être donc des règles universellement applicables, au sens où elles doivent être des règles formelles : elles ne doivent pas notamment dépendre du contenu particulier des termes en jeu. C’est pour cela que, selon Leibniz, le projet d’un calculus ratiocinator devait aller de concert avec la déﬁnition d’un langage symbolique exempte de tout genre d’ambiguïté, à savoir une lingua characteristica universalis. 6 Les méthodes algorithmiques en mathématiques Comme nous venons de le voir, traditionnellement, le modèle de référence du raisonnement ef- fectif et mécanique était le modèle des mathématiques, et plus précisément celui de l’algèbre. En mathématiques nous pouvons trouver, en eﬀet, un grand nombre de méthodes de type algorith- mique. Mais en quoi consiste une méthode algorithmique ? Une première approximation peut être la suivante. Il s’agit d’une méthode qui consiste en une suite ﬁnie et structurée d’instructions, qui peut être (dé)écrite (dans un certain langage) sans ambiguïtés, sous la forme d’un texte, et qui fournit une procédure mécanique générale pour résoudre une certaine tâche (resp. problème) dont l’exécu- tion (resp. la solution) ne requiert aucun type de pensée créative. Les instructions dont se compose la procédure algorithmique doivent être exécutées selon un ordre établi et toujours produire, de manière déterminée, une certaine réponse au bout d’un nombre ﬁni et discret de pas. Autrement dit, chaque instruction doit satisfaire les conditions suivantes : i) quand on l’exécute, on obtient une donnée en sortie (output) qui est déterminée par les données d’entrée (input) ; 7 ii) pour toute entrée, l’exécution termine après un nombre ﬁni (et discret) de pas. Une instruction peut, éventuellement, être composée de sous-instructions. Quand une instruction ne peut pas être ultérieurement décomposée en sous-instructions, elle est dite simple. Un algorithme peut être alors vu comme une combinaison structurée d’un ensemble ﬁni d’instructions simples. Évidemment, une telle caractérisation d’un algorithme est hautement idéalisée. En particulier, la taille des entrées et le temps d’exécution, bien qu’ils soient toujours ﬁnis, ne sont pas bornés. La notion de calculabilité qui est en jeu ici est donc celle d’une calculabilité de type théorique et non pas une calculabilité réelle, concrètement réalisable par un être humain (ou par un ordinateur) soumis à certaines limitations contingentes concernant le temps et l’espace de calcul (comme par exemple les limites de la mémoire ou les limites d’attention cognitive, ou encore l’insuﬃsance de papier disponible pour réaliser le calcul, etc.). Parmi les exemples les plus connus de procédures algorithmiques employées en mathématiques nous pouvons citer les suivants : — trouver le plus grand commun diviseur de deux nombres entiers a et b ; 8 6. Il faut noter que l’étymologie même du terme « calcul » renvoie à l’idée que pour calculer il faut s’appuyer – ou mieux, compter – sur quelque chose (dans le cas en question, ce quelque chose est le système de symboles d’un certain langage). Le mot « calcul » vient, en eﬀet, du latin calculus, caillou, car l’on comptait à l’aide de petits cailloux. Cf. Sundholm (2014, p. 1-2). 7. Cela présuppose qu’on ait spéciﬁé à l’avance l’ensemble des expressions qui peuvent être acceptés comme données d’entrée et de sortie. 8. Nous allons étudier cela en détail dans la section suivante. 2 — déterminer les solutions d’une équation de deuxième degré, à une variable et à coeﬃcients entiers. 9 En revanche, parmi les contre-exemples, nous pouvons mentionner les suivants : — déterminer les solutions d’une équation diophantienne ; 10 — déterminer les solutions d’une équation de degré supérieur à quatre, à une variable et à coeﬃcients entiers. 11 Un exemple : l’algorithme euclidien Nous nous proposons d’analyser ici un algorithme très connu en mathématiques, qui permet de trouver – ou mieux, de calculer – le plus grand commun diviseur de deux nombres entiers positifs (c’est-à-dire, deux nombres entiers naturels). 12 Cette présentation suivra de près l’exposition qui se trouve dans Courant et Robbins (2015, chap. 1, § 4). 13 Tout d’abord, nous allons montrer que la recherche d’un tel algorithme est non seulement pos- sible, mais elle représente aussi une entreprise assez naturelle. Nous allons montrer, en particulier, que le problème posé ne demande pas un espace de recherche inﬁni et qu’on peut ainsi envisager la possibilité de mettre en place une procédure qui permet, pas-à-pas, d’« explorer » tous les cas possibles et trouver ﬁnalement la solution cherchée. 9. La méthode est bien connue et correspond à celle qu’on nous apprend au collège. Considérons, par exemple, l’équation de deuxième degré de la forme ax2 + bx + c = 0 (1) où a ̸= 0. Aﬁn de savoir s’il existe des solutions de (1), il suﬃt de calculer le discriminant ∆= b2 −4ac Trois cas peuvent alors se présenter : — ∆> 0. Dans ce cas, il y a deux solutions distinctes dans les réels : x1 = −b+ √ ∆ 2a et x2 = −b− √ ∆ 2a . — ∆= 0. Dans ce cas, il y a une seule solution dans les réels : x = −b+0 2a = −b−0 2a = −b 2a. — ∆< 0. Dans ce cas, il n’y a pas de solutions dans les réels, mais il y en a dans les complexes. Dans tous les cas on peut donc donner une réponse au problème et cela se fait grâce à une suite d’étapes de calculs bien déterminées, qui opèrent sur les coeﬃcients de (1). 10. Une équation diophantienne est une équation algébrique à une ou plusieurs variables à coeﬃcients entiers pour laquelle on uploads/Philosophie/ se-ance-1.pdf