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

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

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

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

परिभाषाएँ

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

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

सभी नियमित भाषा, प्रसंग निरपेक्ष भाषा, प्रसंग सापेक्ष और पुनरावर्ती भाषाएँ पुनरावर्ती रूप से गणना योग्य हैं।

पोस्ट के प्रमेय से पता चलता है कि आरई अपने पूरक (जटिलता) सह-आरई के साथ अंकगणितीय पदानुक्रम के प्रथम स्तर के अनुरूप है।

उदाहरण

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

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

• समान स्थिति समस्या
• मृत्यु दर (कम्प्यूटेबिलिटी सिद्धांत)
• एंट्सचीडुंग्स समस्या

संवृत्त गुण

पुनरावर्ती गणना योग्य भाषाएँ (आरईएल) निम्नलिखित परिचालनों के अंतर्गत संवृत्त हैं। अर्थात्, यदि 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