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

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

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

सभी पुनरावर्ती रूप से गणना योग्य भाषाओं के वर्ग को आरई (जटिलता) कहा जाता है।

परिभाषाएँ

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

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

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

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

उदाहरण

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

कुछ अन्य पुनरावर्ती रूप से गणना योग्य भाषाएँ जो पुनरावर्ती नहीं हैं उनमें शामिल हैं:

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

बंद गुण

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

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

पुनरावर्ती रूप से गणना योग्य भाषाएँ सेट अंतर या पूरकता के अंतर्गत बंद नहीं होती हैं। सेट अंतर $L-P$ यदि पुनरावर्ती रूप से गणना योग्य है $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