مسئله توقف: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
بدون خلاصۀ ویرایش |
بدون خلاصۀ ویرایش |
||
خط ۱:
در [[Computability theory]] ''' مساله توقف''' یکی از مسائل از دسته [[decision problem]] است که درباره ی صفات یک برنامه ی کامپیوتری با استفاده از یک [[ماشین تورینگ]] تعریف شده(ماشینی برنامه پذیر است که قابلیت انجام هر محاسبه ای را دارد ) که می توان به شکل زیر آن را بیان کرد :
اگر شرح یک برنامه و ورودی متناهی متناظر با آن را داشته باشیم آیا میتوان تشخیص داد که این برنامه تمام می شود یا تا ابد ادامه می یابد . در این مساله هیچ گونه شرطی بر روی زمانی که طول می کشد تا برنامه تمام شود یا حافظه ای که اشغال می شود وجود ندارد و ممکن است زمان زیادی طول بکشد یا حافظه ی زیادی اشغال شود تا برنامه تمام شود ؛یعنی سوال این است که آیا بالاخره این برنامه تمام می شود یا تا ابد ادامه پیدا می کند.
[[تصویر:Alan_Turing.jpg ]]
[[آلن تورینگ]]در سال 1936 اثبات کرد که یک الگوریتم که این مساله را به ازای تمام برنامه ها و ورودی ها حل کند وجود ندارد. در اینصورت خواهیم گفت که مساله توقف بر روی ماشین تورینگ قابل تصمیم گیری نیست.
| |||