مسألة توقف

مسألة التوقف في نظرية الحاسوبية هي كالتالي: «معطى وصف برنامج حاسوبي قرر إذا ما البرنامج يتوقف أو لا يتوقف», مسألة مشابهة ومتكافئة هي إذا كان بالإضافة للبرنامج كان هنالك مدخل والمسألة هي تحديد إذا ما البرنامج سوف يتوقف عندما نشغله مع المدخل أو لن يتوقف.

في عام 1936 برهن الن تيورنج ان خوارزمية عامة التي تحل مسألة التوقف بشكل صحيح لكل المدخلات غير موجودة، ولعل ابرز ما جاء في البرهان هو تعريف الحاسوب وبرنامج الحاسوب بشكل رياضياتي وهو ما عرف لاحقا بالة تيورنج. وبالنسبة لالة تيورنج مسألة التوقف غير قابلة للتقرير.

استخدامات عملية

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

فللنظر للبرنامج التالي:

while (true) continue

هذا البرنامج لن يتوقف ابدا بينما البرنامج:

print "Hello, world!"

سوف يتوقف بسرعة. هذا الامر قد يكون واضحا في هذين البرنامجين فاذا كان البرنامج أكثر تعقيدا هكذا صعب ان يعرف أيتوقف ام لا.

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

اهمية المسألة

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

لعل أحد التعميمات لنتيجة ان مسألة التوقف غير قابلة للتقرير هو قانون رايز، والذي نصه: «كل صفة ليست بديهية للدوال الجزئية التي يمكن تنفيذها بواسطة برامج لا يمكن تقريرها». القصد من التعبير «صفة ليست بديهية» معناه أن مجموعة الدوال الجزئية التي تحقق الصفة هي ليست كل الدوال الجزئية كما انه يجب ان يكون هنالك دالة واحدة على الاقل التي تحقق الصفة. مثال: الصفة: «التوقف على المدخل 0» نلاحظ أن ليس كل الدوال تتوقف على المدخل 0 كما انه يوجد دوال تتوقف على 0 لذا فان هذه الصفة ليست بديهية لذا فهي غير قابلة للتقرير. ويجب الانتباه بأن قانون رايز لا يتحقق إذا كانت الصفة ليست للدوال الجزئية التي يمكن تنفيذها بواسطة برنامج ولكن الصفة أيضا متعلقة بالبرنامج مثل: «التوقف على المدخل 0 خلال 100 خطوة حساب», نلاحظ ان هذه ليست صفة للدوال الجزئية فقط وانما أيضا للبرنامج وهذه المسألة يمكن تقريرها (ببساطة ننفذ البرنامج خلال 100 خطوة عندما المدخل يكون 0 إذا توقف البرنامج المخرج يكون «نعم» وخلاف هذا الإجابة «لا»).

التعريف بواسطة مجموعة

الشكل الاعتيادي لمسائل التقرير يكون على شكل مجموعة من الاشياء التي تحقق السؤال. مجموعة التوقف (halting set) هي:

{البرنامج i سوف يتوقف في حين أن x هو المدخل للبرنامج |(K:= {(i,x

وهذه المجموعة تمثل مسألة التوقف وهي مجموعة مجموعة مرقمة بشكل تراجعي أي انه يوجد دالة قابلة للحساب التي تعدد كل زوج (i,x) ولكن المجموعة المكملة غير قابلة للترقيم أو التعداد.

يوجد الكثير من المسائل التي هي إعادة صياغة لمسألة التوقف حيث أن كل مسألة يوجد لها نفس درجة تيورنج هي كذلك. امثلة لمجموعات كهذه منها:

• { i | برنامج i سوف يتوقف عندما نشغله مع المدخل 0 }
• { i | يوجد مدخل x بحيث أن البرنامج i سوف يتوقف على المدخل x }.

مسألة التوقف غير قابلة للتقرير

لعل ابرز النتائج في علم الحاسوب والرياضيات في القرن العشرين هو أن هذه المسألة غير قابلة للتقرير، والبرهان الذي اعتمده تيورنج شبيه إلى حد بعيد الوسيلة التي استخدمها كانتور ليبين أن $\mathbb{R}$ هي مجموعة لانهائية غير قابلة للعد، والوسيلة هي «القطرية» (diagonalization).

نص المبرهنة

المبرهنة نصها كالتالي: «مسألة التوقف غير قابلة للتقرير» أو "${\text{H}}_{\text{TM}}=\{⟨\text{M,x}⟩|\text{M is a program that halts on input x}\}$ هي مجموعة غير قابلة للتقرير ".

البرهان

البرهان سوف يكون عن طريق التناقض: فلنفرض أنه يوجد برنامج HALTS والذي مدخله برنامج M ومدخل للبرنامج x. وهذا البرنامج مخرجه «نعم» إذا M تتوقف على المدخل x والجواب «لا» خلاف هذا. نبني برنامج جديد NEWHALTS والذي مدخله برنامج M والجواب نعم إذا ما البرنامج M يتوقف عندما يكون المدخل M.

procedure NEWHALTS(M);
  if HALTS(M,M) then writeln('Yes');
  else writeln('No');

والان نعرف برنامج اخر الذي هو OPP كالتالي:

procedure OPP(P);
  if NEWHALTS(P) outputs 'Yes' then
    loop forever
  else halt;

هذا البرنامج يعكس نتيجة NEWHALTS , الآن ماذا يحدث مع (OPP(OPP?

• داخل (OPP(OPP يستدعي (NEWHALTS(OPP والذي يستدعي (HALTS(OPP,OPP حينها:
  • إذا OPP يتوقف على المدخل OPP حينها (OPP(OPP لن يتوقف؛
  • إذا OPP يتوقف على المدخل OPP حينها (OPP(OPP يتوقف.

إذا (OPP(OPP لا يمكن ان يتوقف ولا يمكن ان لا يتوقف. لذا فإن هذا تناقض. والفرضية الوحيدة هي أن HALTS موجود ! لذا فانه لا يمكن ان يكون موجودا.

انظر أيضا

• آلان تورنغ
• كثير حدود وكثير حدود غير قطعي
• مبرهنات عدم الاكتمال لغودل

مراجع

• Sipser، Michael (2006). "Section 4.2: The Halting Problem". Introduction to the Theory of Computation (ط. Second Edition). PWS Publishing. ص. 173–182. {{استشهاد بكتاب}}: |طبعة= يحتوي على نص زائد (مساعدة)
• Randal Nelson , "Computation and Formal Systems course notes",http://www.cs.rochester.edu/~nelson/courses/csc_173/computability/undecidable.html.