Diticulture des machines de Turing qui ne déplacent jamais les têtes au-delà de la chaîne d'entrée

Question

$ l_1=\ \ \ \ \ utilg m, w \ rangs: m \ texte {est un TM qui ne passe jamais la tête après la chaîne d'entrée} w \} $
$ l_2=\ \ \ \ u \ m \ rangs: m \ texte {est un TM qui ne déplace jamais la tête de la tête d'entrée} \} $

Considérez les deux langues ci-dessus.Je veux savoir quels sont décisibles.

Je sais que $ l_1 $ est décembre, car $ m $ n'a qu'une quantité finie deConfigurations possibles avec la chaîne d'entrée $ w $ , afin que nous puissions créer une machine Turing (TM) pour vérifier 1 étape après le nombre de combinaisons et décider.

Cependant, pour $ L_2 $ , pouvons-nous faire cela?Je me sens comme $ l_2 $ est indéformable, car nous ne pouvons y avoir aucune limite aux configurations possibles.

Answer 1

Le problème d'arrêt, $ \ mathsf {halt} $ réduit à $ \ \} $ .

Compte tenu d'une clé TM $ t $ et entrée $ w $ , créez une nouvelle classe TM $ n $ que sur toute entrée de longueur $ n $ , simule $ T $ sur entrée $ w $ pour $ N $ étapes, puis s'arrête, sauf si $ t $ est toujours arrêté avant $ n $ étapes, $ N $ déplacera sa tête vers la droite pour toujours.

Il y a un espace dans la réduction ci-dessus. Quand $ N $ simule $ t $ sur $ w $ pour $ n $ pas, il peut sortir de l'entrée lorsqu'il se déplace à gauche (nous supposons que l'entrée est mise à droite de l'origine, le Position initiale de N $ N $ S, inclusivement). Cet écart peut être résolu par le truc classique de "traduire la bande". Lorsque la simulation est sur le déplacement vers la gauche de l'origine, laissez $ n $ traduisez le courant de la cellule de la bande à droite. Alors $ n $ va à l'origine, comme s'il s'agissait de la cellule à gauche de l'origine. De cette façon, nous veillerons à ce que $ n $ ne quittera jamais la chaîne d'entrée tant que la $ $ sur $ w $ ne s'arrête pas. (Pour activer $ n $ Pour reconnaître l'origine, il doit toujours marquer l'origine avec un symbole "composé" qui indique également son symbole d'origine. Par exemple, si l'original symbole à l'origine est $ a $ , $ n $ devrait le changer en $ a_o $ , un symbole qui n'est pas $ a $ mais pointe vers $ a $ . Les symboles "composés" sont également utilisés lorsque $ n $ traduit le contenu de la bande.)

depuis $ \ mathsf {halt} $ n'est pas décidable, $ \ overline {l_2} $ n'est pas décidable. Donc, $ l_2 $ n'est pas décidable.