هل صحيح أن أقول l هو إعادة إذا يمكنني تخطيط الخريطة من LH إلى L؟

Question

يبدو أنني لا أفهم بشكل صحيح ما تخفيضات يعني لغات اللغات.

على سبيل المثال، دعنا نقول أن هناك لغة تسمى LM.

أريد أن أرى ما إذا كانت LM متكررة أم لا، للقيام بذلك، دعنا نقول أنني أجد تخفيضا من مشكلة L-Halting إلى LM.

وأفترض أن LM متكرر، لذلك أظهر أن مشكلة L-Halting هي أيضا تكرس، والتي بالطبع غير صحيح، وبالتالي لا تكرر LM.

ولكن هل يمكنني أن أقول أن LM هو إعادة لأنني وجدت طريقة للحد من LH إلى LM؟ إن لم يكن كيف يمكنني أن أظهر أن LM هي إعادة؟

Answer 1

دعونا نخلص الأشياء قليلا، لأن هناك العديد من التعاريف المكافئة / المكافئة التي يمكن أن تؤدي إلى سوء الفهم.

• يمكنك إظهار أن لغة $ l $ العودية عن طريق إنشاء وظيفة متكررة $ \ chi_l $ (أو آلة turing أو أي نموذج حساب مكافئ آخر) يقرر ذلك، أي $$ \ chi_l (x)=ادفع {cats} 1 & quad؛ X \ في L \\ 0 & quad؛ \ text {otw}. \ نهاية {الحالات} $ لاحظ أن يجب تحديد $ \ chi_l $ لجميع المدخلات.

• يمكنك إظهار تلك اللغة $ l $ ليست العودية، من خلال العثور على "تخفيض" من غير اللغة اللغة إليها. ربما هذا هو ما تقصده بالتخفيض، ويتم تعريفه على النحو التالي:

  نقول أن لغة $ A $ هي تورينج باختيار بلغة $ B $ ، كتب $ a \ le_t b $ ، إذا استطعنا إنشاء وظيفة متكررة (أو آلة تورينج) تقرر $ $ < / span> عن طريق افتراض أن هناك مثل هذه الوظيفة ل $ B $ .

  كما ترى بحكم التعريف، تخفيض تورينج بطريقة ما "التحويلات العكري" من $ B $ إلى $ $ .

  لأي $ $ و $ B $ مثل $ a \ leq_t b $ ، إذا $ B $ هو العودية، ثم $ $ .

  وبالتالي، إذا كنا نعلم بالفعل أن بعض $ $ $ a \ leq_t b $ لأي $ B $ يجعلها غير متراكسة أيضا.

• يمكنك إظهار أن لغة $ l $ is re، بواسطة إنشاء وظيفة متكررة $ \ varphi_l $ (أو آلة turing) التي $ dom (\ varphi_l)= l $ (أو توقف على / قبول / يقبل ذلك)، على سبيل المثال $$ \ varphi_l (x)=ادبت {cats} 1 & quad؛ x \ in l \\ \ uparrow & quad؛ \ text {otw.} \ End {cats} $

  حيث $ \ uparrow $ يعني "غير محدد" (أو "لا توقف"). هناك تعريفات أخرى لإعادة النيس، مثل "إمكانية التعداد الأسماء"، والتي يمكنك ملاحظتها بسهولة أن تعادل هذا واحد.

• ولكن في إظهار لغة $ L $ غير re، لا يساعد تخفيض turing، لأنه لا بالضرورة نقل إعادة نيس. على سبيل المثال ملاحظة أن $ \ overline {l_ {halt}} \ leq_t l_ {} $ (في الواقع أي لغة هي تورينج لا يقل عنها تكمل والعكس بالعكس)، لكننا نعرف أن $ l_ {halt} $ هو إعادة، في حين $ \ overline {l_ {halt}} $ ليس كذلك.

  ولكن هناك أنواع أخرى من أقوى الحد من نقل إعادة نيس. واحد من هذا القبيل يسمى "تعويض كثير من القصد":

  نقول أن لغة $ $ غير متوقعة ذات اللون $ B $ مكتوب $ a \ leq_m b $ ، إذا كان هناك إجمالي وظيفة العودية $ f $ مثل ذلك لأي إدخال $ x $ $$ X \ في A \ IFF F (x) \ in B $$

  هذا هو الحد أقوى بمعنى أن $ a \ leq_m b $ يعني $ a \ leq_t b $ (وليس بالضرورة العكس). لذلك، مثل تخفيض تورينج، فإنه ينقلك الانكرس. لدينا أيضا

  لأي $ $ و $ B $ مثل $ a \ leq_m b $ ، إذا $ B $ هو إعادة، ثم $ $ .

  لمعرفة كيف هذا صحيح، فقط تأخذ $ \ varphi_a (x)=varphi_b (f (x)) $ .

  .
  .

  وبالتالي الطريقة الصحيحة لإظهار لغة $ B $ ليست، هي العثور على العديد من الأحداث $ a \ leq_m b $ للحصول على بعض اللغة غير إعادة $ $ . لاحظ أن المثال أعلاه لا يعمل هنا، لأنه $ \ overline {l_ {halt}} \ nleq_m l_ {} $ .

لمزيد من القراءة، راجع

L="NOFOLL NOREFERRER"> نظرية الكمبيوتر بواسطة s.باري كوبر PT.أنا، الفصل.7.