Cartographie de la réduction de A à $ Complement _ {TM} $

Question

J'ai une question générale sur la réduction de la cartographie. Je l'ai vu plusieurs exemples de fonctions de réduction de $ A_ {TM} $

où A_ $ {TM} = de \ {\ langle M, w \ rangle: \ texte {} Pour M texte de {est une machine de Turing qui accepte string} w \} $

qui est excellent pour prouver indécidabilité. Mais dis que je veux prouver à la place méconnaissable. Autrement dit, je veux utiliser le corollaire donné $ A \ le_ {m} B $, si $ A $ est méconnaissable alors $ B $ est méconnaissable.

Donc, pour une langue méconnaissable arbitraire $ C $ qui peut être réduit à $ \ overline {A_ {TM}} $ (une langue par exemple suffirait à titre d'exemple), comment puis-je réduire $ \ overline {A_ {TM }} \ le_ {m} C $?

Par souci de simplicité, il suffit de considérer simplement TM $ \ overline {{A_ TM}} $.

EDIT

Pour plus de précisions, $ \ overline {A_ {TM}} = \ {\ langle M, w \ rangle: M texte de {est une machine à turation qui n'accepte pas string} w \} $

Answer 1

Soit de prendre $ de L _ {\ emptyset} = \ {\ langle M \ rangle \ mi L (M) = \ emptyset \} $, ce qui est, toutes les machines qui acceptent sans mot (ie, dont la langue est vide) .

Maintenant, nous montrons la réduction de $ \ overline {{A_ TM}} \ le L_ \ emptyset $. La réduction se fait en prenant un $ d'entrée (\ langle M \ rangle, w) $ de $ \ overline {A_ {TM}} $ et la convertir en un $ d'entrée {\ langle \ tilde M \ rangle} $ pour $ L_ \ emptyset $ tel que

$$ (\ langle M \ rangle, w) \ in \ overline {{A_ TM}} \ quad \ texte {} ssi \ quad \ langle \ tilde M \ rangle \ dans L _ {\ emptyset} $$

Compte tenu de $ (\ langle M \ rangle, w) $, nous pouvons construire \ $ de e façon suivante tilde M $. $ \ Tilde M $ sur entrée y effectue les opérations suivantes:

1. supprime la bande
2. écrit $ w $ sur la bande
3. court $ M $ sur $ w $, et effectue le même (si $ M $ accepte, $ \ tilde M $ accepte aussi bien).

Convainquez-vous qu'il est possible de construire le codage de $ \ tilde M $ du codage de $ M $ et de $ w $. Maintenant, nous allons vérifier que cette réduction est valable:

• Si $ (\ langle M \ rangle, w) \ in \ overline {{A_ TM}} $, alors M $, soit $ ou ne pas les rejets HALT. Si oui, alors aussi $ \ tilde M $ n'accepte pas $ y $, pour toute entrée $ y $. Ce moyen $ L (\ tilde M) = \ emptyset $ ainsi $ \ langle \ tilde M \ rangle \ dans L _ {\ emptyset} $.
• Si $ (\ langle M \ rangle, w) \ Notin \ overline {A_ {TM}} $, alors accepte M $ $ $ w $, donc $ \ tilde M $ accepte $ y $ (pour chaque $ y $ ). Il en résulte que $ L (\ tilde M) = \ Sigma ^ * $, ce qui implique que $ \ langle \ tilde M \ rangle \ L Notin _ {\ emptyset} $.

Le "IFF" condition est remplie et nous avons cartographié avec succès une entrée de $ \ overline {{A_ TM}} $ dans une entrée de $ L_ \ emptyset $. Dans ce cas, nous disons, nous avons réduit $ \ overline {{A_ TM}} $ à $ L_ \ emptyset $. Autrement dit, si nous pouvons résoudre $ L_ \ emptyset $, nous pouvons résoudre $ \ overline {A_ {TM}} $ en convertissant d'abord l'entrée, puis l'exécution de l'algorithme qui permet de résoudre $ L_ \ emptyset $ sur l'entrée convertie.

Answer 2

Vous ne pouvez pas montrer, pour une langue méconnaissable arbitraire $ C $, soit $ \ overline {{A_ TM}} \ leq_m C $. Si $ \ overline {A_ {TM}} \ leq_m C $, alors en particulier le degré de Turing $ C $ est supérieur ou égal au degré de Turing $ \ overline {A_ {TM}} $, parce que beaucoup-un réductibilité implique réductibilité Turing. Le degré de Turing $ \ overline {{A_ TM}} $ 0' $ $, le même que le degré de Turing $ {A_ TM} de $. Il y a beaucoup de langues méconnaissables dont le degré est incomparable avec Turing $ 0 « $ (ni plus ni moins de $ 0 » $).

L'exemple que G. a donné des œuvres Ran parce que $ L_ \ emptyset $ en particulier est $ m $ à $ -équivalent \ overline {{A_ TM}} $. Il y a un phénomène général que la plupart des problèmes « naturels » ont tendance à être comparables entre eux en $ m $ -degré. Mais si vous regardez les problèmes arbitraires, ce ne l'est plus.