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