هل هذه اللغة مائدة؟

Question

كما يقول العنوان؛ هل هذه اللغة حتى وكيف تثبت ذلك؟

$$ L={\ {\ langle m \ rangle \ mid m \ text {هو آلة turing وهناك إدخال} m \ text {haltts on} \}

Answer 1

لغتك ليست صالحة. لإظهار أنه يكفي أن يلاحظ أن وجود آلة Turing $ t $ التي قررت $ l $ يعني وجود آلة تورينج يحل مشكلة وقف.

في الواقع، بالنظر إلى أي آلة تورينج $ m $ مع إدخال $ x $ يمكنك إنشاء turing آلة $ M '$ تتجاهل مدخلاتها، يكتب $ x $ على الشريط، ثم يحاكي < Span Class="حاوية الرياضيات"> $ M $ . بوضوح $ m '$ توقف (بغض النظر عن إدخالها) إذا وفقط إذا كانت $ M $ توقف عند الإدخال $ x $ . يمكننا أن نتحرك ما إذا كانت $ M '$ توقف عن طريق التحقق مما إذا كانت $ m' \ in l $ استخدام $ T $ مع إدخال $ m '$ .