Ouvrir le menu principal
Page d'aide sur l'homonymie Pour les articles homonymes, voir Post.
Emil Post
Emil Leon Post.jpg
Emil Leon Post
Biographie
Naissance
Décès
Voir et modifier les données sur Wikidata (à 57 ans)
New YorkVoir et modifier les données sur Wikidata
Nationalités
Formation
Activités
Autres informations
Domaine
Directeur de thèse

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.

Sommaire

Travaux sur le calcul propositionnelModifier

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 PostModifier

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

 .

On cherche une suite d'indices   telle que la concaténation des   corresponde à celle des  . Ici la suite (1,2,3,2,1) est une solution puisque

 .

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.

BibliographieModifier

Note et référenceModifier

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

Articles connexesModifier