¿Cómo puede un sistema de etiquetas cíclicas detenerse con una salida?

Por ejemplo, podemos decir que tenemos un programa abstracto que, dada una cadena binaria finita como entrada, elimina todos los ceros (es decir, 0010001101011 se evalúa como 111111), que definitivamente es una función computable de Turing.

¿Cómo puede un sistema de etiquetas cíclicas calcular esto (que puede hacerlo, por definición de ser Turing completo) cuando solo se detiene cuando llega a la cadena vacía? El artículo de Wikipedia da un ejemplo de conversión a un sistema de 2 etiquetas, pero agrega una detención emulada que el sistema original no tiene.

No puedo encontrar ninguna referencia a cómo un sistema de etiquetas cíclicas se detiene significativamente. ¿Cuál se supone que es su salida? He considerado cosas como

• Número de pasos (pero luego la entrada restringe la salida posible sin algún tipo de codificación elegante que no puedo encontrar)
• La última producción (pero que solo tiene un rango de salida finito)
• Puntos fijos (que no se pueden detectar en este sistema y solo existen con entradas y reglas de producción muy limitadas)

pero no funcionan, al menos no puedo ver de ninguna manera.

Neary y Woods describen una simulación eficiente de máquinas Turing que utilizan sistemas de etiquetas cíclicas, mejorando el trabajo de Matthew Cook . La integridad de Turing es una noción algo fluida e informal. Un sistema informático X simula otro sistema informático Y si a cada programa en Y se le ocurre un programa en X, de modo que al observar la transcripción del programa X, podemos recuperar una transcripción del programa Y.

Puede consultar los documentos anteriores para ver qué significa esto para los sistemas de etiquetas cíclicas. La idea básica es que cuando la máquina de Turing se detiene, los sistemas de etiquetas cíclicas continúan, repitiendo para siempre la misma secuencia de configuraciones, representando la configuración de detención de la máquina de Turing. En este sentido, en realidad puede calcular funciones.

En una respuesta anterior, noté que algunos modelos de cálculo solo pueden calcular problemas de decisión, en el sentido de que no se detienen o se detienen con solo un bit de salida. En ese caso, puede codificar la función general de al menos dos formas:

1. Dada una función , considere el lenguaje de pares .$f$$\langle x,f(x) \rangle$

2. Dada una función , tenga en cuenta el lenguaje de triples tal que el ésimo bit de (si lo hay) es igual a .$f$$\langle x,i,b \rangle$$i$$f(x)$$b$

Como de costumbre, exigimos que la máquina se detenga siempre .

Si bien las versiones sin interrupción de la etiqueta cíclica pueden ser de especial interés para los autómatas celulares, también se puede diseñar un sistema de etiqueta cíclica para simular una máquina Turing universal de manera que se detenga si la TM se detiene, mostrando una palabra de salida que codifica salida de la máquina:

1. Simule la TM con un sistema de 2 etiquetas que codifique todas las configuraciones instantáneas de la TM, utilizando un "alfabeto de salida" separado para codificar cualquier configuración de detención, de modo que el sistema de etiquetas se detenga (borrando esta palabra letra por letra) si TM se detiene. ( Este documento muestra en detalle cómo se puede hacer esto usando una formulación de TM de máquina Wang ).

2. Simule el sistema de 2 etiquetas mediante un sistema de etiquetas cíclicas como se describe en la sección del sistema de etiquetas cíclicas del artículo de Wikipedia . Dado que cada letra en el alfabeto de salida de 2 etiquetas tiene una cadena vacía como su anexo (lo que hace que la simulación de 2 etiquetas se detenga), el sistema de etiqueta cíclica tendrá el mismo comportamiento de detención / salida.

La clave en este enfoque es que un alfabeto de salida designado, digamos , permite que cada una de sus letras tenga la cadena vacía como su adjunto ( ), haciendo que la simulación borre la palabra de datos y detener.$\{\alpha_i\}$$\alpha_i\rightarrow \epsilon$

NB : Para todos los tres tipos de sistema (TM, tag, etiqueta cíclico), la identificación inequívoca de salida se puede asegurar mediante el uso de un alfabeto de salida especificada, y esto se puede hacer tanto para detener y no detener las variedades de estos sistemas. (Dado que las TM "estándar" son del tipo de detención, es irónico que las máquinas de cómputo originales de Turing fueran de la variedad sin interrupción con el alfabeto de salida .)$\{0,1\}$

Con el mismo enfoque, también podemos construir directamente un sistema simple de 2 etiquetas para borrar cualquier s de una cadena binaria, luego simular eso con una etiqueta cíclica. Los cálculos se vuelven rápidamente tediosos, por lo que solo lo aplicaremos a la cadena de entrada , deteniéndonos con la cadena de salida . (El símbolo denotará la cadena vacía).$0$$101$$11$-

2 etiquetas

input alphabet {a,b}, output alphabet {c}
input encoding:
<0> = aa
<1> = bb
input = <101> = bbaabb
output decoding: <cc> = 1

producciones:

a -> - 
b -> cc 
c -> - 

cálculo:

bbaabb   <-- input word <101>
  aabbcc
    bbcc
      cccc  <-- output word <11>
        cc
         -

etiqueta cíclica

codificación del alfabeto de 2 etiquetas:

<a> = 100
<b> = 010
<c> = 001
cyclic tag system = [-,001001,-,-,-,-]
cyclic tag input = <bbaabb> = 010010100100010010 

cálculo:

appendant    dataword
---------    ---------------------------------------------------------------
-            010010100100010010  <-- input word <bbaabb> = <<101>>
001001        10010100100010010
-              0010100100010010001001
-               010100100010010001001
-                10100100010010001001
-                 0100100010010001001
-                  100100010010001001
001001              00100010010001001
-                    0100010010001001
-                     100010010001001
-                      00010010001001
-                       0010010001001
-                        010010001001
001001                    10010001001
-                          0010001001001001
-                           010001001001001
-                            10001001001001
-                             0001001001001
-                              001001001001  <-- output word <cccc> = <<11>>
001001                          01001001001
-                                1001001001
-                                 001001001
-                                  01001001
-                                   1001001
-                                    001001
001001                                01001
-                                      1001
-                                       001
-                                        01
-                                         1
-                                         -