لماذا هذه اللغة تورينج التعرف عليها وليس لا تورز التعرف عليها

Question

قرأت أن اللغة التالية هي R.E. ولكن ليس لا تورينج التعرف على

$ l $ : on incut $ m $ (حيث $ m $ هي آلة تورينج)، $ M $ يقبل ما لا يقل عن 20 مدخلات أنا لست متأكدا من السبب في عدم التعرف على أنه لا يمكن التعرف عليه.، نظرا لأنني قد أتمكن من إجراء التخفيض التالي من $ \ overline {a_ {tm}} $ إلى $ l $ بالنظر إلى هذا الإجراء $ r $ وهي:

$ r $ : on input $ $ :

1. بناء tm $ m_1 $ ، حيث عند الإدخال $ x $ ، إذا $ x= 1 $ ، قبول
2. إذا كان الإدخال $ x $ لا يساوي $ 1 $ ، تشغيل $ M $ على الإدخال $ W $ for $ | x | $ خطوات. إذا بعد $ | x | $ الخطوات، $ M $ لا تقبل $ W $ ، ثم قبول $ x $

من هذا الحد، إذا كان $ M $ لا يقبل $ W $ ، أي $ \ \ in \ overline {a_ {tm}} $ ، ثم $ m_1 $ يقبل أي إدخال كلمة، أي $ m_1 \ in l $ .

هل أنا أفتقد شيئا هنا؟

Answer 1

ما كنت في عداد المفقودين هو أنه في حالة $ \ langle m، w \ rangle \ notin \ overline {a _ {\ mathrm {tm}}} $ ، أي إذا $ m $ haltts على الإدخال $ W $ ، أنت لا تعرف ما إذا كان $ m_1 \ notin l $ .إذا $ m $ لا تتوقف على $ W $ ، ولكن هذا يستغرق وقتا أطول من 20 دولارا $ الخطوات، وسوف تعقد أيضا تلك $ m_1 \ in l $ .وبالتالي، ليس لديك تخفيض هنا.

أن اللغة $ l $ لا يمكن أن تكون مشتركة هي نتيجة فورية ل نظرية الأرز.