Recursively Enumerable Sets, Turing Machines and Undecidability MCQ Quiz in हिन्दी - Objective Question with Answer for Recursively Enumerable Sets, Turing Machines and Undecidability - मुफ्त [PDF] डाउनलोड करें

विश्लेषिक इंजन: 

• एक विश्लेषिक इंजन एक मशीन है जिसे पहले सामान्य यांत्रिक कंप्यूटर की अवधारणा माना जाता है।
• इसे पंच कार्ड का उपयोग करके प्रोग्राम किया गया था और इसमें एक एकीकृत मेमरी भी है।
• इसे पहली बार 1837 में चार्ल्स बैबेज द्वारा प्रस्तावित किया गया था और इसे सामान्य उद्देश्य वाले कंप्यूटर की पहली डिजाइन अवधारणा के रूप में माना जाता था।

EDSAC:

• EDSAC का अर्थ इलेक्ट्रॉनिक डिले स्टोरेज ऑटोमेटिक कैलकुलेटर है।
• इसे दूसरा संग्रहित प्रोग्राम इलेक्ट्रॉनिक कंप्यूटर माना जाता है।
• इसे ग्राफिकल कंप्यूटर गेम चलाने वाला पहला कंप्यूटर भी माना जाता है।

ENIAC:

• ENIAC का अर्थ इलेक्ट्रॉनिक न्यूमेरिकल इंटीग्रेटर एंड कंप्यूटर होता है, यह पहला सामान्य उद्देश्य वाला इलेक्ट्रॉनिक कंप्यूटर था। यह पहला ट्यूरिंग-पूर्ण, डिजिटल कंप्यूटर था जो कंप्यूटिंग समस्याओं की एक पूरी श्रृंखला को हल करने के लिए रिप्रोग्राम करने में सक्षम था।

सही उत्तर विकल्प 1 है अर्थात्  विश्लेषिक इंजन

सही उत्तर आउटपुट टेप है।

Key Points 

• ट्यूरिंग मशीन एक सैद्धांतिक कम्प्यूटेशनल मॉडल है जिसमें कई प्रमुख घटक होते हैं।
• ट्यूरिंग मशीन के प्रमुख घटक हैं:
  • इनपुट टेप: एक टेप जो कोशिकाओं में विभाजित होता है, जिनमें से प्रत्येक एक सीमित वर्णमाला से एक प्रतीक रख सकता है। यह टेप इनपुट और आउटपुट दोनों के लिए उपयोग किया जाता है।
  • कण्ट्रोल यूनिट: एक सीमित अवस्था मशीन जो वर्तमान अवस्था और टेप हेड के नीचे वर्तमान प्रतीक के आधार पर ट्यूरिंग मशीन की क्रियाओं को नियंत्रित करती है।
• एक आउटपुट टेप ट्यूरिंग मशीन का एक मानक घटक नहीं है क्योंकि इनपुट टेप का उपयोग इनपुट और आउटपुट दोनों कार्यों के लिए किया जाता है।

Additional Information 

• विकल्प 1: इनपुट टेप - यह ट्यूरिंग मशीन का एक घटक है। इसका उपयोग इनपुट पढ़ने और आउटपुट लिखने दोनों के लिए किया जाता है।
• विकल्प 3: कण्ट्रोल यूनिट - यह भी ट्यूरिंग मशीन का एक घटक है। यह वर्तमान अवस्था और टेप से पढ़े जा रहे प्रतीक के आधार पर मशीन के संचालन को निर्देशित करता है।

सही उत्तर गणनीय नहीं है।

Key Points 

• हॉल्टिंग समस्या गणनीयता सिद्धांत में एक निर्णय समस्या है।
• यह पूछता है कि क्या कोई दिया गया प्रोग्राम किसी दिए गए इनपुट के लिए चलना समाप्त करेगा या हमेशा के लिए चलता रहेगा।
• एलन ट्यूरिंग ने 1936 में सिद्ध किया कि सभी संभावित प्रोग्राम-इनपुट जोड़ियों के लिए हॉल्टिंग समस्या को हल करने के लिए एक सामान्य एल्गोरिथम मौजूद नहीं हो सकता।
• नतीजतन, हॉल्टिंग समस्या गणनीय नहीं है, जिसका अर्थ है कि कोई एल्गोरिथम नहीं है जो सभी संभावित इनपुट के लिए समस्या को हल कर सकता है।

Additional Information 

• विकल्प 1: O(1) - यह स्थिर समय जटिलता को दर्शाता है, जिसका अर्थ है कि ऑपरेशन को इनपुट आकार की परवाह किए बिना समान समय लगेगा। हॉल्टिंग समस्या को स्थिर समय में हल नहीं किया जा सकता है।
• विकल्प 2: O(n) - यह रैखिक समय जटिलता को दर्शाता है, जिसका अर्थ है कि ऑपरेशन का समय इनपुट आकार के साथ रैखिक रूप से बढ़ेगा। हॉल्टिंग समस्या को रैखिक समय में हल नहीं किया जा सकता है।

एक ट्यूरिंग मशीन में निम्न शामिल हैं:

- एक परिमित-अवस्था नियंत्रण जो अवस्थाओं के किसी भी परिमित समुच्चय में हो सकता है,

- प्रकोष्ठों में विभाजित एक अनंत टेप, जिनमें से प्रत्येक में एक टेप प्रतीक हो सकता है,

- टेप प्रकोष्ठों में से एक पर स्थित एक पठन/लेखन टेप शीर्ष।

• विराम की समस्या NP-हार्ड है, NP-पूर्ण नहीं है, लेकिन अनिर्णनीय है। अतः विकल्प 2 सही है।
• हैमिल्टनी परीपथ, बिन पैकिंग, विभाजन की समस्याएं NP-पूर्ण समस्याएं हैं।

विकल्प (2) में उल्लिखित समस्या संदर्भ-मुक्त व्याकरण (CFG_S) के लिए अस्पष्टता समस्या अनिर्णनीय है।

व्याख्या:-

व्याकरण की अस्पष्टता अनिर्णनीय है, अर्थात व्याकरण की अस्पष्टता को दूर करने के लिए कोई विशेष एल्गोरिथम नहीं है,  अस्पष्ट व्याकरण के कुछ उदाहरण यहां दिए गए हैं:

• S → aS | Sa | €
• E → E + E | E*E | id
• A → AA | (A) | a

 Additional Information

FSAS के लिए तुल्यता समस्या:- एक स्वचालन एक मशीन है जिसमें स्थितियों की एक सीमित संख्या होती है। किन्हीं दो स्वचालन को समतुल्य कहा जाता है यदि दोनों एक ही स्ट्रिंग के समान सेट को स्वीकार करते हैं।

FSAS के लिए परिमितता समस्या: - परिमितता समस्या (भी CFG_S के लिए) FSAs के लिए निर्णनीय है क्योंकि हमें केवल लूप DFA की जांच करने की आवश्यकता है।

CFGS के लिए सदस्यता समस्या: एक सेट के लिए सदस्यता समस्या यह तय करने की समस्या है कि दो संभावित तत्वों में से कौन सा उस सेट से संबंधित होने की अधिक संभावना है। दूसरे शब्दों में, सदस्य को गैर-सदस्य से अलग करने के लिए दो तत्व दिए गए हैं जिनमें से कम से कम एक सेट में है।

C गलत है क्योंकि सभी पुनरावर्ती गणना योग्य भाषाओं (अर्ध-निर्णायक) का सेट सभी पुनरावर्ती भाषाओं (निर्णायक) के सेट का एक STRICT सुपर सेट है।

D गलत है क्योंकि सभी पुनरावर्ती गणना योग्य भाषाओं (सभी ट्यूरिंग मशीनों का सेट) का सेट एक अनंत लेकिन गणनीय सेट है।

भाषा A = {0ⁿ 1ⁿ 2ⁿ | n = 1, 2, 3, .........}

यह संदर्भ संवेदी भाषा है। 

• यह भाषा संदर्भ मुक्त व्याकरण नहीं हो सकता है। चूँकि सभी 0, 1 और 2 बराबर संख्या में है।

कारण:

यदि हम अधोसंभर ऑटोमेटा की स्थिति लेते हैं। तो सर्वप्रथम सभी 0 को स्टैक में डालिए, फिर प्रत्येक 1 के साथ सभी 0 को बाहर निकालिए। लेकिन अंत में स्टैक पर कोई प्रतीक नहीं होता है और इनपुट शेष रहती है। इसलिए, इसे अधोसंभर ऑटोमेटा द्वारा स्वीकार नहीं किया जाता है और यह संदर्भ मुक्त व्याकरण नहीं हो सकता है।

• यह टैप की अग्र और पश्च गतिविधि की सहायता के साथ रैखिक परिबद्ध ऑटोमेटा द्वारा स्वीकृत होती है।

भाषा A को अस्वीकार करने वाली मशीन:

सही उत्तर विकल्प 4 . है

संकल्पना:

निर्णनीय भाषा: यदि कोई ट्यूरिंग मशीन मौजूद है जो उसे रोकती या स्वीकार करती है तो एक भाषा निर्णायक होती है।

व्याख्या:

1: अनिर्णनीय 

यह निर्धारित करने के लिए कोई TM नहीं है कि दिया गया प्रोग्राम आउटपुट का उत्पादन करेगा या नहीं।

2: अनिर्णनीय 

संदर्भ-मुक्त भाषाएं पूरक के तहत बंद नहीं हैं।

3: अनिर्णनीय 

पूरक के तहत नियमित भाषाएं बंद हैं।

4: अनिर्णनीय 

पुनरावर्ती भाषाएँ पूरक के अंतर्गत बंद हैं।

अतः विकल्प 4 सही है

Key Points

ध्यान दें कि निम्नलिखित कथन सत्य हैं

1. प्रत्येक अनंत नियमित भाषा L में एक सबसेट S होता है जो अनिर्णनीय होता है।
2. प्रत्येक अनंत नियमित भाषा L में एक सबसेट S होता है जिसे पहचाना नहीं जा सकता।
3. प्रत्येक अनंत भाषा L का एक सबसेट S होता है जो अनिर्णनीय होता है।
4. प्रत्येक अनंत भाषा L का एक सबसेट S होता है जिसे पहचाना नहीं जा सकता है।

तो, S1 और S2 दोनों सही हैं।

सही उत्तर विकल्प 4 है

स्पष्टीकरण: S2 कथन के लिए निम्नलिखित विवरण पर विचार 

प्रत्येक अनंत भाषा (नियमित या नहीं) में एक अनिर्णनीय सबसेट होती है।

नियमित भाषाओं पर विशेष ध्यान देने के साथ, इच्छित समाधान कुछ ऐसा हो सकता है जैसे x, y, z को प्राप्त करने के लिए पंपिंग लेम्मा का उपयोग करना, जैसे कि xyⁿz प्रत्येक n के लिए आपकी भाषा में हो, फिर सबसेट A = {xynz | n ∈ N} पर विचार करें। जहाँ A प्राकृतिक संख्याओं का आपका पसंदीदा अनिर्णनीय सेट है।

यह साबित करता है कि s1 सही है।

• DFA की शक्ति NFA के बराबर है इसलिए प्रत्येक NFA को तुल्य DFA में परिवर्तित किया जा सकता है और साथ ही प्रत्येक DFA को तुल्य NFA में परिवर्तित किया जा सकता है।
• DTM की शक्ति NTM के बराबर है इसलिए प्रत्येक NTM को तुल्य DTM में बदला जा सकता है और साथ ही प्रत्येक DTM को तुल्य NTM में बदला जा सकता है।
• नियमित भाषा प्रसंग-मुक्त भाषा का एक उपसमुच्चय है, इसलिए प्रत्येक नियमित भाषा एक प्रसंग-मुक्त भाषा है
• पुनरावर्ती भाषा, पुनरावर्ती गणनीय भाषा का उपसमुच्चय है, इसलिए आवर्ती गणनीय समुच्चय का उपसमुच्चय पुनरावर्ती हो भी सकता है और नहीं भी।

चॉम्स्की अनुक्रम:

अतः विकल्प 2 सही उत्तर है।

उत्तर: विकल्प 2

व्याख्या: 

विकल्प 1: यह निवेश को रोक सकता है और स्वीकार कर सकता है

यह सही नहीं है क्योंकि एक निवेश पर ट्यूरिंग मशीन को देखते हुए निवेश को रोक और स्वीकार कर सकता है। इसलिए कथन सत्य है प्रश्न गलत कथन के लिए पूछ रहा है।

विकल्प 2: निवेश बदलने से यह रुक सकता है

यह सही है। किसी दिए गए निवेश पर ट्यूरिंग मशीन को देखते हुए, यह दिए गए निवेश को नहीं बदल सकता है। अतः कथन असत्य है।

विकल्प 3: यह निवेश को रोक सकता है और अस्वीकार कर सकता है

यह सही नहीं है यदि दिया गया निवेश ट्यूरिंग मशीन की भाषा से संबंधित नहीं है तो संभव है कि ट्यूरिंग मशीन निवेश को अस्वीकार कर दे और रुक जाए।

विकल्प 4: यह कभी नहीं रुक सकता​ है

यह सही नहीं है यह संभव है कि ट्यूरिंग किसी निवेश पर कभी रुके नहीं। यह एक अनंत पाश में फंस सकता है।

• विराम की समस्या NP-हार्ड है, NP-पूर्ण नहीं है, लेकिन अनिर्णनीय है। अतः विकल्प 2 सही है।
• हैमिल्टनी परीपथ, बिन पैकिंग, विभाजन की समस्याएं NP-पूर्ण समस्याएं हैं।

• यदि L पुनरावर्ती भाषा है, तो \(\vec L\) भी पुनरावर्ती है। प्रत्येक पुनरावर्ती, पुनरावर्तत: गणनीय (r.e.) है
• L पुनरावर्तत: गणनीय भाषा (r.e.) है लेकिन पुनरावर्ती नहीं है और इसका अर्थ है कि L, r.e. है। लेकिन \(\vec L\) , r.e नहीं है

विकल्प 1: न तो L और न ही \(\vec L\) पुनरावर्तत: गणनीय है

यह संभव है कि L पुनरावर्तत: गणनीय नहीं है और \(\vec L\) भी पुनरावर्तत: गणनीय नहीं है। इसलिए यह व्यवहार्य है।

विकल्प 2: L में से एक है और \(\vec L\), r.e है। लेकिन पुनरावर्ती नहीं; दूसरा r.e. नहीं है

पुनरावर्तत: गणनीय भाषा पूरक के तहत बंद नहीं है। यदि L, RE है और पुनरावर्ती नहीं है तो \(\vec L\) पुनरावर्ती नहीं है और इसलिए यह व्यवहार्य है।

विकल्प 3: L और \(\vec L\) दोनों r.e हैं। लेकिन पुनरावर्ती नहीं।

पुनरावर्ती पूरकता के तहत बंद है। यदि L और \(\vec L\), RE है और यह निश्चित रूप से पुनरावर्ती है और इसलिए यह संभव नहीं है कि L और \(\vec L\), दोनों r.e हैं। लेकिन पुनरावर्ती नहीं।

विकल्प 4: L और \(\vec L\) दोनों पुनरावर्ती हैं।

पुनरावर्ती पूरकता के तहत बंद है। यदि L पुनरावर्ती है तो और \(\vec L\) भी पुनरावर्ती है इसलिए यह व्यवहार्य है

सही उत्तर विकल्प 3 है।

संकल्पना:

दी गई समस्या 1 की सम संख्या है।

यह DFA के लिए 2 अवस्थाओं को स्वीकार करता है।

एक ट्यूरिंग मशीन में कम से कम दो अवस्थाएँ होनी चाहिए:

एक जो इनपुट को स्वीकार करता है और एक जो इसे अस्वीकार करता है। क्योंकि मशीन एक ही समय में स्वीकार और अस्वीकार नहीं कर सकती है, स्वीकार करने और अस्वीकार करने वाले अवस्थाओं को अलग-अलग होना चाहिए। नतीजतन, कम से कम दो अवस्थाओं की आवश्यकता है।

जब आप एक ही अवस्था में हों तो आप कुछ भी स्वीकार नहीं कर सकते। ट्यूरिंग मशीन का संक्रमण (X, Y, R/L) है। एक अवस्था के साथ, आपको कम से कम एक संक्रमण को परिभाषित करना होगा, जिसमें लगभग निश्चित रूप से R/L होगा। नतीजतन, ट्यूरिंग मशीन कभी भी दाएं या बाएं या दोनों के बीच दोलन करना बंद नहीं करेगी।

अतः सही उत्तर 2 है।