مرجع
آخر الزيارات

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

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

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

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

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

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

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

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

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

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

ملاحظات

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

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

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

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.