Le problème qui détermine-t-il chaque fois que le mot membre $ \ en $ l (m) décidable ou non?

Question

Nous sommes invités à déterminer si membre $ \ in $ in $ l (m). Vous devez comprendre que M n'est pas une machine spécifique et peut être une machine de Turing avec le même alphabet. Mon objectif est de déterminer chaque fois que ce problème est décidé ou non.

Mon idée était d'utiliser la réductibilité de la cartographie.L'objectif était de voir si nous pouvons traduire tous les problèmes de $ a_ {tm} $ connu pour être indéciable dans notre problème actuel.Cela rendrait notre problème actuel indéciable par la contagion.Cependant, je me débatte de le faire parce que je ne suis pas sûr si c'est possible. $ a_ {tm} $ est défini comme une machine de Turing m qui accepte le mot w.

Toute aide pour obtenir un décalcomanie serait appréciée.

Answer 1

Je l'essayerais comme ceci:

réduction de $ a_ {tm} $ : donné TM $ A $ A $ ="Conteneur mathématique"> $ w $ .

Utilisez cela pour définir une nouvelle machine $ A '$ qui fonctionne comme suit:

1. Exécutez comme $ a $ sur entrée $ w $
2. si $ a $ rejette $ w $ , entrez dans la boucle éternelle.
3. si $ a $ accepte, supprimez le contenu de la bande et écrivez "membre"