كيف نناقش أنه إذا تمكنا من حل مشكلة التوقف ، فيمكننا حل القندس المزدحم؟

Question

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

Answer 1

يتم تعريف وظيفة BB على أنها الحد الأقصى لعدد الخطوات التي يمكن أن تنفذها آلة turing بحجم معين وتوقف. (هناك طريقة أخرى لوضعها وهي أن جميع آلات Turing ذات الحجم X ستتوقف إما في أقل من خطوات BB (x) ، أو تعمل إلى الأبد).

على افتراض أن لديك آلة تورينج من التعقيد x ، يمكنك تحديد ما إذا كانت ستتوقف أم لا عن طريق السماح لها بالركض لخطوات زمنية BB (x) - إذا لم تتوقف بحلول ذلك الوقت ، فستكون بحكم تعريفها لن تفعل ذلك أبدًا.

وبالمثل ، إذا تمكنت من حل مشكلة التوقف ، فيمكنك تقييم جميع آلات Turing الممكنة من الحجم X ، والقضاء على تلك التي لا تتوقف ، وتأخذ BB (X) لتكون الحد الأقصى لأوقات تشغيل الباقي.

بالطبع ، BB (X) غير قابل للحساب - وفي الواقع ينمو بشكل أسرع من أي وظيفة حسابية محتملة يمكنك تسميتها - وبالتالي لا يمكن تقريبها.

Answer 2

يمكنك العثور على الدليل الذي تسعى إليه هنا, ، أسفل الدليل على أن مشكلة القندس المزدحمة غير قابلة للتحويل.