Halting problem — undecidability proof by diagonalization

4.6.18 · Coding › Theory of Computation

Halting Problem HAI KYA?

HUM KYUN CARE KARTE HAIN? Bahut saare real questions — "kya yeh loop terminate hogi?", "kya yeh code dead hai?", "kya yeh do programs equivalent hain?" — halting par reduce hote hain. Agar halting unsolvable hai, toh woh bhi hain. Yeh uss hard limit ko mark karta hai jo mechanical computation kabhi bhi achieve kar sakti hai.

PROOF KAISE KAAM KARTA HAI — scratch se derivation

Hum proof by contradiction + diagonalization use karte hain (Cantor ka trick ki integers se "zyada" reals hain, programs ke liye repurpose kiya gaya).

Step 1 — Assume karo ki decider exist karta hai

Maano ek program H halting solve karta hai. Ise precisely define karo:

$H (P, w) = {HALT LOOP if P halts on w if P runs forever on w$

Yeh step kyun? Hum disprove karna chahte hain ki "H exist karta hai." Sabse clean tarika hai maan lo ki karta hai aur ek contradiction nikalo — isse assumption false ho jaati hai.

Key fact jo hum rely karte hain: ek program sirf ek string hai, toh hum ek program ko uska khud ka code as input de sakte hain. (Yahi "self-reference" ka matlab hai yahan.)

Step 2 — Ek troublemaker program `D` banao (the diagonal)

H ko subroutine ki tarah use karte hue, construct karo:

D(P):                # P ek program ka source code hai
    if H(P, P) == HALT:   # kya P apna khud ka code dene par halt karega?
        loop forever
    else:                 # H kehta hai P khud par loop karta hai
        halt

Yeh step kyun? D ko deliberately ulta karne ke liye engineer kiya gaya hai jo H predict karta hai ek program ke khud par run hone ke baare mein. Yeh deliberate flip hi diagonalization hai: hum baad mein D ko "diagonal" par khud ke khilaf rakhenge.

Step 3 — `D` ko uska khud ka code do: `D(D)` run karo

Poochho: kya D halt karta hai input D par? Do cases, dono fatal hain.

Case A: Maano D(D) halt karta hai. Toh D ke andar jo branch liya gaya woh else (woh "halt" branch) raha hoga. Woh branch tabhi run hoti hai jab H(D, D) == LOOP, yaani H claim karta hai ki D(D) hamesha chalta rahega. Lekin humne maana tha ki halt karta hai. Contradiction.
Case B: Maano D(D) hamesha loop karta hai. Toh if-branch liya gaya tha, jo tabhi hota hai jab H(D, D) == HALT, yaani H claim karta hai ki D(D) halt karta hai. Lekin humne maana tha ki loop karta hai. Contradiction.

$D (D) halts ⟺ H (D, D) = LOOP ⟺ D (D) loops$

Ek statement jo apne khud ke negation ke equivalent ho, impossible hai.

Step 4 — Conclude karo

Har consistent answer contradiction ki taraf le jaata hai, toh humari single assumption — ki H exist karta hai — false honi chahiye.

Figure — Halting problem — undecidability proof by diagonalization

ISKO diagonalization KYUN KEHTE HAIN

Worked examples

Common mistakes (steel-manned)

Flashcards

Halting problem humse kaunsi language decide karwana chahta hai?

H A L T = {⟨ P, w ⟩ ∣ P halts on w}

Kya

H A L T

decidable hai ya undecidable?

Undecidable (koi total algorithm ise decide nahi karta).

Halting ki undecidability establish karne ke liye kaunsi proof technique use hoti hai?

Proof by contradiction using diagonalization (self-reference).

Ek supposed decider H se program D kaise define hota hai?

D(P): agar H(P,P)=HALT toh loop forever, else halt.

D(D) run karne par kaunsa contradiction aata hai?

D (D)

halts

⟺ H (D, D) =

LOOP

⟺ D (D)

loops — ek statement jo apne khud ke negation ke equal hai.

Hum ek program ko uska khud ka code as input kyun de sakte hain?

Kyunki ek program khud sirf ek string/data hai.

"Simulate aur dekho" ek decider kyun nahi hai?

Agar

P

hamesha loop karta hai, toh simulation kabhi halt nahi karta, toh kabhi LOOP output nahi karta; ek decider ko hamesha halt karna chahiye.

Agar decidable nahi hai toh

H A L T

ki kya property hai?

Woh semi-decidable / recognizable hai (halting confirm kar sakta hai, looping confirm nahi kar sakta).

Yahan reduction ka kya use hai?

Undecidability transfer karne ke liye: agar problem A, B par reduce hoti hai aur A undecidable hai, toh B bhi hai.

Program×input table mein D kaunse cell se disagree karta hai?

Diagonal cell

(i, i)

se — ki

P_{i}

khud par halt karta hai ya nahi.

Recall Feynman: 12-saal ke bacche ko explain karo

Ek magic box imagine karo jo, kisi bhi video game ke liye, batata hai "yeh game khatam hoga" ya "yeh game hamesha chalta rahega." Ab main Trickster naam ka ek sneaky game banata hoon. Trickster ek game ki instructions dekh kar magic box se us game ke baare mein poochhhta hai jo khud se khel raha hai. Agar box kehta hai "khatam hoga," Trickster hamesha chalne ka decide karta hai. Agar box kehta hai "hamesha chalta rahega," Trickster khatam ho jaata hai. Ab main Trickster ko khud apne aap par dikhata hoon. Box jo bhi predict karta hai, Trickster ulta karta hai — toh box galat hai. Kyunki main hamesha ek Trickster bana sakta hoon, magic box kabhi exist hi nahi kar sakta tha. Isliye koi program halting sabhi programs ke liye predict nahi kar sakta.

Connections

Turing Machines — woh formal model jisme "program" aur "decide" define hote hain.
Decidable vs Recognizable Languages — $H A L T$ in do classes ko alag karta hai.
Reductions and Mapping Reducibility — undecidability kaise propagate hoti hai (Example 2).
Rice's Theorem — generalize karta hai: programs ki har nontrivial semantic property undecidable hai.
Cantor's Diagonal Argument — is proof ka set-theory ancestor.
Universal Turing Machine — kyun ek program doosra program (aur khud ko) run kar sakta hai.
Church–Turing Thesis — kyun "koi program nahi" ka matlab hai "koi bhi possible algorithm nahi."