(Docu) Problème du mot

Le problème est couramment rencontré en algèbre abstraite, où, étant donné une présentation d’une structure algébrique par des générateurs et des relateurs, le problème consiste à déterminer si deux expressions représentent le même élément ; un exemple prototypique est le problème du mot pour les groupes.
De manière moins formelle, le problème du mot dans une algèbre est : étant donné un ensemble d’identités E, et deux expressions x et y, est-il possible de transformer x en y en utilisant les identités dans E comme règles de réécriture dans les deux sens ? Bien que répondre à cette question ne semble pas difficile, le résultat remarquable (et profond) qui émerge, dans de nombreux cas importants, est que le problème est indécidable. De nombreux problèmes indécidables en mathématiques, sinon la plupart, peuvent être posés sous forme de problèmes de mots ; voir la liste des problèmes indécidables pour de nombreux exemples.
L’exemple le plus simple d’un problème indécidable est celui de la logique combinatoire : quand deux chaînes de combinateurs sont-elles équivalentes ? Comme les combinateurs codent toutes les machines de Turing possibles, et que l’équivalence de deux machines de Turing est indécidable, il s’ensuit que l’équivalence de deux chaînes de combinateurs est indécidable. De même, on a essentiellement le même problème dans le lambda calculus (non typé) : étant donné deux expressions lambda distinctes, il n’y a pas d’algorithme qui peut discerner si elles sont équivalentes ou non ; l’équivalence est indécidable. Pour plusieurs variantes typées du lambda calculus, l’équivalence est décidable par comparaison des formes normales.