Problème du mot

Le problème du mot est un problème de décision en algèbre abstraite. Il consiste, pour une présentation donnée d'une structure algébrique, à répondre algorithmiquement (à décider) à la question suivante : étant donné une paire de termes ${\displaystyle t_{1}}$ et ${\displaystyle t_{2}}$ de la structure, est-ce que l'égalité ${\displaystyle t_{1}=t_{2}}$ est satisfaite ? Le premier problème de mot dont on a démontré l'indécidabilité fut le problème du mot dans les groupes. La démonstration a été annoncée par Tarski en 1949[1] et publiée dans le livre Undecidable Theories[2].

Le problème du mot en logique combinatoire est indécidable. Le problème du mot pour les groupes est indécidable en général, mais décidable dans de nombreux cas : il existe un algorithme qui décide si ${\displaystyle t_{1}=t_{2}}$ est vraie dans tous les groupes[3]. Le problème du mot dans les groupes est aussi décidable pour de nombreuses classes de présentations de groupes, par exemple pour les groupes de Coxeter et plus généralement pour les groupes automatiques, mais est indécidable en général, pour une présentation quelconque d'un groupe par générateurs et relations. En 1955, Novikov a même prouvé qu'il existe des présentations de groupes ayant un problème du mot indécidable.

De nombreux problèmes de décision en mathématiques peuvent être formulés comme des problèmes du mot (voir la Liste de problèmes indécidables (en)).

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.