نظرية الأرز لآلة تورينج مع إخراج ثابت

Question

لذلك كان من المفترض أن أثبتت بمساعدة نظرية الأرز ما إذا كانت اللغة: $ l_ {5}={w \} {0،1 \} ^ {*} | \ forall x \ in \ {0،1 \} ^ {*}، m_ {w} (w)= x \} $ هو مرحول.

أولا وقبل كل شيء: لا أفهم، لماذا يمكننا استخدام نظرية الأرز في المقام الأول: إذا كنت قد اخترت اثنين من TiningMachines $ m_ {w} $ و $ m_ {w '} $ مع $ W \ NEQ W' $ ثم سأحصل على $ m_ {w} (w)= m_ {w '} (w)= x $ . ولكن هذا سيؤدي إلى $ W '$ لا يجري في $ l_ {5} $ و $ w \ in l_ {} $ . أو أنا أسيء فهم شيء؟

ثانيا: يقول الحل أن اللغة $ l_ {5} $ حلول مثل $ l_ {5}=emptyset $ لأن الإخراج يحدد بوضوح مع إدخال ثابت. ولكن لماذا هو كذلك؟ اعتقدت أن $ l_ {5} $ غير فارغ لأن هناك tm التي خرج x على مدخلاتها الخاصة وهناك بعض ما لا يفعل ذلك.

Answer 1

كلمة $ W $ ينتمي إلى $ l_5 $ إذا كان $ x \ in \ {0،1 \} ^ * $ هو الحال الذي $ m_w (w)= x $ .على وجه الخصوص، إذا $ w \ in l_5 $ ثم $ m_w (w)= 0 $ و $ m_w (w)= 1 دولار ، والتي لا يمكن أن يكون كل منهما صحيحا.لذلك لا توجد كلمة تنتمي إلى $ l_5 $ .