Emil Post - Définition
Emil Leon Post (né le 11 février 1897, mort le 21 avril 1954) était 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.
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 u1 = aba,u2 = b,u3 = a,u4 = ab,v1 = a,v2 = b,v3 = ababa,v4 = b.
On cherche une suite d'indices i1,i2,...in telle que la concaténation des
Le problème de correspondance de Post (en abrégé PCP) consiste à déterminer l'existence d'une telle suite. Il est indécidable en général : il ne peut pas exister d'algorithme capable de fournir une réponse pour des U et V arbitraires.
