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