Problème du mot

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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ée une paire de termes t_1 et t_2 de la structure, est-ce que l'égalité t_1=t_2 est satisfaite ? Historiquement, le premier problème dont on a démontré l'indécidabilité fut un problème de mot. La démonstration fut faite par Tarski dans les années 1920.

Le problème du mot en logique combinatoire est indécidable. Le problème du mot dans les groupes (en) est 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 (en), 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 (en) 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)).

Articles connexes[modifier | modifier le code]