The Hierarchy of Solvability
ليست كل اللغات "قابلة للحل". هناك تصنيف دقيق لما تستطيع آلة تورنغ فعله:
-
1. Recursive Languages (Decidable)
آلة تورنغ تتوقف (Halt) دائماً.
الجواب دائماً: "نعم" أو "لا". (هذه هي الخوارزميات الحقيقية). -
2. Recursively Enumerable (RE)
إذا كانت الكلمة في اللغة، الآلة تتوقف وتقول "نعم".
إذا لم تكن، قد تتوقف وتقول "لا"، أو قد تستمر للأبد (Loop Forever). - 3. Non-RE Languages لغات لا توجد آلة تورنغ تستطيع التعرف عليها أصلاً! (خارج حدود الحوسبة).
The Diagonalization Language ($L_d$)
أول لغة غير قابلة للحساب (Non-RE)
بما أننا نستطيع ترميز أي آلة تورنغ كسلسلة ثنائية $w_i$، يمكننا تخيل جدول يجمع كل الآلات الممكنة $M_i$ وكل المدخلات الممكنة $w_j$.
| w1 | w2 | w3 | ... | |
| M1 | 0 | 1 | 0 | ... |
| M2 | 1 | 1 | 0 | ... |
| M3 | 0 | 0 | 0 | ... |
$$ L_d = \{ w_i \mid w_i \notin L(M_i) \} $$
النتيجة: $L_d$ تختلف عن كل لغة يقبلها أي $M_i$ (على الأقل في الخانة القطرية).
$\therefore$ لا توجد آلة تورنغ تقبل $L_d$. ( $L_d$ is Not RE).
The Universal Language ($L_u$)
$$ L_u = \{ (M, w) \mid M \text{ accepts } w \} $$
هل نستطيع بناء آلة (Universal TM) تأخذ وصف آلة أخرى $M$ ومدخل $w$ وتخبرنا هل ستقبل $M$ هذا المدخل؟
النتيجة: $L_u$ هي RE ولكنها Undecidable.
The Halting Problem (مشكلة التوقف)
هل سيتوقف البرنامج؟
هل يوجد خوارزمية تأخذ أي برنامج $P$ ومدخل $I$، وتقرر (دائماً وبشكل صحيح) ما إذا كان $P$ سيتوقف أم سيستمر للأبد؟
الدليل (Proof Sketch):
- افترض وجود آلة $H$ تحل المشكلة.
- اصنع آلة جديدة $D$ تستخدم $H$ وتعكس نتيجتها (إذا قالت $H$ سيتوقف، $D$ تدخل في حلقة لا نهائية، والعكس).
- شغل $D$ على نفسها ($D(D)$).
- تحدث تناقض منطقي (Paradox) $\to$ الفرضية خاطئة ولا وجود لـ $H$.
Recursive Languages & Complements
اللغة $L$ تكون Recursive إذا وفقط إذا كانت:
1. $L$ هي RE.
2. ومكملتها $\bar{L}$ هي أيضاً RE.
إذا كانت $L$ هي RE ولكن $\bar{L}$ ليست RE، فإن $L$ تكون Undecidable (مثل $L_u$).
Reduction (التقليص)
لإثبات أن مشكلة جديدة $P_{new}$ غير قابلة للحل:
حول مشكلة التوقف (Halting) المعروفة باستحالتها إلى $P_{new}$.
إذا استطعت حل $P_{new}$، فهذا يعني أنك حللت Halting Problem (وهذا مستحيل).
$\therefore P_{new}$ مستحيلة الحل.