Aucune photo libre
Mojżesz Presburger
Pologne · Sur la carte · Universitaires · 1904 - 1943 · 39 ans
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.
Texte issu de Wikipédia, CC BY-SA 4.0
Mojżesz Presburger : environ 9 lectures par jour, en 9 langues.
Un jour typique, sur 30 jours jusqu'au 8 octobre 2026
Le jour médian de la période comptée : une semaine d'actualité ne peut donc pas le faire bouger. La courbe en dessous montre les 120 derniers jours, un point par jour.
Une erreur ?À propos de cette personne
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. M. Rabin et M. Fischer ont démontré en 1974 que la complexité de cet algorithme est super-exponentielle. 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, rapportée par Ryan Stansifer. Presburger a travaillé dans une compagnie d'assurance. Il est mort dans un camp de concentration vers 1943.
Texte issu de Wikipédia, CC BY-SA 4.0