Philosophie histoire des sciences A

1- Philosophie de la logique (philo/histoire des sciences formelles A) 4 ECTS

Les algorithmes occupent aujourd'hui une place centrale au sein du débat public et scientifique actuel. Lorsque nous lisons ou écoutons des débats sur l’impact croissant de la science et de la technologie dans notre société, nous entendons régulièrement : « les algorithmes changent le monde », « les algorithmes façonnent notre avenir », « les algorithmes gouvernent nos vies », etc. On voit ici apparaître ce sentiment commun selon lequel nous mettons entre les mains des algorithmes non seulement une partie importante de nos décisions, mais aussi de nos propres vies. Ce sentiment contraste toutefois avec un autre constat : le manque de consensus, parmi les experts, à propos de ce qu’est un algorithme.

De façon très étonnante, dans les ouvrages de référence sur l’algorithmique, on ne trouve nulle part de définition générale et exhaustive de la notion. On se limite à l’étude d’exemples, en les répertoriant au mieux selon certaines caractéristiques communes. Dans ce cours nous essaierons de comprendre pourquoi il est si difficile d’aboutir à une définition suffisamment précise de la notion d’algorithme, permettant de traiter les algorithmes comme les véritables objets d’étude d’une théorie scientifique, et plus spécifiquement d’une théorie formelle (mathématisée).

Autrement dit, qu’est-ce qui rend si difficile le développement d’une théorie formelle (mathématique) des algorithmes ?  Nous montrerons que la difficulté réside dans le fait que la notion d’algorithme n’est pas apparue ex nihilo dans le champ des mathématiques ou de l’informatique. Il s’agit en revanche d’une notion se présentant comme intrinsèquement liée à d’autres notions (calcul, instruction, règle, problème, programme, etc.) dont l’usage n’est pas restreint au langage spécifique des mathématiques ou de l’informatique, mais touche aussi notre langage ordinaire. Nous étudierons donc la notion d’algorithme en lien et en comparaison avec certaines de ces notions, notamment celles qui occupent une place fondamentale dans l’histoire et la philosophie de la logique et des mathématiques, telles que la notion de fonction effectivement calculable, la notion de calcul mécanique, la notion de système formel et celle de règle formelle, le problème de la décision, et la question de l’automatisation des démonstrations.

Bibliographie

1. Bourdeau et J. Mosconi (dir.), Anthologie de la calculabilité. Cassini, Paris, 2022.

Chabert, J.-L. et al. (dir.), Histoire d’algorithmes : du caillou à la puce. Belin, Paris , 1994.

Colson, L., « Functions versus algorithms », dans G. Paun et al. (dir.), Current Trends in Theoretical Computer Science: Entering the 21st century, p. 343–362. World Scientific Publishing, Singapore, 2001.

Dean, W., « Algorithms and the mathematical foundations of computer science », dans P.Welch et L. Horsten (dir.), Gödel’s Disjunction: The scope and limits of mathematical knowledge, p. 19–66. Oxford University Press, Oxford, 2016.

Dowek, G., Les métamorphoses du calcul. Le Pommier, Paris, 2007.

Hilbert, D., « Les fondements des mathématiques » (1927), trad. fr. dans J. Largeault (dir.), Intuitionisme et théorie de la démonstration. Vrin, Paris, 1992.

Gödel, K., « The present situation in the foundations of mathematics », dans Collected Works, vol. 3, p. 45–53. Oxford University Press, Oxford, 1995.

Gurevich, Y., « What is an algorithm? », dans M. Bieliková et al. (dir.), SOFSEM 2012: Theory and Practice of Computer Science, p. 31–42. Springer, Berlin, 2012.

Kleene, S.C., Logique mathématique, trad. fr. J. Largeault. Armand Colin, Paris , 1971.

Knuth, D., Algorithmes, trad. fr. P. Cigielski. The University of Chicago Press, Chicago, 2011.

Moschovakis, Y., « What is an algorithm? », dans B. Engquist et W. Schmid (dir.), Mathematics

Unlimited – 2001 and Beyond, pp. 919–936. Springer, Berlin, 2001

Turing, A., « Théorie des nombres calculables, suivie d’une application au problème de la décision » (1936-7), trad. fr. J. Basch, dans La machine de Turing, p. 47–103. Éditions du Seuil, Paris, 1995.