Decidability — decidable (recursive) and recognizable (recursively enumerable) languages

4.6.17 · Coding › Theory of Computation

1. Hum baat kar kya rahe hain?

2. Fundamental relationships (derive karo, memorize mat karo)

2.1 Har decidable language recognizable hoti hai

KYUN: Ek decider pehle se members ko accept karta hai aur non-members ko reject karta hai. Members ko accept karna exactly recognizer ki requirement hai; non-members ko reject karna "may loop" condition se zyada strong hai (aur usse imply karta hai). Isliye: $Decidable \subseteq Recognizable .$

2.2 Complementation theorem — crown jewel

"Decidable ⇒ complement ke under closed" ka derivation: Maano $M$ $L$ ko decide karta hai. $M^{'}$ banao: $M$ run karo; agar $M$ accept kare, $M^{'}$ reject kare; agar $M$ reject kare, $M^{'}$ accept kare. Kyunki $M$ hamesha halt karta hai, $M^{'}$ hamesha halt karega aur $\overline{L}$ decide karega. Accept/reject swap karna tabhi kaam karta hai kyunki machine halt karti hai. ∎

Iff theorem ka derivation (famous "dovetailing" argument):

( $\Rightarrow$ ) Agar $L$ decidable hai, toh $L$ recognizable hai (§2.1), aur $\overline{L}$ decidable hai (§2.2), isliye recognizable bhi hai.

( $\Leftarrow$ ) Maano $M_{1}$ $L$ ko recognize karta hai aur $M_{2}$ $\overline{L}$ ko recognize karta hai. Decider $D$ banao input $w$ par:

$M_{1}$ aur $M_{2}$ ko parallel mein run karo, step-by-step (ek ek step dono ka, alternating). Parallel kyun? Kyunki hum ek ko pehle puri tarah run nahi kar sakte — woh loop kar sakti hai.
Har $w$ exactly $L$ ya $\overline{L}$ mein se kisi ek mein hai. Isliye ek $M_{1}$ ya $M_{2}$ guaranteed hai finite time mein $w$ accept karegi.
- Agar $M_{1}$ accept kare → $D$ accept kare.
- Agar $M_{2}$ accept kare → $D$ reject kare.
$D$ hamesha halt karta hai (ek machine zarur accept karegi), isliye $D$ $L$ decide karta hai. ∎

Figure — Decidability — decidable (recursive) and recognizable (recursively enumerable) languages

3. Worked examples

4. Common mistakes (Steel-manned)

5. Quick mental model

Recall Feynman: ek 12-saal ke bachche ko explain karo

Socho ek robot hai jo check karta hai ki tumhara guess ek chhupi hui word hai ya nahi.

Ek decider robot dono taraf honest hai: woh hamesha beep karta hai "YES, sahi!" ya "NO, galat!" aur phir ruk jaata hai.
Ek recognizer robot sirf "YES!" beep karta hai jab tum sahi hote ho. Jab tum galat hote ho, woh bas sochta rehta hai... aur sochta rehta hai... aur kabhi "no" nahi bolta. Tum wahan hamesha ke liye baithe rahoge yeh jaane bina ki woh almost done hai ya stuck hai. Toh ek decider hamesha answer deta hai; ek recognizer sirf good news confirm karta hai. Aur yahan ek magic trick hai: agar tumhare paas ek robot hai jo "sahi" confirm kare aur doosra jo "galat" confirm kare, tum dono ko ek saath run kar sakte ho aur jo pehle beep kare woh asli jawab batata hai — do aadhe-adhoore robots se ek poora decider bana do!

6. Summary table (80/20 core)

Property	Decidable (Recursive)	Recognizable (RE)
Members par halt karta hai	hamesha (accept)	hamesha (accept)
Non-members par halt karta hai	hamesha (reject)	loop kar sakta hai
Complement ke under closed?	✅ Haan	❌ Nahi
Relationship	Decidable ⊊ Recognizable	superset
Key theorem	—	$L$ decidable $⟺$ $L, \overline{L}$ dono RE
Example	$A_{D F A}$	$A_{T M}$ (RE, undecidable)

Flashcards

Decider kya hai?

Ek TM jo har input par halt karta hai, members ko accept karta hai aur non-members ko reject karta hai.

Ek language decidable hai iff kaise TM exist kare?

Ek TM jo sabhi inputs par halt kare (ek total decider / recursive).

Ek language recognizable hai iff kaise TM exist kare?

Ek TM jo exactly members ko accept kare; non-members par woh reject YA loop forever kar sakta hai.

True/False: Har decidable language recognizable hoti hai.

True (ek decider pehle se recognizer ki condition aur usse zyada satisfy karta hai).

True/False: Recognizable languages complement ke under closed hain.

False — e.g.

A_{T M}

RE hai lekin

\overline{A_{T M}}

nahi.

True/False: Decidable languages complement ke under closed hain.

True — accept/reject swap karo; kaam karta hai kyunki deciders hamesha halt karte hain.

Decidable aur recognizable ko link karne wala iff theorem batao.

L

decidable hai iff dono

L

aur

\overline{L}

recognizable hain.

Iff-theorem proof mein

M_{1}

aur

M_{2}

parallel kyun run karte hain?

Kyunki ek ko puri tarah run karna loop forever kar sakta hai; dovetailing guarantee karta hai ki halting wali machine reach ho.

Ek recognizable lekin undecidable language batao.

A_{T M} = {⟨ M, w ⟩ : M accepts w}

A_{D F A}

decidable kyun hai?

Ek DFA exactly

∣ w ∣

steps mein halt karta hai, isliye simulation hamesha terminate karta hai.

\overline{A_{T M}}

recognizable kyun nahi hai?

Agar hoti, toh

A_{T M}

aur uska complement dono RE hote,

A_{T M}

ko decidable bana dete — contradiction.

Yahan "enumerable" ka matlab kya hai?

Ek TM language ki saari aur sirf wohi strings list (print) kar sakta hai; recognizable hone ke equivalent hai.

Connections

Turing Machines — dono classes ke neeche ka model.
Universal Turing Machine — $A_{T M}$ ka recognizer.
Diagonalization — prove karta hai ki $A_{T M}$ undecidable hai.
Halting Problem — canonical undecidable, RE language.
Reductions and Rice's Theorem — undecidability propagate karna.
Closure Properties — union/intersection vs complement.
Chomsky Hierarchy — RE = Type-0 languages.