Π-कैलकुलस

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

अनौपचारिक परिभाषा

π-कैलकुलस प्रक्रिया गणना के समूह एवं समवर्ती गणना के गुणों का वर्णन और विश्लेषण करने के लिए गणितीय औपचारिकताओं से संबंधित है। वास्तव में π-कैलकुलस, λ-कैलकुलस की तरह इतना न्यूनतम है कि इसमें संख्या, बूलियन, डेटा संरचना, चर, फ़ंक्शन या यहां तक कि सामान्य नियंत्रण प्रवाह विवरण जैसे मूल सम्मिलित नहीं हैं (जैसे, if-then-else, while).

प्रक्रिया निर्माण

π-कैलकुलस का केंद्र इसके नाम की धारणा है। कैलकुलस की सरलता दोहरी भूमिका में निहित है जिसे नाम संपर्क माध्यमों और चरों के रूप में निभाते हैं।

कैलकुलस में उपलब्ध प्रक्रिया निर्माण निम्नलिखित हैं (निम्न अनुभाग में सटीक परिभाषा दी गई है):

• समवर्ती, लिखित $P\mid Q$, जहाँ $P$ और $Q$ दो प्रक्रियाएं या सूत्र समवर्ती रूप से निष्पादित होते हैं।
• संचार, जहाँ
  • इनपुट उपसर्ग $c\left(x\right).P$ एक संदेश की प्रतीक्षा करने की प्रक्रिया है जिसे $P$ के रूप में आगे बढ़ने से पहले $c$ नाम के संचार चैनल पर भेजा गया था जोकि नाम x के लिए प्राप्त नाम को बाध्य करता है। सामान्य रूप से यह मॉडल या तो नेटवर्क से संचार की अपेक्षा करने वाली प्रक्रिया या लेबल c है जो goto c संचालन द्वारा केवल एक बार प्रयोग करने योग्य होती है।
  • आउटपुट उपसर्ग ${\overline {c}}\langle y\rangle .P$ वर्णन करता है कि $P$ के रूप में आगे बढ़ने से पहले नाम $y$ चैनल $c$ पर उत्सर्जित किया जाता है। सामान्य रूप से यह मॉडल या तो नेटवर्क पर एक संदेश भेज रहा है या goto c संचालन।
• प्रतिकृति, लिखित $!\,P$, जिसे एक ऐसी प्रक्रिया के रूप में देखा जा सकता है जो सदैव $P$ की एक नई प्रतिलिपि बना सकती है। सामान्य रूप से यह मॉडल या तो एक नेटवर्क सेवा या एक लेबल c है जो किसी भी संख्या में goto c संचालन की प्रतीक्षा कर रहा है।
• नए नाम $\left(\nu x\right)P$ का निर्माण हुआ जिसे नई स्थिरांक आवंटित करने वाली प्रक्रिया x के रूप में देखा जा सकता है $P$ के साथ π-calculus के स्थिरांक केवल उनके नाम से परिभाषित होते हैं और सदैव संचार चैनल होते हैं। किसी प्रक्रिया में नए नाम के सृजन को प्रतिबंध भी कहा जाता है।
• शून्य प्रक्रिया, लिखित रूप में $0$ एक ऐसी प्रक्रिया है जिसका निष्पादन पूरा हो गया है और रुक गया है।

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

एक छोटा सा उदाहरण

निम्नलिखित प्रक्रिया का एक छोटा उदाहरण है जिसमें तीन समानांतर घटक होते हैं। x नाम का चैनल केवल पहले दो घटकों द्वारा जाना जाता है।

${\begin{aligned}(\nu x)&\;(\;{\overline {x}}\langle z\rangle .\;0\\&\;|\;x(y).\;{\overline {y}}\langle x\rangle .\;x(y).\;0\;)\\&\;|\;z(v).\;{\overline {v}}\langle v\rangle .0\end{aligned}}$

पहले दो घटक चैनल x पर संचार करने में सक्षम हैं और y नाम के लिए z बाध्य हो जाता है इसलिए प्रक्रिया में अगला कदम है।

${\begin{aligned}(\nu x)&\;(\;0\\&\;|\;{\overline {z}}\langle x\rangle .\;x(y).\;0\;)\\&\;|\;z(v).\;{\overline {v}}\langle v\rangle .\;0\end{aligned}}$

ध्यान रहे कि शेष y प्रभावित नहीं होता है क्योंकि इसे आंतरिक सीमा में परिभाषित किया गया है। दूसरा और तीसरा समानांतर घटक अब चैनल नाम पर संवाद कर सकते हैं जहाँ z और v नाम के लिए x बाध्य हो जाता है। प्रक्रिया का अगला चरण अब है

${\begin{aligned}(\nu x)&\;(\;0\\&\;|\;x(y).\;0\\&\;|\;{\overline {x}}\langle x\rangle .\;0\;)\end{aligned}}$

ध्यान दें कि स्थानीय नाम के पश्चात x का उत्पादन किया गया है एवं x का क्षेत्र तीसरे घटक को भी कवर करने के लिए बढ़ाया गया है। अंत में x चैनल x नाम भेजने के लिए उपयोग किया जा सकता है जबकि उसके बाद सभी समवर्ती क्रियान्वित प्रक्रियाएँ रुक गई हैं

${\begin{aligned}(\nu x)&\;(\;0\\&\;|\;0\\&\;|\;0\;)\end{aligned}}$

औपचारिक परिभाषा

शब्दावली

माना कि Χ वस्तुओं का एक सेट है जिसे नाम कहा जाता है। π-कैलकुलस के लिए सार वाक्य रचना निम्नलिखित BNF व्याकरण से बनाया गया है (जहाँ x और y, Χ से कोई नाम हैं):

${\begin{aligned}P,Q::=&\;x(y).P\,\,\,\,\,&{\text{Receive on channel }}x{\text{, bind the result to }}y{\text{, then run }}P\\&\;|\;{\overline {x}}\langle y\rangle .P\,\,\,\,\,&{\text{Send the value }}y{\text{ over channel }}x{\text{, then run }}P\\&\;|\;P|Q\,\,\,\,\,\,\,\,\,&{\text{Run }}P{\text{ and }}Q{\text{ simultaneously}}\\&\;|\;(\nu x)P\,\,\,&{\text{Create a new channel }}x{\text{ and run }}P\\&\;|\;!P\,\,\,&{\text{Repeatedly spawn copies of }}P\\&\;|\;0&{\text{Terminate the process}}\end{aligned}}$

नीचे दिए गए ठोस रचनाक्रम में उपसर्ग समानांतर संरचना (|) की तुलना में अधिक कसकर बांधते हैं जिन्हें कोष्ठकों को अलग करने के लिए उपयोग किया जाता है।

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

Construct	Free names
$0$	None
${\overline {a}}\langle x\rangle .P$	a; x; P के सभी मुक्त नाम
$a(x).P$	a; x को छोड़कर P के सभी मुक्त नाम
$P|Q$	P और Q के सभी मुक्त नाम
$(\nu x)P$	x को छोड़कर P के सभी मुक्त नाम
$!P$	P के सभी मुक्त नाम

संरचनात्मक सर्वांगसमता

न्यूनीकरण शब्दार्थ और लेबल संक्रमण शब्दार्थ दोनों का केंद्र संरचनात्मक सर्वांगसमता की धारणा है। दो प्रक्रियाएं संरचनात्मक रूप से सर्वांगसम होती हैं यदि वे संरचना के समान हों। विशेष रूप से समानांतर रचना विनिमेय और साहचर्य है।

अधिक सटीक रूप से संरचनात्मक अनुरूपता को कम से कम समानता संबंध के रूप में परिभाषित किया जाता है जो प्रक्रिया के निर्माण और संतोषजनक द्वारा संरक्षित होता है:

अल्फा-रूपांतरण:

• $P\equiv Q$ यदि $P$ में एक या एक से अधिक बाध्य नामों का नाम बदलकर $Q$ को $P$ से प्राप्त किया जा सकता है।

समानांतर रचना के लिए सिद्धांत:

• $P|Q\equiv Q|P$
• $(P|Q)|R\equiv P|(Q|R)$
• $P|0\equiv P$

प्रतिबंध के लिए सिद्धांत:

• $(\nu x)(\nu y)P\equiv (\nu y)(\nu x)P$
• $(\nu x)0\equiv 0$

प्रतिकृति के लिए सिद्धांत:

• $!P\equiv P|!P$

सिद्धांत संबंधित प्रतिबंध और समानांतर:

• $(\nu x)(P|Q)\equiv (\nu x)P|Q$ यदि x , $Q$ का मुक्त नाम नहीं है।

इस अंतिम सिद्धांत को कार्यक्षेत्र विस्तार सिद्धांत के रूप में जाना जाता है। यह सिद्धांत केंद्रीय है क्योंकि यह वर्णन करता है कि कैसे एक बाध्य नाम x को आउटपुट क्रिया द्वारा बाहर निकाला जा सकता है जिससे x का क्षेत्र बढ़ाया जा सकता है। ऐसी स्थितियों में जहां x , $Q$ का मुक्त नाम है एवं इसके विस्तार को आगे बढ़ने की अनुमति देने के लिए अल्फा-रूपांतरण का उपयोग किया जा सकता है।

रिडक्शन सेमेंटिक्स

यदि $P$ एक संगणना चरण प्रदर्शित करता है जिसके पश्चात यह अब $P'$ है तब हम $P\rightarrow P'$ लिखते हैं

यह रिडक्शन संबंध $\rightarrow$ कटौती नियमों के सेट के अंतर्गत कम से कम बंद संबंध के रूप में परिभाषित किया गया है।

चैनलों के माध्यम से संवाद करने के लिए प्रक्रियाओं की क्षमता को पकड़ने वाला मुख्य रिडक्शन नियम निम्नलिखित है:

• ${\overline {x}}\langle z\rangle .P|x(y).Q\rightarrow P|Q[z/y]$

जहाँ $Q[z/y]$ प्रक्रिया $Q$ को दर्शाता है जिसमें मुक्त नाम $z$ है एवं $y$ की मुक्त घटनाओं के लिए प्रतिस्थापित किया गया है। यदि मुक्त घटना किसी स्थान $y$ पर होती है तब $z$ मुक्त नहीं होगा एवं अल्फा-रूपांतरण की आवश्यकता हो सकती है।

तीन अतिरिक्त नियम हैं:

• यदि $P\rightarrow Q$ तब भी $P|R\rightarrow Q|R$.

यह नियम कहता है कि समानांतर रचना गणना को बाधित नहीं करती है।

• यदि $P\rightarrow Q$, तब भी $(\nu x)P\rightarrow (\nu x)Q$.

यह नियम सुनिश्चित करता है कि गणना एक प्रतिबंध के अंतर्गत आगे बढ़ सकती है।

• यदि $P\equiv P'$ और $P'\rightarrow Q'$ और $Q'\equiv Q$, तब भी $P\rightarrow Q$.

बाद के नियम में कहा गया है कि संरचनात्मक रूप से संगत प्रक्रियाओं में समान रिडक्शन होता है।

उदाहरण पर पुनः विचार

प्रक्रिया पर पुनः विचार करें

$(\nu x)({\overline {x}}\langle z\rangle .0|x(y).{\overline {y}}\langle x\rangle .x(y).0)|z(v).{\overline {v}}\langle v\rangle .0$

रिडक्शन के शब्दार्थ की परिभाषा को लागू करते हुए, हम रिडक्शन प्राप्त करते हैं

$(\nu x)({\overline {x}}\langle z\rangle .0|x(y).{\overline {y}}\langle x\rangle .x(y).0)|z(v).{\overline {v}}\langle v\rangle .0\rightarrow (\nu x)(0|{\overline {z}}\langle x\rangle .x(y).0)|z(v).{\overline {v}}\langle v\rangle .0$

ध्यान दें कि कैसे रिडक्शन प्रतिस्थापन स्वयंसिद्ध को लागू करते हुए $y$ की मुक्त घटनाएँ अब $z$ के रूप में लेबल किए गए हैं

इसके पश्चात हम रिडक्शन प्राप्त करते हैं

$(\nu x)(0|{\overline {z}}\langle x\rangle .x(y).0)|z(v).{\overline {v}}\langle v\rangle .0\rightarrow (\nu x)(0|x(y).0|{\overline {x}}\langle x\rangle .0)$

ध्यान दें कि स्थानीय नाम के बाद से x का उत्पादन किया गया है एवं x का क्षेत्र तीसरे घटक को भी कवर करने के लिए बढ़ाया गया है। इसे स्कोप एक्सटेंशन स्वयंसिद्ध का उपयोग करके कैप्चर किया गया था।

इसके पश्चात रिडक्शन प्रतिस्थापन स्वयंसिद्ध का उपयोग करके हम प्राप्त करते हैं।

$(\nu x)(0|0|0)$

अंत में समांतर संरचना और प्रतिबंध के लिए सिद्धांतों का उपयोग करके हम प्राप्त करते हैं।

$0$

लेबल किए गए सिमेंटिक्स

वैकल्पिक रूप से कोई π-कैलकुलस को लेबल ट्रांज़िशन सिमेंटिक्स दे सकता है (संचार प्रणालियों की गणना के कैलकुलस के साथ किया गया है)।
इस शब्दार्थ में, क्रिया $\alpha$ के बाद एक स्थिति $P$ से किसी अन्य अवस्था $P'$ में सिमेंटिक्स को इस रूप में नोट किया जाता है:

• $P\,\xrightarrow {\overset {}{\alpha }} P'$

जहां क्षेत्र $P$ और $P'$ प्रक्रियाओं का प्रतिनिधित्व करते हैं और $\alpha$ या तो इनपुट $a(x)$ क्रिया, आउटपुट क्रिया${\overline {a}}\langle x\rangle$ या मौन क्रिया τ है।

लेबल किए गए शब्दार्थ के बारे में मानक परिणाम यह है कि यह संरचनात्मक अनुरूपता तक रिडक्शन शब्दार्थ से सहमत है इस अर्थ में कि

$P\rightarrow P'$ यदि और केवल यदि
$P\,\xrightarrow {\overset {}{\tau }} \equiv P'$ 

विस्तार और संस्करण

ऊपर दी गयी शब्दावली न्यूनतम है। जबकि शब्दावली को विभिन्न तरीकों से संशोधित किया जा सकता है।

गैर-नियतात्मक पसंद ऑपरेटर $P+Q$ शब्दावली में जोड़ा जा सकता है।

नाम समानता के लिए परीक्षण $[x=y]P$ शब्दावली में जोड़ा जा सकता है। यह मैच ऑपरेटर $P$ आगे बढ़ सकता है यदि और केवल यदि x और $y$ एक ही नाम हैं।

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

अतुल्यकालिक π-कैलकुलस बिना किसी प्रत्यय के केवल आउटपुट की अनुमति देता है अर्थात फॉर्म के आउटपुट परमाणु ${\overline {x}}\langle y\rangle$ एक छोटे कैलकुलस की उपज हैं जबकि मूल कैलकुलस में किसी भी प्रक्रिया को प्राप्त करने की प्रक्रिया से स्पष्ट पावती का अनुकरण करने के लिए एक अतिरिक्त मार्ग का उपयोग करके छोटे अतुल्यकालिक π-कैलकुलस द्वारा दर्शाया जा सकता है। चूंकि निरंतरता-मुक्त आउटपुट संदेश-इन-ट्रांजिट को मॉडल कर सकता है एवं यह भाग दिखाता है कि मूल π-कैलकुलस जो सहज रूप से सिंक्रोनस संचार पर आधारित है इसके शब्दावली के अंदर अभिव्यंजक अतुल्यकालिक संचार मॉडल है। जबकि ऊपर परिभाषित गैर-नियतात्मक चयनित ऑपरेटर को इस प्रकार से व्यक्त नहीं किया जा सकता है क्योंकि अनियंत्रित विकल्प को संरक्षित में परिवर्तित कर दिया जाएगा एवं इस तथ्य का उपयोग यह प्रदर्शित करने के लिए किया गया है कि एसिंक्रोनस कैलकुलस सिंक्रोनस (विकल्प ऑपरेटर के साथ) की तुलना में कठिन रूप से कम अभिव्यंजक है।

बहुविकल्पी π-कैलकुलस एक ही क्रिया (पॉलीडिक इनपुट) में एक से अधिक नामों को संप्रेषित करने की अनुमति देता है जैसे ${\overline {x}}\langle z_{1},...,z_{n}\rangle .P$ (पॉलीडिक आउटपुट) और $x(z_{1},...,z_{n}).P$ । यह पॉलीऐडिक विस्तार जो विशेष रूप से नाम पासिंग प्रक्रियाओं के प्रकारों का अध्ययन करते समय उपयोगी होता है जोकि निजी चैनल के नाम को पास करके मोनैडिक कैलकुस में एन्कोड किया जा सकता है जिसके माध्यम से कई तर्क अनुक्रम में पारित किए जाते हैं। एन्कोडिंग को खंडों द्वारा पुनरावर्ती रूप से परिभाषित किया गया है।

${\overline {x}}\langle y_{1},\cdots ,y_{n}\rangle .P$ को $(\nu w){\overline {x}}\langle w\rangle .{\overline {w}}\langle y_{1}\rangle .\cdots .{\overline {w}}\langle y_{n}\rangle .[P]$ के रूप में एन्कोड किया गया है।

$x(y_{1},\cdots ,y_{n}).P$ को $x(w).w(y_{1}).\cdots .w(y_{n}).[P]$ के रूप में एन्कोड किया गया है।

अन्य सभी प्रक्रिया निर्माणों को एन्कोडिंग द्वारा अपरिवर्तित छोड़ दिया जाता है।

ऊपरोक्त में $[P]$, $P$ निरंतरता में सभी उपसर्गों के एन्कोडिंग को दर्शाता है उसी प्रकार से।

प्रतिकृति $!P$ की पूरी शक्ति आवश्यकता नहीं है। प्रायः कोई केवल प्रतिरूपित इनपुट $!x(y).P$ पर विचार करता है जिसकी संरचनात्मक सर्वांगसमता $!x(y).P\equiv x(y).P|!x(y).P$ सिद्धांत है।

प्रतिकृति इनपुट प्रक्रिया जैसे $!x(y).P$ सर्वर के रूप में समझा जा सकता है, चैनल x पर प्रतीक्षा कर रहा है एवं ग्राहकों द्वारा आह्वान किया जाता है। एक सर्वर का आह्वान $P[a/y]$ प्रक्रिया की नई प्रति उत्पन्न करता है जहां बाद के आह्वान के समय क्लाइंट द्वारा सर्वर को दिया गया नाम a है।

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

${\overline {x}}\langle R\rangle .P|x(Y).Q\rightarrow P|Q[R/Y]$

यहाँ $Y$ प्रक्रिया चर को दर्शाता है जिसे एक प्रक्रिया अवधि द्वारा त्वरित किया जा सकता है। सांगियोर्गी ने स्थापित किया कि प्रक्रियाओं को पास करने की क्षमता π-कैलकुलस की अभिव्यंजकता में वृद्धि नहीं करती है: प्रक्रिया P को पारित करने को केवल नाम पास करके अनुकरण किया जा सकता है जो इसके स्थान पर P को इंगित करता है।

गुण

ट्यूरिंग पूर्णता

π-कैलकुलस संगणना का एक सार्वभौमिक मॉडल (ट्यूरिंग पूर्ण) है। इसे पहली बार रॉबिन मिलनर ने अपने पेपर "फंक्शन्स ऐज़ प्रोसेसेस" में देखा था जिसमें उन्होंने π-कैलकुलस में वह लैम्ब्डा-कैलकुलस के दो एनकोडिंग प्रस्तुत किए। एक एन्कोडिंग उत्सुक (कॉल-बाय-वैल्यू) मूल्यांकन रणनीति का अनुकरण करती है तथा अन्य एन्कोडिंग सामान्य-ऑर्डर (कॉल-बाय-नेम) रणनीति का अनुकरण करती है। इन दोनों में महत्वपूर्ण अंतर्दृष्टि पर्यावरण बाइंडिंग का मॉडलिंग है - उदाहरण के लिए x अवधि के लिए बाध्य है जबकि ${\textstyle M}$- प्रतिकृति एजेंटों के रूप में जो शब्द $M$ के लिए संपर्क वापस भेजकर अपनी बाइंडिंग के अनुरोधों का उत्तर देते हैं।

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

π-कैलकुलस में बाईसिमुलेशन

See also: बाईसिमुलेशन

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

π-कैलकुलस में लेबल किए गए बाईसिमुलेशन समकक्ष को परिभाषित करने के (कम से कम) तीन अलग-अलग उपाय हैं: अर्ली, लेट और ओपन बाइसिमिलरिटी। यह इस तथ्य से प्राप्त हुआ है कि π-कैलकुलस एक वैल्यू-पासिंग प्रोसेस कैलकुलस है।

माना कि इस भाग के शेष भाग में $p$ और $q$ प्रक्रियाओं को निरूपित करते है और $R$ प्रक्रियाओं पर द्विआधारी संबंधों को निरूपित करें।

प्रारंभिक और बाद की समानता

मिलनर, पैरो और वाकर ने π-कैलकुलस प्रारंभिक और बाद की समानता दोनों को अपने मूल पेपर में तैयार किया था। द्विआधारी संबंध $R$ प्रक्रियाओं की प्रत्येक जोड़ी के लिए प्रक्रियाओं पर एक प्रारंभिक $(p,q)\in R$ बाईसिमुलेशन है,

• जब भी $p\,\xrightarrow {a(x)} \,p'$ तब प्रत्येक $y$ नाम के लिए कुछ $q'$ उपस्थित है, ऐसा है कि $q\,\xrightarrow {a(x)} \,q'$ और $(p'[y/x],q'[y/x])\in R$;
• किसी भी गैर-इनपुट कार्रवाई $\alpha$ के लिए, यदि ${p\xrightarrow {\overset {}{\alpha }} p'}$ तो कुछ $q'$ उपस्थित है, ऐसा है कि $q\xrightarrow {\overset {}{\alpha }} q'$ और $(p',q')\in R$;
• और सममित आवश्यकताओं के साथ $p$ और $q$ की अदला-बदली।

प्रक्रियाओं $p$ और $q$ को प्रारंभिक बाईसिमिलर एवं लिखित रूप में $p\sim _{e}q$ कहा जाता है, यदि जोड़ी $(p,q)\in R$ कुछ आरम्भिक $R$ बाईसिमुलेशन के लिए।

बाद के द्वि-समानता में संक्रमण मिलान संचरित होने वाले नाम से स्वतंत्र होना चाहिए। द्विआधारी संबंध $R$ प्रक्रियाओं की प्रत्येक जोड़ी के लिए ओवर प्रोसेस लेट बाईसिमुलेशन $(p,q)\in R$ है

• जब कभी $p\xrightarrow {a(x)} p'$होता है इसके पश्चात कुछ $q'$ के लिए यह $q\xrightarrow {a(x)} q'$ और $(p'[y/x],q'[y/x])\in R$ प्रत्येक नाम y के लिए मानता है;
• किसी भी गैर-इनपुट क्रिया $\alpha$ के लिए यदि $p\xrightarrow {\overset {}{\alpha }} p'$,तब इसका तात्पर्य है कि कुछ $q'$ उपस्थित है, ऐसा है कि $q\xrightarrow {\overset {}{\alpha }} q'$और $(p',q')\in R$;
• और सममित आवश्यकताओं के साथ $p$ और $q$ की अदला-बदली।

प्रक्रियाओं $p$ और $q$ परवर्ती बाईस्मिलर एवं लिखित रूप में $p\sim _{l}q$ कहे जाते हैं यदि जोड़ी $(p,q)\in R$ कुछ बाद के बाईसिमुलेशन $R$ के लिए $\sim _{e}$ और $\sim _{l}$ दोनों समस्या से ग्रस्त हैं कि वे इस अर्थ में सर्वांगसम संबंध नहीं हैं एवं वे सभी प्रक्रिया निर्माणों द्वारा संरक्षित नहीं हैं। प्रक्रियाएं $p$ और $q$ अधिक सटीक रूप से उपस्थित हैं, ऐसा है कि $p\sim _{e}q$ परन्तु $a(x).p\not \sim _{e}a(x).q$. इसमें सम्मिलित अधिकतम सर्वांगसमता संबंधों $\sim _{e}$ और $\sim _{l}$ पर विचार करके कोई भी इस समस्या का समाधान कर सकता है इन्हें क्रमशः प्रारंभिक सर्वांगसमता और बाद की सर्वांगसमता के रूप में जाना जाता है।

मुक्त द्विसमानता

भाग्यवश एक तीसरी परिभाषा संभव है जो इस समस्या से सुरक्षित है अर्थात् सांगियोर्गी के कारण मुक्त द्विसमानता।

द्विआधारी संबंध $R$ प्रत्येक जोड़ी तत्वों के लिए ओवर प्रोसेस ओपन बाईसिमुलेशन $(p,q)\in R$ है और प्रत्येक नाम प्रतिस्थापन के लिए $\sigma$ और प्रत्येक क्रिया $\alpha$, जब कभी भी $p\sigma \xrightarrow {\overset {}{\alpha }} p'$ तो कुछ $q'$ उपस्थित है, ऐसा है कि $q\sigma \xrightarrow {\overset {}{\alpha }} q'$ और $(p',q')\in R$.

प्रक्रियाओं $p$ और $q$ मुक्त बाईसिमिलर, $p\sim _{o}q$ लिखित कहे जाते हैं यदि जोड़ी $(p,q)\in R$ कुछ मुक्त बाईसिमुलेशन $R$ के लिए .

प्रारंभिक, बाद के और मुक्त द्विसमानता भिन्न-भिन्न होती है

प्रारंभिक, बाद के और मुक्त द्विसमानता भिन्न-भिन्न हैं। रोकथाम उचित हैं इसलिए $\sim _{o}\subsetneq \sim _{l}\subsetneq \sim _{e}$.

कुछ उप-गणनाओं में जैसे कि अतुल्यकालिक π-कैलकुलस, बाद के, प्रारंभिक और खुली द्विसमानता को मेल खाने के लिए जाना जाता है। जबकि इस सेटिंग में अधिक उपयुक्त धारणा अतुल्यकालिक द्विसमानता की है।

साहित्य में ओपन बाईसिम्यूलेशन (मुक्त द्विसमानता) शब्द सामान्य रूप से अधिक परिष्कृत धारणा को संदर्भित करता है जहां प्रक्रियाओं और संबंधों को विशिष्ट संबंधों द्वारा अनुक्रमित किया जाता है; विवरण ऊपर उद्धृत सांगियोर्गी के पेपर में हैं।

बारबेड तुल्यता

वैकल्पिक रूप से कोई व्यक्ति सिमेंटिक्स को कम करने से सीधे बाईसिम्यूलेशन समकक्ष को परिभाषित कर सकता है। हम लिखते हैं $p\Downarrow a$ यदि प्रक्रिया $p$, $a$ नाम पर तुरंत इनपुट या आउटपुट की अनुमति देता है एवं

द्विआधारी संबंध $R$ प्रक्रियाओं पर बारबेड बाईसिमुलेशन है यदि यह एक सममित संबंध है जो संतुष्ट करता है कि तत्वों की प्रत्येक जोड़ी के लिए $(p,q)\in R$ हमारे पास वह है

(1) $p\Downarrow a$ यदि और केवल यदि $q\Downarrow a$ प्रत्येक $a$ नाम के लिए

और

(2) प्रत्येक रिडक्शन $p\rightarrow p'$ के लिए $q\rightarrow q'$ रिडक्शन होती है

ऐसा है कि $(p',q')\in R$.

हम कहते हैं $p$ और $q$ बारबेड बाईस्मिलर हैं यदि बारबेड बाईसिमुलेशन $R$ उपस्थित है जहाँ $(p,q)\in R$.

संदर्भ को एक π के रूप में छेद वाला शब्द [] के साथ परिभाषित करना जहाँ हम कहते हैं कि दो प्रक्रियाएँ P और Q बारबेड सर्वांगसम हैं, $P\sim _{b}Q\,\!$ लिखी गई हैं यदि प्रत्येक संदर्भ $C[]$ के लिए हमारे पास $C[P]$ और $C[Q]$ बारबेड बाईस्मिलर हैं। यह पता चला है कि बारबेड सर्वांगसमता प्रारंभिक बाईसिमिलरिटी द्वारा प्रेरित सर्वांगसमता के साथ मेल खाती है।

अनुप्रयोग

π-कैलकुलस का उपयोग कई भिन्न-भिन्न प्रकार की समवर्ती प्रणालियों का वर्णन करने के लिए किया गया है। वास्तव में कुछ नवीनतम अनुप्रयोग पारंपरिक कंप्यूटर विज्ञान के क्षेत्र से बाहर हैं।

सन 1997 में मार्टिन अबादी और एंड्रयू गॉर्डन ने π-कैलकुलस का विस्तार क्रिप्टोग्राफ़िक प्रोटोकॉल के बारे में वर्णन करने और तर्क करने के लिए एक औपचारिक संकेतन के रूप में स्पाइ-कैलकुलस प्रस्तावित किया। स्पाइ-कैलकुलस, π-एन्क्रिप्शन और डिक्रिप्शन के लिए आदिम के साथ कैलकुलस का विस्तार होता है। सन 2001 में मार्टिन अबादी और सेड्रिक फोरनेट ने क्रिप्टोग्राफ़िक प्रोटोकॉल के संचालन को लागू करने के लिए π कैलकुलस सामान्यीकृत किया। लागू किए गए वेरिएंट के लिए समर्पित कार्य का एक बड़ा भाग अब π कैलकुलस है जिसमें कई प्रयोगात्मक सत्यापन उपकरण सम्मिलित हैं। एक उदाहरण उपकरण ProVerif [2] है जो ब्रूनो ब्लैंचेट के कारण लागू किए गए अनुवाद पर आधारित है। ब्लैंचेट के लॉजिक प्रोग्रामिंग फ्रेमवर्क में π-कैलकुलस एक अन्य उदाहरण क्रिप्टिक [3] है, एंड्रयू गॉर्डन और एलन जेफरी के कारण जो टाइप सिस्टम के आधार के रूप में वू और लैम के पत्राचार अभिकथन की विधि का उपयोग करता है जो क्रिप्टोग्राफ़िक प्रोटोकॉल के प्रमाणीकरण गुणों की जांच कर सकता है।

सन 2002 के आसपास हॉवर्ड स्मिथ और पीटर फ़िंगर की इसमें रुचि हो गई π-कैलकुलस मॉडलिंग व्यवसाय प्रक्रियाओं के लिए एक विवरण उपकरण बन जाएगा। जुलाई 2006 तक समुदाय में चर्चा हो रही है कि यह कितना उपयोगी होगा। हाल ही में π-कैलकुलस ने बिजनेस प्रोसेस मॉडलिंग लैंग्वेज (BPML) और माइक्रोसॉफ्ट के XLANG के सैद्धांतिक आधार का गठन किया है।

π-कैलकुलस ने आणविक जीव विज्ञान में भी रुचि को आकर्षित किया है। सन 1999 में अवीव रेगेव और एहुद शापिरो ने दिखाया कि एक सेलुलर सिग्नलिंग मार्ग (तथाकथित रिसेप्टर टाइरोसिन किनसे / एमएपीके कैस्केड) और विशेष रूप से आणविक "लेगो" का वर्णन कर सकता है जो π-कैलकुलस के विस्तार में संचार के इन कार्यों को लागू करता है। इस मौलिक पत्र के पश्चात अन्य लेखकों ने न्यूनतम सेल के पूरे चयापचय नेटवर्क का वर्णन किया। सन 2009 में एंथनी नैश और सारा कलवाला ने सिग्नल ट्रांसडक्शन को मॉडल करने के लिए एक π-कैलकुलस फ्रेमवर्क का प्रस्ताव दिया जो डिक्टियोस्टेलियम डिस्कोइडम एग्रीगेशन को निर्देशित करता है।

इतिहास

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

कार्यान्वयन

निम्नलिखित प्रोग्रामिंग भाषाएँ π-कैलकुलस या इसका एक प्रकार कार्यान्वयन करती हैं:

• बिजनेस प्रोसेस मॉडलिंग भाषा (बीपीएमएल)
• ओकम-π
• चित्र प्रोग्रामिंग भाषा
• जोकैमल (जोड़-पथरी पर आधारित)
• रोलैंग

संदर्भ

• Milner, Robin (1999). Communicating and Mobile Systems: The π-calculus. Cambridge, UK: Cambridge University Press. ISBN 0-521-65869-1.
• Milner, Robin (1993). "The Polyadic π-Calculus: A Tutorial". In F. L. Hamer; W. Brauer; H. Schwichtenberg (eds.). Logic and Algebra of Specification. Springer-Verlag.
• Sangiorgi, Davide; Walker, David (2001). The π-calculus: A Theory of Mobile Processes. Cambridge, UK: Cambridge University Press. ISBN 0-521-78177-9.