Emil Post

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 Leon Post

Emil Leon Post (né le 11 février 1897 à Augustów et mort le 21 avril 1954 à 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.

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

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 table de vérités. Puis il généralise ce résultat à tout calcul propositionnel fini-valent (et non uniquement bivalent ).

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 alphabet 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 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é : Système universitaire de documentation • Bibliothèque nationale de France • Fichier d’autorité international virtuel • Bibliothèque du Congrès • Gemeinsame Normdatei • 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., 1977 (1^re éd. 1967) [présentation en ligne]  pp. 264-283. Traduction française, Jean Largeault (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 

Articles connexes

• Théorème de Post
• Algèbre de Post