Emil Post
Modèle:Voir homonymes {{#invoke:Bandeau|ébauche}} Modèle:Infobox Biographie2 Emil Leon Post (né le Modèle:Date de naissance à Augustów et mort le Modèle:Date de décès à 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<ref name="Post46"> Modèle:Article</ref>.
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<ref>Modèle:Ouvrage</ref>.
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
Modèle:Article détaillé On part de deux suites finies U et V contenant le même nombre de mots finis sur un alphabet quelconque. Par exemple
- <math>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~</math>.
On cherche une suite d'indices <math>i_1, i_2, ...i_n</math> telle que la concaténation des <math>u_{i_k}</math> corresponde à celle des <math>v_{i_k}</math>. Ici la suite (1,2,3,2,1) est une solution puisque
- <math> u_1 u_2 u_3 u_2 u_1 = v_1 v_2 v_3 v_2 v_1 = ababababa~</math>.
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
- Modèle:Autorité
- {{#invoke:Langue|indicationDeLangue}} Emil Post, Introduction to a general theory of elementary propositions, 1921. Reproduit dans Modèle:Ouvrage pp. 264-283. Traduction française, Modèle:Ouvrage
- Modèle:Ouvrage
Note et référence
<references/>
