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

इतिहास

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

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

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

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

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

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

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