إظهار أنه لكل لغة هناك لغة أصعب

Question

صادفت هذه المشكلة أنني لم أستطع معرفة ذلك ... لكل لغة $ $ ، من المفترض أن تكون هناك لغة $ B $ بحيث:

$$ a \ leq_t ب

ولكن:

$$ ب \ لا \ leq_t

إذا كان $ a \ leq_tb $ and $ b \ leq_t a $ ، هذا سهلنظرا لأننا يمكن أن ندع $ B:=bar {a} $ ، ولكن لما سبق لا أستطيع التفكير في أي شيء.أي مساعدة؟

Answer 1

هناك طرق قليلة للتعامل مع هذا.

يمكنك استخدام حجة العد لإظهار أنه لكل $ $ هناك $ B $ بحيث $ b \ nleq_t a $ . دع $ l_a={b | B \ le_t a \} $ تشير إلى مجموعة من جميع اللغات المتقتلة $ $ . إظهار أن $ f: l_a \ charnarrow \ mathbb {n} $ تلك الخرائط لغات $ b \ in l_a $ إلى $ n $ مثل $ m_n $ هو تخفيض من $ B $ إلى $ $ هو حقنة، واختتم أن هناك موجود لغة خارج $ l_a $ . بعد ذلك، تريد أن تصنعه $ $ . يمكننا الحصول على مثل هذه اللغة مع مشغل الانضمام:

$ a \ sqcup b={0W | W \ in a \} \ {1W | w \} $ .

أنا أترك الأمر لك لإظهار أن $ a \ sqcup b $ هو الأقل ملزمة $ a، B $ ، أي $ a، b \ le_t a \ sqcup b $ ، بالإضافة إلى كل $ l $ مثل $ a، b \ le_t l $ لدينا $ a \ sqcup b \ le l $ < / span> (أنت تهتم فقط في السابق). إظهار أنه في حالة $ b \ nleq_t a $ ثم $ a \ sqcup b \ nleq_t a $ .

طريقة أخرى لإثبات ذلك هو استخدام مشغل القفز . نحتاج إلى إدخال فكرة أوراكل آلات ، ثم إظهار أن $ b=left \ {\ left (m ^ a، w \ right) | \ text {$ m ^ ^ $ توقف على $ W $} \ right \} $ هي لغة أصعب بدقة. الدليل مطابق لمكثر لمشكلة توقف المشكلات القياسية، فقط الآن نحن الآن نعرض العقار الأقوى الذي لا يوجد آلة مع Oracle Access إلى $ A $ يمكن أن تقرر $ B $ .

يمكنك أيضا إنشاء مثل هذه اللغة مباشرة عبر قطري. تحديد $ b=left \ {n | m_n (n) \ notin a \ right \} $ . شيدنا $ B $ بحيث تكون أي وظيفة حسابية $ m_n $ فشل في أن تكون تخفيضا من $ B $ إلى $ $ على إدخال واحد على الأقل (خصيصا، ترميز التخفيض). يمكنك الآن استخدام مشغل الانضمام لجعلها قابلة للمقارنة.