نظریه رایانش‌پذیری: تفاوت میان نسخه‌ها

 

'''نظریه محاسبه‌پذیری''' از مباحث پایه در [[علوم رایانه]] است که به بررسی محاسبه‌پذیر و محاسبه‌ناپذیر بودن عملیات با استفاده از ابزارهای کلاسیک نظیر [[ماشین ثبات]]، [[ماشین تورینگ]] و [[توابع بازگشتی]] میپردازد.

برای تحلیل این که یک الگوریتم به چقدر زمان و حافظه نیاز دارد، دانشمندان کامپیوتر زمان و حافظه ای را که برای حل یک مسئله مورد نیاز است، به عنوان یک تابع از سایز ورودی مسئله بیان می کنند. برای مثال پیدا کردن یک عدد خاص در یک لیست بلند از اعداد دشوارتر می شود هنگامی که تعداد اعداد افزایش می یابد.