التسلسل الهرمي الحسابي
يصنف التسلسل الهرمي الحسابي مجموعات الأعداد الطبيعية حسب عدد المحددات الكمية المتناوبة اللازمة لتعريفها، ويربط التعقيد المنطقي بدرجات عدم القابلية للحساب.
Definition
يقوم التسلسل الهرمي الحسابي بتقسيم المجموعات القابلة للتعريف في الحساب من الدرجة الأولى عن طريق عد تناوبات المحددات الكمية غير المقيدة أمام مصفوفة قابلة للحساب، حيث تُعرّف مجموعات سيجما-ن بواسطة كتلة تبدأ بمحدد كمي وجودي، ومجموعات باي-ن بواسطة كتلة تبدأ بمحدد كمي كلي.
Scope
يغطي هذا الموضوع تصنيف المجموعات القابلة للتعريف إلى مستويات سيجما وباي ودلتا عن طريق تناوب المحددات الكمية على العلاقات القابلة للحساب، ونظرية بوست التي تربط التسلسل الهرمي بمشكلة التوقف المتكررة وقفزات تورينج، وصرامة التسلسل الهرمي، وامتداده إلى التسلسل الهرمي التحليلي.
Core questions
- كيف يقيس تناوب المحددات الكمية تعقيد المجموعة؟
- كيف ترتبط فئات سيجما وباي ودلتا ببعضها البعض في كل مستوى؟
- كيف يتوافق التسلسل الهرمي مع تكرار مشكلة التوقف؟
- لماذا التسلسل الهرمي صارم، مع كون كل مستوى أكبر بشكل صحيح من سابقه؟
Key theories
- تصنيف المحددات الكمية
- تكون المجموعة سيجما-ن إذا كانت قابلة للتعريف بواسطة ن من كتل المحددات الكمية المتناوبة التي تبدأ بوجودية على علاقة قابلة للحساب، وباي-ن إذا بدأت بكونية؛ والمجموعات القابلة للعد حسابيًا هي بالضبط مجموعات سيجما-واحد.
- نظرية بوست
- تكون المجموعة سيجما-(ن+1) بالضبط عندما تكون قابلة للعد حسابيًا بالنسبة لقفزة تورينج ن، مما يربط مستويات التسلسل الهرمي بمشكلات التوقف النسبية المتكررة.
- صرامة التسلسل الهرمي
- كل قفزة تورينج أكثر تعقيدًا بشكل صارم من سابقتها، لذا فإن كل مستوى من التسلسل الهرمي الحسابي يحتوي بشكل صحيح على المستويات التي تليه ولا ينهار التسلسل الهرمي.
Clinical relevance
يُعد التسلسل الهرمي الحسابي المعيار القياسي لتعقيد المشكلات القابلة للتعريف في المنطق وعلوم الحاسوب: فهو يحدد مشكلات مثل الكلية، والمحدودية، والمحدودية المشتركة للمجموعات القابلة للحساب عند مستويات دقيقة، ويحدد الحدود الفاصلة بين ما هو قابل للعد حسابيًا وما يتطلب موارد غير قابلة للحساب أقوى.
History
قدم كليني وموستوفسكي بشكل مستقل التسلسل الهرمي الحسابي حوالي عام 1943، مصنفين المجموعات حسب تعقيد المحددات الكمية على المحمولات القابلة للحساب. ربطت نظرية بوست التسلسل الهرمي بقفزة تورينج، موحدةً بذلك المنظورين القائمين على التعريف والقابلية للحساب، وتم توسيع الإطار لاحقًا إلى التسلسل الهرمي التحليلي.
Key figures
- Stephen Cole Kleene
- Andrzej Mostowski
- Emil Post
Related topics
Seminal works
- rogers1987
- soare1987
- cutland1980
Frequently asked questions
- ماذا يعني المستوى الأعلى في التسلسل الهرمي؟
- المزيد من المحددات الكمية المتناوبة تعني تعريفًا أكثر تعقيدًا، ووفقًا لنظرية بوست، مشكلة تتطلب المزيد من تكرارات مشكلة التوقف لاتخاذ قرار بشأنها. المجموعات الأعلى في التسلسل الهرمي أقل قابلية للحساب بشكل صارم من تلك التي تقع أسفلها.
- أين تقع المجموعات القابلة للعد حسابيًا؟
- إنها تشغل مستوى سيجما-واحد، ويمكن تعريفها بواسطة محدد كمي وجودي واحد على علاقة قابلة للحساب. مكملاتها تشغل مستوى باي-واحد، والمجموعات التي هي كلاهما، مجموعات دلتا-واحد، هي بالضبط المجموعات القابلة للحساب.