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

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

औपचारिक भाषाओं के चॉम्स्की पदानुक्रम में पुनरावर्ती रूप से गणना योग्य गणनीय भाषाओं को टाइप-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