चर्च-ट्यूरिंग थीसिस तर्क, गणित और कंप्यूटर विज्ञान में एक कुशल, व्यवस्थित या यांत्रिक पद्धति की अवधारणा को संदर्भित करता है। इसे कम्प्यूटेबिलिटी की सहज अवधारणा के विवरण के रूप में तैयार किया गया है और सामान्य पुनरावर्ती कार्यों के संबंध में, इसे अक्सर चर्च की थीसिस कहा जाता है। यह कंप्यूटर-कम्प्यूटेबल फ़ंक्शंस के सिद्धांत को भी संदर्भित करता है। थीसिस 1930 के दशक में सामने आई, जब स्वयं कंप्यूटर अभी तक मौजूद नहीं थे। बाद में इसका नाम अमेरिकी गणितज्ञ अलोंसो चर्च और उनके ब्रिटिश सहयोगी एलन ट्यूरिंग के नाम पर रखा गया।
परिणाम प्राप्त करने की विधि की दक्षता
आधुनिक कंप्यूटर जैसा दिखने वाला पहला उपकरण बॉम्बी था, जो अंग्रेजी गणितज्ञ एलन ट्यूरिंग द्वारा बनाई गई मशीन थी। इसका उपयोग द्वितीय विश्व युद्ध के दौरान जर्मन संदेशों को समझने के लिए किया गया था। लेकिन अपनी थीसिस और एक एल्गोरिथम की अवधारणा को औपचारिक रूप देने के लिए, उन्होंने अमूर्त मशीनों का इस्तेमाल किया, जिन्हें बाद में ट्यूरिंग मशीन कहा गया। थीसिस प्रस्तुत करता हैगणितज्ञों और प्रोग्रामर दोनों के लिए रुचि, क्योंकि इस विचार ने पहले कंप्यूटरों के रचनाकारों को प्रेरित किया।
कम्प्यूटेबिलिटी सिद्धांत में, चर्च-ट्यूरिंग थीसिस को गणना योग्य कार्यों की प्रकृति के बारे में अनुमान के रूप में भी जाना जाता है। इसमें कहा गया है कि प्राकृतिक संख्याओं पर किसी भी एल्गोरिथम रूप से गणना योग्य कार्य के लिए, एक ट्यूरिंग मशीन है जो इसकी गणना करने में सक्षम है। या, दूसरे शब्दों में, इसके लिए उपयुक्त एक एल्गोरिथम है। इस पद्धति की प्रभावशीलता का एक प्रसिद्ध उदाहरण तनातनी के परीक्षण के लिए सत्य तालिका परीक्षण है।
किसी भी वांछित परिणाम को प्राप्त करने का एक तरीका "प्रभावी", "व्यवस्थित" या "यांत्रिक" कहलाता है यदि:
- विधि सटीक निर्देशों की एक सीमित संख्या के संदर्भ में निर्दिष्ट है, प्रत्येक निर्देश वर्णों की एक सीमित संख्या का उपयोग करके व्यक्त किया जाता है।
- यह बिना किसी त्रुटि के चलेगा, कुछ निश्चित चरणों में वांछित परिणाम देगा।
- पेंसिल और कागज के अलावा किसी भी उपकरण के साथ बिना सहायता प्राप्त मानव द्वारा विधि का प्रदर्शन किया जा सकता है
- कार्य करने वाले व्यक्ति की ओर से समझ, अंतर्ज्ञान या सरलता की आवश्यकता नहीं है
पहले गणित में, अनौपचारिक शब्द "प्रभावी रूप से गणना योग्य" का उपयोग उन कार्यों को संदर्भित करने के लिए किया जाता था जिनकी गणना पेंसिल और कागज से की जा सकती है। लेकिन एल्गोरिथम कम्प्यूटेबिलिटी की धारणा किसी भी ठोस चीज़ की तुलना में अधिक सहज थी। अब यह एक प्राकृतिक तर्क के साथ एक फ़ंक्शन की विशेषता थी, जिसके लिए एक गणना एल्गोरिथ्म है। एलन ट्यूरिंग की उपलब्धियों में से एक थीऔपचारिक रूप से सटीक विधेय का प्रतिनिधित्व, जिसकी मदद से अनौपचारिक को बदलना संभव होगा, यदि विधि दक्षता की स्थिति का उपयोग किया जाता है। चर्च ने वही खोज की।
पुनरावर्ती कार्यों की बुनियादी अवधारणाएँ
पहली नज़र में ट्यूरिंग का विधेय परिवर्तन, उनके सहयोगी द्वारा प्रस्तावित एक से अलग लग रहा था। लेकिन परिणामस्वरूप, वे समतुल्य निकले, इस अर्थ में कि उनमें से प्रत्येक गणितीय कार्यों के एक ही सेट का चयन करता है। चर्च-ट्यूरिंग थीसिस का दावा है कि इस सेट में प्रत्येक फ़ंक्शन शामिल है जिसका मूल्य एक विधि द्वारा प्राप्त किया जा सकता है जो दक्षता की स्थिति को पूरा करता है। दोनों खोजों के बीच एक और अंतर था। यह था कि चर्च ने केवल सकारात्मक पूर्णांक के उदाहरणों पर विचार किया, जबकि ट्यूरिंग ने अपने काम को एक अभिन्न या वास्तविक चर के साथ गणना योग्य कार्यों को कवर करने के रूप में वर्णित किया।
आम पुनरावर्ती कार्य
चर्च के मूल सूत्रीकरण में कहा गया है कि गणना -कैलकुलस का उपयोग करके की जा सकती है। यह सामान्य पुनरावर्ती कार्यों का उपयोग करने के बराबर है। चर्च-ट्यूरिंग थीसिस मूल रूप से सोचा की तुलना में अधिक प्रकार की गणना को शामिल करता है। उदाहरण के लिए, सेलुलर ऑटोमेटा, कॉम्बिनेटर, पंजीकरण मशीन और प्रतिस्थापन प्रणाली से संबंधित। 1933 में, गणितज्ञ कर्ट गोडेल और जैक्स हेरब्रांड ने सामान्य पुनरावर्ती कार्यों नामक एक वर्ग की औपचारिक परिभाषा बनाई। यह उन कार्यों का उपयोग करता है जहां एक से अधिक तर्क संभव हैं।
एक विधि बनानाλ-कलन
1936 में, अलोंसो चर्च ने निर्धारण की एक विधि बनाई जिसे -कैलकुस कहा जाता है। वह प्राकृतिक संख्याओं से जुड़ा था। -कैलकुलस के भीतर, वैज्ञानिक ने उनके एन्कोडिंग का निर्धारण किया। नतीजतन, उन्हें चर्च नंबर कहा जाता है। प्राकृत संख्याओं पर आधारित एक फलन को -कम्प्यूटेबल कहा जाता था। एक और परिभाषा थी। चर्च की थीसिस के कार्य को दो शर्तों के तहत -कम्प्यूटेबल कहा जाता है। पहला ऐसा लग रहा था: यदि इसकी गणना चर्च के तत्वों पर की गई थी, और दूसरी शर्त λ-कैलकुलस के सदस्य द्वारा प्रतिनिधित्व किए जाने की संभावना थी।
1936 में भी, अपने सहयोगी के काम का अध्ययन करने से पहले, ट्यूरिंग ने अमूर्त मशीनों के लिए एक सैद्धांतिक मॉडल बनाया, जिसका नाम अब उनके नाम पर रखा गया है। वे टेप पर पात्रों में हेरफेर करके गणना कर सकते थे। यह सैद्धांतिक कंप्यूटर विज्ञान में पाई जाने वाली अन्य गणितीय गतिविधियों पर भी लागू होता है, जैसे क्वांटम संभाव्य कंप्यूटिंग। चर्च की थीसिस के कार्य को बाद में ट्यूरिंग मशीन का उपयोग करके प्रमाणित किया गया था। प्रारंभ में, वे λ-कैलकुलस पर निर्भर थे।
फ़ंक्शन कम्प्यूटेबिलिटी
जब प्राकृतिक संख्याओं को वर्ण अनुक्रम के रूप में उचित रूप से एन्कोड किया जाता है, तो प्राकृतिक संख्याओं पर एक फ़ंक्शन को ट्यूरिंग-कम्प्यूटेबल कहा जाता है यदि सार मशीन ने आवश्यक एल्गोरिदम पाया और इस फ़ंक्शन को टेप पर मुद्रित किया। ऐसा उपकरण, जो 1930 के दशक में मौजूद नहीं था, भविष्य में कंप्यूटर माना जाएगा। सार ट्यूरिंग मशीन और चर्च की थीसिस ने विकास के युग की शुरुआत कीकंप्यूटिंग डिवाइस। यह साबित हो गया कि दोनों वैज्ञानिकों द्वारा औपचारिक रूप से परिभाषित कार्यों के वर्ग मेल खाते हैं। इसलिए, परिणामस्वरूप, दोनों कथनों को एक में जोड़ दिया गया। कम्प्यूटेशनल फ़ंक्शंस और चर्च की थीसिस का भी कम्प्यूटेबिलिटी की अवधारणा पर एक मजबूत प्रभाव था। वे गणितीय तर्क और प्रमाण सिद्धांत के लिए एक महत्वपूर्ण उपकरण भी बन गए।
विधि का औचित्य और समस्याएं
थीसिस पर परस्पर विरोधी विचार हैं। 1936 में चर्च और ट्यूरिंग द्वारा प्रस्तावित "कार्य परिकल्पना" के लिए कई सबूत एकत्र किए गए थे। लेकिन दिए गए से नए प्रभावी रूप से गणना योग्य कार्यों की खोज के लिए सभी ज्ञात विधियां या संचालन मशीनों के निर्माण के तरीकों से जुड़े थे, जो तब मौजूद नहीं थे। चर्च-ट्यूरिंग थीसिस को साबित करने के लिए, इस तथ्य से शुरू होता है कि गणना का हर यथार्थवादी मॉडल समकक्ष है।
विभिन्न विश्लेषणों की विविधता के कारण, इसे आम तौर पर विशेष रूप से मजबूत सबूत माना जाता है। प्रभावी रूप से गणना योग्य फ़ंक्शन की सहज धारणा को अधिक सटीक रूप से परिभाषित करने के सभी प्रयास समतुल्य निकले। प्रस्तावित किए गए प्रत्येक विश्लेषण ने कार्यों के एक ही वर्ग को एकल करने के लिए सिद्ध किया है, अर्थात् वे जो ट्यूरिंग मशीनों द्वारा गणना योग्य हैं। लेकिन कुछ कम्प्यूटेशनल मॉडल विभिन्न कार्यों के लिए समय और स्मृति उपयोग के मामले में अधिक कुशल साबित हुए। बाद में यह नोट किया गया कि पुनरावर्ती कार्यों और चर्च की थीसिस की मूल अवधारणाएं काल्पनिक हैं।
थीसिस एम
ट्यूरिंग की थीसिस और इस दावे के बीच अंतर करना महत्वपूर्ण है कि कंप्यूटिंग डिवाइस द्वारा गणना की जा सकने वाली किसी भी चीज़ की गणना उसकी मशीन द्वारा की जा सकती है। दूसरे विकल्प की अपनी परिभाषा है। गांधी दूसरे वाक्य को "थीसिस एम" कहते हैं। यह इस प्रकार है: "जो कुछ भी एक उपकरण द्वारा गणना की जा सकती है उसकी गणना एक ट्यूरिंग मशीन द्वारा की जा सकती है।" थीसिस के संकीर्ण अर्थ में, यह एक अनुभवजन्य प्रस्ताव है जिसका सत्य मूल्य अज्ञात है। ट्यूरिंग की थीसिस और "थीसिस एम" कभी-कभी भ्रमित होते हैं। दूसरा संस्करण मोटे तौर पर गलत है। विभिन्न सशर्त मशीनों का वर्णन किया गया है जो उन कार्यों की गणना कर सकते हैं जो ट्यूरिंग गणना योग्य नहीं हैं। यह ध्यान रखना महत्वपूर्ण है कि पहली थीसिस में दूसरी थीसिस शामिल नहीं है, बल्कि इसके मिथ्यात्व के अनुरूप है।
थीसिस का उल्टा प्रभाव
कम्प्यूटेबिलिटी सिद्धांत में, चर्च की थीसिस का उपयोग सामान्य पुनरावर्ती कार्यों के एक वर्ग द्वारा कम्प्यूटेबिलिटी की धारणा के विवरण के रूप में किया जाता है। अमेरिकी स्टीफन क्लेन ने अधिक सामान्य सूत्रीकरण दिया। उन्होंने आंशिक रूप से पुनरावर्ती सभी आंशिक कार्यों को एल्गोरिदम द्वारा गणना योग्य कहा।
विपरीत निहितार्थ को आमतौर पर चर्च की रिवर्स थीसिस के रूप में जाना जाता है। यह इस तथ्य में निहित है कि सकारात्मक पूर्णांक के प्रत्येक पुनरावर्ती कार्य का कुशलतापूर्वक मूल्यांकन किया जाता है। एक संकीर्ण अर्थ में, एक थीसिस बस ऐसी संभावना को दर्शाता है। और व्यापक अर्थ में, यह इस सवाल से अलग है कि क्या यह सशर्त मशीन इसमें मौजूद हो सकती है।
क्वांटम कंप्यूटर
गणनीय कार्यों की अवधारणा और चर्च की थीसिस गणित, मशीन सिद्धांत और कई अन्य विज्ञानों के लिए एक महत्वपूर्ण खोज बन गई। लेकिन तकनीक बहुत बदल गई है और इसमें सुधार जारी है। यह माना जाता है कि क्वांटम कंप्यूटर आधुनिक लोगों की तुलना में कम समय के साथ कई सामान्य कार्य कर सकते हैं। लेकिन सवाल बने रहते हैं, जैसे रुकने की समस्या। क्वांटम कंप्यूटर इसका उत्तर नहीं दे सकता। और, चर्च-ट्यूरिंग थीसिस के अनुसार, कोई अन्य कंप्यूटिंग डिवाइस भी नहीं है।
