خرائط تخفيضات من R إلى إعادة

Question

دع $ l_1 $ تكون بعض اللغات في $ r $ .دع $ l_2 $ تكون بعض اللغات في $ RE $ .هل هو بالضرورة أن $ l_1 \ leq_m l_2 $ ؟ أعلم أنه بالنسبة لعدم تافهة $ l_1 $ ، $ l_1 $ في $ r $ من المناسب أن أقول أن $ l_1 \ leq_m l_2 $ . لكنني لا أستطيع إثبات الحالة الأولى.

وسؤال آخر: أنا شبه مؤكد أن ما يلي صحيح، على الرغم من أنني لم أجد أي إشارة إليها على الإنترنت: وظيفة الهوية هي تخفيض رسم الخرائط من $ \ expryset $ إلى $ \ emptyset $ .

Answer 1

إذا كنت $ l_2 \ neq \ sigma ^ * $ و $ l_2 \ neq \ emptyset $ ثم $ l_1 \ in r $ و $ l_2 \ in Re $ يعني $ l_1 \ le_m l_2 $ .

دع $ T $ يكون آلة turing يقرر $ l_1 $ . دع $ a، b \ in \ sigma ^ * $ مثل $ a \ in l_2 $ Span Class="حاوية الرياضيات"> $ b \ not \ in l_2 $ . ل $ x \ in \ sigma ^ * $ ، حدد $ \ phi (x)= \ ابدأ {الحالات} A & \ Text {IF $ t (x) $ يقبل} \\ B & \ Text {IF $ T (x) $ يرفض} \ نهاية {الحالات} $ . من السهل التحقق من أن $ \ Phi $ هو تخفيض رسم الخرائط من $ l_1 $ إلى $ l_2 $ .

إذا كان $ l_2=sigma ^ * $ ثم $ l_1 \ in r $ و $ l_2 \ in Re $ لا يعني $ l_1 \ le_m l_2 $ . < / ص>

يمكن رؤية ذلك، على سبيل المثال، عن طريق اختيار $ l_1=emptyset $ .

إذا $ l_2=emplyset $ ثم $ l_1 \ in r $ Span Class="حاوية الرياضيات"> $ l_2 \ in Re $ لا يعني $ l_1 \ le_m l_2 $ .

يمكن رؤية ذلك، على سبيل المثال، عن طريق اختيار $ l_1=sigma ^ * $ .