نظرية الأساس (قابلية الحساب)

في نظرية الحوسبة ، يوجد عدد من النظريات الأساسية . تُظهر هذه النظريات أن أنواعًا معينة من المجموعات يجب أن تحتوي دائمًا على بعض العناصر التي لا تكون معقدة للغاية من حيث درجة تورينج . وتتعلق إحدى مجموعات النظريات الأساسية بالمجموعات المغلقة فعليًا غير الفارغة (أي غير الفارغة).${\displaystyle \Pi _{1}^{0}}$تُدرس هذه النظريات كجزء من نظرية الحوسبة الكلاسيكية، وهي تُصنف ضمن التسلسل الهرمي الحسابي . وتتعلق مجموعة أخرى من نظريات الأساس بالمجموعات التحليلية غير الفارغة ذات الأوجه المضيئة (أي،${\displaystyle \سيجما _{1}^{1}}$في التسلسل الهرمي التحليلي )؛ يتم دراسة هذه النظريات كجزء من نظرية الحساب الفائق .

تُعدّ المجموعات المغلقة فعليًا موضوعًا للدراسة في نظرية الحوسبة الكلاسيكية. المجموعة المغلقة فعليًا هي مجموعة جميع المسارات التي تمر عبر شجرة فرعية قابلة للحوسبة من الشجرة الثنائية.${\displaystyle 2^{<\omega }}$تُعتبر هذه المجموعات مغلقة، بالمعنى الطوبولوجي ، باعتبارها مجموعات جزئية من فضاء كانتور.${\displaystyle 2^{\omega }}$والمتممة لمجموعة مغلقة فعّالة هي مجموعة مفتوحة فعّالة بالمعنى المقصود في الفضاءات البولندية الفعّالة . وقد أثبت كلين في عام 1952 وجود مجموعة مغلقة فعّالة غير فارغة لا تحتوي على أي نقطة قابلة للحساب (كوبر 1999، ص  134). وتُبين نظريات الأساس أنه لا بد من وجود نقاط ليست "بعيدة جدًا" عن إمكانية الحساب، بمعنى غير رسمي.

فصل دراسي${\displaystyle {\mathcal {C}}\subseteq 2^{\omega }}$تُعتبر أساسًا للمجموعات المغلقة فعليًا إذا كانت كل مجموعة مغلقة فعليًا غير فارغة تتضمن عنصرًا من ${\displaystyle {\mathcal {C}}}$(كوبر  2003، ص  329). تُظهر نظريات الأساس أن فئات معينة تُعد أساسًا بهذا المعنى. وتشمل هذه النظريات (كوبر 1999، ص  134):

• نظرية الأساس المنخفض : كل مجموعة غير فارغة${\displaystyle \Pi _{1}^{0}}$تحتوي المجموعة على عنصر ذي درجة منخفضة.
• نظرية الأساس الخالي من المناعة المفرطة : كل غير فارغ${\displaystyle \Pi _{1}^{0}}$تضم المجموعة عضواً يتمتع بدرجة خالية من فرط المناعة .
• نظرية الأساس re : كل مجموعة غير فارغة${\displaystyle \Pi _{1}^{0}}$تحتوي المجموعة على عنصر من الدرجة القابلة للتعداد بشكل متكرر (re) .

هنا، مجموعة${\displaystyle X\subseteq \mathbb {N} }$يكون منخفضًا إذا كانت قفزة تورينج${\displaystyle X'=\varnothing '}$، درجة مشكلة التوقف .${\displaystyle X}$يتمتع بدرجة خالية من فرط المناعة إذا كان كل إجمالي${\displaystyle X}$- دالة قابلة للحساب${\displaystyle f\colon \mathbb {N} \to \mathbb {N} }$تهيمن عليها دالة حسابية كلية${\displaystyle g}$(معنى${\displaystyle f(n)\leq g(n)}$للجميع${\displaystyle n}$).

لا يمكن دمج أيٍّ من النظريات الثلاث المذكورة أعلاه للحصول على مجموعة الإكمالات المتسقة لـ PA (أو EFA فقط ؛ فدرجات تورينج متطابقة). درجة تورينج الوحيدة التي تُحسب إكمالًا متسقًا لـ PA هي 0'. مع ذلك، يمكن دمج كلٍّ من نظرية الأساس المنخفض ونظرية الأساس الخالي من المناعة الفائقة مع تجنب المخروط، أي أنه لكل X غير قابل للحساب ، يمكننا اختيار عنصر (كما في النظرية) لا يحسب X. كما تُطبَّق النظريات على أي عدد حقيقي.

توجد أيضًا نظريات أساسية للوجه الخفيف${\displaystyle \سيجما _{1}^{1}}$المجموعات. تُدرس نظريات الأساس هذه كجزء من نظرية الحساب الفائق . إحدى هذه النظريات هي نظرية غاندي للأساس، وهي مماثلة لنظرية الأساس المنخفض. تُبين نظرية غاندي للأساس أن كل مجموعة غير فارغة${\displaystyle \سيجما _{1}^{1}}$تحتوي المجموعة على عنصر منخفض حسابيًا بشكل فائق، أي أن قفزته الفائقة لها نفس الدرجة الفائقة (وبالنسبة للنظرية، حتى نفس درجة تورينج) مثل مجموعة كلين${\displaystyle {\mathcal {O}}}$.

• كوبر، إس بي (1999). "نظرية الدرجة المحلية"، في كتاب "دليل نظرية الحوسبة" ، تحرير إي آر غريفور، إلسيفير، ص  121-153 . ISBN 978-0-444-89882-1
• — (2003)، نظرية الحوسبة ، تشابمان-هول. ISBN 1-584-88237-9

• سيمبسون، إس. " مسح لنظريات الأساس "، شرائح من نظرية الحوسبة وأسس الرياضيات ، معهد طوكيو للتكنولوجيا، 18-20 فبراير 2013.