Montrer que le problème de l'arrêt est décidable pour un seul passage des machines de Turing

Question

$ L = \ {<\! M, x \!> \, \ Mi M de \ texte {fonction de transition ne peut se déplacer à droite et} M \ texte {} x sur des arrêts \} $. Je dois montrer que $ L $ est récursive / décidable.

Je pensais que de vérifier l'encodage de $ M $ pour la première et de déterminer si sa fonction de transition ne se déplace que la droite (Puis-je faire cela?). Si oui essayez de simuler $ M $ en $ x $ pour $ | Q | + 1 étapes de $, si elle arrête alors $ <\ M, x \!> \, \ En L $ est par ailleurs pas

Est-ce correct?

Answer 1

Je suppose que $ Q $ est réglé en état de $ M $. Si oui, cette exécution lié ne fait pas beaucoup de sens; en particulier, une machine de Turing avec trois états peut se déplacer à la fin de l'entrée et vérifier si $ x $ est un nombre pair; il est clairement ne suffit pas d'attendre trois étapes.

La question suivante est de savoir si un calculable lié à l'exécution de l'arrêt des machines en un seul passage. Malheureusement, il n'y a pas. $ M $ et peut-être non déterministes arrêt après un nombre quelconque d'étapes

Nous determinise M $ $ en simulant (qui est calculable) et recherchez une destination de tous les chemins. Maintenant, on arrive quelque part: après avoir consommé l'entrée, il y a deux cas. Soit $ M $ ou de haltes, il entre dans une boucle. Comme il ne se déplace à droite (dans la bande vide), ces boucles peuvent être détectées.

  

Pour mettre les choses ensemble, nous simulons un déterminisation de $ M $. Nous courons chaque branche jusqu'à $ x $ est consumed¹ puis pour un autre $ | Q | \ cdot | \ Sigma_T | $ étapes, $ Q $ l'ensemble des états et $ \ Sigma_T $ l'alphabet de bande de $ M $. À ce stade, $ M $ a soit arrêté ou boucles (dans cette branche), que nous détectons par une paire de symbole de l'état actuel et la bande se produisant pour la deuxième fois. Il suffit de vérifier de nombreuses branches jusqu'à finiment à une limite calculable, donc $ L $ est récursive.

---

1. $ M $ boucle pourrait ici déjà si ne bouge pas la tête est autorisée, mais qui peut être détectée, aussi.