مسألة التوقف

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

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