संगणनीयता सिद्धांत
संगणनीयता सिद्धांत यह अध्ययन करता है कि कौन सी समस्याएँ सैद्धांतिक रूप से एक एल्गोरिथम द्वारा हल की जा सकती हैं और अनसुलझी समस्याओं को उनकी कठिनाई के स्तर के अनुसार वर्गीकृत करता है।
Definition
संगणनीयता सिद्धांत, जिसे पुनरावर्तन सिद्धांत भी कहा जाता है, गणितीय तर्क की वह शाखा है जो एक प्रभावी रूप से गणना योग्य फ़ंक्शन की धारणा को सटीक बनाती है, उन सेटों और फ़ंक्शंस का अध्ययन करती है जिन्हें एल्गोरिथम गणना कर सकते हैं और नहीं कर सकते हैं, और अनसुलझी समस्याओं की सापेक्ष कठिनाई को मापती है।
Scope
यह क्षेत्र संगणना के औपचारिक मॉडल और चर्च-ट्यूरिंग थीसिस, संगणनीय और संगणनीय रूप से गणनीय सेट, अनिर्णीत समस्याएँ जैसे कि हॉल्टिंग समस्या, सापेक्ष अघुलनशीलता को मापने वाली न्यूनीकरणशीलता और ट्यूरिंग डिग्री, और क्वांटिफायर जटिलता द्वारा परिभाषा को स्तरीकृत करने वाली अंकगणितीय पदानुक्रम को शामिल करता है।
Sub-topics
Core questions
- किसी फ़ंक्शन या सेट के संगणनीय होने का क्या अर्थ है?
- कौन सी प्राकृतिक समस्याएँ एल्गोरिथम रूप से अनिर्णीत हैं?
- अनसुलझी समस्याओं की कठिनाई की तुलना और रैंकिंग कैसे की जा सकती है?
- तार्किक जटिलता संगणनीयता के स्तरों के अनुरूप कैसे है?
Key theories
- चर्च-ट्यूरिंग थीसिस
- प्रभावी गणना की सहज धारणा ट्यूरिंग मशीन संगणनीयता के साथ मेल खाती है, जो पुनरावर्ती फ़ंक्शंस और लैम्ब्डा-परिभाषित फ़ंक्शंस के समतुल्य है, एल्गोरिथम की एक मजबूत गणितीय परिभाषा को ठीक करती है।
- हॉल्टिंग समस्या की अघुलनशीलता
- कोई भी एल्गोरिथम प्रत्येक प्रोग्राम और इनपुट के लिए यह तय नहीं कर सकता कि प्रोग्राम रुकता है या नहीं, जो एक अनिर्णीत समस्या का पहला और प्रोटोटाइपिक उदाहरण देता है।
- ट्यूरिंग डिग्री
- ट्यूरिंग न्यूनीकरणशीलता सापेक्ष संगणनीयता द्वारा सेटों को रैंक करती है, और प्रेरित डिग्री एक समृद्ध आंशिक क्रम बनाती है जिसकी संरचना, जिसमें मध्यवर्ती डिग्री का अस्तित्व भी शामिल है, अध्ययन का एक केंद्रीय उद्देश्य है।
Clinical relevance
संगणनीयता सिद्धांत एल्गोरिथम समाधान की पूर्ण सीमा को निर्धारित करता है, सैद्धांतिक कंप्यूटर विज्ञान को आधार प्रदान करता है और अनिर्णयता के परिणाम प्रदान करता है, जैसे कि हॉल्टिंग और शब्द समस्याओं की अघुलनशीलता, जो गणित में बार-बार आती हैं और संगणनात्मक जटिलता के सिद्धांत को सूचित करती हैं।
History
संगणनीयता सिद्धांत 1930 के दशक में तब उभरा जब चर्च, ट्यूरिंग, क्लीनी और पोस्ट ने स्वतंत्र रूप से लैम्ब्डा कैलकुलस, ट्यूरिंग मशीनों, पुनरावर्ती फ़ंक्शंस और संयोजी प्रणालियों के माध्यम से एक प्रभावी प्रक्रिया की धारणा को औपचारिक रूप दिया, जो सभी समकक्ष साबित हुए। पोस्ट और क्लीनी ने डिग्री के सिद्धांत और अंकगणितीय पदानुक्रम को विकसित किया, और 1950 के दशक में पेश की गई प्राथमिकता विधि ने संगणनीय रूप से गणनीय डिग्री के गहरे संरचनात्मक अध्ययन को प्रेरित किया।
Key figures
- Alan Turing
- Alonzo Church
- Stephen Cole Kleene
- Emil Post
Related topics
Seminal works
- soare1987
- rogers1987
- cutland1980
Frequently asked questions
- क्या संगणनीयता सिद्धांत जटिलता सिद्धांत के समान है?
- नहीं। संगणनीयता सिद्धांत यह पूछता है कि क्या कोई समस्या किसी भी एल्गोरिथम द्वारा हल की जा सकती है, संसाधनों की उपेक्षा करते हुए, जबकि जटिलता सिद्धांत यह पूछता है कि एक हल करने योग्य समस्या को कितने समय या स्मृति की आवश्यकता होती है। संगणनीयता हल करने योग्य और अनसुलझी के बीच की रेखा खींचती है; जटिलता हल करने योग्य पक्ष को ग्रेड करती है।
- चर्च-ट्यूरिंग थीसिस एक प्रमेय क्यों नहीं है?
- यह एक अनौपचारिक धारणा, प्रभावी गणना, को एक सटीक गणितीय धारणा के साथ बराबर करता है, इसलिए इसे औपचारिक रूप से सिद्ध नहीं किया जा सकता है। इसकी स्वीकृति कई स्वतंत्र औपचारिकताओं के एक ही वर्ग के फ़ंक्शंस में अभिसरण पर निर्भर करती है, जो एक प्रमाण के बजाय एक मजबूत प्रमाण है।