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
