WHY: A decider already accepts members and rejects non-members. Accepting members is exactly the recognizer requirement; rejecting non-members is stronger than (and implies) the "may loop" condition. So:
Decidable⊆Recognizable.
Derivation of "decidable ⇒ closed under complement":
Let M decide L. Build M′: run M; if M accepts, M′ rejects; if M rejects, M′ accepts. Since Malways halts, M′ always halts and decides L. Swapping accept/reject only works because the machine halts. ∎
Derivation of the iff theorem (the famous "dovetailing" argument):
(⇒) If L is decidable, then L is recognizable (§2.1), and L is decidable (§2.2), hence recognizable.
(⇐) Suppose M1 recognizes L and M2 recognizes L. Build decider D on input w:
Run M1 and M2in parallel, step-by-step (one step of each, alternating). Why parallel? Because we can't fully run one first — it might loop.
Every w is in exactly one of L, L. So one of M1, M2 is guaranteed to accept w in finite time.
If M1 accepts → Daccepts.
If M2 accepts → Drejects.
D always halts (one machine must accept), so D decides L. ∎
Imagine a robot that checks if your guess is a hidden word.
A decider robot is honest both ways: it always beeps "YES, correct!" or "NO, wrong!" and then stops.
A recognizer robot only beeps "YES!" when you're right. When you're wrong, it just keeps thinking... and thinking... and never tells you "no." You'd sit there forever not knowing if it's almost done or stuck.
So a decider always answers; a recognizer only confirms the good news. And here's the magic trick: if you have one robot that confirms "right" and another that confirms "wrong," you can run both at once and whichever beeps first tells you the real answer — turning two half-robots into one full decider!
Dekho, ek Turing Machine kisi input pe sirf teen cheezein kar sakti hai: accept, reject, ya phir hamesha ke liye loop mein fas jaana. Yahi teesra option pura khel badal deta hai. Agar koi machine har input pe rukti hai (halt hoti hai) aur saaf saaf yes/no deti hai, to wo language decidable (recursive) hai. Lekin agar machine members pe to "yes" bol deti hai, par non-members pe shayad loop maar de aur kabhi jawab na de, to wo sirf recognizable (RE) hai. Matlab decidable ek strong guarantee hai, recognizable ek weak guarantee.
Sabse important baat yaad rakhna: decidable languages complement ke under closed hain, par recognizable nahi. Kyun? Decider hamesha halt karta hai, to bas accept/reject swap karke complement bana lo. Lekin recognizer to non-member pe loop maar raha hai — usme swap karne ke liye kuch hai hi nahi. Isiliye ATM (TM accepts w) recognizable hai par uska complement recognizable nahi hai.
Ek killer theorem hai: L decidable hai agar aur sirf agar L aur L dono recognizable hon. Iska proof "dovetailing" se hota hai — dono recognizers ko parallel mein, ek-ek step karke chalao. Har string ya to L mein hogi ya L mein, to koi ek machine zaroor finite time mein accept karegi. Bas wahi tumhara real answer hai. Yahan trick yeh hai ki ek machine ko pura mat chalao (wo loop kar sakti hai), warna fas jaoge.
Exam ke liye 80/20: yaad rakho table — decidable always halts (dono taraf), RE sirf yes pe halt; decidable complement-closed, RE nahi; ADFA decidable hai (DFA ∣w∣ steps mein ruk jaati hai), ATM recognizable par undecidable hai. Bas yeh samajh gaye to decidability ka core clear hai.
