نگاهی به ریاضیات پیشرفته/نظریهٔ محاسبه‌پذیری

محاسبه‌پذیری توانایی حل یک مسئله به روشی مؤثر است؛ که یک موضوع کلیدی در زمینه نظریه محاسبه پذیری در منطق ریاضی و نظریه محاسبات در علوم کامپیوتر است. محاسبه‌پذیری یک مسئله ارتباط نزدیکی با وجود یک الگوریتم برای حل مسئله دارد. گسترده‌ترین مدل‌های مورد مطالعه از محاسبات توابع تورینگ-محاسبه پذیر، μ-بازگشتی و حساب لامبدا هستند، که تمامی آن‌ها دارای قدرت محاسباتی معادل هستند. از انواع دیگر مطالعه محاسبه پذیری، همچنین: مفاهیم محاسبه‌پذیری ضعیف تر از ماشین‌های تورینگ که در نظریه اتوماتا مطالعه می‌شود و مفاهیم محاسبه‌پذیری قوی تر از ماشین تورینگ که در زمینه hypercomputation مطالعه می‌شود را می‌توان نام برد.

مسائل

ایده اساسی در محاسبه‌پذیری این است که یک مسئله که یک task است که محاسبه‌پذیری ان را می‌توان بررسی کرد. دو نوع اصلی از مسایل وجود دارد:

مسئلهٔ تصمیم پذیری، یک مجموعه S را معین می‌کند که ممکن است مجموعه‌ای از رشته‌ها، اعداد طبیعی، یا اشیاء دیگری باشد که از مجموعه بزرگتری مانند U امده‌اند باشد. یک مثال خاص از مسئله تصمیم‌گیری این است که ایا یک عنصر u دلخواه از U در S است. به عنوان مثال، اکر U مجموعهٔ اعداد طبیعی و S مجموعهٔ اعداد اول باشد، مسئلهٔ تصمیم‌گیری به تصمیم‌گیری اول بودن تبدیل می‌شود.

مسئلهٔ تابع، شامل یک تابع f از مجموعه U به V است. مجموعه به عنوان یک نمونه از مسئله محاسبهٔ مقدار تابع f برای u داده شده از مجموعه U است. به عنوان مثال، اگر U و V مجموعهٔ تمام رشته‌های دودویی متناهی باشند و f یک رشته را گرفته و معکوس آن را به عنوان خروجی برگرداند آنگاه f(۱۰۱۰) = ۱۰۱۰.

انواع دیگر مسایل شامل مسایل جستجو و مسایل بهینه‌سازی هستند.

یکی از اهداف نظریه محاسبه‌پذیری تعیین این است که کدام مسایل، یا کلاسی از مسئله‌ها، قابل حل در کدام یک از مدل‌های محاسبه‌پذیری هستند.

مدل های مبتنی بر هنزمانی

تعدادی از مدل‌های محاسباتی مبتنی بر همزمانی توسعه یافته‌اند، از جمله ماشین دسترسی تصادفی موازی و شبکه پتری . این مدل‌های محاسبات همزمان هنوز هیچ توابع ریاضی را که توسط ماشین‌های تورینگ قابل پیاده‌سازی نباشد، اجرا نمی‌کنند.

منابع

ویکی پدیای فارسی

ویکی پدیای انگلیسی