مسئله توقف
From Wikipedia, the free encyclopedia
مسئله توقف (به انگلیسی: halting problem) در نظریه محاسبهپذیری، یک مسئله در مورد جوابدادن به این سوال است که: آیا از «توصیف یک برنامه رایانهای اختیاری» و یک «ورودی»، مسئله اجرایش را «تمام(متوقف)» میکند، یا نه (یعنی برای همیشه اجرا خواهد شد). آلن تورینگ در سال ۱۹۳۶ اثبات کرد که یک الگوریتم همگانی برای حل مسئله توقف (یعنی برای همه جفتهای «ورودی-برنامه» ممکن) وجود ندارد. یعنی مسئله توقف بر روی ماشین تورینگ تصمیمپذیر نیست.
مسئله توقف از دسته مسائل تصمیمگیری است که دربارهٔ صفات یک برنامه کامپیوتری با استفاده از یک ماشین تورینگ تعریف شده (ماشینی برنامهپذیر که قابلیت انجام هر محاسبهای را دارد) بحث میکند. میتوان به شکل زیر آن را بیان کرد:
اگر شرح یک برنامه و ورودی متناهی متناظر با آن را داشته باشیم آیا میتوان تشخیص داد که این برنامه متوقف میشود یا تا ابد ادامه مییابد.
در این مسئله هیچ شرطی بر روی زمانی که طول میکشد تا برنامه تمام شود یا حافظهای که اشغال میکند وجود ندارد، یعنی ممکن است اجرای برنامه زمان زیادی طول بکشد، یا حافظه زیادی اشغال شود تا برنامه تمام شود؛ یعنی سؤال این است که آیا بالاخره این برنامه تمام میشود یا تا ابد ادامه پیدا میکند.