L'ensemble des machines de Turing qui s'arrête au maximum en 50 étapes sur toutes les entrées est-il décidable?

19

Soit . Je dois décider si F est décidable ou récursivement énumérable. Je pense que c'est décidable, mais je ne sais pas comment le prouver.F={M:M est un TM qui s'arrête pour chaque entrée en 50 étapes au maximum}

Mes pensées

Cette partie "50 étapes" tourne immédiatement le signe R pour moi. S'il s'agissait d'une entrée spécifique, ce serait décidable. Cependant, ici, c'est pour chaque entrée. Le vérifier pour des entrées infinies me fait penser que le problème est co-RE , c'est -à- dire que son complément est acceptable.

Peut-être que je peux vérifier les configurations et voir que toutes les configurations après 50 étapes ne conduisent pas à accepter l'état - comment faire?

Jozef
la source

Réponses:

21

Considérons le problème plus général des machines qui s'arrêtent après au plus étapes, pour certains N 1 . (Ce qui suit est une simplification substantielle d'une version précédente de cette réponse, mais est effectivement équivalent.)NN1

Comme le fait remarquer swegi dans une réponse précédente, si la machine s'arrête après au plus étapes, seules les cellules 0 , 1 , , N - 1 sur la bande sont significatives. Il suffit alors de simuler la machine M sur toutes les chaînes d'entrée de la forme x Σ N , dont il existe un nombre fini.N0,1,,N-1MXΣN

  • Si l'une de ces simulations ne parvient pas à entrer dans un état d'arrêt par le Netransition, cela indique que toute chaîne d'entrée commençant par est celle pour laquelle la machine ne s'arrête pas dans les N premières étapes.XN
  • Si toutes ces simulations s'arrêtent au Netransition, puis s'arrête en N étapes sur toutes les entrées de n'importe quelle longueur (dont la sous-chaîne de longueur N est tout ce sur quoi elle agit).MNN
Niel de Beaudrap
la source
Et- Dois-je supposer que tel que sa longueur est plus longue que N est automatiquement rejeté? XN
Jozef
Pourquoi ne peut-il pas sauter plus loin que N cellule dans les N étapes du calcul?
Jozef
@Jozef: les simulations par toutes itérer simplement des chaînes d'entrée possibles de longueur N . Vous pouvez parcourir plusieurs chaînes, mais vous n'apprendrez rien de plus, car seuls les N premiers symboles importent de toute façon. La raison pour laquelle cela ne peut pas aller plus loin que N cellules est que les machines de Turing (ou leur définition standard de toute façon) ne déplacent qu'une cellule par étape.
Niel de Beaudrap
D'accord, je l'ai. vous ne vous occupez donc que des N premiers symboles de chaque mot, vous vérifiez donc toutes les combinaisons d'entre eux. pourquoi avez-vous supprimé la description des configurations?
Jozef
Il est toujours visible si vous regardez les modifications précédentes. Je révisa à cela parce que l'autre réponse était peut - être intéressant, beaucoup de ce qui a rendu « intéressant » ne sert à masquer le fait que la procédure de décision est rien de plus ou moins simuler sur toutes les entrées possibles de longueur N . J'ai pensé qu'il valait mieux réviser la réponse à quelque chose de beaucoup plus simple, et qui, fondamentalement, était à l'origine de ce qui rend le problème décidable. MN
Niel de Beaudrap
4

Si s'arrête en pas plus de 50 pas, les positions que M peut atteindre sur la bande normalement infinie sont limitées. Ainsi, la bande infinie peut être simulée par une bande finie. Cela signifie que la bande peut être simulée par un automate fini. Il s'ensuit qu'une machine de turing M qui ne s'arrête pas en plus de 50 pas est bisimilaire à un automate fini M ' .MMMM

Soit l'ensemble des états de M , F Q l'ensemble des états accepteurs et Γ l'alphabet. Ensuite , nous construisons l'ensemble des états Q ' de M ' comme suit: Q ' = { n , q , s , p , un QMFQΓQM p est la position de la tête de lecture / écriture au-dessus de la bande. Nous pouvons limiter la position à { - 50 , . . . , 50 } car le nombre d'étapes de calcul autorisées limite le nombre de positions accessibles.Q={n,q,s,p,a|n{0,...,50}qQ,sΓ,p{50,...,50},aqF}p{50,...,50}

Ayant un état de l'automate fini M ' puis des moyens que nous sommes à l' état q de l'automate d' origine avec s sur la bande à la position p , où également la tête de lecture / écriture est positionnée , après la n - ième étape de calcul. L'état est une accepter une si un t r u e .n,q,s,p,aMqspnatrue

Transformer la relation de transition d'une machine à béton est un peu plus de travail mais pas nécessaire pour la question d'origine, car il suffit de montrer que l'espace d'état est fini (et donc nous pouvons simplement tester chaque entrée avec une longueur d'au plus 50 symboles sur chacun de ces automates). L'idée est de construire une nouvelle relation de transition qui passe d'un état à un état n + 1 , q ' , s ' , p ' , un ' dans le nn,q,s,p,unen+1,q,s,p,an-ième étape de calcul ssi la transition a participé à la relation de transition originale.q,s,pq,s,p

swegi
la source
Comment simulez-vous le stockage sur la bande, c'est-à - dire la possibilité de revoir les symboles que vous avez déjà lus, sur un automate fini?
Niel de Beaudrap
@NieldeBeaudrap: Vous énumérez tout l'espace d'état, c'est-à-dire que vous effectuez une vérification de modèle de la bande finie et de l'automate de contrôle de la machine de turing.
swegi
1
Étant donné que l'OP pose des questions fondamentales de calculabilité pour les machines de Turing, vous voudrez peut-être décompresser ce croquis en quelque chose de plus complet. (Je n'ai moi-même jamais entendu l'expression «vérification de modèle» dans un contexte de calcul auparavant.) Dans le contexte, je suppose généralement par «automate fini» que vous entendez un DFA ou similaire, sauf indication contraire de votre part, et ce n'est pas clair pour moi ce que correspondrait à la contribution du DFA dans une telle construction. Si vous voulez juste dire un graphique représentant les trajectoires possibles de la MT, alors je suis d'accord.
Niel de Beaudrap
Avec le modèle vérifiant la partie finie de la bande, je veux dire essentiellement ce que vous avez écrit dans votre réponse: testez simplement chaque entrée de taille au plus 50 et vérifiez si un état d'acceptation est atteint.
swegi
1
Je souhaite que les gens cessent de propager le mythe selon lequel une bande de machine de Turing doit être infinie. Ce n'est pas le cas - il peut être fini tant qu'il est étendu au besoin.
reinierpost