مسئله توقف

مسئله توقف ( به انگلیسی: halting problem ) در نظریه محاسبه پذیری، یک مسئله در مورد جواب دادن به این سوال است که: آیا از «توصیف یک برنامه رایانه ای اختیاری» و یک «ورودی»، مسئله اجرایش را «تمام ( متوقف ) » می کند، یا نه ( یعنی برای همیشه اجرا خواهد شد ) . آلن تورینگ در سال ۱۹۳۶ اثبات کرد که یک الگوریتم همگانی برای حل مسئله توقف ( یعنی برای همه جفت های «ورودی - برنامه» ممکن ) وجود ندارد. یعنی مسئله توقف بر روی ماشین تورینگ تصمیم پذیر نیست.
مسئله توقف از دسته مسائل تصمیم گیری است که دربارهٔ صفات یک برنامه کامپیوتری با استفاده از یک ماشین تورینگ تعریف شده ( ماشینی برنامه پذیر که قابلیت انجام هر محاسبه ای را دارد ) بحث می کند. می توان به شکل زیر آن را بیان کرد:
اگر شرح یک برنامه و ورودی متناهی متناظر با آن را داشته باشیم آیا می توان تشخیص داد که این برنامه متوقف می شود یا تا ابد ادامه می یابد.
در این مسئله هیچ شرطی بر روی زمانی که طول می کشد تا برنامه تمام شود یا حافظه ای که اشغال می کند وجود ندارد، یعنی ممکن است اجرای برنامه زمان زیادی طول بکشد، یا حافظه زیادی اشغال شود تا برنامه تمام شود؛ یعنی سؤال این است که آیا بالاخره این برنامه تمام می شود یا تا ابد ادامه پیدا می کند.
برای مثال به برنامه زیر که به زبان سی نوشته توجه کنید:
int main ( void )
{ while ( 1 ) ; }
این برنامه هیچ گاه متوقف نمی شود و در این حلقه گیر می کند. از طرف دیگر در برنامه زیر داریم:
int main ( void ) { printf ( "Hello, world" ) ;
return 0; }
که در این برنامه بدون توجه به ورودی متوقف می شود.
در کل مسئله توقف از این جنبه مشهور است که از اولین دسته مسائلی بود که تصمیم ناپذیر بود، بدین صورت که هیچ برنامه کامپیوتری با قابلیت جواب دادن به این سؤال به ازای جمیع ورودی ها پیدا نشد و اثبات شد که وجود ندارد. در نتیجه آن تعدادی زیادی مسائلی از این دست بیان شدند. راه حل رایج برای اثبات کردن اینکه یک مسئله تصمیم ناپذیر است استفاده از روش کاهیدن ( reduction ) است.
یکی از نتایج تصمیم ناپذیر بودن مسئله توقف این است که الگوریتمی عمومی برای پیدا کردن درستی یا نادرستی یک حکم دربارهٔ اعداد طبیعی وجود ندارد. چون می توان گزاره ای که نشان می دهد آیا یک الگوریتم با ورودی های مربوط به آن متوقف می شود یا نه را متناظر با یک حکم دربارهٔ اعداد طبیعی در نظر گرفت. چون می دانیم که این همان مسئله توقف است پس چنین الگوریتمی برای اعداد طبیعی پیدا نمی شود.