مشكلة التوقف وعدم القابلية للحسم

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

Definition

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

Scope

يغطي هذا الموضوع الصياغة الدقيقة لمشكلة التوقف، وإثبات عدم قابليتها للحسم عن طريق الاستدلال القطري (diagonalization)، وتقنية الاختزال من نوع واحد (many-one reduction) لنقل عدم القابلية للحسم، ونظرية رايس حول الخصائص غير البديهية للبرامج، والمشكلات الكلاسيكية غير القابلة للحسم مثل مشكلة القرار (Entscheidungsproblem) ومشكلة الكلمة للمجموعات (word problem for groups).

Core questions

• لماذا لا توجد خوارزمية تحدد ما إذا كانت البرامج تتوقف؟
• كيف تُستخدم الاختزالات لإثبات عدم قابلية حسم مشكلة من مشكلة أخرى؟
• ماذا تقول نظرية رايس عن تحديد خصائص البرامج؟
• ما هي المشكلات الرياضية الشهيرة التي تبين أنها غير قابلة للحسم؟

Key theories

عدم قابلية حل مشكلة التوقف

تُظهر حجة قطرية أن افتراض وجود مُقرر للتوقف يؤدي إلى تناقض، لذا لا يمكن لأي خوارزمية أن تحسم التوقف لجميع البرامج والمدخلات.

الاختزال ونقل عدم القابلية للحسم

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

نظرية رايس

كل خاصية غير بديهية للدالة التي يحسبها البرنامج غير قابلة للحسم، لذا لا يمكن حسم أي خاصية سلوكية مهمة للبرامج خوارزميًا بشكل أساسي.

Clinical relevance

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

History

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

Key figures

• Alan Turing
• Alonzo Church
• Henry Gordon Rice
• Pyotr Novikov

Seminal works

• sipser2013
• turing1936
• rogers1987

Frequently asked questions

لماذا لا يستطيع حاسوب أسرع حل مشكلة التوقف؟

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

هل يمكننا دائمًا معرفة ما إذا كان البرنامج يتوقف؟

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