نظریه محاسبهپذیری
نظریه محاسبهپذیری به بررسی این موضوع میپردازد که کدام مسائل اصولاً میتوانند توسط یک الگوریتم حل شوند و مسائل حلناپذیر را بر اساس درجه دشواری آنها طبقهبندی میکند.
Definition
نظریه محاسبهپذیری، که نظریه بازگشت نیز نامیده میشود، شاخهای از منطق ریاضی است که مفهوم یک تابع قابل محاسبه مؤثر را دقیق میکند، مجموعهها و توابعی را که الگوریتمها میتوانند و نمیتوانند محاسبه کنند مطالعه میکند، و دشواری نسبی مسائل حلناپذیر را اندازهگیری میکند.
Scope
این حوزه مدلهای صوری محاسبه و تز چرچ-تورینگ، مجموعههای محاسبهپذیر و شمارشپذیر محاسبهپذیر، مسائل حلناپذیر مانند مسئله توقف، کاهشپذیریها و درجات تورینگ که حلناپذیری نسبی را اندازهگیری میکنند، و سلسلهمراتب حسابی که تعریفپذیری را بر اساس پیچیدگی سورها طبقهبندی میکند، را پوشش میدهد.
Sub-topics
Core questions
- محاسبهپذیر بودن یک تابع یا مجموعه به چه معناست؟
- کدام مسائل طبیعی به صورت الگوریتمی حلناپذیر هستند؟
- چگونه میتوان دشواری مسائل حلناپذیر را مقایسه و رتبهبندی کرد؟
- چگونه پیچیدگی منطقی با سطوح محاسبهپذیری مطابقت دارد؟
Key theories
- تز چرچ-تورینگ
- مفهوم شهودی محاسبهپذیری مؤثر با محاسبهپذیری ماشین تورینگ، و به طور معادل با توابع بازگشتی و توابع تعریفپذیر با لامبدا، منطبق است و یک تعریف ریاضیاتی قوی از الگوریتم را تثبیت میکند.
- حلناپذیری مسئله توقف
- هیچ الگوریتمی نمیتواند برای هر برنامه و ورودی تصمیم بگیرد که آیا برنامه متوقف میشود یا خیر، که اولین و نمونه اولیه یک مسئله حلناپذیر را ارائه میدهد.
- درجات تورینگ
- کاهشپذیری تورینگ مجموعهها را بر اساس محاسبهپذیری نسبی رتبهبندی میکند، و درجات حاصله یک ترتیب جزئی غنی را تشکیل میدهند که ساختار آن، از جمله وجود درجات میانی، یک موضوع اصلی مطالعه است.
Clinical relevance
نظریه محاسبهپذیری مرز مطلق حلپذیری الگوریتمی را مشخص میکند، که زیربنای علوم کامپیوتر نظری است و نتایج حلناپذیری، مانند حلناپذیری مسائل توقف و کلمه، را فراهم میآورد که در سراسر ریاضیات تکرار میشوند و نظریه پیچیدگی محاسباتی را شکل میدهند.
History
نظریه محاسبهپذیری در دهه 1930 پدید آمد، زمانی که چرچ، تورینگ، کلینی، و پست به طور مستقل مفهوم یک رویه مؤثر را از طریق حساب لامبدا، ماشینهای تورینگ، توابع بازگشتی، و سیستمهای ترکیبیاتی صوریسازی کردند، که همگی معادل یکدیگر اثبات شدند. پست و کلینی نظریه درجات و سلسلهمراتب حسابی را توسعه دادند، و روش اولویت که در دهه 1950 معرفی شد، مطالعه ساختاری عمیق درجات شمارشپذیر محاسبهپذیر را پیش برد.
Key figures
- Alan Turing
- Alonzo Church
- Stephen Cole Kleene
- Emil Post
Related topics
Seminal works
- soare1987
- rogers1987
- cutland1980
Frequently asked questions
- آیا نظریه محاسبهپذیری همان نظریه پیچیدگی است؟
- خیر. نظریه محاسبهپذیری میپرسد که آیا یک مسئله اصلاً میتواند توسط هر الگوریتمی حل شود، بدون توجه به منابع، در حالی که نظریه پیچیدگی میپرسد یک مسئله حلپذیر به چه مقدار زمان یا حافظه نیاز دارد. محاسبهپذیری خط بین حلپذیر و حلناپذیر را ترسیم میکند؛ پیچیدگی جنبه حلپذیر را درجهبندی میکند.
- چرا تز چرچ-تورینگ یک قضیه نیست؟
- این تز یک مفهوم غیررسمی، یعنی محاسبهپذیری مؤثر، را با یک مفهوم دقیق ریاضیاتی برابر میداند، بنابراین نمیتوان آن را به طور رسمی اثبات کرد. پذیرش آن بر همگرایی بسیاری از صوریسازیهای مستقل به یک کلاس از توابع استوار است، که شواهد قوی است تا یک اثبات.