Turing machines, decidability और recognizability
लक्ष्य और machine convention
Language decide और recognize करने का अंतर समझें तथा TM variants की समान computational power पहचानें। हमारी deterministic TM में finite control, दोनों दिशाओं में unbounded tape, एक cell पढ़ने वाला head तथा finite tape alphabet Γ है। Γ में input alphabet Σ और Σ से बाहर blank है। Input consecutive cells में, बाकी tape blank है। Transition symbol पढ़ता, लिखता, state बदलता और एक cell left या right जाता है। Accept तथा reject अलग halting states हैं। Stay-put moves या one-way-infinite tape simulate किए जा सकते हैं; recognized/decidable languages नहीं बदलतीं।
Computation accept, reject या forever run कर सकती है। L(M) में केवल eventually accepted inputs हैं। Recognizer हर member को accept करता है; nonmember पर reject या loop कर सकता है। Decider हर input पर halt करता है और ठीक members accept करता है। “Recursive” अर्थात decidable; “recursively enumerable” (RE), “Turing-recognizable”, “semidecidable” यहाँ recognizer class हैं।
1. a^n b^n c^n का decider
पहले input abc* में है या नहीं जाँचें; नहीं तो reject। बार-बार leftmost unmarked a को X करें, फिर दाएँ जाकर leftmost unmarked b को Y और leftmost unmarked c को Z करें। जरूरी b या c न मिले तो reject। बाएँ लौटकर दोहराएँ। Unmarked a खत्म हो जाएँ तो तभी accept करें जब unmarked b,c भी न बचें। ε accept करें।
aabbcc की पहली round XaYbZc और दूसरी XXYYZZ देती है; final scan accept करता है। aabcc में दूसरी round fresh b नहीं ढूँढ पाती, इसलिए reject। शुरुआती ordering check equal counts लेकिन interleaved symbols वाले words को रोकता है।
Termination proof: हर successful round एक नया a mark करती है और a finitely many हैं। हर scan finite input region में है, जिसकी boundary blanks से पता चलती है। Failed round तुरंत halt करती है। इसलिए हर input पर machine halt करती है। Non-context-free language भी decidable हो सकती है; restricted automaton memory और computability limits अलग बातें हैं।
2. Simulation से recognition
A_TM={⟨M,w⟩:TM M, w accept करती है} लें; machines तथा inputs की effective finite encoding है। Universal simulator M को w पर चलाकर accept होने पर accept करता है। M reject करे तो simulator reject कर सकता है; M loop करे तो loop करता है। इसलिए recognition decider नहीं देता। Invalid encodings finite syntax check से reject कर सकते हैं। कोई fixed timeout सभी machines पर rejection सिद्ध नहीं करता, क्योंकि acceptance बहुत देर बाद भी हो सकती है।
Enumerator strings print करता है, repeats हो सकते हैं और halt जरूरी नहीं। Printed set recognizable है। Membership पहचानने के लिए desired string print होने तक चलाएँ; nonmember forever wait कर सकता है। उलटे, recognizer को सभी strings पर dovetailed stages में simulate करें और accepted strings print करें। Simulations को एक-एक करके completion तक न चलाएँ; पहली हमेशा loop कर सकती है। जो कभी word print न करे वह empty language enumerate करता है।
3. दो recognizers से decidability
L decidable iff L तथा उसका complement दोनों recognizable हैं। Forward: decider L recognize करता है; halting answers उलटने से complement recognize होता है। Reverse: दोनों recognizers को w पर alternating steps में चलाएँ। w ठीक एक set में है, इसलिए ठीक एक machine eventually accept करेगी। L वाली accept करे तो accept; complement वाली accept करे तो reject। दूसरी simulation forever चले तब भी combined procedure halt करता है।
Arbitrary recognizer के accept/reject states उलटना सामान्यतः complement recognize नहीं करता: जिस nonmember पर वह loop करता था, वहाँ अब भी loop करेगा। Decider की हर input पर halting condition ही complement trick सही बनाती है।
4. Variants और classes
Multitape TM को single tape पर tape contents तथा head markers encode करके simulate कर सकते हैं; efficiency बदल सकती है, computability नहीं। Nondeterministic TM में कोई finite branch accept करे तो input accept है। Deterministic simulator finitely branching computation tree को breadth-first खोजता है; इसलिए infinite branch finite accepting branch को छिपा नहीं सकती। दोनों variants की recognized languages समान हैं। यह computability का दावा है, समान running time का नहीं।
a,b,c रखने वाला fixed finite alphabet लें और उसी पर effective machine/input encodings लें। तब regular ⊊ context-free ⊊ decidable ⊊ recognizable ⊊ उस alphabet की सभी languages। Alphabet की शर्त जरूरी है: unary alphabet पर हर context-free language regular होती है। पहले दो strict inclusions के examples a^n b^n तथा a^n b^n c^n हैं। A_TM decidable और recognizable को अलग करता है; Lesson 9 इसका undecidability proof देगा। Two-recognizer theorem से उसका complement recognizable नहीं। “DFA से recognize नहीं” और “TM से recognizable नहीं” को न मिलाएँ।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें।
P01. Recognizer nonmember पर क्या कर सकता है?
A. Accept B. Reject या loop C. Timeout बाद हमेशा accept D. केवल accept में halt
उत्तर: B
A: Acceptance गलत membership देगा।
B: Nonmember पर दोनों behaviors allowed हैं।
C: Timeout nonmember को member नहीं बनाता।
D: ऐसे halt करने पर सभी inputs members बनेंगे।
P02. Decider और arbitrary recognizer में मुख्य अंतर क्या है?
A. Finite control B. हर input पर halt होना C. Tape alphabet D. Members का acceptance
उत्तर: B
A: दोनों finite control लेते हैं।
B: Decider total termination देता है।
C: दोनों में tape alphabet है।
D: दोनों members accept करते हैं।
P03. L और उसका complement दोनों recognizable हों तो L क्या है?
A. जरूर finite B. Decidable C. जरूर regular D. Recognizable नहीं
उत्तर: B
A: a* जैसे infinite examples हैं।
B: दोनों recognizers dovetail करके एक acceptance की प्रतीक्षा करें।
C: Decidable languages nonregular हो सकती हैं।
D: Recognizable होना दिया है।
P04. Nondeterministic TM branches पर breadth-first क्यों?
A. Tape finite बनाने के लिए B. एक infinite branch में हमेशा अटकने से बचने के लिए C. हर branch accept कराने के लिए D. Input alphabet हटाने के लिए
उत्तर: B
A: Tape unbounded है।
B: हर finite accepting branch अंततः खोजी जाती है।
C: Existential acceptance में एक branch पर्याप्त है।
D: Alphabet नहीं बदलता।
P05. Marking decider aabcc क्यों reject करता है?
A. Symbols block order में नहीं B. दूसरे a को fresh b नहीं मिलता C. इसमें दो c हैं D. हर length-five string non-context-free है
उत्तर: B
A: aabcc, abc* में है।
B: दो a के लिए केवल एक b है।
C: दो c अपने आप rejection कारण नहीं।
D: Context-freeness languages की property है, individual lengths की नहीं।
P06. Single-tape और multitape की equivalent computability का अर्थ?
A. हर input पर समान running time B. समान decidable तथा recognizable language classes C. हर language regular बनती है D. सभी computations halt होती हैं
उत्तर: B
A: Simulation समय बढ़ा सकती है।
B: Tape organization efficiency बदलती है, classes नहीं।
C: Finite automata काफी कमजोर हैं।
D: Simulated machines loop कर सकती हैं।
स्रोत और दायरा
यह 2026 course के बताए भाग का पाठ है, पूरे Theory of Computation syllabus की समाप्ति नहीं। सभी गणनात्मक उदाहरण और प्रश्न मौलिक हैं। 2027 की पूर्णता का दावा नहीं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन