Mojżesz Presburger
mathématicien, logicien et philosophe polonais (1904-1943) / De Wikipedia, l'encyclopédie encyclopedia
Cher Wikiwand IA, Faisons court en répondant simplement à ces questions clés :
Pouvez-vous énumérer les principaux faits et statistiques sur Mojżesz Presburger?
Résumez cet article pour un enfant de 10 ans
Pour les articles homonymes, voir Pressburger.
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].
Cet article est une ébauche concernant un mathématicien.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
Naissance | |
---|---|
Décès | |
Nationalité | |
Activités |
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].