Vérification si Turing Machine passe au moins k> 2 états avant d'accepter un mot

Question

$ l={\ utilg m, k \ rangs \ mid \ existe w \ in l (m) \ texte {telle que $ m $ passe au moins $ k> 2 $ d'états distincts avant d'accepter $ w $} \} $

J'essaie de penser à la réduction pour prouver que cette langue n'est ni red noyau. Comment aborder ce problème?Y a-t-il un indice ou une intuition?

Je vérifie habituellement si le riz peut être utilisé, mais la question ici ne concerne pas la langue elle-même

Answer 1

clairement $ l $ est acceptable (simplement simuler $ M $ et garder une trace du nombre de états distincts rencontrés lors de la simulation). Nous montrons maintenant que ce n'est pas décidable.

si $ l $ ont été décidables, vous seriez capable de résoudre le problème d'arrêt comme suit: Compte tenu d'une clé $ t $ et d'une entrée $ x \ in \ sigma ^ * $ , construire un tm $ m $ qui ignore son entrée, simule $ t $ avec entrée $ x $ et, lorsque la simulation est terminée, accepte. Vous pouvez en outre vous assurer que, si $ M $ accepte, alors il traverse également au moins 3 $ états distincts En transition de l'état initial à un autre état (distinct) avant de démarrer la simulation de $ t $ .

.

Vérifiez maintenant si $ \ LANGE M, 3 \ RANGER \ IN L $ . Si la réponse est affirmative, il y a une partie $ w \ in \ sigma ^ * $ pour laquelle $ m (w) $ accepte, montrant que $ t (x) $ s'arrête. Si la réponse est négative, alors $ m $ ne s'arrête jamais, montrant que $ t (x) $ n'est pas arrêter.