ट्यूरिंग मशीन, निर्णेयता व अनिर्णेयता

ट्यूरिंग मशीन वह परिमित स्वचालित्र है जिसके पास ऐसा टेप है जिस पर वह दोनों दिशाओं में चल सकती व लिख सकती है, और वह किसी भी अभिकलनीय चीज़ के अभिकलन हेतु पर्याप्त है — चर्च–ट्यूरिंग परिकल्पना यह दावा है कि कोई युक्तियुक्त मॉडल इससे अच्छा नहीं करता, और नब्बे वर्षों में किसी बात ने उसका खंडन नहीं किया। यह पेपर का सर्वाधिक वैचारिक भाग इसलिए है कि रोचक परिणाम सभी नकारात्मक हैं, और उनके लिए शब्दावली यथार्थ होनी चाहिए। कोई भाषा निर्णेय है यदि कोई मशीन सदा रुककर सही उत्तर दे। वह पहचानीय (या पुनरावर्ती गणनीय) है यदि कोई मशीन भाषा की प्रत्येक माला स्वीकार करे पर उसके बाहर की मालाओं पर अनंत काल चलने की छूट रखे। वे भिन्न हैं, और उनके बीच का अंतराल वहीं है जहाँ अनिर्णेयता रहती है: रुकने की समस्या पहचानीय है और निर्णेय नहीं, जिसका अर्थ है कि आप प्रतीक्षा करके रुकने की पुष्टि कर सकते हैं पर न-रुकने की पुष्टि कभी नहीं। अनिर्णेय भाषाओं का अस्तित्व देखने के दो मार्ग हैं, और गणना-तर्क आरंभ करने हेतु अधिक ईमानदार है: ट्यूरिंग मशीनें गणनीय अनेक हैं और भाषाएँ अगणनीय अनेक, अतः लगभग प्रत्येक भाषा के पास कोई मशीन ही नहीं — अनिर्णेयता सामान्य स्थिति है और निर्णेयता विरल। वहाँ से राइस प्रमेय वह उपकरण है जो अधिकांश परीक्षा-प्रश्न तत्काल बना देता है: मशीन जो भाषा पहचानती है उसका कोई भी अतुच्छ गुण अनिर्णेय है। कठिन वाले नहीं — उनमें कोई भी। और अंतिम बात जो ठीक-ठीक रखने योग्य है वह निर्णेयता-सारणी है, क्योंकि वह समरूप नहीं: तुल्यता DFA हेतु निर्णेय व संदर्भ-मुक्त व्याकरणों हेतु अनिर्णेय है, चाहे रिक्तता व सदस्यता दोनों हेतु निर्णेय हों।

निर्णेय, पहचानीय, तथा उनके बीच का अंतराल

तीन स्तर, तथा प्रत्येक पर मशीन क्या वचन देती है
वर्गवचनएक सदस्य
निर्णेयप्रत्येक निवेश पर सही उत्तर सहित रुकती है{aⁿbⁿcⁿ} — टेप हेतु सरल
पहचानीय (RE)प्रत्येक सदस्य स्वीकारती; अ-सदस्य पर अनंत काल चल सकती हैरुकने की समस्या
अपहचानीयकोई मशीन ठीक यही समुच्चय स्वीकार नहीं करतीरुकने की समस्या का पूरक
🎯 किसी विकर्णीकरण से पूर्व ही अनिर्णेय भाषाएँ क्यों विद्यमान होनी चाहिए
ट्यूरिंग मशीन परिमित वस्तु है — परिमित अवस्था-समुच्चय, परिमित वर्णमाला, परिमित संक्रमण-सारणी — अतः प्रत्येक को परिमित माला के रूप में लिखा जा सकता है, और सभी ट्यूरिंग मशीनों का समुच्चय गणनीय है। भाषा Σ* का कोई भी उपसमुच्चय है, और गणनीय अनंत समुच्चय के सभी उपसमुच्चयों का समुच्चय कैंटर से अगणनीय है। अतः मशीनों से कठोरतः अधिक भाषाएँ हैं, और असंगति सीमांत नहीं: लगभग प्रत्येक भाषा के पास कोई मशीन ही नहीं। अतः अनिर्णेयता सामान्य दशा है और निर्णेयता अपवाद, जो उस पाठ्यक्रम से मिलती छाप के विपरीत है जो सदा केवल मशीनें दिखाता है। किसी विशिष्ट अनिर्णेय भाषा का नाम लेने हेतु — रुकने की समस्या — विकर्णीकरण तब भी चाहिए, पर अस्तित्व का प्रश्न केवल गणना से तय हो जाता है।
🧠 कोई भाषा व उसका पूरक दोनों पहचानीय ठीक तब हैं जब वह निर्णेय हो
यह इस विषय की सर्वाधिक उपयोगी एकल प्रमेय है, क्योंकि वह निर्णेयता के प्रश्नों को पहचानीयता के प्रश्नों में बदल देती है। यदि L व उसके पूरक दोनों के पहचानकर्ता हों, तो दोनों को उसी निवेश पर समांतर चलाएँ: उनमें एक को अंततः स्वीकार करना ही होगा, क्योंकि निवेश एक या दूसरे समुच्चय में है, अतः संयोजन सदा रुकता है — L निर्णेय है। विलोमतः निर्णायक दोनों हेतु पहचानकर्ता तुच्छ रूप से देता है। तत्काल परिणाम वह मानक परीक्षा-तथ्य है: रुकने की समस्या पहचानीय है पर निर्णेय नहीं, अतः उसका पूरक पहचानीय भी नहीं है। कोई भाषा व उसका पूरक देकर यह पूछना कि वे किन वर्गों में आती हैं एक प्रश्न है, और यह प्रमेय उसका उत्तर देती है।

राइस प्रमेय, वह लघु-मार्ग जो अधिकांश प्रश्नों का उत्तर देता है

राइस प्रमेय: ट्यूरिंग मशीन जो भाषा पहचानती है उसका प्रत्येक अतुच्छ गुण अनिर्णेय है। अतुच्छ का अर्थ केवल यह है कि किसी मशीन के पास वह गुण है और किसी के पास नहीं। अतः ये सभी अनिर्णेय हैं, और उनमें किसी को पृथक् न्यूनीकरण नहीं चाहिए: L(M) रिक्त है क्या, L(M) परिमित है क्या, L(M) नियमित है क्या, L(M) में माला 01 है क्या, L(M) = Σ* है क्या, दो मशीनें वही भाषा पहचानती हैं क्या।

⚠️ राइस भाषा पर लागू है, मशीन पर नहीं
प्रमेय L(M) के गुणों के विषय में है — स्वीकृत मालाओं का समुच्चय — और वाक्य-रचना के टुकड़े के रूप में मशीन के गुणों के विषय में कुछ नहीं कहती। "M में सात से अधिक अवस्थाएँ हैं क्या?" मशीन का गुण है और पूर्णतः निर्णेय है: उन्हें गिन लें। "M कभी रिक्त लिखती है क्या?" भी संक्रमण-सारणी के विषय में वाक्य-रचनात्मक प्रश्न है। परंतु "L(M) रिक्त है क्या?" भाषा का गुण है और अनिर्णेय है। लगाने योग्य कसौटी यह है कि वही भाषा पहचानती दो मशीनों को सदा वही उत्तर मिलना ही चाहिए या नहीं: यदि हाँ, तो वह भाषा-गुण है और राइस काटती है; यदि ऐसी दो मशीनें भिन्न हो सकें, तो गुण मशीन के विषय में है और राइस मौन है। वही एक कसौटी प्रश्नों के सम्पूर्ण वर्ग को सुलझा देती है, और अभ्यर्थी उसी को छोड़ते हैं।

निर्णेयता-सारणी, जो समरूप नहीं है

वही प्रश्न तीन प्रकार के वर्णनों से पूछा गया
प्रश्नDFACFGट्यूरिंग मशीन
w भाषा में है क्या? (सदस्यता)निर्णेयनिर्णेय (CYK)अनिर्णेय, पर पहचानीय
भाषा रिक्त है क्या?निर्णेयनिर्णेयअनिर्णेय
दो वर्णन वही भाषा देते हैं क्या?निर्णेयअनिर्णेयअनिर्णेय
भाषा अनंत है क्या?निर्णेयनिर्णेयअनिर्णेय
⚠️ वह एक कोष्ठ जो प्रतिरूप तोड़ता है
CFG स्तंभ नीचे पढ़ें और वह आश्वस्त करता लगता है — सदस्यता, रिक्तता व अनंतता सब निर्णेय — और तब तुल्यता नहीं है। वही एक कोष्ठ इस तालिका का सर्वाधिक पूछा तथ्य है, ठीक इसलिए कि स्तंभ का शेष भाग "संदर्भ-मुक्त चीज़ें निर्णेय हैं" वाले सामान्यीकरण को आमंत्रित करता है। तुल्यता के गिरने का कारण यह है कि उसका निर्णय आपको व्याकरणों के विषय में कहीं कठिन प्रश्नों का निर्णय करने देता; DFA हेतु उसके टिकने का कारण मिहिल–नेरोड है, जो प्रत्येक नियमित भाषा को अद्वितीय न्यूनतम DFA देती है, अतः तुल्यता न्यूनीकृत-करो-और-तुलना-करो पर सिमट जाती है। संदर्भ-मुक्त व्याकरण का कोई प्रामाणिक रूप नहीं है, और वही अनुपस्थिति सम्पूर्ण अंतर है। संबंधित और CFG हेतु अनिर्णेय भी: कोई व्याकरण अस्पष्ट है क्या, तथा दो CFL का सर्वनिष्ठ रिक्त है क्या।

मुख्य बिंदु

  • निर्णेय का अर्थ प्रत्येक निवेश पर रुकना; पहचानीय अ-सदस्यों पर अनंत काल चलने की छूट देता है।
  • ट्यूरिंग मशीनें गणनीय व भाषाएँ अगणनीय हैं, अतः लगभग प्रत्येक भाषा के पास कोई मशीन नहीं।
  • L ठीक तब निर्णेय है जब L व उसका पूरक दोनों पहचानीय हों — दोनों समांतर चलाएँ।
  • रुकने की समस्या पहचानीय व अनिर्णेय है, अतः उसका पूरक पहचानीय भी नहीं है।
  • राइस: L(M) का प्रत्येक अतुच्छ गुण अनिर्णेय है — रिक्त, परिमित, नियमित, 01 रखता, सभी।
  • राइस मशीन के गुणों पर लागू नहीं: "सात से अधिक अवस्थाएँ" गिनकर निर्णेय है।
  • कसौटी: यदि समान भाषा वाली दो मशीनों को वही उत्तर मिलना ही चाहिए, तो वह भाषा-गुण है।
  • तुल्यता DFA हेतु निर्णेय व CFG हेतु अनिर्णेय है — व्याकरण का कोई प्रामाणिक रूप नहीं।

अभ्यास प्रश्न (8)

उत्तर खोलने से पहले प्रत्येक प्रश्न हल करें। हर व्याख्या सही विकल्प के साथ लुभावना गलत विकल्प भी बताती है, क्योंकि अंक वहीं जाते हैं।

  1. इनमें कौन-सी समस्या निर्णेय है?

    1. दो संदर्भ-मुक्त व्याकरण दिए हों, तो क्या वे वही भाषा उत्पन्न करते हैं?
    2. दो DFA दिए हों, तो क्या वे वही भाषा स्वीकारते हैं?
    3. ट्यूरिंग मशीन दी हो, तो क्या उसकी भाषा रिक्त है?
    4. संदर्भ-मुक्त व्याकरण दिया हो, तो क्या वह अस्पष्ट है?
    उत्तर देखें

    उत्तर: B — दो DFA दिए हों, तो क्या वे वही भाषा स्वीकारते हैं?

    DFA तुल्यता निर्णेय है, और कारण मिहिल–नेरोड है: प्रत्येक नियमित भाषा का अद्वितीय न्यूनतम DFA है, अतः दोनों मशीनें न्यूनीकृत करें व जाँचें कि वे पुनर्नामकरण तक समान हैं या नहीं। विकल्प A सारणी का वही कोष्ठ है जो प्रतिरूप तोड़ता है — CFG हेतु सदस्यता, रिक्तता व अनंतता सब निर्णेय हैं, और तुल्यता नहीं, क्योंकि संदर्भ-मुक्त व्याकरण का तुलना योग्य कोई प्रामाणिक रूप नहीं। विकल्प C राइस से अनिर्णेय है, L(M) का अतुच्छ गुण होने से। विकल्प D, व्याकरण-अस्पष्टता, भी अनिर्णेय है। अतः चार में तीन अनिर्णेय हैं, और जो नहीं है वही है जिसके पीछे प्रामाणिक रूप है।

  2. राइस प्रमेय से, ट्यूरिंग मशीन M के विषय में निम्नलिखित में कौन निर्णेय है?

    1. L(M) रिक्त है या नहीं
    2. L(M) नियमित है या नहीं
    3. M में सात से अधिक अवस्थाएँ हैं या नहीं
    4. L(M) में माला 01 है या नहीं
    उत्तर देखें

    उत्तर: C — M में सात से अधिक अवस्थाएँ हैं या नहीं

    राइस L(M) के गुणों पर लागू है, पहचानी गई भाषा, और A, B व D सब उसके अतुच्छ गुण हैं — अतः तीनों अनिर्णेय हैं। विकल्प C मशीन का वाक्य-रचनात्मक वस्तु के रूप में गुण है: संक्रमण-सारणी पढ़ें व गिनें। प्रश्नों के इस पूरे कुल को तय करती कसौटी यह है कि वही भाषा पहचानती दो मशीनों को सदा वही उत्तर मिलना ही चाहिए या नहीं। "L(M) रिक्त है क्या" हेतु मिलना ही चाहिए, अतः वह भाषा-गुण है और राइस काटती है। "सात से अधिक अवस्थाएँ" हेतु आवश्यक नहीं — उसी भाषा की अनेक आकारों की मशीनें हैं — अतः वह भाषा-गुण नहीं और राइस उसके विषय में कुछ नहीं कहती।

  3. कोई भाषा L पहचानीय है और उसका पूरक भी पहचानीय है। इससे निकलता है कि L है:

    1. निर्णेय
    2. अनिर्णेय
    3. नियमित
    4. संदर्भ-मुक्त
    उत्तर देखें

    उत्तर: A — निर्णेय

    निर्णेय। दोनों पहचानकर्ताओं को निवेश पर समांतर चलाएँ, चरण बदलते हुए। निवेश L में या उसके पूरक में है, अतः दोनों में ठीक एक को अंततः स्वीकार करना ही होगा — और अतः संयोजन सदा सही उत्तर सहित रुकता है। वही निर्णायक की परिभाषा है। प्रमेय इस विषय की सर्वाधिक उपयोगी है अपने प्रतिलोम-कथन के कारण, जो मानक परीक्षा-तथ्य है: रुकने की समस्या पहचानीय है और निर्णेय नहीं है, अतः उसका पूरक पहचानीय ही नहीं हो सकता। विकल्प C व D बहुत अधिक दावा करते हैं — निर्णेयता नियमित या संदर्भ-मुक्त होने के विषय में कुछ नहीं कहती, और {aⁿbⁿcⁿ} निर्णेय है जबकि दोनों में से कोई नहीं।

  4. अनिर्णेय भाषाओं के विद्यमान होने का सबसे प्रबल कारण यह है कि:

    1. रुकने की समस्या अनिर्णेय सिद्ध हो चुकी है
    2. ट्यूरिंग मशीनें गणनीय अनेक हैं और भाषाएँ अगणनीय अनेक
    3. कुछ प्रोग्राम अत्यंत लंबे हैं
    4. ट्यूरिंग मशीनों की स्मृति परिमित है
    उत्तर देखें

    उत्तर: B — ट्यूरिंग मशीनें गणनीय अनेक हैं और भाषाएँ अगणनीय अनेक

    प्रत्येक ट्यूरिंग मशीन परिमित वस्तु है और परिमित माला के रूप में लिखी जा सकती है, अतः मशीनें गणनीय हैं। भाषाएँ Σ* के मनमाने उपसमुच्चय हैं, और गणनीय अनंत समुच्चय का घात-समुच्चय कैंटर के तर्क से अगणनीय है। अतः मशीनों से कठोरतः अधिक भाषाएँ हैं, और अनिर्णेयता गणना से निकलती है — कोई रचना आवश्यक नहीं। विकल्प A सत्य है और इस प्रश्न का दुर्बल उत्तर है: वह एक अनिर्णेय भाषा का नाम लेता है, जबकि गणना-तर्क दिखाता है कि लगभग सभी भाषाएँ अनिर्णेय हैं, जो प्रबल व अधिक चकित करने वाला कथन है। विकल्प D असत्य है: ट्यूरिंग मशीन के पास परिमित नियंत्रण व अपरिबद्ध टेप है, और वही अपरिबद्धता उसे परिमित स्वचालित्र से पृथक् करती है।

  5. संदर्भ-मुक्त व्याकरणों हेतु निम्नलिखित में कौन अनिर्णेय हैं? (एक से अधिक सही हो सकते हैं।)

    1. दो व्याकरण वही भाषा उत्पन्न करते हैं या नहीं
    2. कोई व्याकरण अस्पष्ट है या नहीं
    3. उत्पन्न भाषा रिक्त है या नहीं
    4. दो संदर्भ-मुक्त भाषाओं का सर्वनिष्ठ रिक्त है या नहीं
    उत्तर देखें

    उत्तर: A — दो व्याकरण वही भाषा उत्पन्न करते हैं या नहीं; B — कोई व्याकरण अस्पष्ट है या नहीं; D — दो संदर्भ-मुक्त भाषाओं का सर्वनिष्ठ रिक्त है या नहीं

    A, B व D। तुल्यता अनिर्णेय है क्योंकि संदर्भ-मुक्त व्याकरण का तुलना योग्य कोई प्रामाणिक रूप नहीं — DFA से विरोध, जहाँ मिहिल–नेरोड अद्वितीय न्यूनतम मशीन देती है, दोनों के भिन्न होने का सम्पूर्ण कारण वही है। अस्पष्टता अनिर्णेय है, और सर्वनिष्ठ की रिक्तता भी, जो यह स्मरण करने पर आश्चर्यजनक नहीं कि सर्वनिष्ठ संदर्भ-मुक्त भी होना आवश्यक नहीं। C निर्णेय है: उन अ-टर्मिनलों को चिह्नित करें जो टर्मिनल माला व्युत्पन्न कर सकें, ऊपर की ओर प्रसारित करें, और जाँचें कि आरंभ प्रतीक चिह्नित होता है या नहीं। अतः निर्णेयता-सारणी का CFG स्तंभ अधिकांशतः निर्णेय है, तुल्यता अपवाद सहित, और वही अपवाद इस प्रश्न का प्रयोजन है।

  6. रुकने की समस्या का पूरक है:

    1. निर्णेय
    2. पहचानीय पर निर्णेय नहीं
    3. पहचानीय भी नहीं
    4. नियमित
    उत्तर देखें

    उत्तर: C — पहचानीय भी नहीं

    पहचानीय भी नहीं। रुकने की समस्या स्वयं पहचानीय है — मशीन का अनुकरण करें और रुकने पर स्वीकार करें — और वह निर्णेय नहीं है। अब प्रमेय लगाएँ: कोई भाषा ठीक तब निर्णेय है जब वह व उसका पूरक दोनों पहचानीय हों। यदि पूरक पहचानीय होता, तो रुकना निर्णेय होता, जो वह नहीं है। अतः पूरक का कोई पहचानकर्ता ही नहीं। विकल्प B, पूरक के बजाय स्वयं रुकने की समस्या का उत्तर है, और वही स्वाभाविक चूक है। यह युग्म वह मानक उदाहरण है कि पहचानीय भाषाएँ, निर्णेय भाषाओं के विपरीत, पूरक के अंतर्गत संवृत नहीं हैं।

  7. सदस्यता — w, L में है क्या? — किस प्रकार के वर्णन हेतु अनिर्णेय है?

    1. DFA
    2. संदर्भ-मुक्त व्याकरण
    3. ट्यूरिंग मशीन
    4. नियमित व्यंजक
    उत्तर देखें

    उत्तर: C — ट्यूरिंग मशीन

    ट्यूरिंग मशीन हेतु सदस्यता पहचानीय है पर निर्णेय नहीं: M का w पर अनुकरण करें और स्वीकार करने पर स्वीकार करें, परंतु यदि M चक्र में पड़े तो कोई ऐसा बिंदु नहीं जहाँ आप निष्कर्ष निकाल सकें कि वह कभी नहीं करेगी। DFA हेतु आप माला को |w| चरणों में चला देते हैं। संदर्भ-मुक्त व्याकरण हेतु चॉम्स्की सामान्य रूप में रूपांतरण के पश्चात् CYK कलनविधि सदस्यता O(n³) में तय करती है। नियमित व्यंजक DFA में बदल जाता है। अतः निर्णेयता को टेप तोड़ता है, और कारण ठीक वही अपरिबद्धता है जो ट्यूरिंग मशीन को उसकी शक्ति देती है — वही विशेषता चर्च–ट्यूरिंग परिकल्पना में सामर्थ्य के रूप में और यहाँ सीमा के रूप में आती है।

  8. इनमें कौन-से वर्ग पूरक के अंतर्गत संवृत नहीं हैं? (एक से अधिक सही हो सकते हैं।)

    1. नियमित भाषाएँ
    2. निर्णेय भाषाएँ
    3. पहचानीय भाषाएँ
    4. परिमित भाषाएँ
    उत्तर देखें

    उत्तर: C — पहचानीय भाषाएँ; D — परिमित भाषाएँ

    पहचानीय व परिमित भाषाएँ, पूर्णतः भिन्न कारणों से। पहचानीय गहन स्थिति है: रुकने की समस्या पहचानीय है और उसका पूरक नहीं, जो एक उदाहरण से इसे तय कर देता है — वर्ग इस वचन से परिभाषित है कि "प्रत्येक सदस्य स्वीकारती है, अन्यथा अनंत काल चल सकती है", और ऐसे वचन को उलटने का कोई मार्ग नहीं। परिमित उपरी स्थिति है, और उसे खारिज करने के बजाय देखने योग्य: अरिक्त वर्णमाला पर Σ* अनंत है, अतः किसी भी परिमित भाषा का पूरक अनंत है और इसलिए परिमित नहीं। निर्णेय भाषाएँ संवृत हैं, क्योंकि निर्णायक सदा रुकता है और आप सरलतः उसका उत्तर पलट सकते हैं; नियमित भाषाएँ DFA की स्वीकारक अवस्थाएँ बदलकर संवृत हैं। साथ रखने योग्य कसौटी यह है कि वर्ग ऐसे वचन से परिभाषित है या नहीं जिसे आप उलट सकें।