لماذا يجب أن تتعلم عن مسألة القرار (رياضيات)

في الرياضيات تعد Entscheidungsproblem (تنطق [ɛntˈʃaɪdʊŋspʁoˌble:m], في الألمانية وتعني «مشكلة القرار») هو التحدي الذي يطرحه ديفيد هيلبرت عام 1928. Entscheidungsproblem تسأل عن خوارزمية التي ستتخذ وصفا للغة الرسمية وبيانا رياضيا في اللغة كمدخل وتقدم إما «صواب» أو «خطأ» كمخرج وفقا لصحة أو خطا البيان. الحاجة للخوارزمية لا تبرر لا إجابتها ولا تقدم دليلا ما دام صحيحا دائما. مثل هذه الخوارزمية تستطيع أن تقرر، على سبيل المثال، ما إذا كانت البيانات مثل حدسية غولدباخ أو فرضية ريمانصحيحة حتى لو لم يوجد دليل أو نقض معروف عن هذه البيانات. وكثيرا ما تم تحديد Entscheidungsproblem خاصة بأنها مشكلة قرار منطق الرتبة الأولى (وهذا يعني أن مشكلة تحديد، من الناحية الحسابية، ما إذا كان البيان من المرتبة الأولى صحيحا عالميا).

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