آموزش ماشین تورینگ | ماشین تورینگ قابل حل است

تعریف مسئله قابل حل

یک مسئله یا یک زبان را «قابل حل» (Decidable) یا «بازگشتی» (Recursive) می‌نامیم اگر یک ماشین تورینگ وجود داشته باشد که دو کار زیر را با ضمانت انجام دهد:

1. توقف همیشگی: ماشین تورینگ برای هر ورودی‌ای (چه درون زبان باشد و چه خارج از آن) در نهایت متوقف شود و وارد یک حلقه بی‌نهایت نشود.
2. پاسخ قطعی:
   • اگر رشته ورودی درون زبان باشد، ماشین در حالت قبول (Accept) متوقف شود.
   • اگر رشته ورودی خارج از زبان باشد، ماشین در حالت رد (Reject) متوقف شود.

به بیان ساده‌تر، یک مسئله قابل حل است اگر بتوانیم یک برنامه کامپیوتری (هم‌ارز با ماشین تورینگ) بنویسیم که برای هر ورودی ممکن، بدون هیچ ابهامی و پس از مدت زمان محدود، جواب «بله» یا «خیر» بدهد.

مثال کلاسیک:
فرض کنید می‌خواهیم بررسی کنیم که آیا یک رشته فقط از حرف a تشکیل شده است یا خیر.
ما می‌توانیم یک ماشین تورینگ طراحی کنیم که:

• نوار را کاراکتر به کاراکتر بخواند.
• اگر به اولین کاراکتر غیر از a رسید، بلافاصله به حالت Reject برود و متوقف شود.
• اگر به انتهای رشته رسید و همه کاراکترها a بودند، به حالت Accept برود و متوقف شود.

این ماشین هرگز در حلقه نمی‌افتد و برای هر رشته ورودی جواب قطعی می‌دهد. بنابراین این مسئله یک «مسئله قابل حل» است.

نکته مهم:
در مسائل قابل حل، ماشین تورینگ حتماً متوقف می‌شود. اگر ماشین برای ورودی‌های خارج از زبان وارد حلقه بی‌نهایت شود، آن مسئله قابل حل نیست (فقط «نیمه‌قابل حل» یا «بازگشتی شمارا» محسوب می‌شود).