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