Problème du mot

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant la logique
Cet article est une ébauche concernant la logique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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 et de la structure, est-ce que l'égalité 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é par Tarski en 1949[1] et publié dans le livre Undecidable Theories[2].

Le problème du mot en logique combinatoire est indécidable. Le problème du mot dans les groupes (en) est décidable ː il existe un algorithme qui décide si 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 (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)).

Références[modifier | modifier le code]

  1. Solomon Feferman, Anita Burdman Feferman, Alfred Tarski, Life and Logic, Cambridge : Cambridge University Press, 2004. ISBN 0-521-80240-7. p.193
  2. Alfred Tarski in collaboration with A. Mostowski and R. M. Robinson Undecidable theories. North Holland, 1953
  3. « Cours réécriture ENS Cachan »

Articles connexes[modifier | modifier le code]