रिकर्सिव लैंग्वेज

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

निर्णायकता की अवधारणा को संगणना के अन्य मॉडलों तक बढ़ाया जा सकता है। उदाहरण के लिए, कोई गैर-नियतात्मक ट्यूरिंग मशीन पर निर्णायक लैंग्वेजओं की बात कर सकता है। इसलिए, जब भी कोई अस्पष्टता संभव हो, रिकर्सिव लैंग्वेज के लिए प्रयुक्त पर्यायवाची ट्यूरिंग-निर्णायक लैंग्वेज है, न कि उपस्थित निर्णायक हैं।

सभी रिकर्सिव लैंग्वेजओं के वर्ग को अधिकांशतः R (जटिलता) कहा जाता है, चूँकि इस नाम का उपयोग वर्ग RP (जटिलता) के लिए भी किया जाता है।

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

परिलैंग्वेजएँ

रिकर्सिव लैंग्वेज की अवधारणा के लिए दो समतुल्य प्रमुख परिलैंग्वेजएँ हैं:

1. एक रिकर्सिव औपचारिक लैंग्वेज औपचारिक लैंग्वेज के वर्णमाला पर सभी संभावित शब्दों के सेट (गणित) में एक रिकर्सिव सेट सबसेट है।
2. एक रिकर्सिव लैंग्वेज एक औपचारिक लैंग्वेज है जिसके लिए एक ट्यूरिंग मशीन उपस्थित है, जो किसी भी परिमित इनपुट शाब्दिक स्ट्रिंग के साथ प्रस्तुत की जाती है, यदि स्ट्रिंग लैंग्वेज में है, तो रुक जाती है और स्वीकार कर लेती है, और अन्यथा रुक जाती है और अस्वीकार कर देती है। ट्यूरिंग मशीन सदैव रुकती है: इसे एक ऐसी मशीन के रूप में जाना जाता है जो सदैव रुकती है और कहा जाता है कि यह रिकर्सिव लैंग्वेज तय करती है।

दूसरी परिलैंग्वेज के अनुसार, किसी भी निर्णय समस्या को उसके लिए एक कलन विधि प्रदर्शित करके निर्णायक दिखाया जा सकता है जो सभी इनपुट पर समाप्त हो जाता है। एक अनिर्णीत समस्या एक ऐसी समस्या है जो निर्णय लेने योग्य नहीं है।

उदाहरण

जैसा कि ऊपर उल्लेख किया गया है, प्रत्येक संदर्भ-संवेदनशील लैंग्वेज रिकर्सिव है। इस प्रकार, रिकर्सिव लैंग्वेज का एक सरल उदाहरण समुच्चय L={abc, aabbcc, aaabbbccc, ...};

अधिक औपचारिक रूप से, सेट

$L=\{\,w\in \{a,b,c\}^{*}\mid w=a^{n}b^{n}c^{n}{\mbox{ for some }}n\geq 1\,\}$ संदर्भ-संवेदनशील है और इसलिए रिकर्सिव है।

निर्णायक लैंग्वेजओं के उदाहरण जो संदर्भ-संवेदनशील नहीं हैं, उनका वर्णन करना अधिक कठिन है। इस प्रकार के एक उदाहरण के लिए, गणितीय तर्क के साथ कुछ परिचित होना आवश्यक है: प्रेस्बर्गर अंकगणित जोड़ के साथ (किन्तु गुणा के बिना) प्राकृतिक संख्याओं का प्रथम-क्रम सिद्धांत है। चूँकि प्रेस्बर्गर अंकगणित में फर्स्ट-ऑर्डर_लॉजिक फॉर्मूला|सुव्यवस्थित सूत्रों का सेट संदर्भ-मुक्त है, प्रेस्बर्गर अंकगणित में सही कथनों के सेट को स्वीकार करने वाली प्रत्येक नियतात्मक ट्यूरिंग मशीन में कम से कम सबसे खराब स्थिति वाला रनटाइम होता है $2^{2^{cn}}$, कुछ निरंतर सी> 0 के लिए (फिशर & राबिन 1974). यहाँ, n दिए गए सूत्र की लंबाई को दर्शाता है। चूंकि प्रत्येक संदर्भ-संवेदनशील लैंग्वेज को एक रैखिक बाउंडेड ऑटोमेटन द्वारा स्वीकार किया जा सकता है, और इस प्रकार के एक ऑटोमेटन को नियतात्मक ट्यूरिंग मशीन द्वारा सिम्युलेटेड किया जा सकता है, जिसमें सबसे खराब समय चलने वाला समय होता है। $c^{n}$ कुछ निरंतर सी के लिए , प्रेस्बर्गर अंकगणित में मान्य सूत्रों का सेट संदर्भ-संवेदनशील नहीं है। सकारात्मक पक्ष पर, यह ज्ञात है कि एक नियतात्मक ट्यूरिंग मशीन है जो n में सबसे अधिक त्रिगुणात्मक घातीय समय पर चल रही है जो प्रेस्बर्गर अंकगणित में सही सूत्रों का सेट तय करती है (ओपन 1978). इस प्रकार, यह एक ऐसी लैंग्वेज का उदाहरण है जो निर्णायक है किन्तु संदर्भ-संवेदनशील नहीं है।

क्लोजर गुण

रिकर्सिव लैंग्वेजएं निम्नलिखित संक्रियाओं के अंतर्गत क्लोजर (गणित) हैं। अर्थात्, यदि L और P दो रिकर्सिव लैंग्वेजएँ हैं, तो निम्नलिखित लैंग्वेजएँ भी रिकर्सिव हैं:

• क्लेन स्टार $L^{*}$
• इमेज φ(L) एक होमोमोर्फिज्म के अनुसार औपचारिक लैंग्वेज सिद्धांत ई-फ्री होमोमोर्फिज्म φ
• संधि $L\circ P$
• संगठन $L\cup P$
• चौराहा $L\cap P$
• का पूरक $L$
• निर्धारित अंतर $L-P$

अंतिम संपत्ति इस तथ्य से अनुसरण करती है कि सेट अंतर को प्रतिच्छेदन और पूरक के रूप में व्यक्त किया जा सकता है।

यह भी देखें

• रिकर्सिव गणना योग्य लैंग्वेज
• संगणनीय सेट
• पुनरावर्तन

संदर्भ

• Michael Sipser (1997). "Decidability". Introduction to the Theory of Computation. PWS Publishing. pp. 151–170. ISBN 978-0-534-94728-6.
• Chomsky, Noam (1959). "On certain formal properties of grammars". Information and Control. 2 (2): 137–167. doi:10.1016/S0019-9958(59)90362-6.
• Fischer, Michael J.; Rabin, Michael O. (1974). "Super-Exponential Complexity of Presburger Arithmetic". Proceedings of the SIAM-AMS Symposium in Applied Mathematics. 7: 27–41.
• Oppen, Derek C. (1978). "A 2^22pn Upper Bound on the Complexity of Presburger Arithmetic". J. Comput. Syst. Sci. 16 (3): 323–332. doi:10.1016/0022-0000(78)90021-1.