مسئله تصمیم‌ناپذیر

در نظریه محاسبه و نظریه پیچیدگی محاسبه، یک مسئله تصمیم ناپذیر، یعنی یک مسئله تصمیم که می‌دانیم غیرممکن است الگوریتمی را بسازیم که همیشه به یک جواب درست آره یا نه می‌رسد.
مسئله تصمیم، هرسوال دلخواهی است که جواب آن بله/خیر است که ورودی‌های نامتناهی دارد. به همین خاطر معمولاً مسئله تصمیم، هم ارز با مجموعه ورودی‌هایی که مسئله به جواب بله می‌رسد، تعریف می‌شود. این ورودی‌ها می‌توانند اعداد طبیعی باشند و همچنین می‌توانند انواع دیگر مقادیر مثل رشته‌هایی از یک زبان صوری باشند. با استفاده از یک رمز گذاری مثل شماره گذاری گودال، رشته‌ها به عنوان اعداد طبیعی رمزگذاری می‌شوند؛ بنابراین مسئله تصمیم به‌طور غیررسمی به شکل یک زبان صوری تعبیر می‌شود که با یک مجموعه از اعداد طبیعی معادل است.
بطور رسمی، مسئله تصمیم زیرمجموعه‌ای از اعداد طبیعی است. مسئله غیررسمی متناظر تصمیم‌گیری در مورد این است که آیا عدد داده شده در مجموعه است یانه. مسئله تصمیم A، قابل حل یا عملاً قابل حل نامیده می‌شود، اگرA مجموعه‌ای بازگشتی باشد. یک مسئله تا حدی قابل حل، نیمه حل پذیر، قابل حل یا اثبات است، اگر A مجموعه‌ای قابل شمارش باشد. این بدان معناست که الگوریتمی وجود دارد که وقتی جواب بله است بالاخره متوقف می‌شود اما اگر جواب نه است ممکن است دنباله داشته باشد (ادامه یابد). مسائل نسبتاً قابل حل و هر مسئله دیگری که قابل حل نیست، غیرقابل حل نامیده می‌شود.

در نظریه محاسبه

در نظریه محاسبه، مسئله خاتمه پذیر مسئله‌ای قابل حل است که می‌تواند همانند آنچه در ادامه می‌آید بیان شود:
«با دادن توصیف یک مسئله دلبخواهی و ورودی مشخص، تصمیم می‌گیرد که آیا اجرای برنامه متوقف شود یا برای همیشه ادامه یابد.»
آلن تورینگ در سال ۱۹۳۶ ثابت کرد که الگوریتم جامع قابل اجرا در ماشین تورینگ که مسئله خاتمه پذیر را برای همه جفت‌های ممکن ورودی برنامه حل کند لزوماً نمی‌تواند وجود داشته باشد؛ بنابراین مسئله خاتمه پذیر برای ماشین تورینگ، غیرقابل حل است.

ارتباط با نظریه ناقص گودل

مفاهیمی که در نظریه ناقص گودل مطرح می‌شود بسیار شبیه به مفاهیمی هستند که در مسئله دنباله‌دار مطرح می‌شود و اثبات‌ها کاملاً شبیه هستند. در حقیقت، شکلی ضعیف تر از اولین نظریه ناقص، پیامدی طبیعی از غیرقابل حل بودن مسئله خاتمه پذیر است. این شکل ضعیف تر متفاوت از گزاره استاندارد نظریه ناقص است که تأکید دارد بر اصل بدیهی مستدل، محکم، کامل همه گزاره‌ها دربارهٔ این که اعداد طبیعی غیرقابل حصولند. قسمت مستدل، قسمت ضعیف است بدین معنا که ما نیاز به سیستم بدیهی در مورد اثبات گزاره‌های فقط درست دربارهٔ اعداد طبیعی داریم. اظهارنظر در مورد این که بیان شکل استاندارد اولین نظریه ناقص گودل، کاملاً بی ارتباط با سوالات حقیقت است، مربوط است به مسئله‌ای که آیا امکان اثبات دارد یا نه مهم است. شکل ضعیف نظریه می‌تواند از غیرقابل حل بودن مسئله خاتمه پذیر همان‌طور که در ادامه می‌آید، اثبات شود. فرض کنید که ما اصل بدیهی محکم و کاملی از همه گزاره‌های منطقی نوع اول در مورد اعداد طبیعی داریم؛ بنابراین ما می‌توانیم الگوریتمی بسازیم که همه این گزاره‌ها را محاسبه کند: بدین معنا که الگوریتم (N(n ی وجود دارد که با دادن عدد طبیعی n، گزاره منطقی نوع اول درستی را در مورد اعداد طبیعی محاسبه کند که برای همه گزاره‌های درست، حداقل یک n ی وجود دارد که (N(n آن گزاره را می‌دهد. اکنون تصور کنید که می‌خواهیم تصمیم بگیریم که آیا الگوریتمی با تصویر a روی ورودی i متوقف می‌شود. می‌دانیم که این گزاره با گزاره منطقی نوع اول (H(a,i بیان می‌شود. چون اصل بدیهی کامل است پس در ادامه به آن به دنباله آن n ای مثل این (N(n)=H(a,i یا ‘n مثل این (N(n’)=H(a,i وجود دارد؛ بنابراین اگر ما همه n را تکرار کنیم تا جایی که حتی (H(a,i یا نقیض آن دست پیدا کنیم، پس برای همیشه متوقف خواهیم شد. بدین معنا که به ما الگوریتمی می‌دهد که به مسئله خاتمه پذیر خاتمه می‌دهد. در نتیجه، ما می‌دانیم که چنین الگوریتمی نمی‌تواند وجود داشته باشد و در ادامه، فرض وجود اصل بدیهی کامل و محکمی از همه گزاره‌های منطقی نوع اول در مورد اعداد طبیعی باید غلط باشد.

مثال‌هایی از مسائل غیرقابل حل

مقاله اصلی: فهرست مسائل غیرقابل حل
مسائل غیرقابل حل می‌توانند مربوط به عنوان‌های متفاوتی مثل دستگاه‌های انتزاعی، منطقی یا شیوه منظم سازمان یافته topology، باشد. توجه داشته باشید از آن جایی که تعداد زیادی مسئله غیرقابل حل، غیرقابل محاسبه هستند؛ بنابراین هر فهرستی حتی یکی از آن‌هایی که طول بی پایانی دارند، لزوماً کامل نیستند.