Como um sistema de tag cíclico pode parar com uma saída?

Por exemplo, podemos dizer que temos um programa abstrato que, dada uma string binária finita como entrada, remove todos os zeros (ou seja, 0010001101011 é avaliado como 111111), que é definitivamente uma função computável de Turing.

Como um sistema de tag cíclico calcula isso (o que pode, por definição, ser concluído por Turing) quando é interrompido apenas quando atinge a string vazia? O artigo da Wikipedia fornece um exemplo de conversão para um sistema de duas marcas, mas adiciona uma parada emulada que o sistema original não possui.

Não consigo encontrar nenhuma referência sobre como um sistema de etiquetas cíclicas pára significativamente. Qual deve ser sua saída? Eu considerei coisas como

• Número de etapas (mas a entrada restringe a saída possível sem algum tipo de codificação sofisticada que não consigo encontrar)
• A última produção (mas que possui apenas uma faixa de saída finita)
• Pontos fixos (que não podem ser detectados neste sistema e existem apenas com regras e entradas de produção muito limitadas)

mas eles não funcionam, pelo menos não do jeito que eu possa ver.

Neary e Woods descrevem uma simulação eficiente de máquinas de Turing usando sistemas de etiquetas cíclicas, melhorando o trabalho de Matthew Cook . Turing-completeness é uma noção um tanto fluida e informal. Um sistema de computação X simula outro sistema de computação Y. Se, em cada programa em Y, pudermos criar um programa em X de tal forma que, olhando a transcrição do programa X, possamos recuperar uma transcrição do programa Y.

Você pode olhar os documentos acima para ver o que isso significa para os sistemas de etiquetas cíclicas. A idéia básica é que, quando a máquina de Turing parar, os sistemas cíclicos de etiquetas continuam funcionando, repetindo para sempre a mesma sequência de configurações, representando a configuração de parada da máquina de Turing. Nesse sentido, ele pode realmente calcular funções.

Em uma resposta anterior, observei que alguns modelos de computação podem computar apenas problemas de decisão, no sentido de que eles não param, ou com apenas um bit de saída. Nesse caso, você pode codificar a função geral de pelo menos duas maneiras:

1. Dada uma função , considere a linguagem dos pares .$f$$\langle x,f(x) \rangle$

2. Dada uma função , considere a linguagem de triplos tal que o th pouco de (se houver) é igual a .$f$$\langle x,i,b \rangle$$i$$f(x)$$b$

Como sempre, exigimos que a máquina sempre pare.

Embora as versões sem interrupção do tag cíclico possam ser de especial interesse para os autômatos celulares, um sistema de tag cíclico também pode ser projetado para simular uma máquina de Turing universal de forma que pare se a TM parar, exibindo uma palavra de saída que codifica o saída da máquina:

1. Simule a TM com um sistema de 2 tags que codifica todas as configurações instantâneas da TM, usando um "alfabeto de saída" separado para codificar qualquer configuração de parada, de modo que o sistema de tags pare (apagando esta palavra letra por letra) se o TM pára. ( Este artigo mostra em detalhes como isso pode ser feito usando uma formulação de TMs para máquinas Wang .)

2. Simule o sistema de 2 marcações por um sistema de marcações cíclicas, conforme descrito na seção do sistema de marcações cíclicas do artigo da Wikipedia . Como cada letra no alfabeto de saída com 2 marcadores possui uma sequência vazia como seu anexo (causando a interrupção da simulação com 2 marcadores), o sistema de marcadores cíclicos terá o mesmo comportamento de parada / saída.

A chave nesta abordagem é que um alfabeto de saída designado, digamos , permite que cada uma de suas letras tenha a sequência vazia como seu anexo ( ), fazendo com que a simulação apague a palavra de dados e parar.$\{\alpha_i\}$$\alpha_i\rightarrow \epsilon$

NB : Para todos os três tipos de sistema (TM, tag, tag cíclico), a identificação inequívoca da saída pode ser garantida usando um alfabeto de saída especificado, e isso pode ser feito para as variedades de parada e não parada desses sistemas. (Dado que as TMs "padrão" são do tipo de parada, é irônico que as máquinas de computação originais de Turing fossem da variedade não de parada com o alfabeto de saída .)$\{0,1\}$

Com a mesma abordagem, também podemos construir directamente um simples sistema de 2 tag para apagar qualquer s de uma cadeia binária, em seguida, simular que com tag cíclica. Os cálculos se tornam tediosos rapidamente, então apenas o aplicaremos à sequência de entrada , interrompendo com a sequência de saída . (O símbolo indicará a sequência vazia.)$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

produções:

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

computação:

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

etiqueta cíclica

codificando o alfabeto de duas tags:

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

computação:

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
-                                         -