Loading AI tools
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 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ée par Tarski en 1949[1] et publiée dans le livre Undecidable Theories[2].
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 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 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).
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
