El proceso de decisión para determinar si dos palabras en los generadores de una estructura algebraica presentada representan el mismo elemento en el cociente definido por las relaciones; equivalente a decidir si una palabra dada representa la identidad.

Principio

Reducir palabras usando las relaciones definitorias a una forma canónica o normal cuando es posible, o aplicar procedimientos de decisión (sistemas de reescritura, Knuth–Bendix, Todd–Coxeter, algoritmos específicos) que proporcionen igualdad o certifiquen inequivalencia; la decidibilidad depende de la clase de presentaciones.

Demostración

En un grupo libre con generadores a y b, el problema de la palabra se resuelve cancelando pares inversos adyacentes: para decidir si aba^{-1}b^{-1} es la identidad, cancelar sistemáticamente aa^{-1} y bb^{-1} hasta que no queden cancelaciones, concluyendo identidad si se alcanza la palabra vacía.

Aplicación incorrecta

Tratar la igualdad sintáctica (secuencias de símbolos idénticas literalmente) como igualdad en el grupo sin reducir por las relaciones, o asumir decidibilidad para grupos finitamente presentados arbitrarios — muchas presentaciones dan lugar a problemas de la palabra indecidibles en general.

Consecuencia

Un procedimiento de decisión correcto proporciona un algoritmo para calcular formas normales y así resolver consultas de igualdad, o establece indecidibilidad en la clase; los problemas de la palabra solucionados permiten cálculos efectivos en el cociente, como comprobaciones de pertenencia y pruebas de homomorfismo.

Inversión

Contrastarlo con el problema de conjugación (decidir si dos elementos son conjugados) o con el problema de isomorfismo (decidir si estructuras presentadas son isomorfas); invertir la pregunta cambia la igualdad bajo relaciones por equivalencia bajo otro tipo de relación.

Límite

Ámbito limitado por la clase de estructuras algebraicas y presentaciones: grupos libres, grupos finitos y muchas clases especiales tienen problemas de la palabra decidibles; grupos finitamente presentados arbitrarios pueden tener problemas de la palabra indecidibles; recursos computacionales y terminación son límites prácticos.

Tensión semántica

Problema de la palabra versus identidad de lenguajes formales o igualdad sintáctica: el problema de la palabra es semántico (igualdad en el cociente dado por relaciones), mientras que la identidad sintáctica ignora las relaciones; compite conceptualmente con problemas de conjugación y pertenencia como tareas de decisión centrales en álgebra.

Síntesis

La resolución del problema de la palabra reduce la cuestión de igualdad bajo relaciones definitorias a reducciones algorítmicas a formas normales o a la aplicación de procedimientos de decisión; es la prueba algorítmica fundamental de igualdad en sistemas algebraicos presentados, cuya solvencia depende de la clase algebraica y del método computacional elegido.