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

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

आवश्यक विशेषताएं

जबकि वर्तमान प्रक्रिया कैलकुली की विविधता बहुत बड़ी (वैरिएंट सहित जो स्टोकेस्टिक व्यवहार, समय की जानकारी और आणविक इंटरैक्शन का अध्ययन करने के लिए विशेषज्ञता सम्मिलित है) है, ऐसी कई विशेषताएं हैं जो सभी प्रक्रिया कैलकुली में समान हैं:

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

प्रक्रियाओं का गणित

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

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

समानांतर रचना

दो प्रक्रियाओं ${\mathit {P}}$ और ${\mathit {Q}}$ की समानांतर रचना, सामान्यतः $P\vert Q$ लिखी जाती है, गणना के अनुक्रमिक मॉडल से प्रक्रिया गणना को अलग करने वाली प्रमुख अभाज्य है। समानांतर संरचना ${\mathit {P}}$ और ${\mathit {Q}}$ में गणना को एक साथ और स्वतंत्र रूप से आगे बढ़ने की अनुमति देती है। किन्तु यह इंटरेक्शन की भी अनुमति देता है, जो दोनों द्वारा साझा किए गए चैनल पर ${\mathit {P}}$ से ${\mathit {Q}}$ (या इसके विपरीत) से सिंक्रनाइज़ेशन और जानकारी का प्रवाह है। महत्वपूर्ण रूप से, एक कारक या प्रक्रिया को एक समय में एक से अधिक चैनल से जोड़ा जा सकता है।

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

संचार

सहभागिता सूचना का निर्देशित प्रवाह (किन्तु सदैव नहीं होता है) हो सकता है। अर्थात्, इनपुट और आउटपुट को दोहरी अंतःक्रियात्मक अभाज्य के रूप में प्रतिष्ठित किया जा सकता है। प्रक्रिया गणना जो इस तरह के भेद करती है, सामान्यतः इनपुट ऑपरेटर (उदा. $x(v)$) और आउटपुट ऑपरेटर (उदा. $x\langle y\rangle$) को परिभाषित करती है, दोनों इंटरेक्शन बिन्दु (यहाँ ${\mathit {x}}$) का नाम देते हैं जिसका उपयोग दोहरी अंतःक्रिया अभाज्य के साथ सिंक्रनाइज़ करने के लिए किया जाता है।

यदि सूचनाओं का आदान-प्रदान किया जाना चाहिए, तो यह आउटपुटिंग से इनपुटिंग प्रक्रिया तक प्रवाहित होगी। आउटपुट प्रिमिटिव भेजे जाने वाले डेटा को निर्दिष्ट करेगा। $x\langle y\rangle$ में, यह डेटा $y$ है। इसी प्रकार, यदि कोई इनपुट डेटा प्राप्त करने की अपेक्षा करता है, तो या से अधिक बाध्य चर डेटा के आने पर प्लेस-होल्डर्स के रूप में कार्य करेंगे। $x(v)$ में, $v$ वह भूमिका को निभाता है। बातचीत में जिस तरह के डेटा का आदान-प्रदान किया जा सकता है, उसका चयन उन प्रमुख विशेषताओं में से है जो विभिन्न प्रक्रिया गणनाओं को अलग करता है।

अनुक्रमिक रचना

कभी-कभी बातचीत अस्थायी रूप से आदेशित होनी चाहिए। उदाहरण के लिए, एल्गोरिदम निर्दिष्ट करना वांछनीय हो सकता है जैसे: पहले ${\mathit {x}}$ पर कुछ डेटा प्राप्त करें और फिर उस डेटा को ${\mathit {y}}$ पर भेजें। ऐसे उद्देश्यों के लिए अनुक्रमिक संरचना का उपयोग किया जा सकता है। यह गणना के अन्य मॉडलों से अच्छी तरह से जाना जाता है। प्रक्रिया गणना में, क्रमिककरण ऑपरेटर सामान्यतः इनपुट या आउटपुट, या दोनों के साथ एकीकृत होता है। उदाहरण के लिए, प्रक्रिया $x(v)\cdot P$ ${\mathit {x}}$ पर इनपुट के लिए प्रतीक्षा करेगी। केवल जब यह इनपुट हुआ है तो प्रक्रिया ${\mathit {P}}$ सक्रिय हो जाएगी, ${\mathit {x}}$ के माध्यम से प्राप्त डेटा के साथ पहचानकर्ता ${\mathit {v}}$ के लिए प्रतिस्थापित किया जाएगा।

कमी शब्दार्थ

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

$x\langle y\rangle \cdot P\;\vert \;x(v)\cdot Q\longrightarrow P\;\vert \;Q[^{y}\!/\!_{v}]$

इस कमी नियम की व्याख्या है:

1. प्रक्रिया $x\langle y\rangle \cdot P$ संदेश भेजता है, यहाँ ${\mathit {y}}$, चैनल के साथ ${\mathit {x}}$. दो तरह से, प्रक्रिया $x(v)\cdot Q$ चैनल ${\mathit {x}}$ पर वह संदेश प्राप्त करता है।
2. संदेश भेजे जाने के बाद, $x\langle y\rangle \cdot P$ प्रक्रिया बन जाती है ${\mathit {P}}$, जबकि $x(v)\cdot Q$ प्रक्रिया बन जाती है $Q[^{y}\!/\!_{v}]$, जो है ${\mathit {Q}}$ स्थान धारक के साथ ${\mathit {v}}$ द्वारा प्रतिस्थापित ${\mathit {y}}$, ${\mathit {x}}$ पर डेटा प्राप्त हुआ है।

प्रक्रियाओं का वर्ग जो ${\mathit {P}}$ सीमा से अधिक की अनुमति है क्योंकि आउटपुट ऑपरेशन की निरंतरता गणना के गुणों को काफी सीमा तक प्रभावित करती है।

छिपाना

प्रक्रियाएं उन कनेक्शनों की संख्या को सीमित नहीं करती हैं जो किसी दिए गए अंतःक्रियात्मक बिंदु पर किए जा सकते हैं। किन्तु इंटरेक्शन बिन्दु हस्तक्षेप (अर्थात् इंटरैक्शन) की अनुमति देते हैं। कॉम्पैक्ट, न्यूनतम और रचनात्मक प्रणालियों के संश्लेषण के लिए, हस्तक्षेप को प्रतिबंधित करने की क्षमता महत्वपूर्ण है। छिपाने के संचालन से समानांतर में एजेंटों की रचना करते समय बातचीत बिंदुओं के बीच बने कनेक्शनों को नियंत्रित करने की अनुमति मिलती है। छिपाने को विभिन्न विधियों से निरूपित किया जा सकता है। उदाहरण के लिए, π-कैलकुलस में ${\mathit {P}}$ में एक नाम ${\mathit {x}}$ के छिपने को $(\nu \;x)P$ के रूप में व्यक्त किया जा सकता है, जबकि संचार अनुक्रमिक प्रक्रियाओं में इसे $P\setminus \{x\}$ के रूप में लिखा जा सकता है।

पुनरावर्तन और प्रतिकृति

अब तक प्रस्तुत किए गए ऑपरेशन केवल परिमित अंतःक्रिया का वर्णन करते हैं और परिणामस्वरूप पूर्ण संगणनीयता के लिए अपर्याप्त हैं, जिसमें गैर-समाप्ति व्यवहार सम्मिलित है। पुनरावर्तन और प्रतिकृति (कंप्यूटिंग) ऐसे ऑपरेशन हैं जो अनंत व्यवहार के परिमित विवरण की अनुमति देते हैं। प्रत्यावर्तन अनुक्रमिक संसार से अच्छी तरह से जाना जाता है। प्रतिकृति $!P$ को ${\mathit {P}}$ प्रक्रियाओं की एक अनगिनत अनंत संख्या की समांतर संरचना को संक्षिप्त करने के रूप में समझा जा सकता है:

$!P=P\mid !P$

अशक्त प्रक्रिया

प्रक्रिया गणना में सामान्यतः अशक्त प्रक्रिया (जिसे विभिन्न रूप में दर्शाया जाता है ${\mathit {nil}}$, $0$, ${\mathit {STOP}}$, $\delta$, या कोई अन्य उपयुक्त प्रतीक) भी सम्मिलित होती है जिसमें कोई अंतःक्रिया बिंदु नहीं है। यह पूरी तरह से निष्क्रिय है और इसका एकमात्र उद्देश्य आगमनात्मक एंकर के रूप में कार्य करना है जिसके शीर्ष पर और अधिक रोचक प्रक्रियाएं उत्पन्न की जा सकती हैं।

असतत और सतत प्रक्रिया बीजगणित

प्रक्रिया बीजगणित का अध्ययन असतत समय और निरंतर समय # असतत समय और असतत समय और निरंतर समय # सतत समय (वास्तविक समय या सघन समय) के लिए किया गया है।

इतिहास

20वीं शताब्दी के पूर्वार्द्ध में, Μ-रिकर्सिव फ़ंक्शन|μ-रिकर्सिव फ़ंक्शंस, ट्यूरिंग मशीन और लैम्ब्डा गणना संभवतः आज सबसे प्रसिद्ध उदाहरण हैं, संगणनीय फ़ंक्शन की अनौपचारिक अवधारणा को पकड़ने के लिए विभिन्न औपचारिकताओं का प्रस्ताव किया गया था। आश्चर्यजनक तथ्य यह है कि वे अनिवार्य रूप से समतुल्य हैं, इस अर्थ में कि वे सभी एक-दूसरे में एन्कोड करने योग्य हैं, चर्च-ट्यूरिंग थीसिस का समर्थन करते हैं। और साझा सुविधा पर शायद ही कभी टिप्पणी की जाती है: वे सभी अनुक्रमिक संगणना के मॉडल के रूप में सबसे आसानी से समझी जाती हैं। कंप्यूटर विज्ञान के बाद के समेकन के लिए संगणना की धारणा के अधिक सूक्ष्म सूत्रीकरण की आवश्यकता थी, विशेष रूप से संगामिति और संचार के स्पष्ट प्रतिनिधित्व में। 1962 में प्रक्रिया कैलकुली, पेट्री नेट्स और 1973 में अभिनेता मॉडल जैसे संगामिति के मॉडल पूछताछ की इस पंक्ति से उभरे।

1973 से 1980 की अवधि के समय संचार प्रणालियों की गणना (CCS) पर रॉबिन मिलनर के मौलिक कार्य के साथ प्रक्रिया कैलकुली पर शोध आरंभ हुआ। C.A.R. होरे की संचार अनुक्रमिक प्रक्रियाएं (सीएसपी) पहली बार 1978 में सामने आईं, और बाद में 1980 के दशक की शुरुआत में इसे पूर्ण विकसित प्रक्रिया कलन के रूप में विकसित किया गया। विकसित होते ही सीसीएस और सीएसपी के बीच विचारों का बहुत अधिक क्रॉस-फर्टिलाइजेशन हो गया। 1982 में Jan Bergstra और Jan Willem Klop ने संचार प्रक्रियाओं (ACP) के बीजगणित के रूप में जाने जाने वाले काम पर काम करना आरंभ किया, और अपने काम का वर्णन करने के लिए प्रक्रिया बीजगणित की शुरुआत की।सीसीएस, सीएसपी, और एसीपी प्रक्रिया गणना परिवार की तीन प्रमुख शाखाओं का गठन करते हैं: अन्य प्रक्रिया गणनाओं में से अधिकांश इन तीन गणनाओं में से किसी में अपनी जड़ों का पता लगा सकते हैं।

वर्तमान शोध

विभिन्न प्रक्रिया गणनाओं का अध्ययन किया गया है और उनमें से सभी यहाँ चित्रित प्रतिमान में फिट नहीं हैं। सबसे प्रमुख उदाहरण परिवेश कलन हो सकता है। यह अपेक्षित है क्योंकि प्रक्रिया गणना अध्ययन का सक्रिय क्षेत्र है। वर्तमान में प्रक्रिया गणना पर शोध निम्नलिखित समस्याओं पर केंद्रित है।

• कम्प्यूटेशनल घटना के बेहतर मॉडलिंग के लिए नई प्रक्रिया कैलकुली का विकास करना।
• किसी दिए गए प्रक्रिया कैलकुस के अच्छे व्यवहार वाले उप-कैलकुली ढूँढना। यह मूल्यवान है क्योंकि (1) अधिकांश गणना इस अर्थ में काफी जंगली हैं कि वे सामान्य हैं और मनमानी प्रक्रियाओं के बारे में बहुत कुछ नहीं कहा जा सकता है; और (2) कम्प्यूटेशनल अनुप्रयोग शायद ही कभी पूरे गणना को समाप्त करते हैं। बल्कि वे केवल उन प्रक्रियाओं का उपयोग करते हैं जो बहुत सीमित रूप में होती हैं। प्रक्रियाओं के आकार को सीमित करना ज्यादातर प्रकार प्रणाली के माध्यम से अध्ययन किया जाता है।
• प्रक्रियाओं के लिए तर्क जो होरे तर्क के विचारों का पालन करते हुए प्रक्रियाओं के (अनिवार्य रूप से) मनमाने गुणों के बारे में तर्क करने की अनुमति देते हैं।
• व्यवहार सिद्धांत: दो प्रक्रियाओं के समान होने का क्या अर्थ है? हम कैसे तय कर सकते हैं कि दो प्रक्रियाएं अलग हैं या नहीं? क्या हम प्रक्रियाओं के समतुल्य वर्गों के प्रतिनिधि ढूंढ सकते हैं? सामान्यतः, प्रक्रियाओं को समान माना जाता है यदि कोई संदर्भ नहीं है, अर्थात् समानांतर में चल रही अन्य प्रक्रियाएं, अंतर का पता लगा सकती हैं। दुर्भाग्य से, इस अंतर्ज्ञान को सटीक बनाना सूक्ष्म है और अधिकतर समानता के अनावश्यक लक्षणों को जन्म देता है (जो कि ज्यादातर मामलों में भी अनिर्णीत होना चाहिए, हॉल्टिंग समस्या के परिणामस्वरूप)। बिसिमुलेशन तकनीकी उपकरण है जो प्रक्रिया समकक्षों के बारे में तर्क करने में मदद करता है।
• पथरी की अभिव्यक्ति। प्रोग्रामिंग अनुभव से पता चलता है कि कुछ भाषाओं में कुछ समस्याओं को हल करना दूसरों की तुलना में आसान होता है। यह घटना चर्च-ट्यूरिंग थीसिस द्वारा वहन की तुलना में कैलकुली मॉडलिंग संगणना की अभिव्यंजना के अधिक सटीक लक्षण वर्णन की मांग करती है। ऐसा करने का तरीका यह है कि दो औपचारिकताओं के बीच एन्कोडिंग पर विचार किया जाए और देखें कि कौन से गुण एन्कोडिंग संभावित रूप से संरक्षित कर सकते हैं। जितने अधिक गुणों को संरक्षित किया जा सकता है, एन्कोडिंग का लक्ष्य उतना ही अधिक अभिव्यंजक कहा जाता है। प्रक्रिया गणना के लिए, मनाए गए परिणाम यह हैं कि सिंक्रोनस π-गणना अपने एसिंक्रोनस वेरिएंट की तुलना में अधिक अभिव्यंजक है, उच्च-क्रम π-गणना के समान अभिव्यंजक शक्ति है, किन्तु परिवेश कलन से कम है।
• मॉडल जैविक प्रणालियों (स्टोचैस्टिक π-गणना, बायोएम्बिएंट्स, बीटा बाइंडर्स, बायोपीईपीए, ब्रैन गणना) को मॉडल करने के लिए प्रक्रिया गणना का उपयोग करना। कुछ लोगों का मानना ​​है कि प्रक्रिया-सैद्धांतिक उपकरणों द्वारा प्रदान की जाने वाली संरचना जीवविज्ञानियों को अपने ज्ञान को अधिक औपचारिक रूप से व्यवस्थित करने में मदद कर सकती है।

सॉफ्टवेयर कार्यान्वयन

प्रक्रिया बीजगणित के पीछे के विचारों ने कई उपकरणों को जन्म दिया है जिनमें सम्मिलित हैं:

• सीएडीपी
• समवर्ती कार्यक्षेत्र
• mCRL2 टूलसमुच्चय

संगामिति के अन्य मॉडलों से संबंध

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

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

यह भी देखें

• अनुक्रमिक प्रक्रियाओं का संचार करना
• ProVerif
• स्टोकेस्टिक जांच
• तामारिन प्रोवर
• लौकिक प्रक्रिया भाषा
• π-पथरी

अग्रिम पठन

• Matthew Hennessy: Algebraic Theory of Processes, The MIT Press, ISBN 0-262-08171-7.
• C. A. R. Hoare: Communicating Sequential Processes, Prentice Hall, ISBN 0-13-153289-8.
  • This book has been updated by Jim Davies at the Oxford University Computing Laboratory and the new edition is available for download as a PDF file at the Using CSP website.
• Robin Milner: A Calculus of Communicating Systems, Springer Verlag, ISBN 0-387-10235-3.
• Robin Milner: Communicating and Mobile Systems: the Pi-Calculus, Springer Verlag, ISBN 0-521-65869-1.
• Valk, Rüdiger; Moldt, Daniel; Köhler-Bußmeier, Michael, eds. (2011). "Chapter 5: Prozessalgebra - Parallele und kommunizierende Prozesse" (PDF). Formale Grundlagen der Informatik II: Modellierung und Analyse von Informatiksystemen. FGI2. Archived (PDF) from the original on 2019-07-09. Retrieved 2019-07-13. {{cite book}}: |work= ignored (help)