مسئله توقف: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
بدون خلاصۀ ویرایش |
کمی ویرایش |
||
خط ۱:
اگر شرح یک برنامه و ورودی متناهی متناظر با آن را داشته باشیم آیا میتوان تشخیص داد که این برنامه تمام می شود یا تا ابد ادامه می یابد . در این مساله هیچ گونه شرطی بر روی زمانی که طول می کشد تا برنامه تمام شود یا حافظه ای که اشغال می شود وجود ندارد و ممکن است زمان زیادی طول بکشد یا حافظه ی زیادی اشغال شود تا برنامه تمام شود ؛یعنی سوال این است که آیا بالاخره این برنامه تمام می شود یا تا ابد ادامه پیدا می کند.▼
اگر شرح یک برنامه و ورودی متناهی متناظر با آن را داشته باشیم آیا میتوان تشخیص داد که این برنامه متوقف می‌شود یا تا ابد ادامه می‌یابد.
▲
[[تصویر:Alan_Turing.jpg|thumb|[[آلن تورینگ]] از پیش‌گامان کار بر مساله توقف بود.]]
[[آلن تورینگ]]در سال
==مثال==
برای مثال به برنامه زیر که به [[زبان
{{چپچین}}
<code>
سطر ۱۷ ⟵ ۲۱:
</code>
{{پایان چپچین}}
این برنامه
{{چپچین}}
سطر ۳۵ ⟵ ۳۹:
==اهمیت و نتایج مساله توقف==
در کل مساله توقف از این جنبه مشهور است که از اولین دسته مسائلی بود که تصمیم ناپذیر
یکی از نتایج تصمیم ناپذیر بودن مساله توقف این است که
یکی دیگر از نتایج تصمیم ناپذیری مساله توقف تئوری [[Rice's theorem]] است که می گوید به طور کلی نمی توان درباره ی درستی هرعبارت نا بدیهی (non-
▲یکی از نتایج تصمیم ناپذیر بودن مساله توقف این است که یک الگوریتم عمومی برای پیدا کردن درستی یا نادرستی یک حکم درباره اعداد طبیعی وجود ندارد.چون می توان گزاره ای که نشان میدهد آیا یک الگوریتم با ورودی های مربوط به آن متوقف می شود یا نه را متناظر با یک حکم درباره ی اعداد طبیعی در نظر گرفت.و چون می دانیم که این همان مساله توقف است پس چنین الگوریتمی برای اعداد طبیعی پیدا نمی شود.
▲یکی دیگر از نتایج تصمیم ناپذیری مساله توقف تئوری [[Rice's theorem]] است که می گوید به طور کلی نمی توان درباره ی درستی هرعبارت نا بدیهی(non- trival) مربوط به تابعی که توسط یک الگوریتم تعریف شده نظر داد.برای مثال نمی توان به سوال "آیا این الگوریتم با ورودی 0 متوقف می شود یا نه"پاسخ قطعی داد.توجه کنید که این تئوری درباره ی تابعی که توسط الگوریتم تعریف شده نظر می دهد و نه درباره ی خود الگوریتم.برای مثال تشخیص اینکه یک الگوریتم در 100 مرحله متوقف می شود یا نه کار آسانی است و این یک گزاره درباره ی خود الگوریتم است و نه درباره ی تابع آن الگوریتم.
==رسمی کردن مساله توقف==
تورینگ در اثبات خود ایده الگوریتم را با تعریف ماشین تورینگ رسمی کرد، گرچه به هیچ وجه نتیجه مخصوص آنها نیست و به طور مساوی در مدل های دیگر محاسبه که متناظر با توان محاسباتی با ماشین تورینگ هستند به کار بسته می شود مانند
[[الگوریتم های
موضوعی که در این باره بسیار حائز اهمیت است این است که رسمی سازی به ما اجازه تناظر بعضی از گونه های داده که الگوریتم می تواند ازآنها بهره ببرد با خود الگوریتم را می دهد.برای مثال اگر الگوریتم توابعی روی اعداد طبیعی تعریف شده است (مانند توابع محاسباتی) باید یک تناظر از روی الگوریتم به اعداد طبیعی باشد.تناظر به [[رشته]] ها آسان ترین کار است اما تبدیل رشته به عدد با تعریف آنها به صورت اعداد در [[سیستم عددی]] n تایی امکان پذیر است.
| |||