Undecidability, mapping reductions और Rice theorem
लक्ष्य और conventions
Contradiction से undecidability सिद्ध करें और reductions की दिशा सही रखें। Machines की effective finite encodings हैं; यहाँ decision problems में malformed encodings reject होते हैं। A_TM पूछता है M, w accept करता है? HALT_TM पूछता है M, w पर accept या reject करके eventually halt करता है? Acceptance और halting अलग हैं। “Undecidable” का अर्थ कोई algorithm हर instance पर सही yes/no देकर halt नहीं कर सकता; हर individual instance अनसुलझा होना जरूरी नहीं।
1. Acceptance का diagonal proof
मानें A_TM का decider H है। D बनाएँ जो valid ⟨M⟩ पर H को ⟨M,⟨M⟩⟩ देता है। H yes कहे तो D reject; H no कहे तो D accept। Invalid encoding पर D तुरंत reject करता है। H halt करता है, इसलिए D भी हर input पर halt करता है। अब D को अपना encoding दें। H यदि कहे D, ⟨D⟩ accept करेगा, D reject करता है; H no कहे तो D accept करता है। दोनों में H की correctness से contradiction है। इसलिए A_TM undecidable है। Self-input वैध है क्योंकि machine descriptions finite strings हैं जिन्हें input दिया जा सकता है।
फिर भी universal simulation से A_TM recognizable है। इसका complement recognizable नहीं: यदि होता तो two-recognizer theorem से A_TM decidable होता। इसलिए undecidability और nonrecognizability अलग हैं।
2. Mapping reduction और दिशा
A≤m B का अर्थ total computable f है जिससे हर x के लिए x∈A iff f(x)∈B। Hypothetical B decider से A हल करने के लिए f(x) निकालें और B decider से पूछें। इसलिए A undecidable और A≤m B होने पर B undecidable है। B को known-hard A में reduce करना B की hardness सिद्ध नहीं करता; easy problems भी hard problems में reduce हो सकते हैं।
f हर x पर halt करे और yes तथा no दोनों cases बचाए। यह अक्सर machine का description output करता है; उस machine के पूरा चलने की प्रतीक्षा नहीं करता। B recognizable और A≤m B हो तो f के बाद B recognizer चलाकर A recognize कर सकते हैं। Contrapositive से nonrecognizability भी सिद्ध हो सकती है।
3. Acceptance से halting का worked reduction
⟨M,w⟩ से N बनाएँ जो अपना input ignore करके M को w पर simulate करता है। M accept करे तो N accept करके halt करे। M reject करे तो N जानबूझकर infinite loop करे; M loop करे तो N simulation forever चलाए। Output ⟨N,ε⟩ है। Finite program description लिखना terminating transformation है; reducer M के accept करने की प्रतीक्षा नहीं करता।
M, w accept करता है iff N, ε पर halt करता है। इसलिए A_TM≤m HALT_TM और HALT_TM undecidable है। Malformed source encoding के लिए fixed nonhalting machine/input pair दें, जिससे no-case बचता है। “N बस M simulate करे” गलत reduction है: M reject करके halt कर सकता है, जो acceptance का no लेकिन halting का yes होगा।
4. Language properties और Rice theorem
Rice theorem: TM द्वारा recognized language की हर nontrivial semantic property undecidable है। Semantic अर्थात same language recognize करने वाली machines property पर सहमत हों; nontrivial अर्थात कोई recognizable language property रखे और कोई दूसरी न रखे। Examples: L(M) empty, finite, regular है या fixed word रखता है। “Description में पाँच states हैं” जैसी syntactic property पर Rice सीधे लागू नहीं। “M हर input पर halt करता है” operational property भी केवल L(M) से तय नहीं होती, इसलिए Rice का direct application नहीं है। Hypotheses के बाहर की problem दूसरे proof से फिर भी undecidable हो सकती है।
Worked nonemptiness reduction: ⟨M,w⟩ से N बनाएँ जो किसी input x पर M(w) simulate करता है; simulation accept करे तो x accept, वरना कभी accept नहीं। M, w accept करे तो L(N)=Σ*, अन्यथा L(N)=∅। Malformed source encoding पर fixed reject-all machine output करें, ताकि हर invalid source NONEMPTY_TM के no-instance में जाए। इससे transformation सभी strings पर total है और A_TM≤m NONEMPTY_TM मिलता है। NONEMPTY_TM recognizable है: M को सभी strings पर dovetail करें और कोई simulation accept होते ही accept करें। EMPTY_TM undecidable तथा nonrecognizable है: वह और उसका recognizable complement दोनों recognizable होते तो emptiness decidable होती। ये complements valid machine encodings के universe में हैं; malformed encodings को terminating syntax check से अलग handle करने पर results नहीं बदलते।
5. सही proof tool चुनें
DFA membership, emptiness, equivalence के finite graph algorithms terminate करते हैं। CFG membership और emptiness के finite grammar algorithms terminate करते हैं; general equivalence तथा ambiguity undecidable हैं। Arbitrary TM descriptions की language semantics पर अधिक मजबूत impossibility results लगते हैं। Representation तथा question दोनों पहचानें। Language ∅ decidable है, लेकिन उन TM descriptions का set जिनकी recognized language ∅ है undecidable है: encoding के अलग levels पर ये दो अलग languages हैं।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें।
P01. Known-undecidable A से B undecidable सिद्ध करने की सही दिशा क्या है?
A. केवल B≤m A B. A≤m B C. कोई दिशा मदद नहीं करती D. केवल alphabet sizes की equality
उत्तर: B
A: यह B को hardness नहीं देता।
B: B-decider से असंभव A-decider मिल जाएगा।
C: Mapping reductions यहाँ standard tool हैं।
D: Alphabet size hardness नहीं देता।
P02. Mapping reduction function कैसा होना चाहिए?
A. No-instances पर loop कर सके B. Total computable और yes/no बचाने वाला C. Source language का oracle D. हर reduction में injective
उत्तर: B
A: हर input पर output चाहिए।
B: यही defining requirements हैं।
C: Transformation स्वयं computable होना चाहिए।
D: Injectivity जरूरी नहीं।
P03. A_TM से HALT_TM reduction में M, w reject करे तो N क्या करे?
A. Reject करके halt B. Accept करके halt C. Forever loop D. M का reject तुरंत return
उत्तर: C
A: यह गलत halting yes-instance बनाता है।
B: यह भी halting yes-instance बनाता है।
C: Source no को nonhalting में भेजना है।
D: Return करना halting है, reduction टूटेगा।
P04. Rice में कौन-सी nontrivial semantic language property आती है?
A. Encoding की length even है B. Machine में ठीक पाँच states हैं C. L(M) finite है D. Machine ε पर ठीक सात steps चलती है
उत्तर: C
A: Encoding length syntactic है।
B: State count syntactic है।
C: Finiteness केवल recognized language पर निर्भर तथा nontrivial है।
D: Steps operational हैं, L(M) से तय नहीं।
P05. complement(A_TM) recognizable क्यों नहीं है?
A. A_TM recognizable नहीं B. दोनों recognizers से A_TM decider मिल जाएगा C. सभी complements unrecognizable हैं D. उसकी strings infinite हैं
उत्तर: B
A: Simulation से A_TM recognizable है।
B: Dovetailing से A_TM undecidability का contradiction होगा।
C: Decidable languages के complements decidable हैं।
D: Machine/input encodings finite strings हैं।
P06. कौन-सी तुलना सही है?
A. EMPTY_TM undecidable है इसलिए ∅ भी B. ∅ decidable, लेकिन EMPTY_TM undecidable है C. दोनों questions समान हैं D. EMPTY_TM पूछता है input string खाली है या नहीं
उत्तर: B
A: ∅ का decider हर input reject कर सकता है।
B: एक ∅ के words, दूसरा machine descriptions की property है।
C: दोनों अलग encoding levels पर हैं।
D: यह encoded machine की language खाली होने के बारे में है।
स्रोत और दायरा
यह 2026 course के बताए भाग का पाठ है, पूरे Theory of Computation syllabus की समाप्ति नहीं। सभी गणनात्मक उदाहरण और प्रश्न मौलिक हैं। 2027 की पूर्णता का दावा नहीं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन