Reduzieren Sie $ l_c={\ \ Langle m_1 \ Rangle, \ Langle M_2 \ Rangle): l (m_1) \ cap l (m_2) \ neq \ emesyset \} $ to $ a_ {tm} $

Question

Wie man $ l_c={\ Langle M_1 \ Rangle, \ Langle M_2 \ Rangle): L (M_1) \ CAP L (M_2) \ Neq \ EleseSet \} $ bis $ A_ {TM}={\ Langle M, W \ Rangle: M $ ist eine Turing-Maschine, die $ W $ }.

mein Versuch: Konstruieren Sie eine Turing-Maschine $ N $ Verwenden einer Turing-Maschine $ U $ , die universelles Sprache als Unterprogramm entscheidet, um zu entscheiden $ l_c $ . $ n $ , auf einem beliebigen Eingang $ <\ Langle M_1 \ Rangle, \ Langle M_2 \ Rangle> $ :
$ 1. $ Erstellen Sie ein Programm, das Word $ W \ in \ Sum ^ \ AST $ in kanonischer Reihenfolge erzeugt .
$ 2. $ run $ u $ auf $ \ Langle m_1 , W \ Rangle $ und $ \ Langle m_2, W \ Rangle $ .
$ 3. $ Wenn $ u $ beide akzeptiert, akzeptieren Sie.
$ 4. $ Wenn nicht, zurück zu $ 1 $ .

Es scheint nicht funktioniert. Denn wenn $ l (m_1) \ cap l (m_2)=emeleyet $ , $ n $ Schleife für immer (es ist einfach nicht solche $ W $ ).

Answer 1

Die Richtung der Reduktion, nach der Sie fragen, ist ein bisschen seltsam. Normalerweise reduzieren wir von $ A_ {TM} $ , um Unentschlossenheit anzuzeigen.

Vielleicht wollten Sie nach der anderen Richtung fragen?

jedenfalls in der Antwort auf Ihre Frage: Ihr Versuch war eigentlich recht nahe, es braucht nur ein bisschen Modifikation. So können Sie fortfahren:

gegeben $ m_1, m_2 $ als Eingabe für $ l_c $ , erstellen Sie eine neue Maschine $ n $ Das funktioniert wie folgt: Gegebenen Eingabe $ x $ , $ N $ ignoriert ignoriert (dh löschen $ x $ aus diesem Band), und beginnt dann mit der Simulation von $ M_1 $ und $ m_2 $ auf jedem Wort $ w \ in \ sigma ^ * $ , in kanonischer Reihenfolge. HINWEIS, dass, um $ M_1 $ und $ m_2 $ auf alle < / em> Wörter, wir können sie nicht einfach auf jedes Wort beliebig ausführen, da wir möglicherweise stecken bleiben (wir verwenden kein Orakel mit $ A_ {TM} $ ). Stattdessen führen wir sie in parallel : ausführen $ m_1 $ und $ m_2 $ auf jedem der ersten $ K $ Wörter in $ \ Sigma ^ * $ für $ K $ Schritte, und erhöhen Sie dann $ K $ um 1. Dies ist ein ziemlich häufiger Trick, aber es ist ziemlich klug.

Jetzt, wenn an einem beliebigen Punkt sowohl $ m_1 $ und $ m_2 $ akzeptieren, dann $ n $ akzeptiert. Andernfalls läuft es weiter und steigt immer wieder $ K $ für immer.

Die Reduktion wird durch Senden von $ $ in den $ A_ {TM} $ < / Span> Oracle (oder alternativ ist es vollständig, wenn Sie es als Mapping-Reduktion behandeln).

Beachten Sie, dass $ N $ akzeptiert $ \ epsilon $ (und irgendein anderes Wort) iFF Ein Wort, das von sowohl von $ M_1 $ und $ M_2 $ akzeptiert wird.