Rice's theorem — Hinglish notes

4.6.20 · Coding › Theory of Computation

YEH theorem exist hi kyun karti hai?

"Behavior" vs "structure" kya hota hai?

Behavioral (semantic) property = language $L (M)$ ki property — woh set of strings jo machine accept karti hai. Example: "kya $M$ empty string accept karta hai?", "kya $L (M)$ infinite hai?", "kya $L (M) = \emptyset$ hai?".
Structural (syntactic) property = machine description ki property, na ki woh kya compute karta hai. Example: "kya $M$ ke 7 states hain?", "kya $M$ kabhi blank likhta hai?". Yeh aksar decidable hote hain aur Rice inke baare mein kuch nahi kehta.

Statement

Do excluded trivial cases (jo decidable hain):

$P = \emptyset$ (koi language ke paas yeh nahi) → hamesha "no" answer do.
$P = all r.e. languages$ → hamesha "yes" answer do.

DERIVATION first principles se (Halting / $A_{T M}$ se reduction)

Setup. Maano $P$ non-trivial hai. Hum undecidable language $A_{T M} = {⟨ M, w ⟩ : M accepts w}$ use karte hain.

Step 1 — Baseline chuno. WLOG maano $\emptyset \in / P$ (empty language ke paas yeh property nahi hai). Yeh step kyun? Agar $\emptyset \in P$ ho, toh sirf complement property $\overset{ˉ}{P}$ ke liye undecidability prove karo; $P$ decide karna $\overset{ˉ}{P}$ decide karna hoga, toh yeh symmetric hai. Isliye kuch nahi jaata.

Step 2 — Witness pakdo. Kyunki $P$ non-trivial hai aur $\emptyset \in / P$ , koi language $L (M_{P}) \in P$ exist karti hai jise machine $M_{P}$ recognize karti hai. Yeh step kyun? Non-triviality guarantee karti hai kam se kam ek "yes" example. Humein ek target language chahiye jo property rakhti ho taaki hum us mein switch kar sakein.

Step 3 — Gadget. Input $⟨ M, w ⟩$ diya hua, ek nayi machine $G_{M, w}$ banao jo input $x$ par yeh kare:

$x$ ko abhi ignore karo. Pehle $M$ ko $w$ par run karo (simulate).
Agar $M$ ne $w$ accept kiya, toh $M_{P}$ ko $x$ par run karo aur accept karo agar $M_{P}$ accept kare $x$ ko.

Yeh step kyun? Yahi toh dil hai. Dono worlds trace karo:

Agar $M$ ne $w$ accept kiya: step 1 finish hoga, toh $G_{M, w}$ exactly $M_{P}$ ki tarah behave karega, isliye $L (G_{M, w}) = L (M_{P}) \in P$ .
Agar $M$ ne $w$ accept nahi kiya: step 1 kabhi finish nahi hoga, $G_{M, w}$ kabhi step 2 tak nahi pahunchega, kuch accept nahi karega, toh $L (G_{M, w}) = \emptyset \in / P$ .

Toh: $L (G_{M, w}) \in P ⟺ M accepts w .$

Step 4 — Contradiction. Maano $L_{P}$ ke liye ek decider $R$ exist karta hai. Use $⟨ G_{M, w} ⟩$ feed karo: $R$ "yes" bolta hai $⟺ L (G_{M, w}) \in P ⟺ M$ ne $w$ accept kiya. Yeh $A_{T M}$ decide karta hai — impossible. Isliye $L_{P}$ undecidable hai. $■$

Worked Examples

Common Mistakes (Steel-manned)

Recall Feynman: 12-saal ke bachche ko samjhao

Socho tumhare paas ek magic box hai jo doosre chhote robot-programs chalata hai. Tum ek checker-machine chahte ho jo ek robot ki instruction sheet padhe aur bataye "yeh robot eventually cat word bolega." Rice's theorem kehti hai: aisi koi perfect checker machine exist nahi kar sakti kisi bhi interesting "woh eventually kya karega" sawaal ke liye. Sirf boring sawaalon ke jawab hamesha diye ja sakte hain jahan jawab har robot ke liye same ho ("haan, hamesha" ya "nahi, kabhi nahi"). Wajah yeh hai: robot check karne ke liye, tumhare checker ko secretly pata hona chahiye ki robot kab bhi rukta hai — aur hum pehle hi prove kar chuke hain ki yeh general mein koi nahi jaanta.

Connections

Halting Problem — beej; Rice ise generalize karta hai.
A_TM and undecidability — woh language jisse hum reduce karte hain.
Mapping reductions — proof technique (gadget machine banao).
Recursive vs Recursively Enumerable languages — undecidable ≠ non-r.e.
Rice-Shapiro theorem — Rice ko refine karta hai recognizability decide karne ke liye.
Turing Machines — underlying model.

Flashcards

Rice's theorem kya kehta hai?

Har non-trivial semantic property of the language r.e. by a TM undecidable hoti hai.

"Semantic"/behavioral property kya hoti hai?

L (M)

ki property (machine kya accept karti hai), machine ki encoding se independent.

"Non-trivial" property kya hoti hai?

Woh jo kam se kam ek r.e. language ke liye true ho aur kam se kam ek r.e. language ke liye false ho.

Rice ke dwara EXCLUDE hone wale do property types kaun se hain?

Trivial properties (always-true ya always-false) aur syntactic properties (machine description ke baare mein).

Proof mein non-triviality kyun zaroori hai?

Reduction ko ek YES-witness language aur ek NO-witness (

\emptyset

) chahiye flip karne ke liye; trivial properties flip nahi kar sakti.

Proof mein kaunsi language se reduce kiya jaata hai?

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

(equivalently the Halting Problem).

Gadget

G_{M, w}

mein,

L (G_{M, w})

kya hota hai jab

M

w

par reject/loop kiya?

\emptyset

(woh

M

w

par simulation kabhi finish nahi karta, toh kuch accept nahi karta).

Gadget mein,

L (G_{M, w})

kya hota hai jab

M

w

accept kiya?

L (M_{P})

, woh witness language jiske paas property

P

hai.

Kya "kya

M

ke 5 states hain?" Rice se covered hai?

Nahi — yeh description ki syntactic property hai; yeh decidable hai.

Kya Rice kehta hai ki

L_{P}

non-r.e. hai?

Nahi, sirf itna ki woh undecidable hai (not recursive). Woh phir bhi r.e. ho sakta hai.

Kya "

L (M)

regular hai?" decidable hai?

Nahi — non-trivial semantic property → Rice se undecidable.

Kya "

L (M) = \emptyset

?" decidable hai?

Nahi — non-trivial (

\emptyset

ke paas hai,

Σ^{*}

ke paas nahi) → undecidable.