مسئله توقف

مسئله توقف ، در نظریه محاسبه‌پذیری از دسته مسائل تصمیم‌گیری است که درباره صفات یک برنامه کامپیوتری با استفاده از یک ماشین تورینگ تعریف شده (ماشینی برنامه‌پذیر که قابلیت انجام هر محاسبه‌ای را دارد) بحث می‌کند. می‌توان به شکل زیر آن را بیان کرد:
اگر شرح یک برنامه و ورودی متناهی متناظر با آن را داشته باشیم آیا می‌توان تشخیص داد که این برنامه متوقف می‌شود یا تا ابد ادامه می‌یابد.
در این مسئله هیچ شرطی بر روی زمانی که طول می‌کشد تا برنامه تمام شود یا حافظه‌ای که اشغال می‌کند وجود ندارد، یعنی ممکن است اجرای برنامه زمان زیادی طول بکشد، یا حافظه زیادی اشغال شود تا برنامه تمام شود؛ یعنی سوال این است که آیا بالاخره این برنامه تمام می‌شود یا تا ابد ادامه پیدا می‌کند.
آلن تورینگ از پیش‌گامان کار بر مسئله توقف بود.
آلن تورینگ در سال ۱۹۳۶ ثابت کرد که الگوریتمی که این مسئله را به ازای تمام برنامه‌ها و ورودی‌ها حل کند وجود ندارد. یعنی مسئله توقف بر روی ماشین تورینگ قابل تصمیم‌گیری نیست.
مثال
برای مثال به برنامه زیر که به زبان سی نوشته توجه کنید:
int main(void)
{ while (1);
این برنامه هیچ‌گاه متوقف نمی‌شود و در این حلقه گیر می‌کند. از طرف دیگر در برنامه زیر داریم:
int main(void)
printf("Hello, world");
return 0;
که در این برنامه بدون توجه به ورودی متوقف می‌شود.
اهمیت و نتایج مسئله توقف
در کل مسئله توقف از این جنبه مشهور است که از اولین دسته مسائلی بود که تصمیم ناپذیر بود، بدین صورت که هیچ برنامه کامپیوتری با قابلیت جواب دادن به این سوال به ازای جمیع ورودی‌ها پیدا نشد و اثبات شد که وجود ندارد. در نتیجه آن تعدادی زیادی مسائلی از این دست بیان شدند. راه حل رایج برای اثبات کردن اینکه یک مسئله تصمیم ناپذیر است استفاده از روش کاهیدن (reduction) است.
یکی از نتایج تصمیم ناپذیر بودن مسئله توقف این است که الگوریتمی عمومی برای پیدا کردن درستی یا نادرستی یک حکم درباره اعداد طبیعی وجود ندارد. چون می‌توان گزاره‌ای که نشان می‌دهد آیا یک الگوریتم با ورودی‌های مربوط به آن متوقف می‌شود یا نه را متناظر با یک حکم درباره اعداد طبیعی در نظر گرفت. چون می‌دانیم که این همان مسئله توقف است پس چنین الگوریتمی برای اعداد طبیعی پیدا نمی‌شود.
یکی دیگر از نتایج تصمیم ناپذیری مسئله توقف تئوری Rices theorem است که می‌گوید به طور کلی نمی‌توان درباره درستی هرعبارت نا بدیهی (non-trival) مربوط به تابعی که توسط یک الگوریتم تعریف شده نظر داد. برای مثال نمی‌توان به سوال «آیا این الگوریتم با ورودی 0 متوقف می‌شود یا نه» پاسخ قطعی داد. توجه کنید که این تئوری درباره تابعی که توسط الگوریتم تعریف شده نظر می‌دهد و نه درباره خود الگوریتم. برای مثال تشخیص اینکه یک الگوریتم در 100 مرحله متوقف می‌شود یا نه کار آسانی است و این یک گزاره درباره خود الگوریتم است و نه درباره تابع آن الگوریتم.
رسمی کردن مسئله توقف
تورینگ در اثبات خود ایده‌آلگوریتم را با تعریف ماشین تورینگ رسمی کرد، گرچه به هیچ وجه نتیجه مخصوص آنها نیست و به طور مساوی در مدل‌های دیگر محاسبه که متناظر با توان محاسباتی با ماشین تورینگ هستند به کار بسته می‌شود مانند
markov algothims, Lambda calculus یا Post systems
موضوعی که در این باره بسیار حائز اهمیت است این است که رسمی سازی به ما اجازه تناظر بعضی از گونه‌های داده که الگوریتم می‌تواند ازآنها بهره ببرد با خود الگوریتم را می‌دهد.برای مثال اگر الگوریتم توابعی روی اعداد طبیعی تعریف شده است (مانند توابع محاسباتی) باید یک تناظر از روی الگوریتم به اعداد طبیعی باشد.تناظر به رشتهها آسان‌ترین کار است اما تبدیل رشته به عدد با تعریف آنها به صورت اعداد در سیستم عددی n تایی امکان پذیر است.
اثبات
این اثبات نشان می‌دهد که یک تابع به ازای جمیع حالات که تصمیم بگیرد که برنامه i با ورودی دلخواه x آیا متوقف می‌شود یا نه وجود ندارد؛ یعنی تابع h که با شرایط زیر وجود ندارد :
اگر برنامه متوقف شود
اگر برنامه متوقف نشود
زیرا اگر برنامه K را چنان فرض کنیم که به صورت زیر باشد به تناقض می‌رسیم:
Program K(program A)
if(h(A,A)==1)
While(true);
اگر فرض کنیم که خود این برنامه K به عنوان ورودی به خودش داده شود به تناقض خواهیم رسید زیرا اگر h(k,k)=1 در این صورت برنامه متوقف نخواهد شد و در while(true) خواهد ماند اما خود h(k,k)=1 به این معنا است که باید برنامه متوقف شود که تناقض می‌باشد. حالت h(k,k)=0 نیز مشابها به تناقض می‌رسد.
زمان اجرا در بدترین حالت