Aller au contenu
230 411 profils classés

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 ?
Comparer

À 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

Pays
Pologne
Catégorie
Universitaires
Type
Universitaire
Statut
Décédé(e)
Dates
1904 - 1943 · 39 ans