مشكلة التوقف

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

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