مسئله توقف
مسئله توقف از دسته مسائل تصمیم‌گیری است که دربارهٔ صفات یک برنامه کامپیوتری با استفاده از یک ماشین تورینگ تعریف شده (ماشینی برنامه‌پذیر که قابلیت انجام هر محاسبه‌ای را دارد) بحث می‌کند. می‌توان به شکل زیر آن را بیان کرد:
اگر شرح یک برنامه و ورودی متناهی متناظر با آن را داشته باشیم آیا می‌توان تشخیص داد که این برنامه متوقف می‌شود یا تا ابد ادامه می‌یابد.
در این مسئله هیچ شرطی بر روی زمانی که طول می‌کشد تا برنامه تمام شود یا حافظه‌ای که اشغال می‌کند وجود ندارد، یعنی ممکن است اجرای برنامه زمان زیادی طول بکشد، یا حافظه زیادی اشغال شود تا برنامه تمام شود؛ یعنی سؤال این است که آیا بالاخره این برنامه تمام می‌شود یا تا ابد ادامه پیدا می‌کند.
برای مثال به برنامه زیر که به زبان سی نوشته توجه کنید:
codice_1
این برنامه هیچ‌گاه متوقف نمی‌شود و در این حلقه گیر می‌کند. از طرف دیگر در برنامه زیر داریم: codice_2 که در این برنامه بدون توجه به ورودی متوقف می‌شود.
در کل مسئله توقف از این جنبه مشهور است که از اولین دسته مسائلی بود که تصمیم ناپذیر بود، بدین صورت که هیچ برنامه کامپیوتری با قابلیت جواب دادن به این سؤال به ازای جمیع ورودی‌ها پیدا نشد و اثبات شد که وجود ندارد. در نتیجه آن تعدادی زیادی مسائلی از این دست بیان شدند. راه حل رایج برای اثبات کردن اینکه یک مسئله تصمیم ناپذیر است استفاده از روش کاهیدن (reduction) است.
یکی از نتایج تصمیم ناپذیر بودن مسئله توقف این است که الگوریتمی عمومی برای پیدا کردن درستی یا نادرستی یک حکم دربارهٔ اعداد طبیعی وجود ندارد. چون می‌توان گزاره‌ای که نشان می‌دهد آیا یک الگوریتم با ورودی‌های مربوط به آن متوقف می‌شود یا نه را متناظر با یک حکم دربارهٔ اعداد طبیعی در نظر گرفت. چون می‌دانیم که این همان مسئله توقف است پس چنین الگوریتمی برای اعداد طبیعی پیدا نمی‌شود.
یکی دیگر از نتایج تصمیم ناپذیری مسئله توقف تئوری Rice's theorem است که می‌گوید به‌طور کلی نمی‌توان دربارهٔ درستی هرعبارت نا بدیهی (non-trival) مربوط به تابعی که توسط یک الگوریتم تعریف شده نظر داد. برای مثال نمی‌توان به سؤال «آیا این الگوریتم با ورودی 0 متوقف می‌شود یا نه» پاسخ قطعی داد. توجه کنید که این تئوری دربارهٔ تابعی که توسط الگوریتم تعریف شده نظر می‌دهد و نه دربارهٔ خود الگوریتم. برای مثال تشخیص اینکه یک الگوریتم در 100 مرحله متوقف می‌شود یا نه کار آسانی است و این یک گزاره دربارهٔ خود الگوریتم است و نه دربارهٔ تابع آن الگوریتم.
تورینگ در اثبات خود ایده‌آلگوریتم را با تعریف ماشین تورینگ رسمی‌کرد، گرچه به هیچ وجه نتیجه مخصوص آن‌ها نیست و به‌طور مساوی در مدل‌های دیگر محاسبه که متناظر با توان محاسباتی با ماشین تورینگ هستند به کار بسته می‌شود مانند markov algothims, Lambda calculus یا Post systems
موضوعی که در این باره بسیار حائز اهمیت است این است که رسمی سازی به ما اجازه تناظر بعضی از گونه‌های داده که الگوریتم می‌تواند ازآنها بهره ببرد با خود الگوریتم را می‌دهد.برای مثال اگر الگوریتم توابعی روی اعداد طبیعی تعریف شده‌است (مانند توابع محاسباتی) باید یک تناظر از روی الگوریتم به اعداد طبیعی باشد.تناظر به رشتهها آسان‌ترین کار است اما تبدیل رشته به عدد با تعریف آن‌ها به صورت اعداد در سیستم عددی n تایی امکان‌پذیر است.
این اثبات نشان می‌دهد که یک تابع به ازای جمیع حالات که تصمیم بگیرد که برنامهٔ i با ورودی دلخواه x آیا متوقف می‌شود یا نه وجود ندارد؛ یعنی تابع h که با شرایط زیر وجود ندارد :
اگر برنامه متوقف شود formula_1
اگر برنامه متوقف نشود formula_2
زیرا اگر برنامه K را چنان فرض کنیم که به صورت زیر باشد به تناقض می‌رسیم: codice_3
اگر فرض کنیم که خود این برنامه K به عنوان ورودی به خودش داده شود به تناقض خواهیم رسید زیرا اگر h(k,k)=1 در این صورت برنامه متوقف نخواهد شد و در while(true) خواهد ماند اما خود h(k,k)=1 به این معنا است که باید برنامه متوقف شود که تناقض می‌باشد . حالت h(k,k)=0 نیز مشابهاً به تناقض می‌رسد.