سلسلهمراتب حسابی
سلسلهمراتب حسابی مجموعههای اعداد طبیعی را بر اساس تعداد سورهای متناوب مورد نیاز برای تعریف آنها طبقهبندی میکند و پیچیدگی منطقی را به درجات عدممحاسبهپذیری پیوند میدهد.
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
- سطح بالاتر در سلسلهمراتب به چه معناست؟
- سورهای متناوب بیشتر به معنای تعریف پیچیدهتر و طبق قضیه پست، مسئلهای است که برای تصمیمگیری به تکرارهای بیشتری از مسئله توقف نیاز دارد. مجموعههایی که در سلسلهمراتب بالاتر قرار دارند، به طور قابل توجهی کمتر از مجموعههای پایینتر برای محاسبه قابل دسترسی هستند.
- مجموعههای محاسبهپذیر شمارشپذیر کجا قرار میگیرند؟
- آنها سطح سیگما-یک را اشغال میکنند، که با یک سور وجودی منفرد بر روی یک رابطه محاسبهپذیر تعریفپذیر هستند. مکملهای آنها سطح پی-یک را اشغال میکنند، و مجموعههایی که هر دو هستند، یعنی مجموعههای دلتا-یک، دقیقاً مجموعههای محاسبهپذیر هستند.