Sistema de etiquetas

En la teoría de la computación , un sistema de etiquetas es un modelo determinista de computación publicado por Emil Leon Post en 1943 como una forma simple de un sistema canónico de Post . ^{[ 1 ]} Un sistema de etiquetas también puede verse como una máquina abstracta , llamada máquina de etiquetas de Post (que no debe confundirse con las máquinas de Post-Turing ); en resumen, una máquina de estados finitos cuya única cinta es una cola FIFO de longitud ilimitada, de modo que en cada transición la máquina lee el símbolo en la cabeza de la cola, elimina un número constante de símbolos de la cabeza y agrega al final una cadena de símbolos que depende únicamente del primer símbolo leído en esta transición.

Debido a que todas las operaciones indicadas se realizan en una sola transición, una máquina de etiquetas tiene estrictamente un solo estado.

Un sistema de etiquetas es una tripleta ( m , A , P ), donde

• m es un número entero positivo , llamado número de eliminación .
• A es un alfabeto finito de símbolos, uno de los cuales puede ser un símbolo de parada especial . Todas las cadenas finitas (posiblemente vacías) en A se llaman palabras .
• P es un conjunto de reglas de producción , que asigna una palabra P(x) (llamada producción ) a cada símbolo x en A. La producción (digamos P( H ) ) asignada al símbolo de parada se ve más adelante que no juega ningún papel en los cálculos, pero por conveniencia se toma como P( H ) = 'H' .

Una palabra vacilante es una palabra que comienza con el símbolo de parada o cuya longitud es menor que m .

Se define una transformación t (denominada operación de etiquetado ) sobre el conjunto de palabras no detenidas, de modo que si x denota el símbolo más a la izquierda de una palabra S , entonces t ( S ) es el resultado de eliminar los m símbolos más a la izquierda de S y añadir la palabra P(x) a la derecha. Así, el sistema procesa la cabeza de m símbolos para generar una cola de longitud variable, pero la cola generada depende únicamente del primer símbolo de la cabeza.

Un cálculo mediante un sistema de etiquetas es una secuencia finita de palabras producida al iterar la transformación t , comenzando con una palabra dada inicialmente y deteniéndose cuando se produce una palabra de parada. (Según esta definición, un cálculo no se considera existente a menos que se produzca una palabra de parada en un número finito de iteraciones. Definiciones alternativas permiten cálculos que no se detienen, por ejemplo, utilizando un subconjunto especial del alfabeto para identificar las palabras que codifican la salida).

El término sistema de etiquetas m se usa a menudo para enfatizar el número de eliminación. Las definiciones varían un poco en la literatura (véase Referencias), siendo la que se presenta aquí la de Rogozhin. ^{[ 2 ]}

El uso de un símbolo de parada en la definición anterior permite que el resultado de un cálculo se codifique únicamente en la última palabra, mientras que de otro modo el resultado se codificaría en toda la secuencia de palabras producida al iterar la operación de etiqueta.

Una definición alternativa común no utiliza ningún símbolo de parada y trata todas las palabras de longitud menor que m como palabras de parada. Otra definición es la original utilizada por Post (1943) (descrita en la nota histórica a continuación), en la que la única palabra de parada es la cadena vacía .

Sistema de 2 etiquetas Alfabeto: {a,b,c,H} Reglas de producción: a --> ccbaH b --> cca c --> cc Cálculo Palabra inicial: baa acca caccbaH ccbaHcc baHcccc Hcccccca (alto). 

Sistema de 2 etiquetas Alfabeto: {a,b,c} Reglas de producción: a --> bc b --> a c --> aaa Cálculo Palabra inicial: aaa <--> n=3 abecedario CBC caaa aaaaa <--> 5 aaabc abcbc cbcbc cbcaaa caaaaaa aaaaaaaa <--> 8 aaaaaabc aaaabcbc aabcbcbc bcbcbcbc bcbcbca bcbcaa bcaaa aaaa <--> 4 aabc bcbc bca aa <--> 2 antes de Cristo a <--> 1 (detener) 

Para cada m > 1, el conjunto de sistemas de m etiquetas es Turing-completo ; es decir, para cada m > 1, se cumple que para cualquier máquina de Turing T dada , existe un sistema de m etiquetas que emula a T. En particular, se puede construir un sistema de 2 etiquetas para emular una máquina de Turing universal , como lo hicieron Wang (1963) y Cocke y Minsky (1964) .

Por el contrario, se puede demostrar que una máquina de Turing es una máquina de Turing universal probando que puede emular una clase Turing-completa de sistemas de m etiquetas. Por ejemplo, Rogozhin (1996) demostró la universalidad de la clase de sistemas de 2 etiquetas con alfabeto { a ₁ , ..., a _n , H } y producciones correspondientes { a _n a _n W ₁ , ..., a _n a _n W _n-1 , a _n a _n , H }, donde las W _k son palabras no vacías; luego demostró la universalidad de una máquina de Turing muy pequeña (de 4 estados y 6 símbolos) mostrando que puede simular esta clase de sistemas de etiquetas.

El sistema de 2 etiquetas es un simulador eficiente de máquinas de Turing universales, en${\displaystyle O(t^{2}\log t)}$tiempo. Es decir, si${\displaystyle M}$es una máquina de Turing determinista de una sola cinta que se ejecuta en tiempo${\displaystyle t}$, luego hay un sistema de 2 etiquetas que lo simula en${\displaystyle O(t^{2}\log t)}$tiempo. ^{[ 3 ]}

Esta versión del problema de la parada se encuentra entre los problemas de decisión indecidibles más simples y fáciles de describir :

Dado un entero positivo arbitrario n y una lista de n + 1 palabras arbitrarias P ₁ , P ₂ ,..., P _n , Q en el alfabeto {1,2,..., n }, ¿la aplicación repetida de la operación de etiquetado t : ijX → XP _i eventualmente convierte Q en una palabra de longitud menor que 2? Es decir, ¿termina la secuencia Q , t ¹ ( Q ), t ² ( Q ), t ³ ( Q ), ...?

La definición anterior difiere de la de Post (1943) , cuyos sistemas de etiquetas no utilizan ningún símbolo de parada, sino que se detienen solo en la palabra vacía, y la operación de etiqueta t se define de la siguiente manera:

• Si x denota el símbolo más a la izquierda de una palabra no vacía S , entonces t ( S ) es la operación que consiste en agregar primero la palabra P(x) al extremo derecho de S y luego eliminar los m símbolos más a la izquierda del resultado , eliminando todos si hay menos de m símbolos.

La observación anterior sobre la completitud de Turing del conjunto de sistemas de m etiquetas, para cualquier m > 1, también se aplica a estos sistemas de etiquetas tal como los definió originalmente Post.

Un sistema de etiquetas cíclicas es una modificación del sistema de etiquetas original. El alfabeto consta de solo dos símbolos, 0 y 1 , y las reglas de producción comprenden una lista de producciones que se consideran secuencialmente, volviendo al principio de la lista después de considerar la "última" producción. Para cada producción, se examina el símbolo más a la izquierda de la palabra: si el símbolo es 1 , la producción actual se añade al final derecho de la palabra; si el símbolo es 0 , no se añade ningún carácter a la palabra; en ambos casos, se elimina el símbolo más a la izquierda. El sistema se detiene cuando la palabra queda vacía. ^{[ 4 ]}

Sistema de etiquetas cíclicas Producciones: (010, 000, 1111) Cálculo Palabra inicial: 11001 Palabra de producción ---------- -------------- 010 11001 000 1001010 1111 001010000 010 01010000 000 1010000 1111 010000000 010 10000000 . . . . 

Un sistema de etiquetas m con alfabeto { a ₁ , ..., a _n } y producciones correspondientes { P ₁ , ..., P _n } se emula mediante un sistema de etiquetas cíclico con m*n producciones ( Q ₁ , ..., Q _n , -, -, ..., -), donde todas las producciones excepto las primeras n son la cadena vacía (denotada por ' - '). Las Q _k son codificaciones de las respectivas P _k , obtenidas al reemplazar cada símbolo del alfabeto del sistema de etiquetas por una cadena binaria de longitud n de la siguiente manera (esto también se aplicará a la palabra inicial de un cálculo del sistema de etiquetas):

a 1 = 100...00 a 2 = 010...00 . . . a n = 000...01

Es decir, una _k se codifica como una cadena binaria con un 1 en la k ^-ésima posición desde la izquierda y ceros en las demás. Las líneas sucesivas de un cálculo del sistema de etiquetas aparecerán entonces codificadas como cada ( m*n ) ^-ésima línea de su emulación por el sistema de etiquetas cíclico.

Sistema de 2 etiquetas Reglas de producción: (a --> bb, b --> abH, H --> H) Codificación alfabética: a = 100, b = 010, H = 001 Codificaciones de producción: (bb = 010 010, abH = 100 010 001, H = 001) Sistema de etiquetas cíclicas Producciones: (010 010, 100 010 001, 001, -, -, -) Cálculo del sistema de etiquetas Palabra inicial: ba abH Hbb (detenerse) Cálculo del sistema de etiquetas cíclicas Palabra inicial: 010 100 (=ba) Palabra de producción ---------- ------------------------------- * 010 010 010 100 (=ba) 100 010 001 10 100 001 0 100 100 010 001 - 100 100 010 001 - 00 100 010 001 - 0 100 010 001 * 010 010 100 010 001 (=abH) 100 010 001 00 010 001 010 010 001 0 010 001 010 010 - 010 001 010 010 - 10 001 010 010 - 0 001 010 010 * 010 010 parada emulada --> 001 010 010 (=Hbb) 100 010 001 01 010 010 001 1 010 010 - 010 010 001 ... ... 

• autómata de cola
• El juego de la vida de Conway

• Cocke, John ; Minsky, Marvin (1964). "Universalidad de los sistemas de etiquetas con P=2". Journal of the Association for Computing Machinery . 11 : 15–20 . doi : 10.1145/321203.321206 . hdl : 1721.1/6107 . S2CID 2799125 . 
• Cook, Matthew (2004). "Universalidad en autómatas celulares elementales" . Sistemas complejos . 15 : 1–40 . doi : 10.25088/ComplexSystems.15.1.1 . Archivado (PDF) del original el 28 de mayo de 2016.
• De Mol, Liesbeth (enero de 2008). "Sistemas de etiquetas y funciones tipo Collatz" . Theoretical Computer Science . 390 (1): 92– 101. doi : 10.1016/j.tcs.2007.10.020 . hdl : 1854/LU-436211 .
• Minsky, Marvin L. (noviembre de 1961). "Resolubilidad recursiva del problema de Post de "Tag" y otros temas en la teoría de las máquinas de Turing". Annals of Mathematics . 2. 74 (3): 437– 455. doi : 10.2307/1970290 . JSTOR 1970290 . 
• Minsky, Marvin L. (1967). Computación: Máquinas finitas e infinitas . Englewood Cliffs, NJ: Prentice–Hall . págs. 267–273 . ISBN  978-0131655638. LCCN 67-12342 . 
• Post, Emil (1943). "Reducciones formales del problema de decisión combinatoria" . American Journal of Mathematics . 65 (2): 197– 215. doi : 10.2307/2371809 . JSTOR 2371809 . (Los sistemas de etiquetas se presentan en la página  203 y siguientes ).
• Rogozhin, Yurii (20 de noviembre de 1996). "Pequeñas máquinas de Turing universales" . Theoretical Computer Science . 168 (2): 215– 240. doi : 10.1016/S0304-3975(96)00077-1 .
• Wang, Hao (1963). "Sistemas de etiquetas y sistemas de retraso". Annalen Matemáticas . 152 : 65– 74. doi : 10.1007/BF01343730 . S2CID 120383146 . 

• https://mathworld.wolfram.com/TagSystem.html
• https://mathworld.wolfram.com/CyclicTagSystem.html
• https://www.wolframscience.com/nks/p95/ (sistemas de etiquetas cíclicas)
• https://www.wolframscience.com/nks/p669/ (emulación de sistemas de etiquetas)