डोमेन सिद्धांत

From Vigyanwiki
Revision as of 13:23, 1 May 2023 by Manidh (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

प्रेरणा और अंतर्ज्ञान

डोमेन के अध्ययन के लिए प्राथमिक प्रेरणा, जिसे 1960 के दशक के अंत में दाना स्कॉट द्वारा प्रारंभ किया गया था, लैम्ब्डा कैलकुलस के अर्थ संबंधी शब्दार्थ की खोज थी। इस औपचारिकता में, भाषा में कुछ नियमो द्वारा निर्दिष्ट कार्यों पर विचार किया जाता है। विशुद्ध रूप से वाक्य - विन्यास विधि से, कोई सरल कार्यों से उन कार्यों तक जा सकता है जो अन्य कार्यों को उनके इनपुट तर्कों के रूप में लेते हैं। इस औपचारिकता में उपलब्ध वाक्यात्मक परिवर्तन का फिर से उपयोग करके, कोई तथाकथित निश्चित-बिंदु संयोजक प्राप्त कर सकता है (जिनमें से सबसे प्रसिद्ध निश्चित-बिंदु संयोजक या Y संयोजक है); ये, परिभाषा के अनुसार, संपत्ति है कि f('Y'(f)) = 'Y'(f) सभी कार्यों के लिए f है ।

इस तरह के सांकेतिक शब्दार्थ को तैयार करने के लिए, सबसे पहले लैम्ब्डा कैलकुलस के लिए मॉडल बनाने की प्रयास की जा सकती है, जिसमें प्रत्येक लैम्ब्डा शब्द के साथ वास्तविक (कुल) कार्य जुड़ा होता है। इस तरह का मॉडल लैम्ब्डा कैलकुलस के बीच विशुद्ध रूप से वाक्यात्मक प्रणाली और लैम्ब्डा कैलकुलस के बीच ठोस गणितीय कार्यों में हेरफेर करने के लिए सांकेतिक प्रणाली के रूप में लिंक को औपचारिक रूप देगा। संयोजक कैलकुलस ऐसा मॉडल है। चूंकि , संयोजक कैलकुलस के तत्व कार्य से कार्य तक के कार्य हैं; लैम्ब्डा कैलकुस के एक मॉडल के तत्वों के लिए इच्छानुसार से डोमेन और सीमा के होने के लिए वे केवल आंशिक कार्यों के सच्चे कार्य नहीं हो सकते थे।

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

लैम्ब्डा कैलकुस के लिए मॉडल खोजने का महत्वपूर्ण कदम केवल उन कार्यों (आंशिक रूप से आदेशित समूह पर) पर विचार करना है जो कम से कम निश्चित बिंदुओं की आश्वासन देते हैं। इन कार्यों का समूह , उचित क्रम के साथ, सिद्धांत के अर्थ में फिर से डोमेन है। किंतु सभी उपलब्ध कार्यों के उपसमुच्चय के लिए प्रतिबंध का और बड़ा लाभ है: ऐसे डोमेन प्राप्त करना संभव है जिनमें उनके स्वयं के कार्य स्थान होते हैं, अर्थात किसी को ऐसे कार्य मिलते हैं जिन्हें स्वयं पर प्रयुक्त किया जा सकता है।

इन वांछनीय गुणों के अतिरिक्त , डोमेन सिद्धांत भी आकर्षक सहज व्याख्या की अनुमति देता है। जैसा ऊपर बताया गया है, गणना के डोमेन सदैव आंशिक रूप से आदेशित होते हैं। यह क्रम सूचना या ज्ञान के पदानुक्रम का प्रतिनिधित्व करता है। क्रम के अंदर तत्व जितना अधिक होता है, उतना ही अधिक विशिष्ट होता है और इसमें अधिक जानकारी होती है। निचले तत्व अधूरे ज्ञान या मध्यवर्ती परिणामों का प्रतिनिधित्व करते हैं।

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

औपचारिक परिभाषाओं के लिए गाइड

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

अभिसरण विनिर्देशों के रूप में निर्देशित समूह

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

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

अब, अनुक्रमों के स्थिति में, हम निर्देशित समूह की सीमा में रूचि रखते हैं। ऊपर जो कहा गया था, उसके अनुसार, यह ऐसा तत्व होगा जो सूचना का सबसे सामान्य टुकड़ा है जो निर्देशित समूह के सभी तत्वों की जानकारी का विस्तार करता है, जिससे वह अनूठा तत्व जिसमें ठीक वही जानकारी होती है जो निर्देशित समूह में उपस्थित थी, और अधिक कुछ नहीं। आदेश सिद्धांत की औपचारिकता में, यह निर्देशित समूह की 'कम से कम ऊपरी सीमा' है। अनुक्रम की सीमा के स्थिति में, निर्देशित समूह की कम से कम ऊपरी सीमा सदैव उपस्थित नहीं होती है।

स्वाभाविक रूप से, किसी की अभिकलन के उन डोमेन में विशेष रुचि होती है जिसमें सभी सुसंगत विनिर्देश अभिसरण करते हैं, अर्थात उन क्रमों में जिनमें सभी निर्देशित समूहो की ऊपरी सीमा सबसे कम होती है। यह गुण 'निर्देशित पूर्ण आंशिक आदेश , या संक्षेप में 'dcpo' की श्रेणी को परिभाषित करता है। किंतु , डोमेन थ्योरी के अधिकांश विचार केवल उन आदेशों पर विचार करते हैं जो कम से कम निर्देशित पूर्ण हैं।

अपूर्ण ज्ञान का प्रतिनिधित्व करने वाले आंशिक रूप से निर्दिष्ट परिणामों के अंतर्निहित विचार से, अन्य वांछनीय गुण प्राप्त होता है: 'न्यूनतम तत्व' का अस्तित्व ऐसा तत्व मॉडल जो बिना किसी सूचना के स्थान करता है - वह स्थान जहाँ अधिकांश संगणनाएँ प्रारंभ होती हैं। इसे संगणना के आउटपुट के रूप में भी माना जा सकता है जो बिल्कुल भी परिणाम नहीं देता है।

संगणना और डोमेन

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

पूर्ण आंशिक आदेश के साथ करते समय, कोई यह भी चाह सकता है कि संगणना निर्देशित समूह की सीमा के गठन के साथ संगत हो। औपचारिक रूप से, इसका अर्थ है कि, कुछ कार्य f के लिए, निर्देशित समूह D की छवि f(D) (अर्थात 'के प्रत्येक तत्व की छवियों का समूह 'D) फिर से निर्देशित है और कम से कम ऊपरी बाउंड के रूप में 'D' के कम से कम ऊपरी बाउंड की छवि है। कोई यह भी कह सकता है कि एफ लिमिट-प्रिजर्विंग कार्य (क्रम थ्योरी) निर्देशित सुप्रीमा यह भी ध्यान दें कि, दो तत्वों के निर्देशित समूहो पर विचार करके, इस तरह के कार्य को मोनोटोनिक भी होना चाहिए। ये गुण स्कॉट-निरंतर कार्य की धारणा को जन्म देते हैं। चूंकि यह प्रायः अस्पष्ट नहीं होता है इसलिए कोई भी 'निरंतर कार्यों' की बात कर सकता है।

सन्निकटन और परिमितता

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

यदि कोई इस तरह के संबंध को मॉडल करना चाहता है, तो पहले डोमेन के आदेश ≤ के साथ प्रेरित सख्त आदेश <पर विचार करना चाह सकता है। चूंकि , कुल क्रम के स्थिति में यह उपयोगी धारणा है, किंतु आंशिक रूप से क्रम किए गए समूह के स्थिति में यह हमें बहुत कुछ नहीं बताता है। समूह के समावेशन-आदेशों को फिर से ध्यान में रखते हुए, समूह पहले से ही दूसरे की तुलना में सख्ती से छोटा है, संभवतः अनंत, समूह यदि इसमें केवल कम तत्व होता है। किंतु , संभवतः ही कोई इस बात से सहमत होगा कि यह बहुत सरल होने की धारणा को दर्शाता है।

वे-नीचे संबंध

एक अधिक विस्तृत दृष्टिकोण सन्निकटन के तथाकथित क्रम की परिभाषा की ओर ले जाता है, जिसे अधिक सुझावात्मक रूप से नीचे का रास्ता भी कहा जाता है। तत्व x तत्व y के नीचे है, यदि, प्रत्येक निर्देशित समूह D के लिए सर्वोच्चता के साथ ऐसा है

,

D में कुछ तत्व d है जैसे कि

.

फिर कोई यह भी कहता है कि x, y का अनुमान लगाता है और लिखता है

.

इसका अर्थ यह है

,

चूंकि सिंगलटन समूह {y} निर्देशित है। उदाहरण के लिए, समुच्चयों के क्रम में, अनंत समुच्चय अपने किसी परिमित उपसमुच्चय से कहीं ऊपर होता है। दूसरी ओर, परिमित समूहो के निर्देशित समूह (वास्तव में, कुल क्रम या चेन) पर विचार करें

चूँकि इस श्रृंखला का सर्वोच्च सभी प्राकृतिक संख्याओं N का समुच्चय है, इससे पता चलता है कि कोई भी अनंत समुच्चय N से नीचे नहीं है।

चूंकि , किसी तत्व के नीचे होना 'सापेक्ष' धारणा है और अकेले तत्व के बारे में बहुत कुछ नहीं बताता है। उदाहरण के लिए, कोई आदेश -सैद्धांतिक विधि से सीमित समूहो को चित्रित करना चाहता है, किंतु अनंत समूह भी किसी अन्य समूह से नीचे हो सकते हैं। इन परिमित तत्वों x का विशेष गुण यह है कि ये अपने सामान्य से अधिक नीचे हैं, अर्थात्

.

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

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

डोमेन के आधार

पिछले विचार और सवाल उठाते हैं: क्या यह आश्वासन देना संभव है कि किसी डोमेन के सभी तत्वों को बहुत सरल तत्वों की सीमा के रूप में प्राप्त किया जा सकता है? यह अभ्यास में अधिक प्रासंगिक है, क्योंकि हम अनंत वस्तुओं की गणना नहीं कर सकते हैं, किंतु फिर भी हम उन्हें इच्छानुसार से समीप लाने की उम्मीद कर सकते हैं।

अधिक सामान्यतः, हम तत्वों के निश्चित उपसमुच्चय को सीमित करना चाहते हैं क्योंकि अन्य सभी तत्वों को कम से कम ऊपरी सीमा के रूप में प्राप्त करने के लिए पर्याप्त होना चाहिए। इसलिए, पॉसेट P के आधार को P के उपसमुच्चय B के रूप में परिभाषित करता है, जैसे कि, P में प्रत्येक x के लिए, का समूह B में तत्व जो x से नीचे हैं, में सुप्रीमम x के साथ निर्देशित समूह है। पोसेट P सतत पॉजिट है यदि इसका कुछ आधार है। विशेष रूप से, P' ही इस स्थिति में आधार है। कई अनुप्रयोगों में, अध्ययन के मुख्य उद्देश्य के रूप में निरंतर (d) सीपीओ तक सीमित रहता है।

अंत में, आंशिक रूप से आदेशित समूह पर और भी शसक्त प्रतिबंध 'परिमित' तत्वों के आधार के अस्तित्व की आवश्यकता के द्वारा दिया जाता है। ऐसे पॉसेट को बीजगणितीय पॉसेट कहा जाता है। सांकेतिक शब्दार्थ के दृष्टिकोण से, बीजगणितीय पॉसेट विशेष रूप से अच्छी तरह से व्यवहार किए जाते हैं, क्योंकि वे परिमित लोगों तक सीमित होने पर भी सभी तत्वों के सन्निकटन की अनुमति देते हैं। जैसा कि पहले उल्लेख किया गया है, प्रत्येक परिमित तत्व मौलिक अर्थ में परिमित नहीं है और यह अच्छी तरह से हो सकता है कि परिमित तत्व अगणनीय समूह का निर्माण करते हैं।

किंतु , कुछ स्थिति में, पोसेट का आधार गणनीय होता है। इस स्थिति में, ω-निरंतर पोसेट की बात करता है। इसलिए , यदि गणनीय आधार में पूरी तरह से परिमित तत्व होते हैं, तो हम आदेश प्राप्त करते हैं जो ω-बीजगणितीय है।

विशेष प्रकार के डोमेन

एक डोमेन का साधारण विशेष स्थिति प्राथमिक या समतल डोमेन के रूप में जाना जाता है। इसमें अतुलनीय तत्वों का समूह होता है, जैसे कि पूर्णांक, साथ ही निचला तत्व जो अन्य सभी तत्वों से छोटा माना जाता है।

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

आदेशों के इन सभी वर्गों को dcpos की विभिन्न श्रेणी (गणित) में डाला जा सकता है, ऐसे कार्यों का उपयोग करके जो मोनोटोन, स्कॉट-निरंतर, या आकारिकी के रूप में और भी अधिक विशिष्ट हैं। अंत में, ध्यान दें कि 'डोमेन' शब्द अपने सामान्य में स्पष्ट नहीं है और इस प्रकार इसका उपयोग केवल संक्षिप्त नाम के रूप में किया जाता है जब औपचारिक परिभाषा पहले दी गई हो या जब विवरण अप्रासंगिक हों।

महत्वपूर्ण परिणाम

एक पॉसेट D डीसीपीओ है यदि और केवल यदि D में प्रत्येक श्रृंखला में सर्वोच्चता है। ('यदि ' दिशा पसंद के स्वयंसिद्ध पर निर्भर करती है।)

यदि डोमेन D पर एफ सतत कार्य है तो इसका कम से कम निश्चित बिंदु है, जिसे कम से कम तत्व ⊥ पर f के सभी परिमित पुनरावृत्तियों के कम से कम ऊपरी सीमा के रूप में दिया गया है:

.

यह क्लीन नियत-बिंदु प्रमेय है। h> प्रतीक जुड़ें और मिलें है।

सामान्यीकरण

  • "सिंथेटिक डोमेन सिद्धांत". CiteSeerX 10.1.1.55.903. {{cite journal}}: Cite journal requires |journal= (help)
  • सामयिक डोमेन सिद्धांत
  • एक निरंतरता स्थान मीट्रिक रिक्त स्थान और poset का सामान्यीकरण है, जिसका उपयोग मीट्रिक रिक्त स्थान और डोमेन की धारणाओं को एकीकृत करने के लिए किया जा सकता है।

यह भी देखें

अग्रिम पठन


बाहरी संबंध