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