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

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

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

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

परिभाषाएँ

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

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

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

पोस्ट के प्रमेय से पता चलता है कि 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.

बाहरी संबंध

• Complexity Zoo: Class RE
• Lecture slides