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