مسئله توقف: تفاوت میان نسخه‌ها

در این مساله هیچ شرطی بر روی زمانی که طول می‌کشد تا برنامه تمام شود یا حافظه‌ای که اشغال می‌کند وجود ندارد، یعنی ممکن است اجرای برنامه زمان زیادی طول بکشد، یا حافظه زیادی اشغال شود تا برنامه تمام شود؛ یعنی سوال این است که آیا بالاخره این برنامه تمام می‌شود یا تا ابد ادامه پیدا می‌کند.

 

[[آلن تورینگ]]در سال ۱۹۳۶ ثابت کرد که [[الگوریتم|الگوریتمی]] که این مساله را به ازای تمام برنامه‌ها و ورودی‌ها حل کند وجود ندارد. یعنی مساله توقف بر روی ماشین تورینگ قابل تصمیم‌گیری نیست.