لماذا اللغة التالية غير قابلة للتكريس؟

Question

أنا أتعلم حاليا لامتحانات بلدي هذا الفصل الدراسي وحاول حل بعض الامتحانات القديمة من السنوات الأخيرة.

السؤال هو إظهار، أن L غير قابلة للتغيير. $ l={w | t (m_w) \ neq \ emptyset \ land \ forall x \ in t (m_w): xx \ in t (m_w) \ land xxx \ notin (m_w) \} $

أظهرت أن اللغة $ l '={w | T (M_W) \ NEQ \ emptyset \} $ غير قابل للتدوير بسبب نظرية الأرز. قمت بإنشائيتها لتناول الآلات $ m_1 $ مع $ t (m_1)=expryset $ و $ m_2 $ مع $ t (m_2)=sigma ^ * $ لإظهار أن اللغة L 'ليست تافهة وبعد (منذ $ 1 \ في L $ و $ 2 \ Notin A $ . مع فقدان العمومية أفترض الآلات لديها gödelindexes 1 و 2)

مشكلتي الآن هو أنه لا أعرف أي طريقة لإظهارها، أن هذه النتيجة نقل إلى اللغة L. أعرف أن اللغة L يجب أن تحتوي فقط على فهارس Gödel هذه، أنه بالنسبة لتلك الفهارس يجب أن يقبل TM التالي الكلمات اللانهائية ( لأنه في حالة $ x \ in t (m_w) $ يجب أن يكون هناك $ xx \ in t (m_w) $ < / span> ... وبالتالي يجب أن يكون $ xxxx \ in t (m_w) $ etc.)

أحب أن أسمع الاقتراحات / الإجابات! شكرا مقدما

Answer 1

هذه هي نتيجة مباشرة ل نظرية الأرز. كلمة $ W $ هي في $ l $ إذا كانت $ T (M_W) $ يرضي الممتلكات الدلالية التالية:

$ t (m_w) $ غير فارغ، ولأي $ x \ in t (m_w) $ ، لدينا $ x ^ 2 \ in t (m_w) $ و $ x ^ 3 \ notin t (m_w) $ .

من أجل إظهار أن هذه اللغة غير قابلة للكشف عن نظرية الأرز، نحتاج إلى إظهار اثنين من آلات تورينج $ W_1 $ و $ W_2 $ : واحد الذي لا يفي بالملكية، وآخر آخر يلبيه. يمكننا أن نأخذ $ w_1 $ ليكون بعض الآلات مثل $ t (m_ {w_1})=emplyset $ و $ w_2 $ ليكون بعض الآلات مثل $ t (m_ {w_2})={a ^ {2 ^ n}: n \ geq 0 \} $ .