Mojżesz Presburger
Mojżesz Presburger (1904 - 1943) est un mathématicien polonais, logicien et philosophe. Élève de Tarski, il est connu pour avoir démontré la décidabilité de l'arithmétique de Presburger alors qu'il était encore étudiant[1] - [2] - [3].
| Naissance | |
|---|---|
| Décès | |
| Nationalité | |
| Activités |
.jpg.webp){kind=small}
Ce résultat est mathématiquement très important, car l'arithmétique usuelle provenant des axiomes de Peano et comportant la multiplication que ne contient pas l'arithmétique de Presburger, est elle indécidable et incomplète. Ce dernier résultat constitue le cœur des théorèmes d'incomplétude de Gödel.
Bien que la motivation de l'article de Presburger fût de prouver la complétude de la théorie, la méthode de preuve utilisée était constructive et produisait une procédure de décision, autrement dit un algorithme qui détermine si une formule de l'arithmétique de Presburger est vraie ou fausse. L'un des premiers programmes de démonstration de théorèmes utilisait cet algorithme pour prouver les théorèmes de l'arithmétique de Presburger et avait été écrit par Martin Davis au cours de l'été 1954 pour un ordinateur avec une mémoire de seulement 1024 mots[2]. M. Rabin et M. Fischer ont démontré en 1974 que la complexité de cet algorithme est super-exponentielle[4].
Presburger a présenté son article au Congrès des Mathématiciens de Varsovie, mais il n'a pas soutenu de thèse, apparemment Tarski les considérait comme une application évidente de la technique d'élimination des quantificateurs que Thoralf Skolem avait utilisée bien plus tôt : c'est l'opinion de John Newsome Crossley[5], rapportée par Ryan Stansifer[2].
Presburger a travaillé dans une compagnie d'assurance[6] - [7]. Il est mort dans un camp de concentration vers 1943[6] - [7] - [8] - [9].
Prix
L'association européenne d'informatique théorique (EATCS) a institué en 2010 le Prix Presburger qui récompense un jeune scientifique (moins de 35 ans) qui a apporté des contributions exceptionnelles à l'informatique théorique.
Références
- Mojżesz Presburger, « Über der Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchen die Addition als einzige Operation hervortritt », dans F. Leja (éditeur), Comptes Rendus Premier Congrès des Mathématiciens des Pays Slaves, Varsovie 1929 : Sprawozdanie z I Kongresu matematyków krajów słowiańskich, Warszawa 1929, Warsaw, Lwów and Krakow, , p. 92–101 et 395
- Ryan Stansifer, Presburger's Article on Integer Arithmetic: Remarks and Translation, vol. TR84-639, Ithaca/NY, Dept. of Computer Science, Cornell University, (lire en ligne)
- Mojżesz Presburger et Dale Jacquette, « On the Completeness of a Certain System of Arithmetic of Whole Numbers in Which Addition Occurs as the Only Operation », History and Philosophy of Logic, vol. 12, , p. 225–33 (DOI 10.1080/014453409108837187)
- Michael Jo Fischer et Michael O. Rabin, « Super-Exponential Complexity of Presburger Arithmetic », dans Complexity of Computation: Proceedings of a Symposium in Applied Mathematics of the American Mathematical Society and the Society for Industrial and Applied Mathematics, , 27–41 p. (lire en ligne).
- Crossley, John Newsome, « Reminscences of logicians », dans John Newsome Crossley (éditeur), Albegra and Logic, Springer-Verlag, , p. 1-62
- Anita Burdman Feferman et Solomon Feferman, Alfred Tarski : Life and Logic, Cambridge University Press, , 425 p. (ISBN 978-0-521-80240-6, lire en ligne), p. 73-74
- Jan Zygmunt, « Mojżesz Presburger: Life and Work », History and Philosophy of Logic, vol. 12, , p. 211–223 (DOI 10.1080/014453409108837186).
- Jan Woleński, Logic and Philosophy in the Lvov-Warsaw School, Dordrecht, Reidel, , 392 p. (ISBN 978-90-277-2749-7)
- Claus-Peter Wirth, Jörg Siekmann, Christoph Benzmüller et Serge Autexier, Lectures on Jacques Herbrand as a Logician, (lire en ligne), p.48, note 128.
Article connexe
Liens externes
- Notice dans un dictionnaire ou une encyclopédie généraliste :
- Documents concernant Mojżesz Presburger, collationnés par Mikołaj Bojańczyk
- Photo du congrès de 1929