View source for रिकर्सिवली एन्युमरेबल लैंग्वेज

{{short description|Formal language}}
गणित, [[तर्क]] और [[कंप्यूटर विज्ञान]] में, एक [[औपचारिक भाषा|फॉर्मल लैंग्वेज]] को '''रिकर्सिवली एन्युमरेबल लैंग्वेज''' (पार्शियली डिसाइडेबल, सेमीडिसाइडेबल, ट्यूरिंग-अक्सेप्टबल या ट्यूरिंग-रेकॉग्निजबल) कहा जाता है यदि यह लैंग्वेज के [[वर्णमाला (कंप्यूटर विज्ञान)|एल्फाबेट (कंप्यूटर विज्ञान)]] के सभी संभावित शब्दों के [[सेट (गणित)]] में रिकर्सिवली एन्युमरेबल सेट है अर्थात्, यदि कोई [[ट्यूरिंग मशीन]] उपस्थित है जो लैंग्वेज के सभी वैलिड स्ट्रिंग की गणना करेगी। 

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

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

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

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

सभी [[नियमित भाषा|रेगुलर लैंग्वेज]], [[संदर्भ-मुक्त व्याकरण|कॉन्टेक्स्ट-फ्री]], [[संदर्भ-संवेदनशील भाषा|कॉन्टेक्स्ट-सेंसिटिव]] और रिकर्सिव लैंग्वेज रिकर्सिवली एन्युमरेबल हैं।

पोस्ट के प्रमेय से पता चलता है कि '''RE''' अपने [[पूरक (जटिलता)|कम्प्लीमेंट]] co-RE, के साथ [[अंकगणितीय पदानुक्रम|अंकगणितीय]] [[चॉम्स्की पदानुक्रम|हायरार्की]] के प्रथम स्तर के अनुरूप है।

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

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

* [[पोस्ट पत्राचार समस्या|पोस्ट करेस्पॉन्डेंस प्रॉब्लम]]
*[[मृत्यु दर (कम्प्यूटेबिलिटी सिद्धांत)|मोर्टेलिटी (कम्प्यूटेबिलिटी सिद्धांत)]]
*[[निर्णय समस्या|एंट्सचीडुंग्स समस्या]]

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

* L का द क्लीन स्टार <math>L^*</math> 
* L और P का संयोजन <math>L \circ P</math> 
* [[संघ (सेट सिद्धांत)]] <math>L \cup P</math>
* [[प्रतिच्छेदन (सेट सिद्धांत)|प्रतिच्छेदन(सेट सिद्धांत)]] <math>L \cap P</math>.

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

== यह भी देखें ==
*कंप्यूटेबली एन्युमरेबल सेट
*रिकर्शन

==संदर्भ==
* Sipser, M. (1996), ''Introduction to the Theory of Computation'', [[PWS Publishing Co]].
* Kozen, D.C. (1997), ''Automata and Computability'', [[Springer-Verlag|Springer]].


==बाहरी संबंध==
* {{CZoo|Class RE|R#re}}
* [http://www.cs.colostate.edu/~massey/Teaching/cs301/RestrictedAccess/Slides/301lecture23.pdf Lecture slides]

{{Formal languages and grammars}}

[[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:गणना का सिद्धांत]]