Problema de palabras (matemáticas)

Problema de decisión relativo a la equivalencia de expresiones

En matemáticas computacionales , un problema verbal es el problema de decidir si dos expresiones dadas son equivalentes con respecto a un conjunto de identidades de reescritura . Un ejemplo prototípico es el problema verbal de los grupos , pero también hay muchos otros casos. Un resultado profundo de la teoría computacional es que responder a esta pregunta es indecidible en muchos casos importantes . ^[1]

Antecedentes y motivación

En álgebra computacional, a menudo se desea codificar expresiones matemáticas utilizando un árbol de expresiones. Pero a menudo hay múltiples árboles de expresiones equivalentes. Naturalmente, surge la pregunta de si existe un algoritmo que, dadas como entrada dos expresiones, decida si representan el mismo elemento. Un algoritmo de este tipo se llama solución al problema verbal . Por ejemplo, imaginemos que son símbolos que representan números reales ; entonces, una solución relevante al problema verbal, dada la entrada , produciría la salida , y de manera similar produciría a partir de . ${\displaystyle x,y,z}$ ${\displaystyle (x\cdot y)/z\mathrel {\overset {?}{=}} (x/z)\cdot y}$EQUALNOT_EQUAL ${\displaystyle (x\cdot y)/z\mathrel {\overset {?}{=}} (x/x)\cdot y}$

La solución más directa a un problema de palabras toma la forma de un teorema de forma normal y un algoritmo que asigna cada elemento en una clase de equivalencia de expresiones a una única codificación conocida como la forma normal ; el problema de palabras se resuelve entonces comparando estas formas normales a través de la igualdad sintáctica . ^[1] Por ejemplo, uno podría decidir que es la forma normal de , , y , y diseñar un sistema de transformación para reescribir esas expresiones a esa forma, demostrando en el proceso que todas las expresiones equivalentes se reescribirán a la misma forma normal. ^[2] Pero no todas las soluciones al problema de palabras utilizan un teorema de forma normal: hay propiedades algebraicas que implican indirectamente la existencia de un algoritmo. ^[1] ${\displaystyle x\cdot y\cdot z^{-1}}$ ${\displaystyle (x\cdot y)/z}$ ${\displaystyle (x/z)\cdot y}$ ${\displaystyle (y/z)\cdot x}$

Mientras que el problema de palabras pregunta si dos términos que contienen constantes son iguales, una extensión adecuada del problema de palabras, conocida como el problema de unificación , pregunta si dos términos que contienen variables tienen instancias que son iguales o, en otras palabras, si la ecuación tiene alguna solución. Como ejemplo común, es un problema de palabras en el grupo de números enteros , mientras que es un problema de unificación en el mismo grupo; dado que los primeros términos son iguales en , el último problema tiene la sustitución como solución. ${\displaystyle t_{1},t_{2}}$ ${\displaystyle t_{1}=t_{2}}$ ${\displaystyle 2+3\mathrel {\overset {?}{=}} 8+(-3)}$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle 2+x\mathrel {\overset {?}{=}} 8+(-x)}$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle \{x\mapsto 3\}}$

Historia

Uno de los casos más estudiados del problema verbal se encuentra en la teoría de semigrupos y grupos . A continuación se presenta una cronología de los artículos relacionados con el teorema de Novikov-Boone : ^{[3] [4]}

• 1910 : Axel Thue plantea un problema general de reescritura de términos en estructuras arborescentes. Afirma que "la solución de este problema en el caso más general puede estar relacionada con dificultades insuperables". ^{[5] [6]} ( 1910 )
• 1911 : Max Dehn plantea el problema de las palabras para grupos finitamente presentados . ^[7] (1911)
• 1912 : Dehn presenta el algoritmo de Dehn y demuestra que resuelve el problema verbal para los grupos fundamentales de variedades bidimensionales orientables cerradas de género mayor o igual a 2. ^[8] Autores posteriores lo han extendido en gran medida a una amplia gama de problemas de decisión de teoría de grupos . ^{[9] [10] [11]} (1912)
• 1914 : Axel Thue plantea el problema de las palabras para semigrupos finitamente presentados. ^[12] (1914)
• 1930  – 1938 : Surge la tesis de Church-Turing , que define nociones formales de computabilidad e indecidibilidad. ^[13] (1930) (1938)
• 1947 : Emil Post y Andrey Markov Jr. construyen de forma independiente semigrupos finitamente presentados con problemas verbales irresolubles. ^{[14] [15]} La construcción de Post se basa en máquinas de Turing, mientras que la de Markov utiliza los sistemas normales de Post. ^[3] (1947)
• 1950 : Alan Turing demuestra que el problema verbal de los semigrupos de cancelación es irresoluble, ^[16] al profundizar la construcción de Post. La prueba es difícil de seguir pero marca un punto de inflexión en el problema verbal de los grupos. ^{[3] : 342} (1950)
• 1955 : Pyotr Novikov da la primera prueba publicada de que el problema verbal para grupos es irresoluble, utilizando el resultado de semigrupo de cancelación de Turing. ^{[17] [3] : 354} La prueba contiene un "Lema principal" equivalente al Lema de Britton . ^{[3] : 355} (1955)
• 1954  – 1957 : William Boone demuestra de forma independiente que el problema verbal de los grupos es irresoluble, utilizando la construcción de semigrupos de Post. ^{[18] [19]} (1954) (1957)
• 1957  – 1958 : John Britton ofrece otra prueba de que el problema verbal de los grupos es irresoluble, basándose en el resultado de los semigrupos de cancelación de Turing y en algunos de los trabajos anteriores de Britton. ^[20] Aparece una versión temprana del Lema de Britton. ^{[3] : 355} (1957) (1958)
• 1958  – 1959 : Boone publica una versión simplificada de su construcción. ^{[21] [22]} (1958) (1959)
• 1961 : Graham Higman caracteriza los subgrupos de grupos finitamente presentados con el teorema de incrustación de Higman , ^[23] conectando la teoría de recursión con la teoría de grupos de una manera inesperada y dando una prueba muy diferente de la irresolubilidad del problema verbal. ^[3] (1961)
• 1961  – 1963 : Britton presenta una versión muy simplificada de la prueba de Boone de 1959 de que el problema verbal para grupos es irresoluble. ^[24] Utiliza un enfoque de teoría de grupos, en particular el Lema de Britton . Esta prueba se ha utilizado en un curso de posgrado, aunque existen pruebas más modernas y condensadas. ^[25] (1961) (1963)
• 1977 : Gennady Makanin demuestra que la teoría existencial de ecuaciones sobre monoides libres es solucionable. ^[26] (1977)

El problema de las palabras para los sistemas semi-Thue

El problema de accesibilidad para los sistemas de reescritura de cadenas (sistemas semi-Thue o semigrupos) se puede plantear de la siguiente manera: Dado un sistema semi-Thue y dos palabras (cadenas) , se puede transformar en aplicando reglas de ? Nótese que la reescritura aquí es unidireccional. El problema de la palabra es el problema de accesibilidad para relaciones de reescritura simétricas, es decir, sistemas Thue. ^[27] ${\displaystyle T:=(\Sigma ,R)}$ ${\displaystyle u,v\in \Sigma ^{*}}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle R}$

Los problemas de accesibilidad y de palabras son indecidibles , es decir, no existe un algoritmo general para resolver este problema. ^[28] Esto se mantiene incluso si limitamos los sistemas a tener presentaciones finitas, es decir, un conjunto finito de símbolos y un conjunto finito de relaciones en esos símbolos. ^[27] Incluso el problema de palabras restringido a términos básicos no es decidible para ciertos semigrupos presentados finitamente. ^{[29] [30]}

El problema de las palabras para grupos

Dada una presentación para un grupo G , el problema verbal es el problema algorítmico de decidir, dadas como entrada dos palabras en S , si representan el mismo elemento de G . El problema verbal es uno de los tres problemas algorítmicos para grupos propuestos por Max Dehn en 1911. Pyotr Novikov demostró en 1955 que existe un grupo G presentado finitamente tal que el problema verbal para G es indecidible . ^[31] ${\displaystyle \langle S\mid {\mathcal {R}}\rangle }$

El problema de las palabras en el cálculo combinatorio y el cálculo lambda

Una de las primeras pruebas de que un problema verbal es indecidible fue para la lógica combinatoria : ¿cuándo son equivalentes dos cadenas de combinadores? Como 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. Alonzo Church observó esto en 1936. ^[32]

De la misma manera, en el cálculo lambda (sin tipificar) se tiene esencialmente el mismo problema : dadas dos expresiones lambda distintas, no hay ningún algoritmo que pueda discernir si son equivalentes o no; la equivalencia es indecidible . En el caso de varias variantes tipificadas del cálculo lambda, la equivalencia es decidible mediante la comparación de formas normales.

El problema de las palabras para los sistemas de reescritura abstracta

Para resolver el problema de las palabras, decidir si generalmente requiere una búsqueda heurística ( rojo , verde ), mientras que decidir es sencillo ( gris ). ${\displaystyle x{\stackrel {*}{\leftrightarrow }}y}$ ${\displaystyle x\downarrow =y\downarrow }$

El problema verbal para un sistema de reescritura abstracta (ARS) es bastante sucinto: dados los objetos x e y, ¿son equivalentes bajo ? ^[29] El problema verbal para un ARS es indecidible en general. Sin embargo, existe una solución computable para el problema verbal en el caso específico donde cada objeto se reduce a una única forma normal en un número finito de pasos (es decir, el sistema es convergente ): dos objetos son equivalentes bajo si y solo si se reducen a la misma forma normal. ^[33] El algoritmo de compleción de Knuth-Bendix se puede utilizar para transformar un conjunto de ecuaciones en un sistema de reescritura de términos convergente . ${\displaystyle {\stackrel {*}{\leftrightarrow }}}$ ${\displaystyle {\stackrel {*}{\leftrightarrow }}}$

El problema de las palabras en el álgebra universal

En el álgebra universal se estudian estructuras algebraicas que consisten en un conjunto generador A , una colección de operaciones sobre A de aridad finita y un conjunto finito de identidades que estas operaciones deben satisfacer. El problema verbal para un álgebra consiste entonces en determinar, dadas dos expresiones (palabras) que involucran a los generadores y operaciones, si representan el mismo elemento del álgebra módulo las identidades. Los problemas verbales para grupos y semigrupos pueden formularse como problemas verbales para álgebras. ^[1]

El problema verbal sobre las álgebras de Heyting libres es difícil. ^[34] Los únicos resultados conocidos son que el álgebra de Heyting libre en un generador es infinita y que el álgebra de Heyting completa libre en un generador existe (y tiene un elemento más que el álgebra de Heyting libre).

El problema de las palabras para las redes libres

El problema verbal sobre redes libres y, más generalmente, redes libres acotadas tiene una solución decidible. Las redes acotadas son estructuras algebraicas con las dos operaciones binarias ∨ y ∧ y las dos constantes ( operaciones nularias ) 0 y 1. El conjunto de todas las expresiones bien formadas que se pueden formular utilizando estas operaciones sobre elementos de un conjunto dado de generadores X se llamará W ( X ). Este conjunto de palabras contiene muchas expresiones que resultan denotar valores iguales en cada red. Por ejemplo, si a es algún elemento de X , entonces a  ∨ 1 = 1 y a  ∧ 1 = a . El problema verbal para redes libres acotadas es el problema de determinar cuál de estos elementos de W ( X ) denota el mismo elemento en la red libre acotada FX , y por lo tanto en cada red acotada.

El problema de palabras puede resolverse de la siguiente manera. Una relación ≤ _~ en W ( X ) puede definirse inductivamente estableciendo w ≤ _~ v si y solo si se cumple una de las siguientes condiciones:

1.   w = v (esto puede restringirse al caso donde w y v son elementos de X ),
2.   w = 0,
3.   v = 1,
4.   w = w ₁ ∨ w ₂ y tanto w ₁ ≤ _~ v como w ₂ ≤ _~ v se cumplen,
5.   w = w ₁ ∧ w ₂ y se cumple w ₁ ≤ _~ v o w ₂ ≤ _~ v ,
6.   v = v ₁ ∨ v ₂ y se cumple w ≤ _~ v ₁ o w ≤ _~ v ₂ ,
7.   v = v ₁ ∧ v ₂ y tanto w ≤ _~ v ₁ como w ≤ _~ v ₂ se cumplen.

Esto define un preorden ≤ _~ en W ( X ), por lo que una relación de equivalencia puede definirse por w ~ v cuando w ≤ _~ v y v ≤ _~ w . Entonces se puede demostrar que el conjunto cociente parcialmente ordenado W ( X )/~ es la red acotada libre FX . ^{[35] [36]} Las clases de equivalencia de W ( X )/~ son los conjuntos de todas las palabras w y v con w ≤ _~ v y v ≤ _~ w . Dos palabras bien formadas v y w en W ( X ) denotan el mismo valor en cada red acotada si y solo si w ≤ _~ v y v ≤ _~ w ; las últimas condiciones se pueden decidir efectivamente utilizando la definición inductiva anterior. La tabla muestra un ejemplo de cálculo para demostrar que las palabras x ∧ z y x ∧ z ∧( x ∨ y ) denotan el mismo valor en cada red acotada. El caso de las redes que no están acotadas se trata de manera similar, omitiendo las reglas 2 y 3 en la construcción anterior de ≤ _~ .

Ejemplo: Un sistema de reescritura de términos para decidir el problema de palabras en el grupo libre

Bläsius y Bürckert ^[37] demuestran el algoritmo de Knuth-Bendix en un conjunto de axiomas para grupos. El algoritmo produce un sistema de reescritura de términos confluente y noetheriano que transforma cada término en una única forma normal . ^[38] Las reglas de reescritura están numeradas de forma incontigua ya que algunas reglas se volvieron redundantes y se eliminaron 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

${\displaystyle ((a^{-1}\cdot a)\cdot (b\cdot b^{-1}))^{-1}\mathrel {\overset {R2}{\rightsquigarrow }} (1\cdot (b\cdot b^{-1}))^{-1}\mathrel {\overset {R13}{\rightsquigarrow }} (1\cdot 1)^{-1}\mathrel {\overset {R1}{\rightsquigarrow }} 1^{-1}\mathrel {\overset {R8}{\rightsquigarrow }} 1}$, y

${\displaystyle b\cdot ((a\cdot b)^{-1}\cdot a)\mathrel {\overset {R17}{\rightsquigarrow }} b\cdot ((b^{-1}\cdot a^{-1})\cdot a)\mathrel {\overset {R3}{\rightsquigarrow }} b\cdot (b^{-1}\cdot (a^{-1}\cdot a))\mathrel {\overset {R2}{\rightsquigarrow }} b\cdot (b^{-1}\cdot 1)\mathrel {\overset {R11}{\rightsquigarrow }} b\cdot b^{-1}\mathrel {\overset {R13}{\rightsquigarrow }} 1}$

comparten la misma forma normal, es decir, ; por lo tanto, ambos términos son iguales en cada grupo. 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 cada grupo. De hecho, suelen ser diferentes en grupos no abelianos . ${\displaystyle 1}$ ${\displaystyle 1\cdot (a\cdot b)}$ ${\displaystyle b\cdot (1\cdot a)}$ ${\displaystyle a\cdot b}$ ${\displaystyle b\cdot a}$

Véase también

• Problema de conjugación
• Problema de isomorfismo de grupos

Referencias

1. Evans, Trevor (1978). "Problemas de palabras". Boletín de la Sociedad Americana de Matemáticas . 84 (5): 790. doi : 10.1090/S0002-9904-1978-14516-9 .
2. Cohen, Joel S. (2002). Álgebra computacional y computación simbólica: algoritmos elementales . Natick, Mass.: AK Peters. pp. 90–92. ISBN 1568811586.
3. Miller, Charles F. (2014). Downey, Rod (ed.). "Máquinas de Turing para problemas verbales" (PDF) . El legado de Turing : 330. doi :10.1017/CBO9781107338579.010. hdl :11343/51723. ISBN 9781107338579. Recuperado el 6 de diciembre de 2021 .
4. Stillwell, John (1982). "El problema de las palabras y el problema del isomorfismo para grupos". Boletín de la Sociedad Matemática Americana . 6 (1): 33–56. doi : 10.1090/S0273-0979-1982-14963-1 .
5. Müller-Stach, Stefan (12 de septiembre de 2021). «Max Dehn, Axel Thue y lo indecidible». pág. 13. arXiv : 1703.09750 [math.HO].
6. Steinby, Magnus; Thomas, Wolfgang (2000). "Árboles y reescritura de términos en 1910: sobre un artículo de Axel Thue". Boletín de la Asociación Europea de Ciencias Informáticas Teóricas . 72 : 256–269. CiteSeerX 10.1.1.32.8993 . MR  1798015. 
7. Dehn, Max (1911). "Über unendliche diskontinuierliche Gruppen". Annalen Matemáticas . 71 (1): 116-144. doi :10.1007/BF01456932. ISSN  0025-5831. SEÑOR  1511645. S2CID  123478582.
8. Dehn, Max (1912). "Transformación der Kurven auf zweiseitigen Flächen". Annalen Matemáticas . 72 (3): 413–421. doi :10.1007/BF01456725. ISSN  0025-5831. SEÑOR  1511705. S2CID  122988176.
9. Greendlinger, Martin (junio de 1959). "Algoritmo de Dehn para el problema de palabras". Communications on Pure and Applied Mathematics . 13 (1): 67–83. doi :10.1002/cpa.3160130108.
10. Lyndon, Roger C. (septiembre de 1966). "Sobre el algoritmo de Dehn". Annalen Matemáticas . 166 (3): 208–228. doi :10.1007/BF01361168. hdl : 2027.42/46211 . S2CID  36469569.
11. Schupp, Paul E. (junio de 1968). "Sobre el algoritmo de Dehn y el problema de la conjugación". Annalen Matemáticas . 178 (2): 119-130. doi :10.1007/BF01350654. S2CID  120429853.
12. Power, James F. (27 de agosto de 2013). "El artículo de Thue de 1914: una traducción". arXiv : 1308.5858 [cs.FL].
13. Véase Historia de la tesis de Church-Turing . Las fechas se basan en Sobre proposiciones formalmente indecidibles de Principia Mathematica y sistemas relacionados y Sistemas de lógica basados ​​en ordinales .
14. Post, Emil L. (marzo de 1947). "Recursive Unsolvability of a problem of Thue" (PDF) . Journal of Symbolic Logic . 12 (1): 1–11. doi :10.2307/2267170. JSTOR  2267170. S2CID  30320278 . Consultado el 6 de diciembre de 2021 .
15. Mostowski, Andrzej (septiembre de 1951). "A. Markov. Névožmoinost' nékotoryh algoritmov v téorii associativnyh sistém (Imposibilidad de ciertos algoritmos en la teoría de sistemas asociativos). Doklady Akadémii Nauk SSSR, vol. 77 (1951), págs. 19-20". Revista de Lógica Simbólica . 16 (3): 215. doi : 10.2307/2266407. JSTOR  2266407.
16. Turing, AM (septiembre de 1950). "El problema verbal en semigrupos con cancelación". Anales de matemáticas . 52 (2): 491–505. doi :10.2307/1969481. JSTOR  1969481.
17. Novikov, PS (1955). "Sobre la insolubilidad algorítmica del problema verbal en la teoría de grupos". Actas del Instituto Steklov de Matemáticas (en ruso). 44 : 1–143. Zbl  0068.01301.
18. Boone, William W. (1954). "Ciertos problemas simples e irresolubles de la teoría de grupos. I". Indagationes Mathematicae (Actas) . 57 : 231–237. doi :10.1016/S1385-7258(54)50033-8.
19. Boone, William W. (1957). "Ciertos problemas simples e irresolubles de la teoría de grupos. VI". Indagationes Mathematicae (Actas) . 60 : 227–232. doi : 10.1016/S1385-7258(57)50030-9 .
20. Britton, JL (octubre de 1958). "El problema verbal para grupos". Actas de la London Mathematical Society . s3-8 (4): 493–506. doi :10.1112/plms/s3-8.4.493.
21. Boone, William W. (1958). "El problema de las palabras" (PDF) . Actas de la Academia Nacional de Ciencias . 44 (10): 1061–1065. Bibcode :1958PNAS...44.1061B. doi : 10.1073/pnas.44.10.1061 . PMC 528693 . PMID  16590307. Zbl  0086.24701. 
22. Boone, William W. (septiembre de 1959). "El problema de las palabras". Anales de las matemáticas . 70 (2): 207–265. doi :10.2307/1970103. JSTOR  1970103.
23. Higman, G. (8 de agosto de 1961). "Subgrupos de grupos finitamente presentados". Actas de la Royal Society de Londres. Serie A. Ciencias matemáticas y físicas . 262 (1311): 455–475. Bibcode :1961RSPSA.262..455H. doi :10.1098/rspa.1961.0132. S2CID  120100270.
24. Britton, John L. (enero de 1963). "El problema de las palabras". Anales de las matemáticas . 77 (1): 16–32. doi :10.2307/1970200. JSTOR  1970200.
25. Simpson, Stephen G. (18 de mayo de 2005). "Una prueba ingeniosa de la insolubilidad del problema verbal para grupos finitamente presentados" (PDF) . Consultado el 6 de diciembre de 2021 .
26. "Subgrupos de grupos finitamente presentados". Matemáticas de la URSS-Sbornik . 103 (145): 147–236. 13 de febrero de 1977. doi :10.1070/SM1977v032n02ABEH002376.
27. Matiyasevich, Yuri; Sénizergues, Géraud (enero de 2005). "Problemas de decisión para sistemas semi-Thue con algunas reglas". Ciencias de la Computación Teórica . 330 (1): 145–169. doi : 10.1016/j.tcs.2004.09.016 .
28. Davis, Martin (1978). "¿Qué es un cálculo?" (PDF) . Mathematics Today Twelve Informal Essays : 257–259. doi :10.1007/978-1-4613-9435-8_10. ISBN 978-1-4613-9437-2. Recuperado el 5 de diciembre de 2021 .
29. Baader, Franz; Nipkow, Tobias (5 de agosto de 1999). Term Rewriting and All That [Reescritura de términos y todo eso]. Cambridge University Press. págs. 59–60. ISBN 978-0-521-77920-3.
30. • Matiyasevich, Yu. V. (1967). "Простые примеры неразрешимых ассоциативных исчислений" [Ejemplos sencillos de cálculos asociativos indecidibles]. Doklady Akademii Nauk SSSR (en ruso). 173 (6): 1264-1266. ISSN  0869-5652.
    • Matiyasevich, Yu. V. (1967). "Ejemplos sencillos de cálculos asociativos indecidibles". Matemáticas soviéticas . 8 (2): 555–557. ISSN  0197-6788.
31. Novikov, PS (1955). "Sobre la insolubilidad algorítmica del problema verbal en la teoría de grupos". Trudy Mat. Inst. Steklov (en ruso). 44 : 1–143.
32. Statman, Rick (2000). "Sobre el problema de las palabras para combinadores". Técnicas de reescritura y aplicaciones . Apuntes de clase en informática. 1833 : 203–213. doi :10.1007/10721975_14. ISBN 978-3-540-67778-9.
33. Beke, Tibor (mayo de 2011). "Categorización, reescritura de términos y el procedimiento Knuth-Bendix". Revista de álgebra pura y aplicada . 215 (5): 730. doi : 10.1016/j.jpaa.2010.06.019 .
34. Peter T. Johnstone, Stone Spaces , (1982) Cambridge University Press, Cambridge, ISBN 0-521-23893-5 . (Véase el capítulo 1, párrafo 4.11) 
35. Whitman, Philip M. (enero de 1941). "Free Lattices". Anales de Matemáticas . 42 (1): 325–329. doi :10.2307/1969001. JSTOR  1969001.
36. Whitman, Philip M. (1942). "Free Lattices II". Anales de Matemáticas . 43 (1): 104–115. doi :10.2307/1968883. JSTOR  1968883.
37. KH Bläsius y H.-J. Bürckert, ed. (1992). Sistema de deducciones . Oldenburgo. pag. 291.; aquí: p.126, 134
38. Aplicar reglas en cualquier orden a un término, siempre que sea posible; el resultado no depende del orden; es la forma normal del término.