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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث

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


انظر أيضا[عدل]

ملاحظات[عدل]

  1. ^ قدم بحث تشرتش للمجتمع الرياضي الأمريكي في 19 ابريل 1935 ونشرت يوم 15 ابريل 1936. أصيب تورنج بخيبة أمل ، وهو الذي حقق تقدما كبيرا في كتابة النتائج الخاصة به ، لتعلم إثبات تشرتش على نشره (انظر المراسلات بين ماكس نيومان و تشرتش في أبحاث ألونزو تشرتش). اكمل تورنج أبحاثه سريعا وهرع إلى نشرها و تم استقبالها من قبل وقائع المجتمع الرياضي في لندن في 28 مايو 1936 و تمت قراءتها في 12 نوفمبر 1936 ونشرت في يناير 1936 ، السلسلة الثانية ، مجلد42 (1936-1937) .أضاف تورنج تصحيحات في المجلد 43 (1937) ص 544-546 . انظر ديفيز 1965 : 116.

المراجع[عدل]

  • Alonzo Church, "An unsolvable problem of elementary number theory", 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 London Mathematical Society, 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.
  • Martin Davis, "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.
  • Andrew Hodges, 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.
  • Alfred North Whitehead and Bertrand Russell, 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.