Problème du mot

Problème du mot

Le problème du mot est un problème de décision en algèbre abstraite qui consiste, étant données une paire de termes t1 et t2 et une présentation d'une structure algébrique, à répondre par algorithme (à décider) si oui ou non l'égalité t1 = t2 est satisfaite. Historiquement le premier problème dont on a démontré l'indécidabilité fut un problème de mot. La démonstation fut faite par Tarski dans les années 1920.

Le problème du mot en logique combinatoire est indécidable, tandis que le problème du mot dans les groupes est décidable, cependant il existe des présentations de groupes (Novikov (en)) ayant un problème du mot indécidable.

Articles connexes


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Problème du mot de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • MOT — M L’unité que le sens commun serait enclin à considérer comme fondamentale au niveau de la parole est pour la linguistique la source d’un certain nombre de critiques fécondes: le mot ne correspond, en effet, que très imparfaitement aux éléments… …   Encyclopédie Universelle

  • Probleme de la mesure quantique — Problème de la mesure quantique Cet article fait partie de la série Mécanique quantique Postulats de la mécanique quantique H …   Wikipédia en Français

  • Problème de la mesure — quantique Cet article fait partie de la série Mécanique quantique Postulats de la mécanique quantique H …   Wikipédia en Français

  • Probleme — Problème Pour les articles homonymes, voir pb. Un problème dans son acception la plus courante, est une situation dans laquelle un obstacle empêche de progresser, d avancer ou de réaliser ce que l on voulait faire. Sommaire 1 Étymologie 2 …   Wikipédia en Français

  • Problème de circulation — Problème Pour les articles homonymes, voir pb. Un problème dans son acception la plus courante, est une situation dans laquelle un obstacle empêche de progresser, d avancer ou de réaliser ce que l on voulait faire. Sommaire 1 Étymologie 2 …   Wikipédia en Français

  • Problème interne — Problème Pour les articles homonymes, voir pb. Un problème dans son acception la plus courante, est une situation dans laquelle un obstacle empêche de progresser, d avancer ou de réaliser ce que l on voulait faire. Sommaire 1 Étymologie 2 …   Wikipédia en Français

  • Problème moral — Problème Pour les articles homonymes, voir pb. Un problème dans son acception la plus courante, est une situation dans laquelle un obstacle empêche de progresser, d avancer ou de réaliser ce que l on voulait faire. Sommaire 1 Étymologie 2 …   Wikipédia en Français

  • Problème national — Problème Pour les articles homonymes, voir pb. Un problème dans son acception la plus courante, est une situation dans laquelle un obstacle empêche de progresser, d avancer ou de réaliser ce que l on voulait faire. Sommaire 1 Étymologie 2 …   Wikipédia en Français

  • Problème informatique — Informatique L´informatique contraction d´information et automatique est le domaine d activité scientifique, technique et industriel en rapport avec le traitement automatique de l information par des machines telles que les ordinateurs, les… …   Wikipédia en Français

  • Problème —          ARON (Raymond)     Bio express : Philosophe et sociologue français (1905 1983)     «Le problème politique est éternel que l on retourne la terre à la pioche ou avec le bulldozer.»     Source : Dimension de la conscience historique… …   Dictionnaire des citations politiques

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”