مساله توقف
از ویکی‌پدیا، دانشنامهٔ آزاد.
 |
در متن این مقاله از هیچ منبع و ماخذی نام برده نشده‌است. شما می‌توانید با افزودن منابع بر طبق اصول اثبات‌پذیری و شیوه‌نامهٔ ارجاع به منابع، به ویکی‌پدیا کمک کنید. مطالب بی‌منبع احتمالاً در آینده حذف خواهند شد. |
 |
این مقاله نیازمند ویکی‌سازی است. لطفاً با توجه به راهنمای ویرایش و شیوه‌نامه آن را تغییر دهید. در پایان، پس از ویکی‌سازی این الگوی پیامی را بردارید. |
مسألهٔ توقف اصطلاحی در نظریه ماشین‌ها است که به بررسی توقف یک برنامه ماشین تورینگ می‌پردازد. این مسأله حل‌نشدنی است. هیچ برنامه‌ای (بر ماشین تورینگ) نمی‌توان نوشت که بتواند توقف هر برنامه‌ای را بررسی کند. فرض کنید برنامهٔ «توقف» وجود دارد که توقف برنامهٔ «ورودی» را بررسی می‌کند. برنامهٔ «دردسر» را در نظر بگیرید که تنها در صورتی متوقف می‌شود که برنامهٔ «توقف» تصمیم بگیرد که برنامهٔ «دردسر» متوقف نمی‌شود. در صورتی که برنامهٔ «توقف» تصمیم بگیرد که «دردسر» متوقف می‌شود، «دردسر» برعکس عمل می‌کند و متوقف نمی‌شود و در صورتی که برنامهٔ «توقف» تصمیم بگیرد که «دردسر» متوقف نمی‌شود، «دردسر» برعکس عمل می‌کند و متوقف می‌شود. در هر دو حالت برنامهٔ «توقف» اشتباه کرده است. پس فرض وجود برنامهٔ «توقف» نادرست بوده است. به این روش اثبات قطری سازی گفته می‌شود.
