Sistema Semi-Thue

Sistema de reescritura de cadenas

En la informática teórica y la lógica matemática, un sistema de reescritura de cadenas ( SRS ), históricamente llamado sistema semi-Thue , es un sistema de reescritura sobre cadenas de un alfabeto (normalmente finito ) . Dada una relación binaria entre cadenas fijas sobre el alfabeto, llamadas reglas de reescritura , denotadas por , un SRS extiende la relación de reescritura a todas las cadenas en las que el lado izquierdo y derecho de las reglas aparecen como subcadenas , es decir , donde , , y son cadenas. ${\displaystyle R}$ ${\displaystyle s\rightarrow t}$ ${\displaystyle usv\rightarrow utv}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle u}$ ${\displaystyle v}$

La noción de un sistema semi-Thue coincide esencialmente con la presentación de un monoide . Por lo tanto, constituyen un marco natural para resolver el problema verbal de los monoides y los grupos.

Un SRS puede definirse directamente como un sistema de reescritura abstracto . También puede verse como un tipo restringido de un sistema de reescritura de términos , en el que todos los símbolos de función tienen una aridad de como máximo 1. Como formalismo, los sistemas de reescritura de cadenas son Turing completos . ^[1] El nombre semi-Thue proviene del matemático noruego Axel Thue , quien introdujo el tratamiento sistemático de los sistemas de reescritura de cadenas en un artículo de 1914. ^[2] Thue introdujo esta noción con la esperanza de resolver el problema de las palabras para semigrupos presentados finitamente. Solo en 1947 se demostró que el problema era indecidible : este resultado fue obtenido de forma independiente por Emil Post y AA Markov Jr. ^{[3] [4]}

Definición

Un sistema de reescritura de cadenas o sistema semi-Thue es una tupla donde ${\displaystyle (\Sigma ,R)}$

• ${\displaystyle \Sigma }$es un alfabeto, que generalmente se supone finito. ^[5] Los elementos del conjunto (* es la estrella de Kleene aquí) son cadenas finitas (posiblemente vacías) en , a veces llamadas palabras en lenguajes formales ; aquí simplemente las llamaremos cadenas. ${\displaystyle \Sigma ^{*}}$ ${\displaystyle \Sigma }$
• ${\displaystyle R}$es una relación binaria en cadenas de , es decir, cada elemento se denomina regla (de reescritura) y normalmente se escribe . ${\displaystyle \Sigma }$ ${\displaystyle R\subseteq \Sigma ^{*}\times \Sigma ^{*}.}$ ${\displaystyle (u,v)\in R}$ ${\displaystyle u\rightarrow v}$

Si la relación es simétrica , entonces el sistema se llama sistema Thue . ${\displaystyle R}$

Las reglas de reescritura en se pueden extender naturalmente a otras cadenas en al permitir que las subcadenas se reescriban de acuerdo con . Más formalmente, la relación de reescritura de un paso relación inducida por on para cualquier cadena : ${\displaystyle R}$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle R}$ ${\displaystyle {\xrightarrow[{R}]{}}}$ ${\displaystyle R}$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle s,t\in \Sigma ^{*}}$

${\displaystyle s{\xrightarrow[{R}]{}}t}$si y sólo si existen tales que , , y . ${\displaystyle x,y,u,v\in \Sigma ^{*}}$ ${\displaystyle s=xuy}$ ${\displaystyle t=xvy}$ ${\displaystyle u\rightarrow v}$

Dado que es una relación en , el par se ajusta a la definición de un sistema de reescritura abstracto . Obviamente es un subconjunto de . Algunos autores utilizan una notación diferente para la flecha en (por ejemplo, ) para distinguirla de sí misma ( ) porque luego quieren poder eliminar el subíndice y aún así evitar la confusión entre y la reescritura de un paso inducida por . ${\displaystyle {\xrightarrow[{R}]{}}}$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle (\Sigma ^{*},{\xrightarrow[{R}]{}})}$ ${\displaystyle R}$ ${\displaystyle {\xrightarrow[{R}]{}}}$ ${\displaystyle {\xrightarrow[{R}]{}}}$ ${\displaystyle {\xrightarrow[{R}]{}}}$ ${\displaystyle R}$ ${\displaystyle \rightarrow }$ ${\displaystyle R}$ ${\displaystyle R}$

Claramente, en un sistema semi-Thue podemos formar una secuencia (finita o infinita) de cadenas producida comenzando con una cadena inicial y reescribiéndola repetidamente haciendo un reemplazo de subcadena a la vez: ${\displaystyle s_{0}\in \Sigma ^{*}}$

${\displaystyle s_{0}\ {\xrightarrow[{R}]{}}\ s_{1}\ {\xrightarrow[{R}]{}}\ s_{2}\ {\xrightarrow[{R}]{}}\ \ldots }$

Una reescritura de cero o más pasos como esta se captura mediante el cierre transitivo reflexivo de , denotado por (ver sistema de reescritura abstracta#Nociones básicas ). Esto se llama relación de reescritura o relación de reducción en inducida por . ${\displaystyle {\xrightarrow[{R}]{}}}$ ${\displaystyle {\xrightarrow[{R}]{*}}}$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle R}$

Congruencia de Thue

En general, el conjunto de cadenas de un alfabeto forma un monoide libre junto con la operación binaria de concatenación de cadenas (denotada como y escrita multiplicativamente eliminando el símbolo). En un SRS, la relación de reducción es compatible con la operación monoide, lo que significa que implica para todas las cadenas . Dado que es por definición un preorden , forma un preorden monoidal . ${\displaystyle \Sigma ^{*}}$ ${\displaystyle \cdot }$ ${\displaystyle {\xrightarrow[{R}]{*}}}$ ${\displaystyle x{\xrightarrow[{R}]{*}}y}$ ${\displaystyle uxv{\xrightarrow[{R}]{*}}uyv}$ ${\displaystyle x,y,u,v\in \Sigma ^{*}}$ ${\displaystyle {\xrightarrow[{R}]{*}}}$ ${\displaystyle \left(\Sigma ^{*},\cdot ,{\xrightarrow[{R}]{*}}\right)}$

De manera similar, el cierre simétrico transitivo reflexivo de , denotado (ver sistema de reescritura abstracta#Nociones básicas ), es una congruencia , lo que significa que es una relación de equivalencia (por definición) y también es compatible con la concatenación de cadenas. La relación se llama congruencia de Thue generada por R . En un sistema de Thue, es decir, si R es simétrico, la relación de reescritura coincide con la congruencia de Thue . ${\displaystyle {\xrightarrow[{R}]{}}}$ ${\displaystyle {\overset {*}{\underset {R}{\leftrightarrow }}}}$ ${\displaystyle {\overset {*}{\underset {R}{\leftrightarrow }}}}$ ${\displaystyle {\xrightarrow[{R}]{*}}}$ ${\displaystyle {\overset {*}{\underset {R}{\leftrightarrow }}}}$

Factor monoide y presentaciones monoides

Como es una congruencia, podemos definir el factor monoide del monoide libre por la congruencia de Thue de la manera habitual . Si un monoide es isomorfo con , entonces el sistema semi-Thue se denomina presentación monoide de . ${\displaystyle {\overset {*}{\underset {R}{\leftrightarrow }}}}$ ${\displaystyle {\mathcal {M}}_{R}=\Sigma ^{*}/{\overset {*}{\underset {R}{\leftrightarrow }}}}$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {M}}_{R}}$ ${\displaystyle (\Sigma ,R)}$ ${\displaystyle {\mathcal {M}}}$

Inmediatamente obtenemos algunas conexiones muy útiles con otras áreas del álgebra. Por ejemplo, el alfabeto { a , b } con las reglas { ab → ε, ba → ε }, donde ε es la cadena vacía , es una presentación del grupo libre en un generador. Si en cambio las reglas son simplemente { ab → ε }, entonces obtenemos una presentación del monoide bicíclico .

La importancia de los sistemas semi-Thue como presentación de monoides se hace más fuerte por lo siguiente:

Teorema : Todo monoide tiene una presentación de la forma , por lo tanto siempre puede presentarse mediante un sistema semi-Thue, posiblemente sobre un alfabeto infinito. ^[6] ${\displaystyle (\Sigma ,R)}$

En este contexto, el conjunto se denomina conjunto de generadores de , y se denomina conjunto de relaciones definitorias . Podemos clasificar inmediatamente los monoides en función de su presentación. se denomina ${\displaystyle \Sigma }$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle R}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {M}}}$

• finitamente generado si es finito. ${\displaystyle \Sigma }$
• finitamente presentado si tanto y son finitos. ${\displaystyle \Sigma }$ ${\displaystyle R}$

Indecidibilidad del problema de palabras

Post demostró que el problema verbal (para semigrupos) es indecidible en general, esencialmente reduciendo el problema de detención ^[7] para máquinas de Turing a una instancia del problema verbal.

Concretamente, Post ideó una codificación como una cadena finita del estado de una máquina de Turing más una cinta, de modo que las acciones de esta máquina puedan ser llevadas a cabo por un sistema de reescritura de cadenas que actúe sobre esta codificación de cadenas. El alfabeto de la codificación tiene un conjunto de letras para los símbolos en la cinta (donde significa espacio en blanco), otro conjunto de letras para los estados de la máquina de Turing y, finalmente, tres letras que tienen papeles especiales en la codificación. y son intuitivamente estados internos adicionales de la máquina de Turing a los que pasa cuando se detiene, mientras que marca el final de la parte no en blanco de la cinta; una máquina que llega a un debería comportarse igual que si hubiera un espacio en blanco allí, y el estuviera en la siguiente celda. Las cadenas que son codificaciones válidas de los estados de la máquina de Turing comienzan con un , seguido de cero o más letras de símbolo, seguido de exactamente una letra de estado interno (que codifica el estado de la máquina), seguido de una o más letras de símbolo, seguido de un final . Las letras de símbolo son directamente del contenido de la cinta, y la letra de estado interno marca la posición de la cabeza; El símbolo que sigue a la letra del estado interno es el de la celda que se encuentra actualmente bajo la cabeza de la máquina de Turing. ${\displaystyle S_{0},S_{1},\dotsc ,S_{m}}$ ${\displaystyle S_{0}}$ ${\displaystyle q_{1},\dotsc ,q_{r}}$ ${\displaystyle q_{r+1},q_{r+2},h}$ ${\displaystyle q_{r+1}}$ ${\displaystyle q_{r+2}}$ ${\displaystyle h}$ ${\displaystyle h}$ ${\displaystyle h}$ ${\displaystyle h}$ ${\displaystyle q_{i}}$ ${\displaystyle h}$

Una transición en la que la máquina, al estar en estado y ver el símbolo , vuelve a escribir símbolo , se mueve a la derecha y pasa al estado implementado por la reescritura. ${\displaystyle q_{i}}$ ${\displaystyle S_{k}}$ ${\displaystyle S_{l}}$ ${\displaystyle q_{j}}$

${\displaystyle q_{i}S_{k}\to S_{l}q_{j}}$

mientras que esa transición en lugar de moverse hacia la izquierda se implementa mediante la reescritura

${\displaystyle S_{p}q_{i}S_{k}\to q_{j}S_{p}S_{l}}$

con una instancia para cada símbolo en esa celda a la izquierda. En el caso de que lleguemos al final de la parte visitada de la cinta, usamos en su lugar ${\displaystyle S_{p}}$

${\displaystyle hq_{i}S_{k}\to hq_{j}S_{0}S_{l}}$,

alargando la cadena en una letra. Debido a que todas las reescrituras involucran una letra de estado interno , las codificaciones válidas solo contienen una de esas letras, y cada reescritura produce exactamente una de esas letras, el proceso de reescritura sigue exactamente la ejecución de la máquina de Turing codificada. Esto demuestra que los sistemas de reescritura de cadenas son Turing completos. ${\displaystyle q_{i}}$

La razón para tener dos símbolos detenidos es que queremos que todas las máquinas de Turing que se detienen terminen en el mismo estado total , no solo en un estado interno particular . Esto requiere limpiar la cinta después de detenerse, por lo que se come el símbolo de la izquierda hasta llegar a , donde pasa a que en su lugar se come el símbolo de la derecha. (En esta fase, el sistema de reescritura de cadenas ya no simula una máquina de Turing, ya que esta no puede eliminar celdas de la cinta). Una vez que se han ido todos los símbolos, hemos llegado a la cadena terminal . ${\displaystyle q_{r+1}}$ ${\displaystyle q_{r+2}}$ ${\displaystyle q_{r+1}}$ ${\displaystyle h}$ ${\displaystyle q_{r+2}}$ ${\displaystyle hq_{r+2}h}$

Un procedimiento de decisión para el problema de palabras también produciría un procedimiento para decidir si la máquina de Turing dada termina cuando se inicia en un estado total particular , al probar si y pertenecen a la misma clase de congruencia con respecto a este sistema de reescritura de cadenas. Técnicamente, tenemos lo siguiente: ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle hq_{r+2}h}$

Lema. Sea una máquina de Turing determinista y sea el sistema de reescritura de cadenas que implementa , como se describió anteriormente. Entonces se detendrá cuando se inicie desde el estado total codificado como si y solo si (es decir, si y solo si y son congruentes con Thue para ). ${\displaystyle M}$ ${\displaystyle R}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle t}$ ${\displaystyle t\mathrel {\overset {*}{\underset {R}{\leftrightarrow }}} hq_{r+2}h}$ ${\displaystyle t}$ ${\displaystyle hq_{r+2}h}$ ${\displaystyle R}$

Que si se detiene cuando se inicia desde es inmediato a partir de la construcción de (simplemente correr hasta que se detiene construye una prueba de ), pero también permite que la máquina de Turing dé pasos hacia atrás. Aquí se vuelve relevante que es determinista, porque entonces los pasos hacia adelante son todos únicos; en una caminata desde a el último paso hacia atrás debe ser seguido por su contraparte como un paso hacia adelante, por lo que estos dos se cancelan, y por inducción todos los pasos hacia atrás pueden eliminarse de tal caminata. Por lo tanto, si no se detiene cuando se inicia desde , es decir, si no tenemos , entonces tampoco tenemos . Por lo tanto, decidir nos dice la respuesta al problema de detención para . ${\displaystyle t\mathrel {\overset {*}{\underset {R}{\rightarrow }}} hq_{r+2}h}$ ${\displaystyle M}$ ${\displaystyle t}$ ${\displaystyle R}$ ${\displaystyle M}$ ${\displaystyle t\mathrel {\overset {*}{\underset {R}{\rightarrow }}} hq_{r+2}h}$ ${\displaystyle {\overset {*}{\underset {R}{\leftrightarrow }}}}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle {\overset {*}{\underset {R}{\leftrightarrow }}}}$ ${\displaystyle t}$ ${\displaystyle hq_{r+2}h}$ ${\displaystyle M}$ ${\displaystyle t}$ ${\displaystyle t\mathrel {\overset {*}{\underset {R}{\rightarrow }}} hq_{r+2}h}$ ${\displaystyle t\mathrel {\overset {*}{\underset {R}{\leftrightarrow }}} hq_{r+2}h}$ ${\displaystyle {\overset {*}{\underset {R}{\leftrightarrow }}}}$ ${\displaystyle M}$

Una aparente limitación de este argumento es que para producir un semigrupo con un problema verbal indecidible, primero se debe tener un ejemplo concreto de una máquina de Turing para la cual el problema de detención sea indecidible, pero las diversas máquinas de Turing que figuran en la prueba de la indecidibilidad del problema general de detención tienen todas como componente una máquina de Turing hipotética que resuelve el problema de detención, por lo que ninguna de esas máquinas puede existir en realidad; todo lo que prueba es que hay alguna máquina de Turing para la cual el problema de decisión es indecidible. Sin embargo, que haya alguna máquina de Turing con un problema de detención indecidible significa que el problema de detención para una máquina de Turing universal es indecidible (ya que puede simular cualquier máquina de Turing), y se han construido ejemplos concretos de máquinas de Turing universales. ${\displaystyle \Sigma ^{*}{\big /}{\overset {*}{\underset {R}{\leftrightarrow }}}}$ ${\displaystyle M}$

Conexiones con otras nociones

Un sistema semi-Thue también es un sistema de reescritura de términos , uno que tiene palabras monádicas (funciones) que terminan en la misma variable que los términos del lado izquierdo y derecho, ^[8] por ejemplo, una regla de término es equivalente a la regla de cadena . ${\displaystyle f_{2}(f_{1}(x))\rightarrow g(x)}$ ${\displaystyle f_{1}f_{2}\rightarrow g}$

Un sistema semi-Thue es también un tipo especial de sistema postcanónico , pero cada sistema postcanónico también puede reducirse a un SRS. Ambos formalismos son Turing completos , y por lo tanto equivalentes a las gramáticas irrestrictas de Noam Chomsky , que a veces se denominan gramáticas semi-Thue . ^[9] Una gramática formal solo se diferencia de un sistema semi-Thue por la separación del alfabeto en terminales y no terminales, y la fijación de un símbolo de inicio entre los no terminales. Una minoría de autores define en realidad un sistema semi-Thue como una tripleta , donde se denomina el conjunto de axiomas . Según esta definición "generativa" de sistema semi-Thue, una gramática irrestricta es simplemente un sistema semi-Thue con un solo axioma en el que se divide el alfabeto en terminales y no terminales, y se convierte el axioma en un no terminal. ^[10] El simple artificio de dividir el alfabeto en terminales y no terminales es muy poderoso; permite definir la jerarquía de Chomsky en función de qué combinación de terminales y no terminales contienen las reglas. Este fue un avance crucial en la teoría de los lenguajes formales . ${\displaystyle (\Sigma ,A,R)}$ ${\displaystyle A\subseteq \Sigma ^{*}}$

En computación cuántica, se puede desarrollar la noción de un sistema cuántico de Thue. ^[11] Dado que la computación cuántica es intrínsecamente reversible, se requiere que las reglas de reescritura sobre el alfabeto sean bidireccionales (es decir, el sistema subyacente es un sistema de Thue, ^{[ dudoso – discutir ]} no un sistema semi-Thue). En un subconjunto de caracteres del alfabeto se puede adjuntar un espacio de Hilbert , y una regla de reescritura que toma una subcadena a otra puede realizar una operación unitaria en el producto tensorial del espacio de Hilbert adjunto a las cadenas; esto implica que preservan el número de caracteres del conjunto . De manera similar al caso clásico, se puede demostrar que un sistema cuántico de Thue es un modelo computacional universal para la computación cuántica, en el sentido de que las operaciones cuánticas ejecutadas corresponden a clases de circuitos uniformes (como las de BQP cuando, por ejemplo, se garantiza la terminación de las reglas de reescritura de cadenas dentro de un número polinomial de pasos en el tamaño de entrada), o equivalentemente una máquina de Turing cuántica . ${\displaystyle \Sigma }$ ${\displaystyle Q\subseteq \Sigma }$ ${\displaystyle \mathbb {C} ^{d}}$ ${\displaystyle Q}$

Historia e importancia

Los sistemas Semi-Thue se desarrollaron como parte de un programa para añadir construcciones adicionales a la lógica , de modo de crear sistemas como la lógica proposicional , que permitirían expresar teoremas matemáticos generales en un lenguaje formal , y luego probarlos y verificarlos de manera automática y mecánica. La esperanza era que el acto de probar teoremas pudiera entonces reducirse a un conjunto de manipulaciones definidas sobre un conjunto de cadenas. Posteriormente se descubrió que los sistemas Semi-Thue son isomorfos a las gramáticas sin restricciones , que a su vez se sabe que son isomorfas a las máquinas de Turing . Este método de investigación tuvo éxito y ahora se pueden utilizar computadoras para verificar las pruebas de teoremas matemáticos y lógicos.

Por sugerencia de Alonzo Church , Emil Post, en un artículo publicado en 1947, demostró por primera vez que "cierto problema de Thue" era irresoluble, lo que Martin Davis afirma como "...la primera prueba de irresolubilidad de un problema de las matemáticas clásicas - en este caso el problema verbal de los semigrupos". ^[12]

Davis también afirma que la prueba fue ofrecida independientemente por AA Markov . ^[13]

Véase también

• Sistema L
• Algoritmo de Markov : una variante de los sistemas de reescritura de cadenas
• Rompecabezas MU

Notas

1. Véase la sección “Indecidibilidad del problema de las palabras” en este artículo.
2. Libro y Otto, pág. 36
3. Abramsky y otros, pág. 416
4. Salomaa y otros, pág. 444
5. En Book y Otto se define un sistema semi-Thue sobre un alfabeto finito a lo largo de la mayor parte del libro, excepto en el capítulo 7, cuando se introducen las presentaciones monoides, momento en el que se abandona discretamente esta suposición.
6. Book y Otto, Teorema 7.1.7, pág. 149
7. Post, siguiendo a Turing , técnicamente hace uso de la indecidibilidad del problema de impresión (si una máquina de Turing imprime alguna vez un símbolo particular), pero los dos problemas se reducen el uno al otro. De hecho, Post incluye un paso adicional en su construcción que convierte efectivamente la impresión del símbolo observado en detención.
8. Nachum Dershowitz y Jean-Pierre Jouannaud . Rewrite Systems (1990) pág. 6
9. DIA Cohen , Introducción a la teoría de la computación, 2.ª ed., Wiley-India, 2007, ISBN  81-265-1334-9 , pág. 572
10. Dan A. Simovici, Richard L. Tenney, Teoría de lenguajes formales con aplicaciones , World Scientific, 1999 ISBN 981-02-3729-4 , capítulo 4 
11. J. Bausch, T. Cubitt, M. Ozols, La complejidad de las cadenas de espín invariantes en la traducción con baja dimensión local , Ann. Henri Poincare 18(11), 2017 doi :10.1007/s00023-017-0609-7 pp. 3449-3513
12. Martin Davis (editor) (1965), Lo indecidible: documentos básicos sobre proposiciones indecidibles, problemas irresolubles y funciones computables , a partir de la página 292, Raven Press , Nueva York
13. AA Markov (1947) Doklady Akademii Nauk SSSR (NS) 55: 583–586

Referencias

Monografías

• Ronald V. Book y Friedrich Otto, Sistemas de reescritura de cadenas , Springer, 1993, ISBN 0-387-97965-4 . 
• Matthias Jantzen, Reescritura de cadenas confluentes , Birkhäuser, 1988, ISBN 0-387-13715-7 . 

Libros de texto

• Martin Davis , Ron Sigal, Elaine J. Weyuker, Computabilidad, complejidad y lenguajes: fundamentos de la informática teórica , 2.ª ed., Academic Press, 1994, ISBN 0-12-206382-1 , capítulo 7 
• Elaine Rich , Autómatas, computabilidad y complejidad: teoría y aplicaciones , Prentice Hall, 2007, ISBN 0-13-228806-0 , capítulo 23.5. 

Encuestas

• Samson Abramsky, Dov M. Gabbay, Thomas SE Maibaum (ed.), Manual de lógica en ciencias de la computación: modelado semántico , Oxford University Press, 1995, ISBN 0-19-853780-8 . 
• Grzegorz Rozenberg, Arto Salomaa (ed.), Manual de lenguajes formales: palabra, lenguaje, gramática , Springer, 1997, ISBN 3-540-60420-0 . 

Documentos de referencia

• Post, Emil (1947). "Recursive Unsolvability of a Problem of Thue". The Journal of Symbolic Logic . 12 (1): 1–11. doi :10.2307/2267170. JSTOR  2267170. S2CID  30320278. Archivado desde el original el 2019-09-29 . Consultado el 2019-09-29 .