جهاز اتخاذ القرار (آلة تورينج)

في نظرية الحوسبة ، يُعتبر جهاز اتخاذ القرار آلة تورينج تتوقف عند كل مدخل. ^{[ 1 ]} ويُطلق على جهاز اتخاذ القرار أيضًا اسم آلة تورينج الكلية ^{[ 2 ]} لأنه يمثل دالة كلية .

لأنها تتوقف دائمًا، تستطيع هذه الآلة تحديد ما إذا كانت سلسلة معينة تنتمي إلى لغة رسمية . وتُعرف فئة اللغات التي يمكن لهذه الآلات تحديدها باسم مجموعة اللغات الاسترجاعية .

بالنظر إلى أي آلة تورينغ، فإن تحديد ما إذا كانت آلة اتخاذ قرار يُعد مشكلة غير قابلة للحل . هذه مشكلة من نوع مشكلة التوقف ، التي تسأل عما إذا كانت آلة تورينغ تتوقف عند إدخال مُدخل مُحدد.

عمليًا، يمكن حساب العديد من الدوال المهمة بواسطة آلات تتوقف دائمًا. يمكن إجبار آلة تستخدم ذاكرة محدودة فقط على أي مدخل معين على التوقف عند كل مدخل عن طريق تقييد قدرات التحكم في التدفق لديها ، بحيث لا يتسبب أي مدخل في دخول الآلة في حلقة لا نهائية . على سبيل المثال، ستتوقف الآلة التي تُنفذ شجرة قرار محدودة دائمًا.

ليس من الضروري أن تكون الآلة خالية تمامًا من إمكانيات التكرار لضمان التوقف. فإذا قصرنا حجم الحلقات على حجم محدود يمكن التنبؤ به (مثل حلقة FOR في لغة BASIC )، يمكننا التعبير عن جميع الدوال التكرارية الأولية (ماير وريتشي، 1967). وتُعد لغة البرمجة PL- مثالًا على هذه الآلة.{GOTO} من براينرد ولاندويبر (1974).

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

على الرغم من الأمثلة المذكورة أعلاه للغات البرمجة التي تضمن إنهاء البرامج، لا توجد لغة برمجة تُجسّد بدقة جميع الدوال التكرارية ، أي الدوال التي يمكن حسابها بواسطة آلة تورينج تتوقف دائمًا. والسبب في ذلك هو أن وجود مثل هذه اللغة سيُناقض عدم قابلية حل مسألة ما إذا كانت آلة تورينج تتوقف عند كل مُدخلات .

تقوم آلة تورينج العامة بحساب دالة جزئية. ويمكن طرح سؤالين حول العلاقة بين آلات تورينج الجزئية وآلات تورينج الكلية:

1. هل يمكن توسيع كل دالة جزئية قابلة للحساب بواسطة آلة تورينج جزئية (أي توسيع نطاقها) لتصبح دالة قابلة للحساب كليًا؟
2. هل من الممكن تغيير تعريف آلة تورينج بحيث يمكن إيجاد فئة معينة من آلات تورينج الكلية، التي تحسب جميع الدوال القابلة للحساب؟

الإجابة على كل هذه الأسئلة هي لا.

تُبين النظرية التالية أن الدوال القابلة للحساب بواسطة الآلات التي تتوقف دائمًا لا تشمل امتدادات جميع الدوال القابلة للحساب جزئيًا، مما يعني أن الإجابة على السؤال الأول أعلاه سلبية. وترتبط هذه الحقيقة ارتباطًا وثيقًا بعدم إمكانية حل مشكلة التوقف خوارزميًا .

في الواقع، إذا كانت g دالة قابلة للحساب كليًا تمتد من f ، فإن g ستكون قابلة للحساب بواسطة آلة تورينج ما؛ لنفترض أن e هو فهرس هذه الآلة. قم ببناء آلة تورينج M ، باستخدام نظرية كلين للاستدعاء الذاتي ، بحيث عند إدخالتقوم الدالة 0 أولاً بمحاكاة الآلة ذات الفهرس e التي تعمل على الفهرس n _M لـ M (وبالتالي يمكن للآلة M إنتاج فهرس لنفسها؛ وهذا هو دور نظرية الاستدعاء الذاتي). بافتراض أن هذه المحاكاة ستُرجع في النهاية إجابة. ثم تضيف M القيمة 1 وتتوقف، بحيث إذا كانت g ( nM ₎ = m فإن القيمة المُعادة من M هي${\displaystyle m+1}$وبالتالي ، فإن f ( nM ) هي القيمة الحقيقية لعائد M عند الإدخال _.لن يساوي 0 _قيمة g ( nM ). وبالتالي ، فإن g لا تمتد إلى f .

يتناول السؤال الثاني، في جوهره، ما إذا كان هناك نموذج حسابي معقول آخر يحسب الدوال الكلية فقط، ويحسب جميع الدوال الكلية القابلة للحساب. بعبارة أخرى، إذا وُجد مثل هذا النموذج، فإنه يمكن محاكاة كل حاسوب من حواسيبه بواسطة آلة تورينج. وبالتالي، إذا كان هذا النموذج الحسابي الجديد يتكون من متتالية${\displaystyle M_{1},M_{2},\ldots }$من الآلات، سيكون هناك تسلسل قابل للتعداد بشكل متكرر${\displaystyle T_{1},\ldots T_{2},\ldots }$من آلات تورينج التي تحسب الدوال الكلية، بحيث يمكن حساب كل دالة كلية قابلة للحساب بواسطة إحدى الآلات T _i . هذا مستحيل، لأنه يمكن إنشاء آلة كلية T بحيث عند إدخال المدخل i، تُرجع الآلة T قيمة معينة.${\displaystyle T_{i}(i)+1\,}$لا يمكن أن تكون هذه الآلة مكافئة لأي آلة T في القائمة: لنفترض أنها موجودة في القائمة عند الفهرس j . عندئذٍ${\displaystyle T_{j}(j)=T_{j}(j)+1\,}$وهذا تناقض. وهذا يدل على أن السؤال الثاني له إجابة سلبية.

إن مسألة اتخاذ القرار بشأن ما إذا كانت آلة تورينج ذات المؤشر e ستتوقف عند كل مدخل غير قابلة للحل. في الواقع، هذه المسألة على مستوى${\displaystyle \Pi _{2}^{0}}$من التسلسل الهرمي الحسابي . وبالتالي، فإن هذه المشكلة أصعب بكثير من مشكلة التوقف ، التي تسأل عما إذا كانت الآلة ذات المؤشر e تتوقف عند الإدخال 0. وبشكل بديهي، يرجع هذا الاختلاف في عدم إمكانية الحل إلى أن كل حالة من حالات مشكلة "الآلة الكلية" تمثل عددًا لا نهائيًا من حالات مشكلة التوقف.

قد يهتم المرء ليس فقط بما إذا كانت آلة تورينج كلية، ولكن أيضًا بما إذا كان من الممكن إثبات ذلك في نظام منطقي معين، مثل حساب بيانو من الدرجة الأولى .

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

بما أنه يمكن حصر جميع البراهين في نظام البرهان، يمكن بناء آلة تورينج على المدخل n، بحيث تمر على أول n برهان وتبحث عن تناقض. إذا وجدت تناقضًا، فإنها تدخل في حلقة لا نهائية ولا تتوقف أبدًا؛ وإلا فإنها تتوقف. إذا كان النظام متسقًا ، فإن آلة تورينج ستتوقف عند كل مدخل، ولكن لا يمكن إثبات ذلك في نظام برهان قوي بما فيه الكفاية بسبب نظريات عدم الاكتمال لغودل .

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

إن آلة تورينج التي تمر عبر متواليات جودشتاين وتتوقف عند الصفر هي آلة كاملة ولكن لا يمكن إثبات ذلك في حساب بيانو.

• بلوب وفلوب
• البرمجة الوظيفية الكاملة
• تحليل الإنهاء

• Brainerd, WS, Landweber, LH (1974), نظرية الحوسبة ، Wiley.
• Meyer, AR , Ritchie, DM (1967), The complex of loop programs , Proc. of the ACM National Meetings, 465.
• Sipser, M. (2006), مقدمة في نظرية الحوسبة ، شركة PWS للنشر.
• كوزين، دي سي (1997)، الأتمتة والحوسبة ، سبرينغر.
• أوهليبوش، إي. (2002)، مواضيع متقدمة في إعادة كتابة المصطلحات ، سبرينغر.