अभिकलन का सिद्धांत

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

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

इतिहास

मुख्य लेख: History of theory of computation

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

अभिकलन सिद्धांत के कुछ अग्रदूतों में रहे अलोंजो चर्च, एलन ट्यूरिंग, स्टीफन क्लीन, जॉन वॉन न्यूमन, क्लाउड शेनन और नोम चोम्स्की.

कम्प्यूटेबिलिटी सिद्धांत

मुख्य लेख: Computability theory

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

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

कम्प्यूटेबिलिटी सिद्धांत, गणितीय तर्क की शाखा, जिसे रिकर्शन सिद्धांत कहा जाता है, से निकट रूप से संबंधित है, जो उस प्रतिबंध को हटाता है जिसके तहत अभिकलन के सिर्फ उन मॉडलों का अध्ययन किया जाता है जिन्हें ट्यूरिंग मशीन के योग्य किया जा सकता है। कई गणितज्ञ और अभिकलन सिद्घांतकार जो रिकर्शन सिद्धांत का अध्ययन करते हैं, वे उसे कम्प्यूटेबिलिटी सिद्धांत के रूप में उल्लेख करेंगे।

जटिलता सिद्धांत

मुख्य लेख: Computational complexity theory

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

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

इस समस्या को सरल बनाने के लिए, कंप्यूटर वैज्ञानिकों ने Big O नोटेशन को अपनाया है, जो कार्यों की इस तरह से तुलना करने की अनुमति देता है जो यह सुनिश्चित करता है कि मशीन के निर्माणों के कुछ विशेष पहलुओं पर विचार करने की आवश्यकता नहीं है, बल्कि केवल एसिम्प्टोटिक व्यवहार को देखना होता है जब समस्याएं बड़ी हो जाती हैं। तो हमारे पिछले उदाहरण में, हम कह सकते हैं कि इस समस्या को हल करने के लिए $O(n)$ चरणों की आवश्यकता है।

शायद सम्पूर्ण कंप्यूटर विज्ञान में सबसे महत्त्वपूर्ण मुक्त समस्या, इस सवाल पर है कि क्या NP चिह्नित समस्याओं का एक निश्चित व्यापक वर्ग कुशलतापूर्वक हल किया जा सकता है कि नहीं। इस पर आगे चलकर जटिलता वर्ग P और NP में चर्चा की गई है।

अभिकलन की अन्य औपचारिक परिभाषा

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

लम्ब्डा कलन

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

कोम्बिनेटरी तर्क

एक अवधारणा है जिसमें $\lambda$-कलन से कई समानताएं हैं, लेकिन कुछ महत्त्वपूर्ण अंतर भी मौजूद हैं (जैसे नियत बिन्दु कोम्बिनेटर Y का कोम्बिनेटरी तर्क में सामान्य रूप है लेकिन $\lambda$-कलन में नहीं). कोम्बिनेटरी तर्क को बड़ी महत्वाकांक्षाओं के साथ विकसित किया गया था: विरोधाभासों की प्रकृति समझते हुए, गणित की नींव को और अधिक किफायती (अवधारणात्मक रूप से) बनाते हुए, चर की धारणा समाप्त करते हुए (इस प्रकार गणित में उनकी भूमिका को स्पष्ट करते हुए).

mu-पुनरावर्ती क्रिया

एक अभिकलन, mu-पुनरावर्ती क्रिया से निर्मित होता है, यानी उसका परिभाषित अनुक्रम, कोई भी इनपुट मूल्य और इनपुट और आउटपुट के साथ परिभाषित अनुक्रम में प्रदर्शित होता पुनरावर्ती क्रिया का अनुक्रम. इस प्रकार, पुनरावर्ती क्रिया के एक परिभाषित अनुक्रम में $f(x)$ क्रिया $g(x)$ और $h(x,y)$ दिखाई देते हैं, तो स्वरूप का नियम होगा g(5)=7 या h(3,2)=10 प्रदर्शित हो सकता है। इस अनुक्रम में प्रत्येक प्रविष्टि को मूल क्रिया के एक अनुप्रयोग के रूप में होना चाहिए या कम्पोजीशन, प्रिमिटिव रिकर्शन या mu रिकर्शन के उपयोग से ऊपर प्रविष्टियों का पालन करना चाहिए. उदाहरण के लिए, यदि $f(x)=h(x,g(x))$, तब f(5)=3' को प्रकट करने के लिए, 'g(5)=6' और 'h(5,6)=3' जैसे शब्दों को ऊपर आना चाहिए. अभिकलन तभी नष्ट होता है जब अंतिम टर्म, इनपुट पर लागू किये गए पुनरावर्ती क्रिया के मान को देता है।

मार्कोव एल्गोरिथ्म

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

रजिस्टर मशीन

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

P"

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

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

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

कंप्यूटिंग का सैद्धांतिक आधार

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

अतिरिक्त पठन

कंप्यूटर वैज्ञानिकों के उद्देश्य से पाठ्यपुस्तकें

(इस क्षेत्र में कई पाठ्यपुस्तकें हैं, यह सूची आवश्यकता से अधूरी है।)

• होपक्रॉफ्ट, जॉन ई., और जेफ्री डी. उलमान (2006). इंट्रोडक्शन टु ऑटोमेटा थिओरी, लेंग्वेज, एंड कम्प्यूटेशन तीसरा संस्करण रीडिंग, MA: एडिसन-वेस्ले. ISBN 978-0-321-45536-9 इस क्षेत्र में एक मानक संदर्भ
• Michael Sipser (2006). Introduction to the Theory of Computation 2ed. PWS Publishing. आई॰ऍस॰बी॰ऍन॰ 0-534-94728-X.
• Eitan Gurari (1989). [http://www.cse.ohio-state.edu/~gurari/theory-bk/theory-bk.html An Introduction to the Theory of Computation]. Computer Science Press. आई॰ऍस॰बी॰ऍन॰ 0-7167-8182-4. मूल से 2 अक्तूबर 2019 को पुरालेखित. अभिगमन तिथि 23 अक्तूबर 2019.
• हेन, जेम्स एल (1996) संगणना के सिद्धांत. सुड्बेरी, एमए: जोन्स और बार्टलेट. ISBN 978-0-86720-497-1 इस क्षेत्र के बारे में एक सौम्य परिचय, दूसरे वर्ष के स्नातक कंप्यूटर विज्ञान के छात्रों के लिए उपयुक्त.
• टेलर, आर ग्रेगरी (1998). अभिकलन और औपचारिक भाषा मॉडल. न्यूयॉर्क : ऑक्सफोर्ड यूनिवर्सिटी प्रेस. ISBN 978-0-19-510983-2 एक असामान्य रूप से पठनीय पुस्तक, ऊपरी स्तर के स्नातक से नीचे या स्नातक छात्रों के लिए उपयुक्त.
• लुईस, एफ.डी (2007). अनिवार्य सैद्धांतिक कंप्यूटर विज्ञान औपचारिक भाषाओं, व्याकरणों और ऑटोमेटा विषयों को आवृत्त करती पाठ्यपुस्तक परिणामों पर सबूत पेश करने की जगह जोर परिणामों का एक खाका उपलब्ध कराने पर प्रतीत होता है।
• मार्टिन डेविस, रॉन सिगल, ऐलेन जे वेयुकर, कम्प्यूटेबिलिटी, कम्प्लेक्सिटी, एंड लैंग्वेजेज़: फंडामेंटल ऑफ़ थिओरेटिकल कंप्यूटर साइंस 2 एड., एकेडेमिक प्रेस, 1994, ISBN 0-12-206382-1. अन्य परिचयात्मक पुस्तकों की तुलना में सबसे अधिक व्यापक विषयों को आवृत्त करती है जिसमें शामिल हैं प्रोग्राम सिमेन्टिक्स और क्वान्टिफिकेशन थिओरी. स्नातक छात्रों के लिए।

अभिकलन सिद्धांत पर (व्यापक) गणितीय दृष्टिकोण से किताबें

• हार्टले रोजर्स, जूनियर (1987). थ्योरी ऑफ़ रिकर्सिव फंक्शन एंड इफेक्टिव कम्प्यूटेबिलिटी MIT प्रेस ISBN 0-87311-016-1
• S. Barry Cooper (2004). Computability Theory. Chapman and Hall/CRC. आई॰ऍस॰बी॰ऍन॰ 1-58488-237-9. मूल से 2 अक्तूबर 2019 को पुरालेखित. अभिगमन तिथि 23 अक्तूबर 2019. .
• कार्ल एच. स्मिथ, अ रिकर्सिव इंट्रोडक्शन टु द थिओरी ऑफ़ कम्प्यूटेशन 1994, ISBN 0-387-94332-3 कंप्यूटर विज्ञान की स्नातक छात्रों के लिए उपयुक्त पाठ्यपुस्तक.

ऐतिहासिक परिप्रेक्ष्य

• [7].

इन्हें भी देखें

सैद्धांतिक कंप्यूटर विज्ञान

बाहरी कड़ियाँ

• कम्प्यूटेबिलिटी लोजिक - इंटरैक्टिव अभिकलन का एक सिद्धांत है। इस विषय पर मुख्य वेब स्रोत है।