En matemáticas e informática , un problema verbal para un conjunto S con respecto a un sistema de codificaciones finitas de sus elementos es el problema algorítmico de decidir si dos representantes dados representan el mismo elemento del conjunto. El problema se encuentra comúnmente en el álgebra abstracta , donde dada una presentación de una estructura algebraica por generadores y relatores , el problema es determinar si dos expresiones representan el mismo elemento; un ejemplo prototípico es el problema verbal para grupos . De manera menos formal, el problema verbal en un álgebra es: dado un conjunto de identidades E y dos expresionesX e Y , es posible transformar x en y utilizando las identidades de E como la reescritura de las reglas en ambas direcciones? Si bien responder a esta pregunta puede no parecer difícil, el resultado notable (y profundo ) que surge, en muchos casos importantes, es que el problema es indecidible .
Muchos, si no la mayoría, de los problemas matemáticos indecidibles pueden plantearse como problemas verbales; consulte la lista de problemas indecidibles para ver muchos ejemplos.
Antecedentes y motivación
En matemáticas surgen muchas ocasiones en las que se desea utilizar una cantidad finita de información para describir un elemento de un conjunto (típicamente infinito). Este problema es particularmente evidente en las matemáticas computacionales. Los modelos tradicionales de cálculo (como la máquina de Turing ) tienen una capacidad de almacenamiento ilimitada, por lo que en principio es posible realizar cálculos con los elementos de conjuntos infinitos. Por otro lado, dado que la cantidad de espacio de almacenamiento en uso en un momento dado es finita, necesitamos que cada elemento tenga una representación finita.
Por diversas razones, no siempre es posible o deseable utilizar un sistema de codificaciones únicas , es decir, uno en el que cada elemento tenga una única codificación. Cuando se utiliza un sistema de codificación sin unicidad, surge naturalmente la pregunta de si existe un algoritmo que, dado como entrada dos codificaciones, decide si representan el mismo elemento. Este algoritmo se denomina solución al problema de palabras del sistema de codificación.
El problema verbal en cálculo combinatorio
El ejemplo más simple de un problema verbal indecidible ocurre en la lógica combinatoria : ¿cuándo son equivalentes dos cadenas de combinadores? Debido a que los combinadores codifican todas las máquinas de Turing posibles , y la equivalencia de dos máquinas de Turing es indecidible, se deduce que la equivalencia de dos cadenas de combinadores es indecidible.
Asimismo, uno tiene esencialmente el mismo problema en el cálculo lambda (sin tipo) : dadas dos expresiones lambda distintas, no hay ningún algoritmo que pueda discernir si son equivalentes o no; la equivalencia es indecidible . Para varias variantes tipificadas del cálculo lambda, la equivalencia se puede decidir mediante la comparación de formas normales.
El problema verbal en álgebra universal
En álgebra , a menudo se estudian álgebras infinitas que son generadas (bajo las operaciones finitarias del álgebra) por un número finito de elementos. En este caso, los elementos del álgebra tienen un sistema natural de codificación finita como expresiones en términos de generadores y operaciones. Por tanto, el problema verbal aquí es determinar, dadas dos de tales expresiones, si representan el mismo elemento del álgebra.
A grandes rasgos, el problema de la palabra en un álgebra es: dado un conjunto E de las identidades (una teoría ecuacional ), y dos términos s y t , es posible transformar s en t usando las identidades en E como la reescritura de las reglas en ambas direcciones? . [1] Una extensión adecuada del problema verbal se conoce como el problema de unificación (también conocido como el problema de resolución de ecuaciones ). Mientras que el primero pregunta si dos términos son iguales, el segundo pregunta si tienen instancias que son iguales. Como ejemplo común, ""es un problema verbal en el grupo de enteros ℤ , mientras que""es un problema de unificación en el mismo grupo; dado que los primeros términos resultan ser iguales en ℤ, el último problema tiene la sustitución como solución.
Las sustituciones se pueden ordenar en un orden parcial , por lo tanto, la unificación es el acto de encontrar una unión en una celosía . [ aclaración necesaria ] En este sentido, el problema de palabras en una celosía tiene una solución, a saber, el conjunto de todas las palabras equivalentes es la celosía libre . [ aclaración necesaria ]
Uno de los casos más profundamente estudiados del problema verbal es el de la teoría de semigrupos y grupos . Hay muchos grupos para los que el problema verbal no es decidible , ya que no existe una máquina de Turing que pueda determinar la equivalencia de dos palabras arbitrarias en un tiempo finito.
El problema verbal en términos básicos no es decidible. [2] [ aclaración necesaria ]
El problema verbal sobre álgebras de Heyting libres es difícil. [3] Los únicos resultados conocidos son que el álgebra de Heyting libre en un generador es infinito, y que el álgebra de Heyting libre completa en un generador existe (y tiene un elemento más que el álgebra de Heyting libre).
Ejemplo: un sistema de reescritura de términos para decidir el problema verbal en el grupo libre
Bläsius y Bürckert [4] demuestran el algoritmo de Knuth-Bendix en un conjunto de axiomas para grupos. El algoritmo produce un sistema de reescritura de términos confluentes y noetherianos que transforma cada término en una forma normal única . [5] Las reglas de reescritura están numeradas de manera incontigua ya que algunas reglas se volvieron redundantes y fueron eliminadas durante la ejecución del algoritmo. La igualdad de dos términos se sigue de los axiomas si y solo si ambos términos se transforman literalmente en el mismo término de forma normal. Por ejemplo, los términos
- , y
comparten la misma forma normal, a saber. ; por tanto, ambos términos son iguales en todos los grupos. Como otro ejemplo, el término y tiene la forma normal y , respectivamente. Dado que las formas normales son literalmente diferentes, los términos originales no pueden ser iguales en todos los grupos. De hecho, suelen ser diferentes en grupos no abelianos .
A1 | ||
A2 | ||
A3 |
R1 | ||
R2 | ||
R3 | ||
R4 | ||
R8 | ||
R11 | ||
R12 | ||
R13 | ||
R14 | ||
R17 |
Ver también
- Árbol de munn
- Problema verbal para grupos
- Algoritmo de finalización de Knuth-Bendix
- Unificación (informática)
Referencias
- ^ Franz Baader y Tobias Nipkow , Reescritura de términos y todo eso , Cambridge University Press, 1998, p. 5
- ^ Yuri Matijasevich, (1967) "Ejemplos simples de cálculos asociativos indecidibles", Matemáticas soviéticas - Doklady 8 (2) pp 555–557.
- ^ Peter T. Johnstone, Stone Spaces , (1982) Cambridge University Press, Cambridge, ISBN 0-521-23893-5 . (Ver capítulo 1, párrafo 4.11)
- ^ KH Bläsius y H.-J. Bürckert, ed. (1992). Deduktionsssysteme . Oldenbourg. pag. 291.; aquí: p.126, 134
- ^ Aplicar reglas en cualquier orden a un término, siempre que sea posible; el resultado no depende del pedido; es la forma normal del término.