Mojżesz Presburger
# 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^,^,.$

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^,^,^,.$

## 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.

