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

في الرياضيات تعد 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 ألونزوتشرتش في 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, ISBN 0-393-32229-7 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.