Reduzieren Sie $ l_c={\ \ Langle m_1 \ Rangle, \ Langle M_2 \ Rangle): l (m_1) \ cap l (m_2) \ neq \ emesyset \} $ to $ a_ {tm} $
-
29-09-2020 - |
Frage
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
$ 3. $ Wenn $ u $ beide akzeptiert, akzeptieren Sie.
Es scheint nicht funktioniert. Denn wenn $ l (m_1) \ cap l (m_2)=emeleyet $ , $ n $ Schleife für immer (es ist einfach nicht solche
Lösung
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
Jetzt, wenn an einem beliebigen Punkt sowohl
Die Reduktion wird durch Senden von $
Beachten Sie, dass $ N $ akzeptiert $ \ epsilon $ (und irgendein anderes Wort) iFF Ein Wort, das von sowohl von $ M_1 $ und $ M_2 $ akzeptiert wird.