अभिकलन का सिद्धांत
अभिकलन का सिद्धांत या कंप्यूटर सिद्धांत, कंप्यूटर विज्ञान और गणित की एक शाखा है जो यह देखती है की क्या और कितनी कुशलता से एल्गोरिथ्म का उपयोग करते हुए अभिकलन के मॉडल पर एक समस्या को हल किया जा सकता है। इस क्षेत्र को दो प्रमुख शाखाओं में विभाजित किया गया है: अभिकलनात्मक सिद्धांत और जटिलता सिद्धांत, लेकिन दोनों शाखाएं अभिकलन के औपचारिक मॉडल की चर्चा करतीं हैं।
अभिकलन का एक गहन अध्ययन करने के लिए, कंप्यूटर वैज्ञानिक, कंप्यूटर के एक गणितीय सारग्रहण के साथ काम करते हैं जिसे अभिकलन का मॉडल कहा जाता है। कई मॉडल उपयोग में हैं, लेकिन सबसे अधिक जांच किया जाने वाला है ट्यूरिंग मशीन. एक ट्यूरिंग मशीन को एक डेस्कटॉप PC के रूप में समझा जा सकता है जिसमें संभावित रूप से एक अनंत स्मृति क्षमता होती है, यद्यपि वह, इस स्मृति का उपयोग केवल छोटी असतत मात्रा में कर सकता है। कंप्यूटर वैज्ञानिक, ट्यूरिंग मशीन का अध्ययन करते हैं क्योंकि इसे सूत्रबद्ध करना आसान है, विश्लेषण किया जा सकता है और परिणामों को साबित करने के लिए इस्तेमाल किया जाता है और क्योंकि यह ऐसे मॉडल का प्रतिनिधित्व करता है जिसे कई लोग अभिकलन का सबसे शक्तिशाली संभव "उचित" मॉडल मानते हैं। ऐसा लग सकता है कि सक्षम अनंत स्मृति क्षमता एक अप्राप्य विशेषता है, लेकिन ट्यूरिंग मशीन द्वारा हल कोई भी निर्धारणीय समस्या को हमेशा केवल एक परिमित राशि की स्मृति की आवश्यकता होती है। इसलिए सिद्धांत रूप में, कोई भी समस्या जिसे एक ट्यूरिंग मशीन द्वारा हल (निर्णित) किया जा सकता है उसे एक ऐसे कंप्यूटर द्वारा हल किया जा सकता है जिसमें स्मृति की एक निश्चित राशि है।
अभिकलन के सिद्धांत को, कंप्यूटर विज्ञान के क्षेत्र में सभी प्रकार के मॉडलों के निर्माण के रूप में समझा जा सकता है। इसलिए गणित और तर्क का इस्तेमाल किया जाता किया जाता है। पिछली सदी में यह एक स्वतंत्र शैक्षणिक विषय बन गया और गणित से अलग हो गया।
अभिकलन सिद्धांत के कुछ अग्रदूतों में रहे अलोंजो चर्च, एलन ट्यूरिंग, स्टीफन क्लीन, जॉन वॉन न्यूमन, क्लाउड शेनन और नोम चोम्स्की.
कम्प्यूटेबिलिटी सिद्धांत, मुख्य रूप से उस सीमा के सवाल की चर्चा करता है जिस सीमा तक एक समस्या को एक कंप्यूटर पर हल किया जा सकता है। यह बयान कि एक हॉल्टिंग समस्या को एक ट्यूरिंग मशीन द्वारा हल नहीं किया जा सकता है, कम्प्यूटेबिलिटी सिद्धांत में सबसे महत्त्वपूर्ण परिणामों में से एक है, चूंकि यह एक ऐसी ठोस समस्या का उदाहरण है जिसे सूत्रबद्ध करना आसान और ट्यूरिंग मशीन के उपयोग से हल करना असंभव है। कम्प्यूटेबिलिटी सिद्धांत का अधिकांश हिस्सा हॉल्टिंग समस्या के परिणाम पर बनता है।
कम्प्यूटेबिलिटी सिद्धांत में एक और महत्त्वपूर्ण कदम राइस प्रमेय है, जो कहता है कि आंशिक क्रियाओं के सभी नन-ट्रीविअल गुणों के लिए यह अनिर्णित है कि एक ट्यूरिंग मशीन उस गुण के साथ एक आंशिक क्रिया का परिकलन करती है या नहीं।
कम्प्यूटेबिलिटी सिद्धांत, गणितीय तर्क की शाखा, जिसे रिकर्शन सिद्धांत कहा जाता है, से निकट रूप से संबंधित है, जो उस प्रतिबंध को हटाता है जिसके तहत अभिकलन के सिर्फ उन मॉडलों का अध्ययन किया जाता है जिन्हें ट्यूरिंग मशीन के योग्य किया जा सकता है। कई गणितज्ञ और अभिकलन सिद्घांतकार जो रिकर्शन सिद्धांत का अध्ययन करते हैं, वे उसे कम्प्यूटेबिलिटी सिद्धांत के रूप में उल्लेख करेंगे।
जटिलता सिद्धांत सिर्फ यह नहीं देखता है कि क्या एक समस्या कंप्यूटर पर हल की जा सकती है, बल्कि यह भी देखता है कि यह समस्या कितनी कुशलतापूर्वक हल की जा सकती है। दो प्रमुख पहलुओं पर विचार किया जाता है: समय जटिलता और स्पेस जटिलता, जिसका क्रमशः अर्थ है कि एक अभिकलन को संपादित करने में कितने चरण लगते हैं और उस अभिकलन को संपादित करने में कितनी स्मृति की आवश्यकता होती है।
यह विश्लेषण करने में कि एक दिए गए एल्गोरिथ्म को कितने समय और स्पेस की आवश्यकता है, कंप्यूटर वैज्ञानिक उस समस्या को हल करने के लिए आवश्यक समय और स्पेस को इनपुट समस्या के आकार के फलन के रूप में व्यक्त करते हैं। उदाहरण के लिए, संख्याओं की एक लंबी सूची में एक विशेष संख्या को ढूंढना, संख्या की सूची के लम्बे होने से कठिन होता जाता है। अगर हम कहते हैं कि सूची में formula_1 संख्या है और यदि सूची को किसी भी तरह से हल या अनुक्रमित नहीं किया गया है तो हमें अपनी इच्छित संख्या को खोजने के लिए प्रत्येक संख्या को देखना पड़ सकता है। इस प्रकार हम कह सकते हैं कि इस समस्या को हल करने के लिए, कंप्यूटर को कई चरण संपादित करने की ज़रूरत होगी जो समस्या के आकार में रैखिक रूप से बढ़ता है।
इस समस्या को सरल बनाने के लिए, कंप्यूटर वैज्ञानिकों ने Big O नोटेशन को अपनाया है, जो कार्यों की इस तरह से तुलना करने की अनुमति देता है जो यह सुनिश्चित करता है कि मशीन के निर्माणों के कुछ विशेष पहलुओं पर विचार करने की आवश्यकता नहीं है, बल्कि केवल एसिम्प्टोटिक व्यवहार को देखना होता है जब समस्याएं बड़ी हो जाती हैं। तो हमारे पिछले उदाहरण में, हम कह सकते हैं कि इस समस्या को हल करने के लिए formula_2 चरणों की आवश्यकता है।
शायद सम्पूर्ण कंप्यूटर विज्ञान में सबसे महत्त्वपूर्ण मुक्त समस्या, इस सवाल पर है कि क्या NP चिह्नित समस्याओं का एक निश्चित व्यापक वर्ग कुशलतापूर्वक हल किया जा सकता है कि नहीं। इस पर आगे चलकर जटिलता वर्ग P और NP में चर्चा की गई है।
ट्यूरिंग मशीन के अलावा, अन्य समकक्ष (देखें: चर्च ट्यूरिंग थीसिस) अभिकलन मॉडल का उपयोग किया जाता हैं। सामान्य अभिकलन मॉडल के अलावा, कुछ सरल अभिकलन मॉडल विशेष, सीमित अनुप्रयोगों के लिए उपयोगी होते हैं। रेग्युलर एक्सप्रेशन, उदाहरण के लिए, कार्यालय उत्पादकता सॉफ्टवेयर से लेकर प्रोग्रामिंग भाषा तक, कई संदर्भों में स्ट्रिंग पैटर्न को निर्दिष्ट करते हैं। एक और फोर्मलिज्म जो गणितीय रूप से रेग्युलर एक्सप्रेशन के समकक्ष है, परिमित ऑटोमेटा है जिसका प्रयोग सर्किट डिज़ाइन में और समस्या सुलझाने के कुछ प्रकारों में किया जाता है। संदर्भ मुक्त व्याकरण, प्रोग्रामिंग भाषा के वाक्य विन्यास को निर्दिष्ट करते हैं। गैर नियतात्मक पुशडाउन ऑटोमेटा, संदर्भ-मुक्त व्याकरणों के समकक्ष एक अन्य फोर्मलिज्म हैं। प्रिमिटिव पुनरावर्ती क्रिया, पुनरावर्ती क्रियाओं का एक परिभाषित उपवर्ग है।
अभिकलन के विभिन्न मॉडलों में भिन्न कार्य करने की क्षमता होती है। एक अभिकलन मॉडल की शक्ति को मापने के लिए एक तरीका उन औपचारिक भाषाओं के वर्ग का अध्ययन करना है जिन्हें मॉडल उत्पन्न कर सकता है; इस तरीके से भाषाओं के चोम्स्की पदानुक्रम को प्राप्त किया जाता है।
अभिकलन सिद्धांत का गठन करने वाले तत्वों की व्यापक जांच में औपचारिक शब्दार्थ विज्ञान और गणितीय तर्क शामिल हो सकता है और इसमें कुछ विषयों के सैद्धांतिक पहलू भी शामिल हो सकते हैं जैसे समानांतर परिकलन, न्यूरल नेटवर्क और क्वांटम अभिकलन.
(इस क्षेत्र में कई पाठ्यपुस्तकें हैं, यह सूची आवश्यकता से अधूरी है।) सैद्धांतिक कंप्यूटर विज्ञान