Emil Post

Page d’aide sur l’homonymie

Pour les articles homonymes, voir Post.

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.

Consultez la liste des tâches à accomplir en page de discussion.

Emil Post
Emil Leon Post
Biographie
Naissance
Voir et modifier les données sur Wikidata
Augustów (Empire russe)Voir et modifier les données sur Wikidata
Décès
Voir et modifier les données sur Wikidata (à 57 ans)
New YorkVoir et modifier les données sur Wikidata
Sépulture
Nom de naissance
Emil Leon PostVoir et modifier les données sur Wikidata
Nationalité
américaineVoir et modifier les données sur Wikidata
Formation
Townsend Harris High School (en) (jusqu'en )
City College of New York (jusqu'en )
Université Columbia (-)Voir et modifier les données sur Wikidata
Activités
Mathématicien, logicien, philosophe, professeur d'universitéVoir et modifier les données sur Wikidata
Autres informations
A travaillé pour
City College of New York (-)
George Washington High School (en) (-)
Université Cornell (-)
Université Columbia (-)
Université de Princeton (-)Voir et modifier les données sur Wikidata
Directeur de thèse
Archives conservées par
American Philosophical Society Library (d) (Mss.Ms.Coll.45)Voir et modifier les données sur Wikidata
Œuvres principales
Problème de correspondance de Post, Post's inversion formula (d), Post's lattice (d), théorème de Post, système canonique de PostVoir et modifier les données sur Wikidata

modifier - modifier le code - modifier WikidataDocumentation du modèle

Emil Leon Post (né le à Augustów et mort le à New York) est un mathématicien américain né sur le territoire de l'actuelle Pologne dans une famille juive. Il est à l'origine du problème de correspondance de Post[1].

Il a également publié en 1921 une étude exhaustive des clones des algèbres à deux éléments.


Biographie

Emil Post est né en Pologne en 1897 sous le nom de Postawelski, il émigre avec sa famille vers les États-Unis en 1904 où son nom est américanisé.

Il est amputé du bras gauche à l’âge de 13 ans à la suite d’un accident avec une voiture. Il n’évoquera pas cet événement tout au long de sa vie et pose toujours en photo de manière que l’on ne voie pas le bras manquant.

Brillant élève, il obtient une thèse à l’université Columbia en 1920, puis commence ses recherches en logique dès l’année suivante à Princeton grâce à une bourse.

Il subit une crise en 1921, puis une seconde en 1924 qui l’écarte de ses travaux sur la logique jusqu’en 1936 où il se remet au travail en temps limité.

Il meurt le 21 avril 1954 à la suite d'un traitement par électrochocs, il était interné depuis l’été précédent[2].

Travaux sur le calcul propositionnel

Dans son Introduction to a general theory of elementary propositions de 1921, il établit la complétude sémantique du calcul propositionnel des Principia Mathematica de Whitehead et Russell par le système des tables de vérité. Puis il généralise ce résultat à tout calcul propositionnel fini-valent (et non uniquement bivalent).

Le problème de correspondance de Post

On part de deux suites finies U et V contenant le même nombre de mots finis sur un alphabet quelconque. Par exemple

u 1 = a b a , u 2 = b , u 3 = a , u 4 = a b et v 1 = a , v 2 = b , v 3 = a b a b a , v 4 = b   {\displaystyle u_{1}=aba,u_{2}=b,u_{3}=a,u_{4}=ab\qquad {\textrm {et}}\qquad v_{1}=a,v_{2}=b,v_{3}=ababa,v_{4}=b~} .

On cherche une suite d'indices i 1 , i 2 , . . . i n {\displaystyle i_{1},i_{2},...i_{n}} telle que la concaténation des u i k {\displaystyle u_{i_{k}}} corresponde à celle des v i k {\displaystyle v_{i_{k}}} . Ici la suite (1,2,3,2,1) est une solution puisque

u 1 u 2 u 3 u 2 u 1 = v 1 v 2 v 3 v 2 v 1 = a b a b a b a b a   {\displaystyle u_{1}u_{2}u_{3}u_{2}u_{1}=v_{1}v_{2}v_{3}v_{2}v_{1}=ababababa~} .

Le problème de correspondance de Post (en abrégé PCP) consiste à déterminer s'il existe une telle suite. Il est indécidable : il n'existe pas d'algorithme général capable de fournir une réponse pour des U et V arbitraires.

Bibliographie

  • Notices d'autoritéVoir et modifier les données sur Wikidata :
    • VIAF
    • ISNI
    • BnF (données)
    • IdRef
    • LCCN
    • GND
    • Italie
    • Pays-Bas
    • Pologne
    • Israël
    • NUKAT
    • Suède
    • WorldCat
  • (en) Emil Post, Introduction to a general theory of elementary propositions, 1921. Reproduit dans (en) Jean van Heijenoort (dir.), From Frege To Gödel: A Source Book in Mathematical Logic, 1879-1931, Harvard Univ. Press., (1re éd. 1967) (présentation en ligne) pp. 264-283. Traduction française, Jean Largeault (dir.), Logique Mathématique : Textes, Armand Colin,
  • (en) Emil L. Post, Solvability, Provability, Definability: the Complete Works of Emil L. Post, Boston, Basel, Birkhaüser,

Note et référence

  1. ↑ (en) E. L. Post, « A variant of a recursively unsolvable problem », Bull. Amer. Math. Soc, vol. 52,‎ (lire en ligne)
  2. ↑ Pierre Cassou-Noguès, Les démons de Gödel, Logique et folie, Seuil, , 411 p., Partie IV : Le cas Post, une brève digression. Pages 253-257

Articles connexes

  • icône décorative Portail des mathématiques
  • icône décorative Portail de l'informatique théorique
  • icône décorative Portail de la logique