Comment un système d'étiquettes cycliques peut-il s'arrêter avec une sortie?

Par exemple, nous pouvons dire que nous avons un programme abstrait qui, étant donné une chaîne binaire finie en entrée, supprime tous les zéros (c'est-à-dire que 0010001101011 est évalué à 111111), ce qui est certainement une fonction calculable par Turing.

Comment un système de balises cycliques peut-il calculer cela (ce qu'il peut, par définition, étant Turing-complet) alors qu'il s'arrête uniquement lorsqu'il atteint la chaîne vide? L'article de Wikipedia donne un exemple de conversion vers un système à 2 balises, mais il ajoute un arrêt émulé que le système d'origine n'a pas.

Je ne trouve aucune référence à la façon dont un système d'étiquette cyclique s'arrête de manière significative. Quelle est sa sortie censée être? J'ai pensé à des choses comme

• Nombre d'étapes (mais alors l'entrée restreint la sortie possible sans une sorte d'encodage sophistiqué que je ne trouve pas)
• La dernière production (mais qui n'a qu'une plage de sortie finie)
• Points fixes (qui ne peuvent pas être détectés dans ce système et n'existent qu'avec des règles de production et des intrants très limités)

mais ils ne fonctionnent pas, du moins pas du tout que je puisse voir.

Neary et Woods décrivent une simulation efficace de machines de Turing utilisant des systèmes d'étiquettes cycliques, améliorant le travail de Matthew Cook . La complétude de Turing est une notion quelque peu fluide et informelle. Un système informatique X simule un autre système informatique Y si, pour chaque programme en Y, nous pouvons trouver un programme en X de telle sorte qu'en regardant la transcription du programme X, nous pouvons récupérer une transcription du programme Y.

Vous pouvez consulter les articles ci-dessus pour voir ce que cela signifie pour les systèmes d'étiquettes cycliques. L'idée de base est que lorsque la machine Turing s'arrête, les systèmes d'étiquettes cycliques continuent de fonctionner, répétant à jamais la même séquence de configurations, représentant la configuration d'arrêt de la machine Turing. En ce sens, il peut réellement calculer des fonctions.

Dans une réponse antérieure, j'ai noté que certains modèles de calcul ne peuvent calculer que des problèmes de décision, dans le sens où ils ne s'arrêtent pas ou s'arrêtent avec un seul bit de sortie. Dans ce cas, vous pouvez coder la fonction générale d'au moins deux façons:

1. Étant donné une fonction $f$, considérez la langue des paires $\langle x,f(x) \rangle$.

2. Étant donné une fonction $f$, considérons le langage des triples telle sorte que le ème bit de (le cas échéant) soit égal à .$\langle x,i,b \rangle$$i$$f(x)$$b$

Comme d'habitude, nous exigeons que la machine s'arrête toujours .

Bien que les versions sans interruption de l'étiquette cyclique puissent être d'un intérêt particulier pour les automates cellulaires, un système d'étiquette cyclique peut également être conçu pour simuler une machine de Turing universelle de telle sorte qu'elle s'arrête si les TM s'arrêtent, affichant un mot de sortie qui code la sortie de la machine:

1. Simulez la MT avec un système à 2 balises qui code toutes les configurations instantanées de la TM, en utilisant un "alphabet de sortie" distinct pour coder toute configuration d'arrêt, de sorte que le système de balises s'arrête (en effaçant ce mot lettre par lettre) ssi le TM s'arrête. ( Cet article montre en détail comment cela peut être fait en utilisant une formulation de machine Wang de MT.)

2. Simulez le système à 2 balises par un système de balises cycliques comme décrit dans la section système de balises cycliques de l'article Wikipedia . Étant donné que chaque lettre de l'alphabet de sortie à 2 balises a une chaîne vide en tant qu'appendice (provoquant l'arrêt de la simulation à 2 balises), le système de balises cycliques aura le même comportement d'arrêt / sortie.

La clé de cette approche est qu'un alphabet de sortie désigné, par exemple $\{\alpha_i\}$, permet à chacune de ses lettres d'avoir la chaîne vide comme annexe ($\alpha_i\rightarrow \epsilon$), ce qui entraîne l'effacement et l'arrêt de la simulation.

NB : Pour les trois types de système (TM, étiquette, étiquette cyclique), l'identification univoque de la production peut être assurée à l'aide d' un alphabet de sortie spécifié, et cela peut être fait pour les stopper et non hésitants variétés de ces systèmes. (Étant donné que les MT "standard" sont du type à arrêt, il est ironique que les machines informatiques originales de Turing étaient de la variété sans arrêt avec alphabet de sortie$\{0,1\}$.)

Avec la même approche, nous pouvons également construire directement un système simple à 2 balises pour effacer tout $0$s à partir d'une chaîne binaire, puis simulez-la avec une balise cyclique. Les calculs deviennent rapidement fastidieux, nous ne l'appliquerons donc qu'à la chaîne d'entrée$101$, arrêt avec la chaîne de sortie $11$. (Le symbole -désignera la chaîne vide.)

2 balises

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

productions:

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

calcul:

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

balise cyclique

encodage de l'alphabet à 2 balises:

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

calcul:

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