در نظریه محاسبه پذیری به زبان L (که یک مجموعه شمارش پذیر است) بازگشتی (Recursive)، "محاسبه پذیر" یا "تصمیم پذیر" می گوییم اگر و تنها اگر شرایط زیر برقرار باشد:
۱- اگر رشته w متعلق به زبان باشد برنامه ی مربوطه اش آن را بپذیرد (و متوقف شود)
۲- اگر رشته متعلق به زبان نیست باز هم در نهایت برنامه مربوطه آن را نپذیرد و متوقف شود.
البته تعریف بالا کاملا با شهود ما در رابطه با این که یک الگوریتم چیست و چیزهایی که تاکنون گفته ایم می خواند یک الگوریتم باید برای هر ورودی ای که دارد متوقف شود چه ورودی جز زبان باشد چه نباشد و این کار باید طی تعداد متناهی قدم انجام شود.
چیزی که تمامی صحبت های ما را تاکنون مقداری مبهم کرده است این است که ما واژه های "برنامه" و "الگوریتم" را خیلی به جای هم استفاده کردیم و اصلا محاسبه را تعریف نکردیم. در واقع در تمام مدتی که از واژه برنامه یا الگوریتم استفاده می کردیم منظور ما ماشین تورینگ (Turing Machine) بود. ماشین تورینگ یک مدل محاسباتی است که ساختار ساده ای دارد.
ماشین تورینگ از یک هد و یک نوار تشکیل شده است که هد می تواند روی نوار حرکت کند چیزی روی آن بنویسید یا بخواند طول نوار می تواند هر قدر طولانی باشد نکته مهم در مورد ماشین تورینگ این است که این مدل محاسباتی برخلاف مدل های دیگری که ضعیف تر بودند.(مانند اتومات های متناهی قطعی (Deterministic Finite State machine) ) حافظه دار است. ماشین تورینگ توانایی انجام هر محاسبه ای را دارد در واقع ماشین تورینگ قدرتمند ترین مدل محاسباتی است.(توجه کنید این بدان نیست که این کار را برای هر محاسبه ای به بهینه ترین روش ممکن انجام می دهد) هر تلاشی برای قدرتمندتر کردن ماشین تورینگ با شکست مواجه می شود اگر ما تعداد نوار ها را زیاد کنیم یا طول آن ها را بیشتر کنیم نتیجه مدل قدرتمند تری نخواهد بود.

اما این ادعای بزرگی است آیا مدل های محاسباتی دیگری وجود ندارند؟ باید گفت مدل های محاسباتی مهم دیگر یکی توسط آلونزو چرچ (Alonzo Church) ابداع شد که پایه ی آن توابعی است که توسط حساب لمبدا (λ-calculus) تعریف می شوند. دیگری توسط استفن کلین (Stephen Kleen) و چرچ ابداع شد و به نام توابع بازگشتی معروف است. به همین دلیل به مجموعه زبان های محاسبه پذیر، بازگشتی هم می گفتیم (بالا) چون توسط یک تابع بازگشتی قابل تولید اند.
اگرچه در ابتدا به نظر می رسید مدل های گفته شده بسیار از هم متفاوتند اما به تدریج مشخص شد که توانایی های مشابهی دارند و در نهایت به صورت ریاضی ثابت شد که هر سه یک کلاس از توابع را مشخص می کنند. این واقعیت دانشمندان علوم کامپیوتر را متقاعد کرد که مفهوم محاسبه به درستی توسط این ۳ مدلِ معادل بیان می شوند. و از همین نتیجه تز چرچ تورینگ بیان شد:
"اگر روشی(الگوریتمی) وجود داشته باشد که یک محاسبه را بتوان با آن انجام داد این کار توسط یک ماشین تورینگ قابل انجام است"
تز چرچ تورینگ گزاره ای در مورد طبیعت محاسبه است و لذا نمی توان به صورت فرمال آن را ثابت کرد. تلاش های زیادی برای توسعه مفهوم محاسبه به فراتر از محدوده ی ماشین تورینگ انجام شد مانند ماشین شمارنده توسط ماروین مینسکی(Marvin Minsky) وبعد توسعه یافته توسط لامبک (Lambek). ماشین های ثباتی و مدل های دیگری که مبتنی بر مفهوم منطق ترکیبی و زنجیره های مارکف بود تمامی تلاش ها منجر به مدل هایی شد که باز هم با ماشین تورینگ معادل بودند. آنچه باعث این برابری می شود این است که همه از چند اصل عقلانی (Reasonable) یا شیوه موثر (Effective Method) در مورد مفهوم الگوریتم پیروی می کنند:
۱- همیشه یک و تنها یک جواب می دهند.
۲- همواره جواب درست می دهند.
۳- همواره در تعداد محدودی قدم به جواب می رسیم.
۴- برای همه ی نمونه مساله ها از یک کلاس جواب می دهد.
یک "روش موثر" برای محاسبه ی یک تابع را یک الگوریتم می گویند. و توابعی که به این طریق قابل محاسبه اند را توابع محاسبه پذیر می گویند.
همه ی موارد بالا بسیار واضح به نظر می رسند ما به طور شهودی در مورد الگوریتم شرط های بالا را در ذهن داریم اما اگر برخی از شرط ها را در نظر نگیریم چه؟
کلاس دیگری از زبان ها وجود دارد که ویژگی عجیبی دارند به این معنا که اگر رشته ای عضو آن ها باشد ماشین تورینگی وجود دارد که در نهایت متوقف می شود و آن را می پذیرد، اما اگر رشته عضو زبان نباشد هیچ تضمینی وجود ندارد که ماشین تورینگ متوقف شود! به عبارتی شرط اول "شیوه های موثر" را ندارد به این کلاس از زبان ها شبه تصمیم پذیر (semidecideable) یا به طور بازگشتی شمارش پذیر (Recursively Enumerable) می گویند این کلاس زبان های بیشتری را شامل می شود.

جالب اینجاست اولین کسی که ایده ابر ماشین ها به ذهنش رسید خود تورینگ بود تورینگ در مقاله ای در سال ۱۹۳۹ به بیان چنین ماشین های فرضی ای پرداخت او اشاره کرد اگر چه چنین ماشین هایی قادر به حل مسائلی هستند که برای ماشین های تورینگ تصمیم ناپذیرند اما خود این ماشین ها هم مسائل تصمیم ناپذیر خود را دارند!!
تز چرچ-تورینگ تا حد زیادی یک تز فیزیکی است تا تزی فرمال در منطق. به این خاطر این حرف را می زنیم که چنین تزی به طبیعت محاسبه کار دارد و این که هیچ ماشینی قادر نیست یک کار بی نهایت را در زمان محدود انجام دهد. اما آیا واقعا هیچ بی نهایتی در جهان فیزیکی وجود ندارد؟ پاسخ به این سوال دشوار است. به طور کلی کار کردن با بی نهایت ها دشوار است در موارد زیادی اشتباهی که در مساله در مورد بی نهایت طرح شده به جهان خارج نمی کشد بلکه دارای اشکالات منطقی است و به همین خاطر ما را به اشتباه می اندازد. یکی از این موارد پارادوکس زنون است: پارادوکس زنون دارای ۳ بخش است مهمترین آن ها را بیان می کنیم:
آشیل قهرمان افسانه ای دوی سرعت با یک لاک پشت مسابقه می دهد اما لاک پشت فقط یک متر از آشیل جلو تر است زنون استدلال می کند که آشیل هیچ گاه به لاک پشت نمی رسد زیرا در مدتی که ۱ متر را طی می کند لاک پشت قدری جلو رفته است اما اگر این مقدار را طی کند در مدت زمان طی آن لاک پشت باز هم قدری جلوتر رفته است بهمین ترتیب آشیل هیچ گاه به لاک پشت نمی رسد.
این پارادوکس تا زمانی که حساب دیفرانسیل و انتگرال توسعه نیافته بود حل نشده باقی ماند تا در نهایت با استفاده از سری و حد مساله حل شد در این جا با جزئیات حل کاری نداریم نکته راه حل در این است که اگر حتی فضا را پیوسته در نظر بگیریم مشکلی در مورد مساله وجود ندارد به عبارتی مشکل پارادوکس یک مشکل ریاضی- منطقی است. اما برخی پارادوکس ها چموش ترند یکی از آن ها توسط تامپسون (Thomson) اختراع شد و به نام پارادوکس تامپسون معروف است :
اگر لامپی در زمان صفر تا نیم ثانیه روشن باشد و بعد در زمان 0.5 تا 0.75 ثانیه خاموش و دوباره در زمان 0.75 تا 0.875 ثانیه روشن شود (توجه کنید بازه ها هر بار نصف می شوند) و همین روند ادامه یابد در زمان یک ثانیه روشن است یا خاموش؟
زمان یک ثانیه برای دنباله بالا یک مقدار حدی است اگر به این مساله فکر کنیم به نظر می رسد هیچ راه حلی نداشته باشد. خود تامسون این پارادوکس را بوجود آورد تا نشان دهد ابر وظیفه (Supertask) ها غیر ممکن اند. ابر وظیفه به کارهایی گفته می شود که بی نهایت قدم را در زمان محدودی انجام می دهند. پارادوکسی مثل تامسون اگرچه در محدوده ی ریاضیات به نحوی حل و فصل می شود(مانند بیان این که دنباله 1(روشن) و صفر(خاموش) ها در بالا حد ندارد) اما وقتی وارد دنیای واقعی می شود دچار مشکلات جدی می شود دنیای ما حداقل در سطح ماکرو (جدای از ابر حالات کوانتومی در دنیای زیر اتمی) قطعی است و نمی توان گفت لامپ در وضعیتی است که هم روشن و هم خاموش است یا نه روشن و نه خاموش است (اصلا حتی دو شق قبلی توسط ریاضیات مساله حمایت نمی شوند) با تمام این اوصاف بهتر است که چنین وضعیت هایی را ناممکن بدانیم. با همین استدلال به نظر نمی رسد "ابر وظایف" در "ابر محاسبه" فارغ از چنین وضعیت هایی باشند به همین خاطر باید در مورد امکانشان شک کرد.
در کنار چنین مسائلی بسیاری از کمیت ها در فیزیکی که می شناسیم پیوسته نیستند مهمترین آن ها انرژی است (کوانتیزه بودن انرژی) اما نظریات جالب تری وجود دارند که در تکمیل نظریه کوانتوم بیان می کنند که حتی خود فضا و زمان هم کمیت هایی گسسته و کوانتومی اند به این ترتیب که هر بازه ی زمانی تشکیل شده از واحد های زمانی تقسیم ناپذیر به نام زمان پلانک به طول ده به توان منفی ۴۳ ثانیه و فضا هم تشکیل شده از واحد فضای پلانک که دارای طول ده به توان منفی ۳۵ متر است. این فرضیات در مدرن ترین نظریات یعنی نظریه ریسمان و نظریه M نقش اساسی دارند. حتی شاخه ای از فیزیک تمامی خواص فیزیکی را پارامتر هایی دیجیتال (صفر یا یک) می داند. این حقایق حتی بیشتر بی نهایت یا تاثیر منطقی آن در جهان فیزیکی را نامحتمل می داند و تز چرچ تورینگ را محکم تر نشان می دهد.
با این توصیفات "ابر محاسبه" و عملی شدن آن بسیار نامحتمل به نظر می رسد با این وضعیت تکلیف پرسش هایی که ذاتا تصمیم ناپذیرند چه می شود؟ بدون الگوریتم آیا می توان کاری کرد؟ اول باید گفت اکثر مسائل تصمیم ناپذیر بدون کاربرد یا با کاربرد های محدود هستند در عمل ما برای اکثر کار هایی که در زندگی روزمره پیش می آید الگوریتم داریم اگرچه نه همیشه الگوریتم های سریعی؛ اما بسیاری از ریاضیدانان و فیلسوفان جدید بر این باورند که برای پاسخ به چنین پرسش هایی چاره ای به جز آزمایش نداریم! اما آزمایش در این حوزه چگونه است؟ مطمئنا تفاوت های بسیاری با حوزه های دیگر دارد در این جا دانشمندان علوم کامپیوتر با کامپیوتر هایشان به آزمایش می پردازند و به جواب های تقریبی روی می آورند مثلا در مورد مسائلی که نمی توان روی زمان محاسبه ی آن ها مطمئن بود این زمان را به زمان های خاصی محدود میکنند اگر در آن بازه به نتیجه نرسیدند اعلام می کنند که مثلا فلان x عضو مجموعه نیست این حرف را با علم به این می زنند که اطمینان صد در صدی روی آن نیست. این شیوه به روش های تجربی در علومی مانند فیزیک و شیمی بیشتر شباهت دارد .نکته مهمی که در این میان وجود دارد این است که احتمالات هم وارد کار می شوند و ما درست بودن یک رویه را نه با اطمینان کامل (همانطور که در روش صوری و قابل اثبات وجود داشت) بلکه با احتمال بیان می کنیم این زمینه توسط گریگوری چایتین مورد تحقیق قرار گرفته و دراین جا بیشتر به آن نمی پردازیم.
جالب ترین این روش ها در کتاب "نوع جدیدی از علم" نوشته ولفرام آمده است. به اعتقاد ولفرام برای برخورد با این مسائل ما باید به صورت تجربی به مطالعه سیستم های محاسبه گر در طبیعت بپردازیم و آن ها را کاملا مستند کرده و شبیه سازی کنیم مانند سیستم های آب و هوایی، مغز انسان، ساختار کهکشان ها، سیستم فرگشت طبیعی همه ی این ها سیستم های محاسبه ای هستند که دارای پیچیدگی زیادی هستند و ما اطلاعات زیادی در موردشان نداریم به همین خاطر ولفرام چنین تحقیقی را نوع جدیدی از علم میداند.
همچنین وجود عنصر شانس در تقریبا تمام روش های هوش مصنوعی باعث می شود آن ها خارج از این تعریف بگنجند. شانس یا تصادفی بودن عنصر بسیار مهمی است که هنوز اطلاعات زیادی در مورد اینکه چرا اینقدر در این الگوریتم های جدید مفید هستند، نداریم. اما بدون تصادف مثلا هیچ کدام از الگوریتم های فرگشتی یا شبکه های عصبی نتیجه ای ندارند. به طور مثال می توان ثابت کرد تصادف منجر به ایجاد خلاقیت و جواب های جدید در الگوریتم های فرگشتی و حتی خود فرآیند فرگشت در طبیعت می شود. با حذف تصادف تقریبا تمام روح این روش ها گرفته شده و از کار می افتند.