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

یکی دیگر از نتایج تصمیم ناپذیری مساله توقف تئوری [[Rice's theorem]] است که می گوید به طور کلی نمی توان درباره یدربارهٔ درستی هرعبارت نا بدیهی (non-trival) مربوط به تابعی که توسط یک الگوریتم تعریف شده نظر داد. برای مثال نمی توان به سوال «آیا این الگوریتم با ورودی 0 متوقف می شود یا نه» پاسخ قطعی داد. توجه کنید که این تئوری درباره تابعی که توسط الگوریتم تعریف شده نظر می دهد و نه درباره یدربارهٔ خود الگوریتم. برای مثال تشخیص اینکه یک الگوریتم در 100 مرحله متوقف می شود یا نه کار آسانی است و این یک گزاره درباره یدربارهٔ خود الگوریتم است و نه درباره یدربارهٔ تابع آن الگوریتم.

این اثبات نشان می دهد که یک تابع به ازای جمیع حالات که تصمیم بگیرد که برنامه یبرنامهٔ i با ورودی دلخواه x آیا متوقف می شود یا نه وجود ندارد ؛ یعنی تابع h که با شرایط زیر وجود ندارد :