مجموعههای شمارشپذیر محاسبهپذیر و درجات تورینگ
مجموعههای شمارشپذیر محاسبهپذیر آنهایی هستند که اعضایشان را میتوان به طور مؤثر فهرست کرد، و درجات تورینگ تمام مجموعهها را بر اساس محاسبهپذیری نسبی رتبهبندی میکنند و چشمانداز مسائل حلناپذیر را سازماندهی مینمایند.
Definition
یک مجموعه شمارشپذیر محاسبهپذیر است اگر یک الگوریتم دقیقاً اعضای آن را فهرست کند؛ یک مجموعه به مجموعه دیگری کاهشپذیر تورینگ است اگر بتوان آن را با استفاده از دیگری به عنوان اوراکل محاسبه کرد، و کلاسهای همارزی تحت کاهشپذیری متقابل، درجات تورینگ هستند که بر اساس محاسبهپذیری نسبی به طور جزئی مرتب شدهاند.
Scope
این موضوع شامل مجموعههای شمارشپذیر محاسبهپذیر و ویژگیهای اساسی آنها، کاهشپذیری تورینگ و ترتیب جزئی درجات، مجموعه توقف به عنوان یک مجموعه شمارشپذیر کامل، مسئله پست و حل آن با روش اولویت، و نظریه ساختاری درجات شمارشپذیر محاسبهپذیر است.
Core questions
- تفاوت بین یک مجموعه محاسبهپذیر و یک مجموعه صرفاً شمارشپذیر محاسبهپذیر چیست؟
- کاهشپذیری تورینگ چگونه دشواری دو مجموعه را مقایسه میکند؟
- آیا درجات شمارشپذیر محاسبهپذیر دقیقاً بین مجموعههای محاسبهپذیر و مسئله توقف وجود دارند؟
- ساختار کلی درجات حلناپذیری چیست؟
Key theories
- مکملسازی و مجموعه توقف
- یک مجموعه دقیقاً زمانی محاسبهپذیر است که هم خودش و هم مکملش شمارشپذیر محاسبهپذیر باشند، و مجموعه توقف شمارشپذیر محاسبهپذیر است اما محاسبهپذیر نیست، که مجموعه شمارشپذیر کامل کانونی است.
- مسئله پست و روش اولویت
- پست پرسید که آیا درجات شمارشپذیر محاسبهپذیر دقیقاً بین مجموعههای محاسبهپذیر و مسئله توقف وجود دارند؛ فریدبرگ و موچنیک با ابداع روش اولویت آسیب محدود، پاسخ مثبت دادند.
- ساختار درجات
- درجات تورینگ و درجات شمارشپذیر محاسبهپذیر ساختارهای غنی و چگال مرتبی را تشکیل میدهند که از طریق ساختارهای اولویت پیشرفته مورد مطالعه قرار میگیرند و ویژگیهای تعریفپذیری و تعبیهسازی پیچیدهای را آشکار میسازند.
Clinical relevance
نظریه درجات، طبقهبندی دقیقی از مسائل حلناپذیر ارائه میدهد و نشان میدهد که عدم تصمیمپذیری در سطوح بینهایت و به شدت افزایشی وجود دارد، و روش اولویت که برای مطالعه آنها توسعه یافته است، یک تکنیک اثبات مرکزی است که بر ریاضیات معکوس و تحلیل تصادفی بودن الگوریتمی تأثیر گذاشته است.
History
پست مجموعههای شمارشپذیر محاسبهپذیر را معرفی کرد و مسئله خود را در سال 1944 مطرح نمود و پرسید که آیا درجات شمارشپذیر غیرمحاسبهپذیر ناقص وجود دارند یا خیر. فریدبرگ و موچنیک به طور مستقل در حدود سال 1956 با روش اولویت آن را حل کردند، که به ابزار اصلی برای مطالعه ساختاری عمیق درجات که توسط ساکس، سوار و بسیاری دیگر دنبال شد، تبدیل گشت.
Key figures
- Emil Post
- Richard Friedberg
- Albert Muchnik
- Robert Soare
Related topics
Seminal works
- soare1987
- post1944
- rogers1987
Frequently asked questions
- اوراکل در نظریه محاسبهپذیری چیست؟
- اوراکل یک منبع خارجی است که به سوالات عضویت برای یک مجموعه ثابت فوراً پاسخ میدهد. یک ماشین با اوراکل میتواند از آن پاسخها در طول محاسبات خود استفاده کند، و کاهشپذیری تورینگ میپرسد که آیا یک مجموعه را میتوان توسط ماشینی که مجهز به مجموعه دیگری به عنوان اوراکل خود است، محاسبه کرد.
- چرا مسئله پست اهمیت داشت؟
- این مسئله پرسید که آیا حلناپذیری در میان مجموعههای شمارشپذیر محاسبهپذیر، بین مسائل تصمیمپذیر و مسئله توقف، سطوح میانی دارد یا خیر. پاسخ مثبت، ساختار دقیقی از درجات را آشکار کرد و به روش اولویت، یک تکنیک جدید قدرتمند که کل این حوزه را شکل داده است، نیاز داشت.