مسألة القرار (رياضيات)

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

تاريخ المشكلة

أصل Entscheidungsproblem يرجع إلى غوتفريد لايبنتز الذي في، القرن السابع عشر، بعد إنشاء آلة حساب ميكانيكية ناجحة، قد حلم ببناء آلة يمكنها التعامل مع الرموز لتحديد القيم الحقيقية للبيانات الرياضية (ديفيز 2000 الصفحات 3-20) وأدرك أن الخطوة الأولى يجب أن تكون لغة رسمية نظيفة، والكثير من أعماله اللاحقة كان موجها نحو هذا الهدف. في عام 1928، طرح ديفيد هيلبرت وويلهيلم أكرمان المسألة في الشكل المذكور أعلاه. في استمرار ل«برنامجه» الذي تحدى به مجتمع الرياضيات عام 1900، في المؤتمر الدولي 1928، سأل ديفيد هيلبرت ثلاثة أسئلة، ثالثها أصبح يعرف باسم «Entscheidungsproblemالخاصة بهيلبرت» (هودجز ص 91) في أواخر 1930 اعتقد أنه لن يكون هناك مثل هذه المشاكل الغير قابلة للحل (هودجز ص 92 نقلا عن هيلبرت).

الإجابة السلبية

قبل أن تتم الإجابة عن السؤال، فإن مفهوم «الخوارزمية» يجب أن يعرف رسميا. وقد فعل ذلك ألونزو تشرتش عام 1936 مع مفهوم «القدرة الحسابية الفعالة» على أساس حسابات اللامدا الخاصة به وآلان تورنغ في نفس السنة بمفهومه آلة تورنغ وقد تم الاعترف في وقت لاحق أن هذه المفاهيم معادلة لنماذج الحساب.

أعطى الجواب السلبي ل Entscheidungsproblem ألونزو تشرتش في 1935 -36 وبشكل مستقل بعد ذلك بوقت قصير بواسطة آلان تورنغ عام 1936-37 . أثبت تشرتش أنه لا توجد دوال حسابية تقرر ما إذا كان تعبيرين λ حسابيين معينين متعادلين أم لا. لقد اعتمد بشكل كبير على العمل السابق من قبل ستيفن كلين. خفض تورنغ وقف المشكلة لآلات تورنغ ل Entscheidungsproblem . وقد تأثر بشدة عمل كل من المؤلفين بالعمل السابق لكورت غودل في نظريته عدم الاكتمال وخاصة من خلال طريقة تعيين أرقام (ترقيم غودل) لصيغ منطقية من أجل تقليل المنطق للحساب. حجة تورنغ على النحو التالي: افترض أن لدينا قرار رياضي عام للعبارات في لغة من منطق الرتبة الأولى السؤال هو هل يمكن إيقاف آلة تورنغ معينة أم لا يمكن صياغته كبيان من الدرجة الأولى والذي سيكون عرضة لخوارزمية القرار.ولكن تورنغ أثبت سابقا أنه لا توجد خوارزمية عامة يمكن أن تقرر إذا كانت آلة تورنغ تتوقف.

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