Une question relative à une machine de Turing avec un état inutile

Question

OK, alors voici une question d'un test passé dans ma Théorie de la classe de calcul:

  

Un état inutile dans un TM est celui qui est jamais entré sur une chaîne d'entrée. Laissez $$ \ mathrm {INUTILE} _ {\ mathrm {TM}} = \ {\ langle M, q \ rangle \ mid q \ texte {est un état inutile dans} M \}. $$   Montrer que $ \ mathrm {INUTILE} _ {\ mathrm {TM}} $ est indécidable.

Je crois avoir une réponse, mais je ne suis pas sûr si elle est correcte. Comprendra dans la section de réponse.

Answer 1

Ceci est clairement réductibles du problème d'arrêt. Si une machine $ M $ ne se limite pas à l'entrée $ x puis $ tout état final est « inutile ». Étant donné une entrée M $, x $ pour le problème de l'arrêt, il est facile de construire $ m_x $ qui arrête sur chaque entrée (donc son état final n'est pas inutile) si et seulement si $ M $ arrêts sur $ x $. De cette façon, vous pouvez décider si vous Enrayer problème pouvez décider $ \ mathrm {INUTILE} _ {\ mathrm {TM}} $, ce qui donne une contradiction.

Answer 2

Aux fins de cette preuve, nous allons supposer que $ \ mathrm {INUTILE} _ {\ mathrm {TM}} $ est décidable pour afficher une contradiction.

Créer TM $ R $ qui effectue les opérations suivantes:

• Convertis TM $ M $ à un $ P pushdown $ Automates avec une pile détendue (ie. Pas d'exigence LIFO). Ceci est équivalent à un graphe orienté détaillant la transition entre les états de $ M $.
• Marquer le état initial de $ P $.
• A partir de l'état initial commence une recherche en largeur d'abord le long de chaque bord sortant de marquage de chaque noeud non marqué.
• Lorsque la recherche se termine, s'il y a des noeuds non marqués qui correspondent à $ q $, acceptent ; sinon rejeter .

Ensuite, créez TM $ S $ = « En entrée $$

1. Créer TM $ R $ comme indiqué ci-dessus.
2. Exécuter $ q $ sur $ R $.
3. Si $ R retourne $ acceptent, accepte ; si $ R $ rejets de rejeter »

Ainsi, si $ R $ est un decider pour $ \ mathrm {INUTILE} _ {\ mathrm {TM}} $, alors $ S $ est un decider pour $ A _ {\ mathrm {TM}} $ (le problème d'acceptation ). Depuis $ A _ {\ mathrm {TM}} $ est prouvé indécidable (voir Michael Sipser Théorie de calcul théorème 4.11 à la page 174), nous avons atteint une contradiction. Par conséquent, l'hypothèse de départ est incorrecte et $ \ mathrm {INUTILE} _ {\ mathrm {TM}} $ est indécidable.