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