books the issue of stopping is not quantifiable
If you do not find what you're looking for, you can use more accurate words.
مسألة التوقف غير قابلة للتقرير (Info)
لعل ابرز النتائج في علم الحاسوب والرياضيات في القرن العشرين هو أن هذه المسألة غير قابلة للتقرير، والبرهان الذي اعتمده تيورنج شبيه إلى حد بعيد الوسيلة التي استخدمها كانتور ليبين أن هي مجموعة لانهائية غير قابلة للعد، والوسيلة هي "القطرية" (diagonalization).
نص المبرهنة
المبرهنة نصها كالتالي: " مسألة التوقف غير قابلة للتقرير " أو " هي مجموعة غير قابلة للتقرير ".
البرهان
البرهان سوف يكون عن طريق التناقض: فلنفرض أنه يوجد برنامج 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 موجود ! لذا فانه لا يمكن ان يكون موجودا.
