مسألة توقف
من ويكيبيديا، الموسوعة encyclopedia
مسألة التوقف في نظرية الحاسوبية هي كالتالي: «معطى وصف برنامج حاسوبي قرر إذا ما البرنامج يتوقف أو لا يتوقف», مسألة مشابهة ومتكافئة هي إذا كان بالإضافة للبرنامج كان هنالك مدخل والمسألة هي تحديد إذا ما البرنامج سوف يتوقف عندما نشغله مع المدخل أو لن يتوقف.[1][2][3]
في عام 1936 برهن الن تيورنج ان خوارزمية عامة التي تحل مسألة التوقف بشكل صحيح لكل المدخلات غير موجودة، ولعل ابرز ما جاء في البرهان هو تعريف الحاسوب وبرنامج الحاسوب بشكل رياضياتي وهو ما عرف لاحقا بالة تيورنج. وبالنسبة لالة تيورنج مسألة التوقف غير قابلة للتقرير.