समवर्ती गणना में अनिश्चितता

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

तर्क प्रोग्रामिंग की एक अनुमानित सीमा

पैट्रिक जे. हेस [1973] ने तर्क दिया कि गणना और कटौती की प्रक्रियाओं के बीच जो सामान्य तीव्र अंतर किया जाता है, वह भ्रामक है। रॉबर्ट कोवाल्स्की ने यह थीसिस विकसित की कि गणना को कटौती द्वारा समाहित किया जा सकता है और अनुमोदन के साथ उद्धृत किया जा सकता है कि गणना नियंत्रित कटौती है। जिसका श्रेय उन्होंने प्रोलॉग के प्रारंभिक इतिहास पर अपने 1988 के पेपर में हेस को दिया। कोवाल्स्की और हेस के विपरीत, कार्ल हेविट ने दावा किया कि तार्किक कटौती खुली प्रणालियों में समवर्ती गणना करने में असमर्थ थी.

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

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

आगमन क्रम अनिश्चितता

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

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

एक्टर्स का गणितीय सिद्धांत इस बारे में क्या कहता है? एक बंद प्रणाली को उस प्रणाली के रूप में परिभाषित किया जाता है जो बाहर से संचार नहीं करती है। अभिनेता मॉडल सिद्धांत प्रतिनिधित्व प्रमेय [हेविट 2007] का उपयोग करके एक बंद अभिनेता प्रणाली की सभी संभावित गणनाओं को निम्नानुसार चित्रित करने का साधन प्रदान करता है: <ब्लॉककोट>

एक बंद प्रणाली द्वारा दर्शाया गया गणितीय संकेत S नामक आरंभिक व्यवहार से उत्तरोत्तर बेहतर सन्निकटन बनाकर पाया जाता है ⊥_S व्यवहार सन्निकटन फ़ंक्शन का उपयोग करना progression_S के लिए एक संकेत (अर्थ) का निर्माण करना S निम्नलिखित नुसार:

$\mathbf {Denote} _{\mathtt {S}}\equiv \lim _{i\to \infty }\mathbf {progression} _{{\mathtt {S}}^{i}}(\bot _{\mathtt {S}})$

</ब्लॉककोट> इस प्रकार, का व्यवहार S को इसके सभी संभावित व्यवहारों के संदर्भ में गणितीय रूप से चित्रित किया जा सकता है (जिनमें असीमित गैर-नियतिवाद शामिल है)।

इसलिए गणितीय तर्क एक बंद एक्टर सिस्टम की सभी संभावित गणनाओं को चिह्नित (कार्यान्वयन के विपरीत) कर सकता है।

जानकारी की कमी के कारण तर्क की एक सीमा

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

प्रोलॉग-जैसी समवर्ती प्रणालियों को गणितीय तर्क पर आधारित होने का दावा किया गया था

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

कार्ल हेविट और गुल आगा [1991] ने तर्क दिया कि ये प्रोलॉग-जैसी समवर्ती प्रणालियाँ न तो निगमनात्मक थीं और न ही तार्किक: अभिनेता मॉडल की तरह, प्रोलॉग-जैसी समवर्ती प्रणालियाँ संदेश पारित करने पर आधारित थीं और परिणामस्वरूप समान अनिश्चितता के अधीन थीं।

तार्किक संचालन और सिस्टम दक्षता

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

गणना के अन्य मॉडलों में अनिश्चितता

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

यह भी देखें

• क्वांटम कम्प्यूटिंग
• यादृच्छिक एल्गोरिथ्म
• गैर-नियतात्मक ट्यूरिंग मशीन

संदर्भ

• Carl Hewitt What is computation? Actor Model versus Turing's Model in A Computable Universe: Understanding Computation & Exploring Nature as Computation. Dedicated to the memory of Alan M. Turing on the 100th anniversary of his birth. Edited by Hector Zenil. World Scientific Publishing Company. 2012
• Carl Hewitt. PLANNER: A Language for Proving Theorems in Robots IJCAI 1969.
• Carl Hewitt. Procedural Embedding of Knowledge In Planner IJCAI 1971.
• Carl Hewitt, Peter Bishop and Richard Steiger. A Universal Modular Actor Formalism for Artificial Intelligence IJCAI 1973.
• Robert Kowalski Predicate Logic as Programming Language Memo 70, Department of Artificial Intelligence, Edinburgh University. 1973.
• Pat Hayes. Computation and Deduction Mathematical Foundations of Computer Science: Proceedings of Symposium and Summer School, Štrbské Pleso, High Tatras, Czechoslovakia, September 3–8, 1973.
• Carl Hewitt and Henry Baker Laws for Communicating Parallel Processes IFIP-77, August 1977.
• Carl Hewitt. Viewing Control Structures as Patterns of Passing Messages Journal of Artificial Intelligence. June 1977.
• Henry Baker. Actor Systems for Real-Time Computation MIT EECS Doctoral Dissertation. January 1978.
• Bill Kornfeld and Carl Hewitt. The Scientific Community Metaphor IEEE Transactions on Systems, Man, and Cybernetics. January 1981.
• Will Clinger. Foundations of Actor Semantics MIT Mathematics Doctoral Dissertation. June 1981.
• Carl Hewitt. The Challenge of Open Systems Byte Magazine. April 1985. Reprinted in The foundation of artificial intelligence–a sourcebook Cambridge University Press. 1990.
• Gul Agha. Actors: A Model of Concurrent Computation in Distributed Systems Doctoral Dissertation. MIT Press. 1986.
• Robert Kowalski. The limitation of logic Proceedings of the 1986 ACM 14th Annual Conference on Computer science.
• Ehud Shapiro (Editor). Concurrent Prolog MIT Press. 1987.
• Robert Kowalski. The Early Years of Logic Programming Communications of the ACM. January 1988.
• Ehud Shapiro. The family of concurrent logic programming languages ACM Computing Surveys. September 1989.
• Carl Hewitt and Gul Agha. Guarded Horn clause languages: are they deductive and Logical? International Conference on Fifth Generation Computer Systems, Ohmsha 1988. Tokyo. Also in Artificial Intelligence at MIT, Vol. 2. MIT Press 1991.
• Carl Hewitt. *Carl Hewitt. The repeated demise of logic programming and why it will be reincarnated What Went Wrong and Why: Lessons from AI Research and Applications. Technical Report SS-06-08. AAAI Press. March 2006.

बाहरी संबंध

• Hewitt, Meijer and Szyperski: The Actor Model (everything you wanted to know, but were afraid to ask) Microsoft Channel 9. April 9, 2012.