Emil Post

Biographie
Naissance	11février1897; Augustów(Empire russe)
Décès	21avril1954(à 57 ans); New York
Sépulture	Cimetière du mont Hebron
Nom de naissance	Emil Leon Post
Nationalité	américaine
Formation	Townsend Harris High School(en)(jusqu'en1913); City College of New York(jusqu'en1917); Université Columbia(1917-1920)
Activités	Mathématicien,logicien,philosophe,professeur d'université
A travaillé pour	City College of New York(1932-1954); George Washington High School(en)(1927-1932); Université Cornell(1924-1927); Université Columbia(1921-1924); Université de Princeton(1920-1921)
Directeur de thèse	Cassius Jackson Keyser(1920)
Archives conservées par	American Philosophical Society Library(d)(Mss.Ms.Coll.45)
	Problème de correspondance de Post,Post's inversion formula(d),Post's lattice(d),théorème de Post,système canonique de Post

Cet article est uneébaucheconcernant un mathématicien.

Vous pouvez partager vos connaissances en l’améliorant (comment?) selon les recommandations desprojets correspondants.

Consultez la liste destâches à accomplirenpage de discussion.

Emil Leon Post(né le11 février 1897àAugustówet mort le21 avril 1954à New York) est unmathématicien américainné sur le territoire de l'actuellePolognedans une famillejuive. Il est à l'origine duproblème de correspondance de Post^[1].

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

Biographie

Emil Post est né enPologneen 1897 sous le nom de Postawelski, il émigre avec sa famille vers lesÉtats-Unisen 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é Columbiaen 1920, puis commence ses recherches en logique dès l’année suivante àPrincetongrâ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 sonIntroduction to a general theory of elementary propositionsde 1921, il établit lacomplétudesémantique ducalcul propositionneldesPrincipia MathematicadeWhiteheadetRussellpar le système destables de vérité.Puis il généralise ce résultat à tout calcul propositionnel fini-valent (et non uniquementbivalent).

Le problème de correspondance de Post

Article détaillé: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 Alpha bet quelconque. Par exemple

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}$ telle que la concaténation des $u_{i_{k}}$ corresponde à celle des $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}=ababababa~

.

Le problème de correspondance de Post (en abrégé PCP) consiste à déterminer s'il existe une telle suite. Il estindé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é:
- 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)Jeanvan Heijenoort(dir.),FromFregeToGödel:A Source Book in Mathematical Logic, 1879-1931,Harvard Univ. Press.,1977(1^reéd.1967)(présentation en ligne)pp. 264-283. Traduction française,JeanLargeault(dir.),Logique Mathématique: Textes,Armand Colin,1972
(en)Emil L.Post,Solvability, Provability, Definability: the Complete Works of Emil L. Post,Boston, Basel,Birkhaüser,1994

Note et référence

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

Articles connexes

[Post46-1] (en)E. L. Post, «A variant of a recursively unsolvable problem»,Bull. Amer. Math. Soc,vol.52,‎1946(lire en ligne)

[2] Pierre Cassou-Noguès,Les démons de Gödel, Logique et folie,Seuil,2007,411p.,Partie IV: Le cas Post, une brève digression. Pages 253-257

[1]

[2]