'''نظریه محاسبهپذیریرایانشپذیری''' از مباحث پایه در [[علوم رایانه]] است که به بررسی محاسبهپذیر و محاسبهناپذیر بودن عملیات با استفاده از ابزارهای کلاسیک نظیر [[ماشین ثبات]]، [[ماشین تورینگ]] و [[توابع بازگشتی]] میپردازد.
بدون شک یکی از علل پیشرفت این نظریه تلاش محققین برای اثبات پاسخ منفی به مسئله دهم هیلبرت بودهاست.
دانشمندان [[کامپیوتر]]، برای مطالعهٔ جدی نظریه محاسبه،رایانش (شماره پذیری)، با یک مفهوم انتزاعی ریاضی برای کامپیوترهاستکامپیوترها که مدل محاسبهرایانش گفته میشود، سر و کار دارند. قاعده سازیهای متعددی، برای استفاده وجود دارد، اما ماشین تورینگ(Turing) در این میان بیشترین کاربرد را دارد. یک ماشین تورینگ را میتوان هم ارز یک کامپیوتر شخصی رومیزی، در نظر گرفت، با حافظهٔ بینهایت که به این حافظه از طریق تعداد زیادی تکههای کوچک گسسته، دسترسی دارد. دانشمندان کامپیوتر به دلیل قابلیت سادگی قاعده سازی، تحلیل و آنالیز و قابل استفاده برای اثبات نتایج از این ماشین استفاده میکنند.
چون حافظهٔ بینهایت یک نسبت غیر مادی در نظر گرفته میشود، برای هر مسئله که با استفاده از ماشین تورینگ حل میشود، حافظهٔ مورد استفاده همواره محدود است. در نتیجه هر مسئله را میتوان با استفاده از یک کامپیوتر شخصی که حافظهٔ مورد نیاز بر روی آن نصب شده، از طریق یک ماشین تورینگ حل کرد.