جميع المشكلات المتعلقة بآلات تورينج والتي تتضمن فقط اللغة التي تقبلها ذاكرة الترجمة غير قابلة للحسم

Question

لقد صادفت البيان أدناه في النص الكلاسيكي "مقدمة لنظرية الأتمتة واللغات والحساب" بقلم هوبكروفت وأولمان ومتواني.

All problems about Turing machines that involve only the language that the TM accepts are undecidable

يقولون أن النظرية المذكورة أعلاه هي حسب نظرية رايس التي تنص على ما يلي:

"كل خاصية غير تافهة للغات التعليم العالي غير قابلة للتقرير."

كيف تكون هذين البيانين متساويين؟الصفقات السابقة فقط مشاكل بينما يتعامل الأخير مع خاصية غير تافهة.

Answer 1

هناك بعض الكلمات الرئيسية في المقتطف من الكتاب النصي المذكور - غير تافهة، مشكلة، الملكية.

الآن ما هي المشكلة، على افتراض أننا لا نتعامل مع مشاكل التحسين التوافقي، أي.نحن نتعامل فقط مع الأسئلة التي لها إجابة بنعم أو لا.عندما تطرح سؤالاً بنعم أو لا على سلسلة إدخال إذا كانت الإجابة بنعم، فإنك تضعه في مجموعة $ل$ وإذا كان الجواب لا، فما عليك سوى التخلص منه.الآن هذه المجموعة $ل$ هي اللغة أو المشكلة.أنه يحتوي على كل تلك السلاسل التي تلبي سؤالنا بنعم أو لا.

كل غير تافهة مشاكل عن آلات تورينج التي تنطوي على اللغة التي يقبلها TM فقط غير قابلة للتقرير

هنا يتحدث المؤلف عن أسئلة نعم أو لا (فيما يتعلق بآلات تورينج) التي تتضمن فقط اللغة التي تقبلها آلة تورينج،أي.اللغة القابلة للتعداد بشكل متكرر (RE)، مما يعني أن مجموعة "المشكلة" الخاصة بنا يجب أن تحتوي على لغات RE فقط.الآن، المشكلة التافهة هي تلك التي يكون فيها سؤالنا نعم أو لا راضيًا عن جميع المدخلات أو لا يرضي أيًا من المدخلات.لذا فإن المشكلة غير التافهة هي تلك التي ليست فارغة ولا تحتوي على كل المدخلات الممكنة.

نظرية الأرز:"كل خاصية غير تافهة للغات التعليم العالي غير قابلة للتقرير."

خاصية لغات الطاقة المتجددة هي مجموعة من لغات الطاقة المتجددة التي تتمتع بالخاصية المذكورة.

خاصية غير تافهة:الخاصية إما مستوفية لجميع اللغات المعنية أو لا شيء.

لذا فإن "الخاصية غير التافهة للغات الطاقة المتجددة" تصبح مجموعة لغات الطاقة المتجددة وهي ليست فارغة ولا تحتوي على جميع لغات الطاقة المتجددة الممكنة.

من خلال الحجة المذكورة أعلاه يمكننا القول أن العبارتين متكافئتين.

(في الواقع، الخاصية والمشكلة هما نفس الشيء، فكلاهما عبارة عن مجموعة من السلاسل بعد كل شيء.الآن قد نعتقد أن الخاصية هي مجموعة من اللغات، على الرغم من أن هذا صحيح، إلا أنه من غير المناسب تمثيل اللغات في مجموعة (حيث يمكن أن تكون اللغات طويلة إلى ما لا نهاية)، وبدلًا من اللغة، فإننا نمثل المقابل آلة تورينج مع ترميز مناسب)