sistema semi-Thue

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 (generalmente finito ) . Dada una relación binaria${\displaystyle R}$entre cadenas fijas sobre el alfabeto, llamadas reglas de reescritura , denotadas por${\displaystyle s\rightarrow t}$, 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${\displaystyle usv\rightarrow utv}$, dónde${\displaystyle s}$,${\displaystyle t}$,${\displaystyle u}$, y${\displaystyle v}$son cadenas.

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 de la palabra para monoides y 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 la palabra para semigrupos finitamente presentados. Recién en 1947 se demostró que el problema era indecidible ; este resultado fue obtenido independientemente por Emil Post y AA Markov Jr. ^{[ 3 ] [ 4 ]}

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

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

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

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

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

Desde${\displaystyle {\xrightarrow[{R}]{}}}$es una relación en${\displaystyle \Sigma ^{*}}$, la pareja${\displaystyle (\Sigma ^{*},{\xrightarrow[{R}]{}})}$Se ajusta a la definición de un sistema de reescritura abstracto . Obviamente${\displaystyle R}$es un subconjunto de${\displaystyle {\xrightarrow[{R}]{}}}$Algunos autores utilizan una notación diferente para la flecha en${\displaystyle {\xrightarrow[{R}]{}}}$(p.ej${\displaystyle {\underset {R}{\Rightarrow }}}$) para distinguirlo de${\displaystyle R}$él mismo (${\displaystyle \rightarrow }$) porque luego quieren poder eliminar el subíndice y aún así evitar confusiones entre${\displaystyle R}$y la reescritura de un solo paso inducida por${\displaystyle R}$.

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

${\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${\displaystyle {\xrightarrow[{R}]{}}}$, denotado por${\displaystyle {\xrightarrow[{R}]{*}}}$(ver sistema de reescritura abstracto#Nociones básicas ). Esto se denomina relación de reescritura o relación de reducción en${\displaystyle \Sigma ^{*}}$inducido por${\displaystyle R}$.

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

De manera similar, el cierre simétrico transitivo reflexivo de${\displaystyle {\xrightarrow[{R}]{}}}$, denotado${\displaystyle {\overset {*}{\underset {R}{\leftrightarrow }}}}$(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${\displaystyle {\overset {*}{\underset {R}{\leftrightarrow }}}}$se denomina congruencia de Thue generada por R. En un sistema de Thue, es decir, si R es simétrico, la relación de reescritura${\displaystyle {\xrightarrow[{R}]{*}}}$coincide con la congruencia de Thue${\displaystyle {\overset {*}{\underset {R}{\leftrightarrow }}}}$.

Desde${\displaystyle {\overset {*}{\underset {R}{\leftrightarrow }}}}$es una congruencia, podemos definir el monoide factorial${\displaystyle {\mathcal {M}}_{R}=\Sigma ^{*}/{\overset {*}{\underset {R}{\leftrightarrow }}}}$del monoide libre${\displaystyle \Sigma ^{*}}$por la congruencia de Thue de la manera habitual . Si un monoide${\displaystyle {\mathcal {M}}}$es isomorfo con${\displaystyle {\mathcal {M}}_{R}}$, luego el sistema semi-Thue${\displaystyle (\Sigma ,R)}$se denomina presentación monoide de${\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 ve reforzada por lo siguiente:

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

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

• generado finitamente si${\displaystyle \Sigma }$es finito.
• presentado de forma finita si ambos${\displaystyle \Sigma }$y${\displaystyle R}$son finitos.

Post demostró que el problema de la palabra (para semigrupos) es indecidible en general, esencialmente reduciendo el problema de la parada ^{[ 7 ]} para máquinas de Turing a una instancia del problema de la palabra (véase el problema de correspondencia de Post ).

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

Una transición donde la máquina al estar en estado${\displaystyle q_{i}}$y viendo el símbolo${\displaystyle S_{k}}$símbolo de respuesta${\displaystyle S_{l}}$, se mueve a la derecha y pasa al estado${\displaystyle q_{j}}$se implementa mediante la reescritura

${\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${\displaystyle S_{p}}$en esa celda a la izquierda. En el caso de que lleguemos al final de la porción visitada de la cinta, usamos en su lugar

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

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

La razón por la que hay dos símbolos detenidos${\displaystyle q_{r+1}}$y${\displaystyle q_{r+2}}$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 borrar la cinta después de la parada, por lo que${\displaystyle q_{r+1}}$come el símbolo a su izquierda hasta llegar al${\displaystyle h}$, donde hace la transición a${\displaystyle q_{r+2}}$que en su lugar se come el símbolo a su derecha. (En esta fase, el sistema de reescritura de cadenas ya no simula una máquina de Turing, puesto que esta no puede eliminar celdas de la cinta). Una vez que todos los símbolos han desaparecido, hemos llegado a la cadena terminal.${\displaystyle hq_{r+2}h}$.

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

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

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

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

Un sistema semi-Thue es también 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érminos${\displaystyle f_{2}(f_{1}(x))\rightarrow g(x)}$es equivalente a la regla de cadena${\displaystyle f_{1}f_{2}\rightarrow g}$.

Un sistema semi-Thue es también un tipo especial de sistema postcanónico , pero todo sistema postcanónico también puede reducirse a un SRS. Ambos formalismos son Turing completos y, por lo tanto, equivalentes a las gramáticas no restringidas 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 inicial entre los no terminales. Una minoría de autores define un sistema semi-Thue como una tripleta${\displaystyle (\Sigma ,A,R)}$, dónde${\displaystyle A\subseteq \Sigma ^{*}}$se denomina conjunto de axiomas . Bajo esta definición "generativa" del sistema semi-Thue, una gramática no restringida es simplemente un sistema semi-Thue con un único axioma en el que se divide el alfabeto en terminales y no terminales, y se convierte el axioma en un no terminal. ^{[ 10 ]} El sencillo artificio de dividir el alfabeto en terminales y no terminales es poderoso; permite definir la jerarquía de Chomsky en función de la combinación de terminales y no terminales que contienen las reglas. Este fue un desarrollo crucial en la teoría de los lenguajes formales .

En computación cuántica, se puede desarrollar la noción de un sistema de Thue cuántico. ^{[ 11 ]} Dado que la computación cuántica es intrínsecamente reversible, las reglas de reescritura sobre el alfabeto${\displaystyle \Sigma }$Se requiere que sean bidireccionales (es decir, el sistema subyacente es un sistema Thue, no un sistema semi-Thue). En un subconjunto de caracteres del alfabeto${\displaystyle Q\subseteq \Sigma }$Se puede adjuntar un espacio de Hilbert.${\displaystyle \mathbb {C} ^{d}}$y una regla de reescritura que transforma una subcadena en otra puede realizar una operación unitaria sobre el producto tensorial del espacio de Hilbert asociado a las cadenas; esto implica que conservan el número de caracteres del conjunto.${\displaystyle Q}$. De forma similar al caso clásico, se puede demostrar que un sistema de Thue cuántico 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 en un número polinomial de pasos en el tamaño de entrada), o equivalentemente una máquina de Turing cuántica .

Los sistemas semi-Thue se desarrollaron como parte de un programa para añadir construcciones adicionales a la lógica , con el fin de crear sistemas como la lógica proposicional , que permitirían expresar teoremas matemáticos generales en un lenguaje formal y, posteriormente, demostrarlos y verificarlos de forma automática y mecánica. La esperanza era que el acto de demostrar teoremas pudiera 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 no restringidas , las cuales, a su vez, son isomorfas a las máquinas de Turing . Este método de investigación tuvo éxito y ahora se pueden usar computadoras para verificar las demostraciones de teoremas matemáticos y lógicos.

A 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 para un problema de las matemáticas clásicas; en este caso, el problema de las palabras para semigrupos". ^{[ 12 ]}

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

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