Problema verbal (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 para grupos , pero también hay muchos otros casos. Un resultado profundo de la teoría computacional es que responder a esta pregunta es, en muchos casos importantes, indecidible . ^[1]

Antecedentes y motivación

En álgebra informática, a menudo se desea codificar expresiones matemáticas utilizando un árbol de expresiones. Pero a menudo existen varios árboles de expresión 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 denomina solución del problema verbal . Por ejemplo, imagine 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 verbal toma la forma de un teorema y algoritmo de forma normal que asigna cada elemento en una clase de equivalencia de expresiones a una única codificación conocida como forma normal ; el problema verbal se resuelve luego comparando estas formas normales mediante igualdad sintáctica . ^[1] Por ejemplo, uno podría decidir que es la forma normal de ,, y , e idear un sistema de transformación para reescribir esas expresiones en esa forma, demostrando en el proceso que todas las expresiones equivalentes se reescribirán en la misma forma normal. ^[2] Pero no todas las soluciones al problema verbal utilizan un teorema de forma normal; existen 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 verbal pregunta si dos términos que contienen constantes son iguales, una extensión adecuada del problema verbal conocida como 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 verbal 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 resultan ser 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 profundamente estudiados del problema verbal es en la teoría de semigrupos y grupos . Una cronología de artículos relevantes para el teorema de Novikov-Boone es la siguiente: ^{[3] [4]}

• 1910 : Axel Thue plantea un problema general de reescritura de términos en estructuras arbóreas. Afirma que "la solución de este problema en el caso más general tal vez esté asociada a dificultades insuperables". ^{[5] [6]} ( 1910 )
• 1911 : Max Dehn plantea el problema verbal para grupos presentados finitamente . ^[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] Los autores posteriores lo han extendido en gran medida a una amplia gama de grupos. Problemas de decisión teórica . ^{[9] [10] [11]} (1912)
• 1914 : Axel Thue plantea el problema verbal para semigrupos presentados finitamente. ^[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 presentados de forma finita con un problema verbal sin solución. ^{[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 no tiene solución, ^[16] avanzando en la construcción de Post. La demostración es difícil de seguir, pero marca un punto de inflexión en el problema planteado para grupos. ^{[3] : 342} (1950)
• 1955 : Pyotr Novikov da la primera prueba publicada de que el problema verbal para grupos no tiene solución, utilizando el resultado de cancelación de semigrupos de Turing. ^{[17] [3] : 354} La prueba contiene un "lema principal" equivalente al lema de Britton . ^{[3] : 355} (1955)
• 1954  - 1957 : William Boone muestra de forma independiente que el problema planteado para grupos no tiene solución, utilizando la construcción de semigrupos de Post. ^{[18] [19]} (1954) (1957)
• 1957  - 1958 : John Britton da otra prueba de que el problema verbal para grupos no tiene solución, basándose en el resultado de cancelación de semigrupos de Turing y en algunos de los trabajos anteriores de Britton. ^[20] Aparece una primera versión 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 presentados finitamente con el teorema de incrustación de Higman , ^[23] conectando la teoría de la recursión con la teoría de grupos de una manera inesperada y dando una prueba muy diferente de la insolubilidad 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 no tiene solución. ^[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 tiene solución. ^[26] (1977)

El problema verbal 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 aplicando reglas de ? Tenga en cuenta que la reescritura aquí es unidireccional. El problema verbal 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 planteados y de accesibilidad son indecidibles , es decir, no existe un algoritmo general para resolver este problema. ^[28] Esto es válido incluso si limitamos los sistemas a tener presentaciones finitas, es decir, un conjunto finito de símbolos y un conjunto finito de relaciones sobre esos símbolos. ^[27] Incluso el problema verbal restringido a términos fundamentales no es decidible para ciertos semigrupos presentados finitamente. ^{[29] [30]}

El problema verbal 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 verbal en cálculo combinatorio y cálculo lambda.

Una de las primeras pruebas de que un problema planteado es indecidible fue la de 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. Alonzo Church observó esto en 1936. ^[32]

Del mismo modo, uno tiene esencialmente el mismo problema en el cálculo lambda (sin escribir) : dadas dos expresiones lambda distintas, no existe 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 comparando las formas normales.

El problema verbal para sistemas de reescritura abstracta

Resolver el problema verbal: 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 planteado para un sistema de reescritura abstracta (ARS) es bastante conciso: dados los objetos x e y , ¿son equivalentes bajo ? ^[29] El problema verbal para una ARS es indecidible en general. Sin embargo, existe una solución computable para el problema verbal en el caso específico en el que cada objeto se reduce a una forma normal única en un número finito de pasos (es decir, el sistema es convergente ): dos objetos son equivalentes si y sólo si se reducen a la misma forma normal. ^[33] El algoritmo de finalizació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 verbal en álgebra universal.

En álgebra universal se estudian estructuras algebraicas que constan de 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 es entonces determinar, dadas dos expresiones (palabras) que involucran los generadores y las operaciones, si representan el mismo elemento del álgebra módulo las identidades. Los problemas planteados para grupos y semigrupos se pueden formular como problemas planteados para álgebras. ^[1]

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

El problema verbal de las celosías libres.

El problema verbal sobre redes libres y, más generalmente , redes acotadas libres tiene una solución decidible. Las redes acotadas son estructuras algebraicas con las dos operaciones binarias ∨ y ∧ y las dos constantes ( operaciones nulas ) 0 y 1. El conjunto de todas las expresiones bien formadas que se pueden formular utilizando estas operaciones en elementos de un conjunto dado de generadores X será llamarse 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 acotadas libres es el problema de determinar cuál de estos elementos de W ( X ) denota el mismo elemento en la red acotada libre FX y, por tanto, en cada red acotada.

El problema verbal se puede resolver de la siguiente manera. Una relación ≤ _~ en W ( X ) se puede definir inductivamente estableciendo w ≤ _~ v si y sólo si se cumple una de las siguientes condiciones:

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

Esto define un preorden ≤ _~ en W ( X ), por lo que se puede definir una relación de equivalencia mediante 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 sólo 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 mostrar que las palabras x ∧ z y x ∧ z ∧( x ∨ y ) denotan el mismo valor en cada red acotada. El caso de 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 verbal 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 genera un sistema de reescritura de términos confluentes y noetherianos que transforma cada término en una forma normal única . ^[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 sólo si ambos términos se transforman literalmente en el mismo término en 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, a saber. ; por lo tanto ambos términos son iguales en cada grupo. Como otro ejemplo, el término y tiene la forma normal y , respectivamente. Como 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 . ${\displaystyle 1}$ ${\displaystyle 1\cdot (a\cdot b)}$ ${\displaystyle b\cdot (1\cdot a)}$ ${\displaystyle a\cdot b}$ ${\displaystyle b\cdot a}$

Ver también

• problema de conjugación
• Problema de isomorfismo de grupo

Referencias

1. Evans, Trevor (1978). "Problemas de palabras". Boletín de la Sociedad Matemática Estadounidense . 84 (5): 790. doi : 10.1090/S0002-9904-1978-14516-9 .
2. Cohen, Joel S. (2002). Álgebra informática y computación simbólica: algoritmos elementales . Natick, Massachusetts: AK Peters. págs. 90–92. ISBN 1568811586.
3. Miller, Charles F. (2014). Downey, Rod (ed.). "Máquinas de Turing a problemas planteados" (PDF) . El legado de Turing : 330. doi :10.1017/CBO9781107338579.010. hdl :11343/51723. ISBN 9781107338579. Consultado el 6 de diciembre de 2021 .
4. Stillwell, John (1982). "El problema verbal y el problema de isomorfismo para grupos". Boletín de la Sociedad Matemática Estadounidense . 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". pag. 13. arXiv : 1703.09750 [matemáticas.HO].
6. Steinby, Magnus; Thomas, Wolfgang (2000). "Árboles y reescritura de términos en 1910: en un artículo de Axel Thue". Boletín de la Asociación Europea de Informática Teórica . 72 : 256–269. CiteSeerX 10.1.1.32.8993 . SEÑOR  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 verbal". Comunicaciones sobre Matemática Pura y Aplicada . 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. Poder, James F. (27 de agosto de 2013). "El artículo de Thue de 1914: una traducción". arXiv : 1308.5858 [cs.FL].
13. Ver Historia de la Iglesia – Tesis de 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. Publicación, Emil L. (marzo de 1947). "Insolubilidad recursiva de un problema de Thue" (PDF) . Revista de Lógica Simbólica . 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". Los Anales de las 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 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 Sociedad Matemática de Londres . T3-8 (4): 493–506. doi :10.1112/plms/s3-8.4.493.
21. Boone, William W. (1958). «El problema verbal» (PDF) . Procedimientos de la Academia Nacional de Ciencias . 44 (10): 1061-1065. Código bibliográfico : 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". Los 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 presentados finitamente". Actas de la Royal Society de Londres. Serie A. Ciencias Matemáticas y Físicas . 262 (1311): 455–475. Código bibliográfico : 1961RSPSA.262..455H. doi :10.1098/rspa.1961.0132. S2CID  120100270.
24. Britton, John L. (enero de 1963). "El problema de las palabras". Los 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 hábil de la insolubilidad del problema verbal para grupos presentados de forma finita" (PDF) . Consultado el 6 de diciembre de 2021 .
26. "Subgrupos de grupos presentados finitamente". 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". Informática Teórica . 330 (1): 145–169. doi : 10.1016/j.tcs.2004.09.016 .
28. Davis, Martín (1978). "¿Qué es una computación?" (PDF) . Matemáticas hoy Doce ensayos informales : 257–259. doi :10.1007/978-1-4613-9435-8_10. ISBN 978-1-4613-9437-2. Consultado el 5 de diciembre de 2021 .
29. , Franz; Nipkow, Tobias (5 de agosto de 1999). Reescritura de términos y todo eso. Prensa de la Universidad de Cambridge. 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 teoría de grupos". Trudy Mat. Inst. Steklov (en ruso). 44 : 1–143.
32. Estatista, Rick (2000). "Sobre el problema verbal para combinadores". Técnicas y aplicaciones de reescritura . Apuntes de conferencias sobre informática. 1833 : 203–213. doi :10.1007/10721975_14. ISBN 978-3-540-67778-9.
33. Beke, Tibor (mayo de 2011). "Categorificación, reescritura de términos y procedimiento Knuth-Bendix". Revista de Álgebra Pura y Aplicada . 215 (5): 730. doi : 10.1016/j.jpaa.2010.06.019 .
34. Peter T. Johnstone, Espacios de piedra , (1982) Cambridge University Press, Cambridge, ISBN 0-521-23893-5 . (Ver capítulo 1, párrafo 4.11) 
35. Whitman, Philip M. (enero de 1941). "Celosías libres". Los Anales de las Matemáticas . 42 (1): 325–329. doi :10.2307/1969001. JSTOR  1969001.
36. Whitman, Philip M. (1942). "Celosías libres 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, durante el mayor tiempo posible; el resultado no depende del orden; es la forma normal del término.