रिकर्सिवली एन्युमरेबल लैंग्वेज: Difference between revisions

Latest revision as of 15:23, 31 July 2023

गणित, तर्क और कंप्यूटर विज्ञान में, एक फॉर्मल लैंग्वेज को रिकर्सिवली एन्युमरेबल लैंग्वेज (पार्शियली डिसाइडेबल, सेमीडिसाइडेबल, ट्यूरिंग-अक्सेप्टबल या ट्यूरिंग-रेकॉग्निजबल) कहा जाता है यदि यह लैंग्वेज के एल्फाबेट (कंप्यूटर विज्ञान) के सभी संभावित शब्दों के सेट (गणित) में रिकर्सिवली एन्युमरेबल सेट है अर्थात्, यदि कोई ट्यूरिंग मशीन उपस्थित है जो लैंग्वेज के सभी वैलिड स्ट्रिंग की गणना करेगी।

फॉर्मल लैंग्वेज के चॉम्स्की हायरार्की में रिकर्सिवली एन्युमरेबल लैंग्वेज को टाइप-0 लैंग्वेज के रूप में जाना जाता है। सभी रेगुलर लैंग्वेज, कॉन्टेक्स्ट-फ्री, कॉन्टेक्स्ट-सेंसिटिव और रिकर्सिव लैंग्वेज रिकर्सिवली एन्युमरेबल हैं।

सभी रिकर्सिवली एन्युमरेबल लैंग्वेज के वर्ग को आरई (जटिलता) कहा जाता है।

परिभाषाएँ

रिकर्सिवली एन्युमरेबल लैंग्वेज की तीन समकक्ष परिभाषाएँ हैं:

एक रिकर्सिवली एन्युमरेबल लैंग्वेज जो वर्णमाला पर सभी संभावित शब्दों के सेट(गणित) में एक रिकर्सिवली एन्युमरेबल उपसमुच्चय है।
रिकर्सिवली एन्युमरेबल लैंग्वेज एक फॉर्मल लैंग्वेज है जिसके लिए एक ट्यूरिंग मशीन (या अन्य गणना योग्य फ़ंक्शन) उपस्थित है जो लैंग्वेज के सभी वैलिड स्ट्रिंग की गणना करेगी। ध्यान दें कि यदि लैंग्वेज अपरिमित है तो दी गई गणना एल्गोरिदम का चयन किया जा सकता है जिससे यह पुनरावर्तन से बच सके क्योंकि हम परीक्षण कर सकते हैं कि संख्या n के लिए निर्मित स्ट्रिंग "पहले से ही" उस संख्या के लिए निर्मित है जो n से कम है। यदि यह पहले से ही निर्मित है तो इसके स्थान पर इनपुट n+1 के लिए आउटपुट का उपयोग करें (रिकर्सिवली) किंतु पुनः परीक्षण करें कि क्या यह "नया" है।
रिकर्सिवली एन्युमरेबल लैंग्वेज एक फॉर्मल लैंग्वेज है जिसके लिए एक ट्यूरिंग मशीन (या अन्य गणना योग्य फ़ंक्शन) उपस्थित है जो इनपुट के रूप में लैंग्वेज में किसी भी स्ट्रिंग के साथ प्रस्तुत होने पर रुक जाएगी तथा स्वीकार कर लेगी, किंतु लैंग्वेज में एक स्ट्रिंग के साथ नहीं प्रस्तुत होने पर या तो रुक सकती है और अस्वीकार कर सकती है या सदैव के लिए लूप कर सकती है। इसकी तुलना रिकर्सिव लैंग्वेज से करें जिनके लिए आवश्यक है कि ट्यूरिंग मशीन सभी स्थितियों में रुक जाए।

सभी रेगुलर लैंग्वेज, कॉन्टेक्स्ट-फ्री, कॉन्टेक्स्ट-सेंसिटिव और रिकर्सिव लैंग्वेज रिकर्सिवली एन्युमरेबल हैं।

पोस्ट के प्रमेय से पता चलता है कि RE अपने कम्प्लीमेंट co-RE, के साथ अंकगणितीय हायरार्की के प्रथम स्तर के अनुरूप है।

उदाहरण

ट्यूरिंग मशीनों को रोकने का सेट रिकर्सिवली एन्युमरेबल है किंतु रिकर्सिव नहीं है। वास्तव में, कोई ट्यूरिंग मशीन चला सकता है और यदि मशीन रुकती है तो उसे स्वीकार कर सकता है, इसलिए यह रिकर्सिवली एन्युमरेबल है। दूसरी ओर समस्या अनिर्णीत है।

कुछ अन्य रिकर्सिवली एन्युमरेबल लैंग्वेज जो रिकर्सिव नहीं हैं उनमें सम्मिलित हैं:

संवृत्त गुण

रिकर्सिवली एन्युमरेबल लैंग्वेज(आरईएल) निम्नलिखित परिचालनों के अंतर्गत संवृत्त हैं। अर्थात्, यदि L और P दो रिकर्सिवली एन्युमरेबल लैंग्वेज हैं तो निम्नलिखित लैंग्वेज भी रिकर्सिवली एन्युमरेबल हैं:

L का द क्लीन स्टार $L^{*}$
L और P का संयोजन $L\circ P$
संघ (सेट सिद्धांत) $L\cup P$
प्रतिच्छेदन(सेट सिद्धांत) $L\cap P$ .

रिकर्सिवली एन्युमरेबल लैंग्वेज सेट अंतर या पूरकता (कम्प्लीमेंटशन)के अंतर्गत संवृत्त नहीं होती हैं। यदि $P$ रिकर्सिव है तो सेट अंतर $L-P$ रिकर्सिवली एन्युमरेबल है। यदि $L$ रिकर्सिवली एन्युमरेबल है, तो $L$ का पूरक (कम्प्लीमेंट) रिकर्सिवली एन्युमरेबल है यदि और केवल यदि $L$ भी रिकर्सिव है।

यह भी देखें

कंप्यूटेबली एन्युमरेबल सेट
रिकर्शन

संदर्भ

Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.
Kozen, D.C. (1997), Automata and Computability, Springer.

बाहरी संबंध

@@ Line 1: / Line 1: @@
 {{short description|Formal language}}
-गणित, [[तर्क]] और [[कंप्यूटर विज्ञान]] में, एक [[औपचारिक भाषा]] को पुनरावर्ती रूप से गणना योग्य (पहचानने योग्य, आंशिक रूप से निर्णय लेने योग्य, अर्धनिर्णय योग्य, ट्यूरिंग-स्वीकार्य या ट्यूरिंग-पहचानने योग्य) कहा जाता है यदि यह सभी संभावित शब्दों के [[सेट (गणित)]] में पुनरावर्ती रूप से गणना योग्य सेट है भाषा की [[वर्णमाला (कंप्यूटर विज्ञान)]], यानी, यदि कोई [[ट्यूरिंग मशीन]] मौजूद है जो भाषा के सभी वैध तारों की गणना करेगी।
+गणित, [[तर्क]] और [[कंप्यूटर विज्ञान]] में, एक [[औपचारिक भाषा|फॉर्मल लैंग्वेज]] को '''रिकर्सिवली एन्युमरेबल लैंग्वेज''' (पार्शियली डिसाइडेबल, सेमीडिसाइडेबल, ट्यूरिंग-अक्सेप्टबल या ट्यूरिंग-रेकॉग्निजबल) कहा जाता है यदि यह लैंग्वेज के [[वर्णमाला (कंप्यूटर विज्ञान)|एल्फाबेट (कंप्यूटर विज्ञान)]] के सभी संभावित शब्दों के [[सेट (गणित)]] में रिकर्सिवली एन्युमरेबल सेट है अर्थात्, यदि कोई [[ट्यूरिंग मशीन]] उपस्थित है जो लैंग्वेज के सभी वैलिड स्ट्रिंग की गणना करेगी।
-औपचारिक भाषाओं के [[चॉम्स्की पदानुक्रम]] में पुनरावर्ती रूप से गणना योग्य भाषाओं को टाइप-0 भाषाओं के रूप में जाना जाता है। सभी [[नियमित भाषा]], [[संदर्भ-मुक्त व्याकरण]]|संदर्भ-मुक्त, [[संदर्भ-संवेदनशील भाषा]]|संदर्भ-संवेदनशील और [[पुनरावर्ती भाषा]] भाषाएँ पुनरावर्ती रूप से गणना योग्य हैं।
+फॉर्मल लैंग्वेज के [[चॉम्स्की पदानुक्रम|चॉम्स्की हायरार्की]] में रिकर्सिवली एन्युमरेबल लैंग्वेज को टाइप-0 लैंग्वेज के रूप में जाना जाता है। सभी [[नियमित भाषा|रेगुलर लैंग्वेज]], [[संदर्भ-मुक्त व्याकरण|कॉन्टेक्स्ट-फ्री]], [[संदर्भ-संवेदनशील भाषा|कॉन्टेक्स्ट-सेंसिटिव]] और [[पुनरावर्ती भाषा|रिकर्सिव]] लैंग्वेज रिकर्सिवली एन्युमरेबल हैं।
-सभी पुनरावर्ती रूप से गणना योग्य भाषाओं के वर्ग को [[आरई (जटिलता)]] कहा जाता है।
+सभी रिकर्सिवली एन्युमरेबल लैंग्वेज के वर्ग को [[आरई (जटिलता)]] कहा जाता है।
 ==परिभाषाएँ==
-पुनरावर्ती रूप से गणना योग्य भाषा की तीन समकक्ष परिभाषाएँ हैं:
+रिकर्सिवली एन्युमरेबल लैंग्वेज की तीन समकक्ष परिभाषाएँ हैं:
-# एक पुनरावर्ती रूप से गणना योग्य भाषा जो वर्णमाला पर सभी संभावित शब्दों के [[सबसेट|सेट]] (गणित) में एक पुनरावर्ती रूप से गणना योग्य उपसमुच्चय है।
+# एक रिकर्सिवली एन्युमरेबल लैंग्वेज जो वर्णमाला पर सभी संभावित शब्दों के [[सबसेट|सेट]](गणित) में एक रिकर्सिवली एन्युमरेबल उपसमुच्चय है।
-# पुनरावर्ती गणना योग्य भाषा एक औपचारिक भाषा है जिसके लिए एक ट्यूरिंग मशीन (या अन्य गणना योग्य फ़ंक्शन) मौजूद है जो भाषा के सभी वैध स्ट्रिंग्स की गणना करेगी। ध्यान दें कि यदि भाषा अनंत है, तो प्रदान किए गए गणना एल्गोरिदम को चुना जा सकता है ताकि यह दोहराव से बचा जा सके, क्योंकि हम परीक्षण कर सकते हैं कि संख्या n के लिए उत्पादित स्ट्रिंग पहले से ही उस संख्या के लिए बनाई गई है जो n से कम है। यदि यह पहले से ही निर्मित है, तो इसके बजाय इनपुट n+1 के लिए आउटपुट का उपयोग करें (पुनरावर्ती रूप से), लेकिन फिर से, परीक्षण करें कि क्या यह नया है।
+# रिकर्सिवली एन्युमरेबल लैंग्वेज एक फॉर्मल लैंग्वेज है जिसके लिए एक ट्यूरिंग मशीन (या अन्य गणना योग्य फ़ंक्शन) उपस्थित है जो लैंग्वेज के सभी वैलिड स्ट्रिंग की गणना करेगी। ध्यान दें कि यदि लैंग्वेज अपरिमित है तो दी गई गणना एल्गोरिदम का चयन किया जा सकता है जिससे यह पुनरावर्तन से बच सके क्योंकि हम परीक्षण कर सकते हैं कि संख्या n के लिए निर्मित स्ट्रिंग "पहले से ही" उस संख्या के लिए निर्मित है जो n से कम है। यदि यह पहले से ही निर्मित है तो इसके स्थान पर इनपुट n+1 के लिए आउटपुट का उपयोग करें (रिकर्सिवली) किंतु पुनः परीक्षण करें कि क्या यह "नया" है।
-# पुनरावर्ती रूप से गणना योग्य भाषा एक औपचारिक भाषा है जिसके लिए एक ट्यूरिंग मशीन (या अन्य गणना योग्य फ़ंक्शन) मौजूद है जो इनपुट के रूप में भाषा में किसी भी [[शाब्दिक स्ट्रिंग]] के साथ प्रस्तुत होने पर रुक जाएगी और स्वीकार कर लेगी लेकिन प्रस्तुत किए जाने पर या तो रुक सकती है और अस्वीकार कर सकती है या हमेशा के लिए लूप कर सकती है एक स्ट्रिंग भाषा में नहीं है. इसकी तुलना पुनरावर्ती भाषाओं से करें, जिसके लिए आवश्यक है कि ट्यूरिंग मशीन सभी मामलों में रुक जाए।
+# रिकर्सिवली एन्युमरेबल लैंग्वेज एक फॉर्मल लैंग्वेज है जिसके लिए एक ट्यूरिंग मशीन (या अन्य गणना योग्य फ़ंक्शन) उपस्थित है जो इनपुट के रूप में लैंग्वेज में किसी भी स्ट्रिंग के साथ प्रस्तुत होने पर रुक जाएगी तथा स्वीकार कर लेगी, किंतु लैंग्वेज में एक स्ट्रिंग के साथ नहीं प्रस्तुत होने पर या तो रुक सकती है और अस्वीकार कर सकती है या सदैव के लिए लूप कर सकती है। इसकी तुलना रिकर्सिव लैंग्वेज से करें जिनके लिए आवश्यक है कि ट्यूरिंग मशीन सभी स्थितियों में रुक जाए।
-सभी नियमित भाषा, [[संदर्भ-मुक्त भाषा]]|संदर्भ-मुक्त, संदर्भ-संवेदनशील भाषा|संदर्भ-संवेदनशील और पुनरावर्ती भाषा भाषाएँ पुनरावर्ती रूप से गणना योग्य हैं।
+सभी [[नियमित भाषा|रेगुलर लैंग्वेज]], [[संदर्भ-मुक्त व्याकरण|कॉन्टेक्स्ट-फ्री]], [[संदर्भ-संवेदनशील भाषा|कॉन्टेक्स्ट-सेंसिटिव]] और रिकर्सिव लैंग्वेज रिकर्सिवली एन्युमरेबल हैं।
-पोस्ट के प्रमेय से पता चलता है कि 'आरई (जटिलता)', इसके [[पूरक (जटिलता)]] सह-आरई के साथ, [[अंकगणितीय पदानुक्रम]] के पहले स्तर के अनुरूप है।
+पोस्ट के प्रमेय से पता चलता है कि '''RE''' अपने [[पूरक (जटिलता)|कम्प्लीमेंट]] co-RE, के साथ [[अंकगणितीय पदानुक्रम|अंकगणितीय]] [[चॉम्स्की पदानुक्रम|हायरार्की]] के प्रथम स्तर के अनुरूप है।
 ==उदाहरण==
-ट्यूरिंग मशीनों को रोकने का सेट पुनरावर्ती रूप से गणना योग्य है किंतु पुनरावर्ती नहीं है। वास्तव में, कोई ट्यूरिंग मशीन चला सकता है और यदि मशीन रुकती है तो उसे स्वीकार कर सकता है, इसलिए यह पुनरावर्ती रूप से गणना योग्य है। दूसरी ओर समस्या अनिर्णीत है।
+ट्यूरिंग मशीनों को रोकने का सेट रिकर्सिवली एन्युमरेबल है किंतु रिकर्सिव नहीं है। वास्तव में, कोई ट्यूरिंग मशीन चला सकता है और यदि मशीन रुकती है तो उसे स्वीकार कर सकता है, इसलिए यह रिकर्सिवली एन्युमरेबल है। दूसरी ओर समस्या अनिर्णीत है।
-कुछ अन्य पुनरावर्ती रूप से गणना योग्य भाषाएँ जो पुनरावर्ती नहीं हैं उनमें सम्मिलित हैं:
+कुछ अन्य रिकर्सिवली एन्युमरेबल लैंग्वेज जो रिकर्सिव नहीं हैं उनमें सम्मिलित हैं:
-* [[पोस्ट पत्राचार समस्या]]
+* [[पोस्ट पत्राचार समस्या|पोस्ट करेस्पॉन्डेंस प्रॉब्लम]]
-*[[मृत्यु दर (कम्प्यूटेबिलिटी सिद्धांत)]]
+*[[मृत्यु दर (कम्प्यूटेबिलिटी सिद्धांत)|मोर्टेलिटी (कम्प्यूटेबिलिटी सिद्धांत)]]
-*[[निर्णय समस्या]]
+*[[निर्णय समस्या|एंट्सचीडुंग्स समस्या]]
 ==संवृत्त गुण==
-पुनरावर्ती गणना योग्य भाषाएँ (आरईएल) निम्नलिखित परिचालनों के अंतर्गत संवृत्त हैं। अर्थात्, यदि L और P दो पुनरावर्ती रूप से गणना योग्य भाषाएँ हैं तो निम्नलिखित भाषाएँ भी पुनरावर्ती रूप से गणना योग्य हैं:
+रिकर्सिवली एन्युमरेबल लैंग्वेज(आरईएल) निम्नलिखित परिचालनों के अंतर्गत संवृत्त हैं। अर्थात्, यदि L और P दो रिकर्सिवली एन्युमरेबल लैंग्वेज हैं तो निम्नलिखित लैंग्वेज भी रिकर्सिवली एन्युमरेबल हैं:
 * L का द क्लीन स्टार <math>L^*</math>
@@ Line 34: / Line 34: @@
 * [[प्रतिच्छेदन (सेट सिद्धांत)|प्रतिच्छेदन(सेट सिद्धांत)]] <math>L \cap P</math>.
-पुनरावर्ती रूप से गणना योग्य भाषाएँ सेट अंतर या पूरकता के अंतर्गत संवृत्त नहीं होती हैं। यदि <math>P</math> पुनरावर्ती है तो सेट अंतर <math>L - P</math>  पुनरावर्ती रूप से गणना योग्य है। यदि <math>L</math> पुनरावर्ती रूप से गणना योग्य है, तो <math>L</math> का पूरक पुनरावर्ती रूप से गणना योग्य है यदि और केवल यदि <math>L</math> भी पुनरावर्ती है।
+रिकर्सिवली एन्युमरेबल लैंग्वेज सेट अंतर या पूरकता (कम्प्लीमेंटशन)के अंतर्गत संवृत्त नहीं होती हैं। यदि <math>P</math> रिकर्सिव है तो सेट अंतर <math>L - P</math>  रिकर्सिवली एन्युमरेबल है। यदि <math>L</math> रिकर्सिवली एन्युमरेबल है, तो <math>L</math> का पूरक (कम्प्लीमेंट) रिकर्सिवली एन्युमरेबल है यदि और केवल यदि <math>L</math> भी रिकर्सिव है।
 == यह भी देखें ==
-*गणनायोग्य सेट
+*कंप्यूटेबली एन्युमरेबल सेट
-*पुनरावर्तन
+*रिकर्शन
 ==संदर्भ==
@@ Line 50: / Line 50: @@
 {{Formal languages and grammars}}
-[[Category: औपचारिक भाषाएँ]] [[Category: गणना का सिद्धांत]] [[Category: कंप्यूटिंग का गणित]] [[Category: एलन ट्यूरिंग]]
-[[Category: Machine Translated Page]]
 [[Category:Created On 07/07/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:एलन ट्यूरिंग]]
+[[Category:औपचारिक भाषाएँ]]
+[[Category:कंप्यूटिंग का गणित]]
+[[Category:गणना का सिद्धांत]]

Anonymous

Search

रिकर्सिवली एन्युमरेबल लैंग्वेज: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 15:23, 31 July 2023

Contents

परिभाषाएँ

उदाहरण

संवृत्त गुण

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

रिकर्सिवली एन्युमरेबल लैंग्वेज: Difference between revisions

Latest revision as of 15:23, 31 July 2023

परिभाषाएँ

उदाहरण

संवृत्त गुण

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories