في الرياضيات تعد 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 . بعض النظريات من الدرجة الأولى قابلة للقرار حسابيا، أمثلة على ذلك تتضمن حساب بريسبرجر، مجالات حقيقية مغلقة و نظم ثابتة النوع (لغالبية) لغة البرمجة . إن النظرية العامة من الدرجة الأولى لعدد طبيعي والتي تم التعبير عنها في بديهيات بيانو لا يمكن ،مع ذلك ،أن تقرر عن طريق مثل هذه الخوارزمية.
ملاحظات
- قدم بحث تشرتش للمجتمع الرياضي الأمريكي في 19 ابريل 1935 ونشرت يوم 15 ابريل 1936. أصيب تورنغ بخيبة أمل ، وهو الذي حقق تقدما كبيرا في كتابة النتائج الخاصة به ، لتعلم إثبات تشرتش على نشره (انظر المراسلات بين ماكس نيومان و تشرتش في أبحاث ألونزو تشرتش). اكمل تورنغ أبحاثه سريعا وهرع إلى نشرها و تم استقبالها من قبل وقائع المجتمع الرياضي في لندن في 28 مايو 1936 و تمت قراءتها في 12 نوفمبر 1936 ونشرت في يناير 1936 ، السلسلة الثانية ، مجلد42 (1936-1937) .أضاف تورنغ تصحيحات في المجلد 43 (1937) ص 544-546 . انظر ديفيز 1965 : 116.
المراجع
- Alonzo Church, "An unsolvable problem of نظرية الأعداد", American Journal of Mathematics, 58 (1936), pp 345–363
- Alonzo Church, "A note on the Entscheidungsproblem", Journal of Symbolic Logic, 1 (1936), pp 40–41.
- Martin Davis, 2000, Engines of Logic, W.W. Norton & Company, London, pbk.
- Alan Turing, "On computable numbers, with an application to the Entscheidungsproblem", Proceedings of the جمعية الرياضيات في لندن, Series 2, 42 (1937), pp 230–265. Online versions: from journal website, from Turing Digital Archive, from abelard.org. Errata appeared in Series 2, 43 (1937), pp 544–546.
- مارتن ديفيس, "The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions", Raven Press, New York, 1965. Turing's paper is #3 in this volume. Papers include those by Godel, Church, Rosser, Kleene, and Post.
- أندرو هودجز, Alan Turing: The Enigma, Simon and Schuster, New York, 1983. Alan M. Turing's biography. Cf Chapter "The Spirit of Truth" for a history leading to, and a discussion of, his proof.
- Toulmin, Stephen, "Fall of a Genius", a book review of "Alan Turing: The Enigma by Andrew Hodges", in The New York Review of Books, January 19, 1984, p. 3ff.
- ألفريد نورث وايتهيد and بيرتراند راسل, Principia Mathematica to *56, Cambridge at the University Press, 1962. Re: the problem of paradoxes, the authors discuss the problem of a set not be an object in any of its "determining functions", in particular "Introduction, Chap. 1 p. 24 "...difficulties which arise in formal logic", and Chap. 2.I. "The Vicious-Circle Principle" p. 37ff, and Chap. 2.VIII. "The Contradictions" p. 60 ff.