History of the Church–Turing thesis
चर्च-ट्यूरिंग थीसिस ("थीसिस") के इतिहास में उन कार्यों की प्रकृति के अध्ययन के विकास का इतिहास शामिल है जिनके मूल्य प्रभावी रूप से गणना योग्य हैं; या, अधिक आधुनिक शब्दों में, ऐसे कार्य जिनके मूल्य एल्गोरिथम रूप से गणना योग्य हैं। यह आधुनिक गणितीय सिद्धांत और कंप्यूटर विज्ञान में एक महत्वपूर्ण विषय है, विशेष रूप से अलोंजो चर्च और एलन ट्यूरिंग के काम से जुड़ा हुआ है। "गणना" और "पुनरावृत्ति" के अर्थ की बहस और खोज लंबी और विवादास्पद रही है। यह लेख "स्वयंसिद्ध" के अर्थ की हालिया चर्चा के माध्यम से 1889 में पीनो के स्वयंसिद्धों से उस बहस और खोज का विवरण प्रदान करता है। पीनो के अंकगणित के नौ स्वयंसिद्ध सिद्धांत 1889 में, ग्यूसेप पीनो ने डेडेकिंड के काम के आधार पर एक नई विधि द्वारा प्रस्तुत अपने अंकगणित के सिद्धांतों को प्रस्तुत किया। सोरे का सुझाव है कि "आदिम पुनरावृत्ति" की उत्पत्ति औपचारिक रूप से पीनो के स्वयंसिद्धों के साथ शुरू हुई, हालांकि "उन्नीसवीं शताब्दी से काफी पहले गणितविदों ने प्रेरण द्वारा एक फलन को परिभाषित करने के सिद्धांत का उपयोग किया था। डेडेकिंड 1888 ने स्वीकृत स्वयंसिद्धियों का उपयोग करते हुए साबित किया कि इस तरह की परिभाषा एक अद्वितीय कार्य को परिभाषित करती है, और उन्होंने इसे m + n, m x n, और mn कार्यों की परिभाषा पर लागू किया। डेडेकिंड के इस काम के आधार पर, पीनो 1889 और 1891 ने सकारात्मक पूर्णांकों के लिए परिचित पाँच [एस. आई. सी] स्वयंसिद्ध शब्द लिखे। अपने पाँचवें [एसआईसी] स्वयंसिद्ध, गणितीय प्रेरण के एक साथी के रूप में, पीनो ने प्रेरण द्वारा परिभाषा का उपयोग किया, जिसे आदिम पुनरावृत्ति कहा जाता है (पीटर 1934 और क्लेन 1936 के बाद से)। "। ध्यान दें कि वास्तव में पीनो के स्वयंसिद्ध संख्या में 9 हैं और स्वयंसिद्ध 9 पुनरावृत्ति/प्रेरण स्वयंसिद्ध है। "इसके बाद 9 को घटाकर 5 कर दिया गया क्योंकि स्वयंसिद्ध 2,3,4 और 5 जो पहचान से संबंधित हैं, अंतर्निहित तर्क से संबंधित हैं। यह उन पाँच स्वयंसिद्धियों को छोड़ देता है जो सार्वभौमिक रूप से "पीनो स्वयंसिद्धियों" के रूप में जाने जाते हैं। पीनो स्वीकार करते हैं (1891बी, पृष्ठ 93) कि उनके स्वयंसिद्ध सिद्धांत डेडेकिंड से आते हैं। "। हिल्बर्ट और 1900 में पेरिस में गणितविदों की अंतर्राष्ट्रीय कांग्रेस (आई. सी. एम.) में प्रसिद्ध गणितशास्त्री डेविड हिल्बर्ट ने समस्याओं का एक समूह प्रस्तुत किया-जिसे अब हिल्बर्ट की समस्याओं के रूप में जाना जाता है-उनका प्रकाश स्तंभ बीसवीं शताब्दी के गणितविदों के लिए मार्ग प्रशस्त करता है। हिल्बर्ट की दूसरी और 10वीं समस्याओं ने ("निर्णय समस्या") की शुरुआत की। अपनी दूसरी समस्या में उन्होंने एक प्रमाण मांगा कि "अंकगणित" "सुसंगत" है। कर्ट गोडेल 1931 में साबित करेंगे कि, जिसे उन्होंने "पी" कहा था (जिसे आजकल पीनो अंकगणित कहा जाता है), "अनिश्चित वाक्य [प्रस्ताव] मौजूद हैं"। इस वजह से, "पी की स्थिरता पी में अप्रमाणित है, बशर्ते पी सुसंगत हो"। जबकि गोडेल का प्रमाण अलोंजो चर्च और एलन ट्यूरिंग के समाधान के लिए आवश्यक उपकरणों को प्रदर्शित करेगा, वह खुद इसका जवाब नहीं देगा। यह हिल्बर्ट की 10वीं समस्या के भीतर है जहाँ एक का प्रश्न वास्तव में प्रकट होता है। द्रव्य का मूल निम्नलिखित प्रश्न थाः "हमारा क्या मतलब है जब हम कहते हैं कि एक फलन 'प्रभावी रूप से गणना योग्य' है?" इसका उत्तर इस प्रभाव के लिए कुछ होगाः "जब फलन की गणना एक यांत्रिक प्रक्रिया (प्रक्रिया, विधि) द्वारा की जाती है।" यद्यपि आजकल आसानी से कहा जा सकता है, प्रश्न (और उत्तर) सटीक रूप से तैयार होने से पहले लगभग 30 वर्षों तक चलता रहेगा। समस्या 10 का हिल्बर्ट का मूल विवरण इस प्रकार शुरू होता हैः "10। डायोफैंटाइन समीकरण की समाधानशीलता का निर्धारण। किसी भी संख्या में अज्ञात मात्राओं और तर्कसंगत अभिन्न गुणांक के साथ एक डायोफैंटाइन समीकरण को देखते हुएः एक ऐसी प्रक्रिया तैयार करना जिसके अनुसार इसे सीमित संख्या में संचालन में निर्धारित किया जा सके कि क्या समीकरण तर्कसंगत पूर्णांकों में हल करने योग्य है। 1922 तक, डायोफैंटाइन समीकरणों पर लागू एक विशिष्ट प्रश्न किसी भी गणितीय सूत्र के लिए "निर्णय विधि" के बारे में अधिक सामान्य प्रश्न के रूप में विकसित हो गया था। मार्टिन डेविस इसे इस तरह से समझाते हैंः मान लीजिए कि हमें एक "गणनात्मक प्रक्रिया" दी गई है जिसमें (1) स्वयंसिद्धों का एक समूह और (2) प्रथम-क्रम तर्क में लिखा गया एक तार्किक निष्कर्ष है, जिसे डेविस "फ्रेज के कटौती के नियम" (या बूलियन तर्क के आधुनिक समकक्ष) कहते हैं। गोडेल के डॉक्टरेट शोध प्रबंध ने साबित किया कि फ्रेज के नियम पूर्ण थे. "इस अर्थ में कि हर वैध सूत्र सिद्ध करने योग्य है।" उस उत्साहजनक तथ्य को देखते हुए, क्या कोई सामान्यीकृत "गणनात्मक प्रक्रिया" हो सकती है जो हमें बताए कि क्या इसके परिसर से कोई निष्कर्ष निकाला जा सकता है? डेविस ऐसी गणनात्मक प्रक्रियाओं को "एल्गोरिदम" कहते हैं। यह एक एल्गोरिथ्म भी होगा। "सिद्धांत रूप में, [के] के लिए एक एल्गोरिथ्म सभी मानव अनुमानात्मक तर्क को क्रूर गणना में कम कर देता।" दूसरे शब्दों मेंः क्या कोई "एल्गोरिथ्म" है जो हमें बता सकता है कि क्या कोई सूत्र "सही" है (यानी। एक एल्गोरिथ्म जो हमेशा सही निर्णय "सत्य" या "झूठ" देता है?) ". हिल्बर्ट को यह स्पष्ट लग रहा था कि इस समस्या के समाधान के साथ, एंटशेइडंग्सप्रॉब्लम, कि सिद्धांत रूप में सभी गणितीय प्रश्नों को विशुद्ध रूप से यांत्रिक तरीके से हल करना संभव होना चाहिए। इसलिए, अनसुलझी समस्याओं को देखते हुए, यदि हिल्बर्ट सही थे, तो एंटशेइडंग्सप्रॉब्लम अपने आप में अनसुलझी होनी चाहिए। वास्तव मेंः हमारे एल्गोरिदम के बारे में क्या? क्या यह सीमित संख्या में चरणों में निर्धारित कर सकता है कि क्या यह अपने आप में "सफल" और "सत्यवादी" है (यानी, यह एक अंतहीन "चक्र" या "लूप" में नहीं लटकता है, और यह अपने स्वयं के व्यवहार और परिणामों के बारे में सही निर्णय "सत्य" या "झूठ" देता है)? हिल्बर्ट की दूसरी और दसवीं समस्याओं से तीन समस्याएं 1928 की कांग्रेस में [बोलोग्ना, इटली में] हिल्बर्ट ने प्रश्न को बहुत सावधानी से तीन भागों में परिष्कृत किया। स्टीफन हॉकिंग का सारांश निम्नलिखित हैः "1. यह साबित करने के लिए कि सभी सही गणितीय कथनों को सिद्ध किया जा सकता है, यानी गणित की पूर्णता। "2. यह साबित करने के लिए कि केवल सही गणितीय कथनों को ही सिद्ध किया जा सकता है, अर्थात गणित की स्थिरता। गणित की निर्णायकता को साबित करने के लिए, यानी किसी भी गणितीय प्रस्ताव की सच्चाई या असत्यता को तय करने के लिए एक निर्णय प्रक्रिया का अस्तित्व। गैब्रियल सूडान (1927) और विल्हेम एकरमैन (1928) के लिए अपरिवर्तनीय सरल अंकगणितीय कार्य पुनरावर्ती कार्य प्रदर्शित करते हैं जो आदिम पुनरावर्ती नहीं हैंः "क्या ऐसी पुनरावृत्तियाँ हैं जो आदिम पुनरावर्तन के लिए अपरिवर्तनीय नहीं हैं; और विशेष रूप से पुनरावृत्ति का उपयोग एक ऐसे कार्य को परिभाषित करने के लिए किया जा सकता है जो आदिम पुनरावर्ती नहीं है? "यह प्रश्न निरंतरता समस्या पर 1926 में हिल्बर्ट के एक अनुमान से उत्पन्न हुआ था, और एकरमैन 1928 द्वारा इसका उत्तर दिया गया था [हांः ऐसी पुनरावृत्तियाँ हैं जो आदिम पुनरावर्ती नहीं हैं]।" बाद के वर्षों में क्लेन ने देखा कि रोसा पेटर (1935) ने एकरमैन के उदाहरण को सरल बनाया। हिल्बर्ट-बर्नेज़ 1934 ") और राफेल रॉबिन्सन (1948)। पीटर ने एक और उदाहरण (1935) का प्रदर्शन किया जिसने कैंटर के विकर्ण तर्क को नियोजित किया। पीटर (1950) और एकरमैन (1940) ने भी "ट्रांसफाइनाइट रिकर्शन" प्रदर्शित किया, और इसने क्लेन को आश्चर्यचकित कियाः ". क्या हम किसी भी" रिकर्शन "की धारणा को किसी भी सटीक तरीके से चिह्नित कर सकते हैं, या सभी" रिकर्सिव फ़ंक्शंस "के वर्ग को। क्लेन ने निष्कर्ष निकाला कि सभी "पुनरावृत्तियों" में (i) प्रारंभिक पुनरावर्ती कार्यों की अपनी §54 औपचारिक गणनाओं में प्रस्तुत औपचारिक विश्लेषण और (ii) गणितीय प्रेरण का उपयोग शामिल है। वह तुरंत आगे कहते हैं कि वास्तव में गोडेल-हर्ब्रैंड परिभाषा वास्तव में "सभी पुनरावर्ती कार्यों की विशेषता है"-नीचे 1934 में उद्धरण देखें। गोडेल का प्रमाण 1930 में, गणितशास्त्री हिल्बर्ट के लिए एक गणित बैठक और सेवानिवृत्ति कार्यक्रम के लिए एकत्र हुए। जैसा कि भाग्य के पास होगा, "उसी बैठक में, एक युवा चेक गणितशास्त्री, कर्ट गोडेल ने परिणामों की घोषणा की, जिसने इसे [हिल्बर्ट की राय कि तीनों उत्तर हाँ थे] एक गंभीर झटका दिया।" उन्होंने घोषणा की कि 1928 के हिल्बर्ट के तीन प्रश्नों में से पहले दो का उत्तर नहीं था। इसके बाद 1931 में गोडेल ने अपना प्रसिद्ध पेपर ऑन फॉर्मली अनडिसीडबल प्रपोसिशंस ऑफ प्रिंसिपिया मैथेमेटिका एंड रिलेटेड प्रकाशित किया इस पेपर की अपनी प्रस्तावना में मार्टिन डेविस एक चेतावनी देते हैंः "पाठक को चेतावनी दी जानी चाहिए कि [इस विशेष पेपर में] जिसे गोडेल रिकर्सिव फंक्शन कहते हैं, उन्हें अब प्रिमिटिव रिकर्सिव फंक्शन कहा जाता है। (संशोधित शब्दावली क्लेन द्वारा पेश की गई थी) "। "प्रभावी गणना" का गोडेल विस्तार क्लेन (1952) को उद्धृत करने के लिए, "सभी" पुनरावर्ती कार्यों "का लक्षण वर्णन गोडेल 1934 द्वारा 'सामान्य पुनरावर्ती कार्य' की परिभाषा में पूरा किया गया था, जिन्होंने हरब्रांड के सुझाव पर निर्माण किया था" (क्लेन 1952:274)। गोडेल ने इंस्टीट्यूट फॉर एडवांस्ड स्टडी (आई. ए. एस.), प्रिंसटन एन. जे. में व्याख्यानों की एक श्रृंखला दी। मार्टिन डेविस डेविस द्वारा लिखित एक प्रस्तावना में डेविस ने कहा है कि "डॉ. गोडेल ने एक पत्र में कहा है कि वे इन व्याख्यानों के समय, इस बात से बिल्कुल भी आश्वस्त नहीं थे कि उनकी पुनरावृत्ति की अवधारणा में सभी संभावित पुनरावृत्तियां शामिल थीं।" डॉसन का कहना है कि इन व्याख्यानों का उद्देश्य इस चिंता को स्पष्ट करना था कि "अपूर्णता प्रमेय किसी तरह औपचारिकरण की विशिष्टताओं पर निर्भर थे": "गोडेल ने अपने 1934 के पेपर के अंतिम खंड में एकरमैन के उदाहरण का उल्लेख किया," सामान्य पुनरावर्ती कार्य "की अवधारणा को प्रेरित करने के एक तरीके के रूप में जिसे उन्होंने वहां परिभाषित किया था; लेकिन इससे पहले फुटनोट 3 में, उन्होंने पहले ही अनुमान लगा लिया था (" एक शोध सिद्धांत "के रूप में) कि सभी परिमित रूप से गणना योग्य कार्यों को प्राप्त किया जा सकता है। "इस अनुमान के बाद से बहुत सारी टिप्पणियां सामने आई हैं। विशेष रूप से, जब मार्टिन डेविस ने गोडेल के 1934 के व्याख्यानों को [डेविस 1965:41 ff में] प्रकाशित करने का बीड़ा उठाया तो उन्होंने इसे चर्च के थीसिस का एक रूप माना; लेकिन डेविस को लिखे एक पत्र में। गोडेल ने जोर देकर कहा कि यह "सच नहीं" था क्योंकि उन व्याख्यानों के समय वह "बिल्कुल भी आश्वस्त नहीं थे" कि उनकी पुनरावृत्ति की अवधारणा में "सभी संभावित पुनरावृत्तियाँ" शामिल थीं। बल्कि, उन्होंने कहा, "वहाँ कहा गया अनुमान केवल 'सीमित (गणना) प्रक्रिया' और 'पुनरावर्ती प्रक्रिया' की समानता को संदर्भित करता है।" इस मुद्दे को स्पष्ट करने के लिए गोडेल ने व्याख्यानों में एक पोस्टस्क्रिप्ट जोड़ा, जिसमें उन्होंने संकेत दिया कि जिस बात ने उन्हें अंततः आश्वस्त किया था कि सहज रूप से कम्प्यूटेबल कार्य उन लोगों के साथ मेल खाते हैं जो सामान्य पुनरावर्ती थे, वह एलन ट्यूरिंग का काम था। "प्रभावी संगणनाशीलता की अनौपचारिक धारणा के पर्याप्त लक्षण वर्णन के रूप में सामान्य पुनरावृत्ति या λ-परिभाषा को मानने के लिए गोडेल की अनिच्छा की कई लेखकों द्वारा विस्तार से जांच की गई है [फुटनोट 248: विशेष रूप से डेविस 1982; गैंडी 1980 और 1988; सिग 1994 देखें]। एक आम सहमति है कि, वास्तव में, न तो गोडेल की और न ही चर्च की औपचारिकताएं एलन ट्यूरिंग के विश्लेषण की तरह इतनी स्पष्ट या आंतरिक रूप से प्रेरक थीं, और विल्फ्रेड सीग ने तर्क दिया है कि चर्च के थीसिस के पक्ष में साक्ष्य "विभिन्न धारणाओं के संगम" द्वारा प्रदान किए गए हैं (तथ्य यह है कि चर्च, गोडेल, पोस्ट और एलन ट्यूरिंग द्वारा प्रस्तावित सभी प्रणालियों में एक ही विस्तार है) जो आम तौर पर माना जाता है, उससे कम सम्मोहक है। इसलिए, गोडेल की जन्मजात सावधानी के अलावा उनके संदेह के अच्छे कारण थे। लेकिन फिर, वह सामान्य पुनरावृत्ति की अपनी धारणा के माध्यम से क्या हासिल करने का प्रयास कर रहा था? ". बल्कि, गोडेल ने हरब्रांड के विचारों के संशोधन के माध्यम से [सामान्य पुनरावर्ती कार्यों के वर्ग की] अपनी परिभाषा प्राप्त की. और विल्फ्रेड सीग ने तर्क दिया है कि 1934 के पेपर के अंतिम खंड में उनका वास्तविक उद्देश्य [हरब्रांड की] प्रमाण की ज्ञानशास्त्रीय रूप से प्रतिबंधित धारणा से पुनरावर्ती कार्यों को अलग करना था" "समीकरण प्राप्त करने के लिए यांत्रिक नियमों को निर्दिष्ट करके।" सीग का सुझाव है कि गोडेल की "सामान्य" पुनरावृत्ति की धारणा के बारे में जो अधिक सामान्य था, वह यह था कि हरब्रांड का उद्देश्य केवल उन कार्यों को चिह्नित करना था जिन्हें परिमित साधनों [250] द्वारा पुनरावर्ती साबित किया जा सकता था। प्रिंसटन क्लेन और रॉसर में गोडेल के व्याख्यानों ने प्रिंसटन में गोडेल के 1934 के व्याख्यानों का प्रतिलेखन किया। अपने शोधपत्र 'जनरल रिकर्सिव फ़ंक्शंस ऑफ़ नेचुरल नंबर्स' में क्लेन कहते हैंः "प्राकृतिक संख्याओं के सामान्य पुनरावर्ती फलन की एक परिभाषा का सुझाव हरब्रांड ने गोडेल को दिया था, और इसका उपयोग गोडेल ने 1934 में प्रिंसटन में व्याख्यानों की एक श्रृंखला में एक महत्वपूर्ण संशोधन के साथ किया था।" गोडेल के अर्थ में एक पुनरावर्ती फलन (संबंध) को अब एक आदिम पुनरावर्ती फलन (संबंध) कहा जाएगा। "प्रभावी रूप से गणना योग्य" चर्च के पेपर एन अनसोल्वेबल प्रॉब्लम ऑफ एलीमेंट्री नंबर थ्योरी (1936) की चर्च परिभाषा ने साबित किया कि λ-कैलकुलस और गोडेल-हर्ब्रैंड के सामान्य पुनरावृत्ति के भीतर एंटशेइडंग्सप्रॉब्लम अनिर्णायक थी; इसके अलावा चर्च ने क्लेन के दो प्रमेयों का हवाला दिया जो साबित करते हैं कि λ-कैलकुलस में परिभाषित कार्य सामान्य पुनरावृत्ति द्वारा परिभाषित कार्यों के समान हैंः "प्रमेय XVI। सकारात्मक पूर्णांकों का प्रत्येक पुनरावर्ती फलन λ-definable.16 "प्रमेय XVII" है। सकारात्मक पूर्णांकों का प्रत्येक λ-परिभाषित फलन recursive.17 "16 है। यहाँ के रूप में यह पहली बार क्लेन द्वारा प्राप्त किया गया था। "17 यह परिणाम वर्तमान लेखक और एस. सी. क्लेन द्वारा लगभग एक ही समय में स्वतंत्र रूप से प्राप्त किया गया था। पेपर एक बहुत लंबे फुटनोट के साथ खुलता है, 3। एक अन्य फुटनोट, 9, भी दिलचस्प है। मार्टिन डेविस का कहना है कि "यह पेपर मुख्य रूप से अपने स्पष्ट कथन के लिए महत्वपूर्ण है (जिसे चर्च की थीसिस के रूप में जाना जाता है) कि जिन कार्यों की गणना एक सीमित एल्गोरिथ्म द्वारा की जा सकती है, वे सटीक रूप से पुनरावर्ती कार्य हैं, और इसके परिणामस्वरूप एक स्पष्ट अनसुलझी समस्या दी जा सकती है": "3 जैसा कि दिखाई देगा, प्रभावी गणना की इस परिभाषा को दो समकक्ष रूपों में से किसी एक में कहा जा सकता है, (1). λ-परिभाषित. 2). पुनरावर्ती। λ-परिभाषा की धारणा संयुक्त रूप से वर्तमान लेखक और एस. सी. क्लेन के कारण है, इसकी दिशा में क्रमिक कदम वर्तमान लेखक द्वारा एनल्स ऑफ मैथेमैटिक्स, वॉल्यूम में उठाए गए हैं। 34 (1933), पृष्ठ 863, और अमेरिकन जर्नल ऑफ मैथेमैटिक्स में क्लेन, खंड। 57 (1935), पृष्ठ 219। नीचे §4 के अर्थ में पुनरावृत्ति की धारणा जैक्स हरब्रांड और कर्ट गोडेल के कारण है, जैसा कि वहाँ समझाया गया है। और दोनों धारणाओं की समानता का प्रमाण मुख्य रूप से क्लेन के कारण है, लेकिन आंशिक रूप से वर्तमान लेखक और जे। बी. रोसर.. प्रभावी गणना की सहज धारणा के साथ इन धारणाओं की पहचान करने का प्रस्ताव पहले वर्तमान पत्र में किया गया है (लेकिन नीचे §7 का पहला फुटनोट देखें)। "क्लेन (अमेरिकन जर्नल ऑफ मैथेमैटिक्स, 1935) के तरीकों की सहायता से, वर्तमान पेपर के विचारों को, तुलनात्मक रूप से मामूली संशोधन के साथ, पुनरावृत्ति की धारणा का उपयोग किए बिना, पूरी तरह से λ-परिभाषा के संदर्भ में किया जा सकता है। दूसरी ओर, चूंकि वर्तमान पेपर के परिणाम प्राप्त किए गए थे, इसलिए क्लेन द्वारा यह दिखाया गया है (उनके आगामी पेपर, "प्राकृतिक संख्याओं के सामान्य पुनरावर्ती कार्य" देखें) कि λ-परिभाषा का उपयोग किए बिना, अनुरूप परिणाम पूरी तरह से पुनरावृत्ति के संदर्भ में प्राप्त किए जा सकते हैं। हालाँकि, यह तथ्य कि दो ऐसी व्यापक रूप से अलग और (लेखक की राय में) प्रभावी गणनाशीलता की समान रूप से प्राकृतिक परिभाषाएँ समतुल्य साबित होती हैं, यह विश्वास करने के लिए नीचे दिए गए कारणों की ताकत को बढ़ाती हैं कि वे इस धारणा के सामान्य लक्षण वर्णन के रूप में हैं जो इसकी सामान्य सहज ज्ञान युक्त समझ के अनुरूप है। फुटनोट 9 अनुभाग §4 रिकर्सिव कार्यों में हैः "9 यह परिभाषा [" रिकर्सिव "की] रिकर्सिव कार्यों की एक परिभाषा से निकटता से संबंधित है, और द्वारा सुझाई गई थी, जिसे कर्ट गोडेल द्वारा प्रिंसटन, एन. जे., 1934 में व्याख्यानों में प्रस्तावित किया गया था, और उनके द्वारा आंशिक रूप से जैक्स हरब्रांड के एक अप्रकाशित सुझाव को श्रेय दिया गया था। जिन प्रमुख विशेषताओं में पुनरावृत्ति की वर्तमान परिभाषा गोडेल की परिभाषा से अलग है, वे एस. सी. क्लेन के कारण हैं। क्लेन द्वारा "प्राकृतिक संख्याओं के सामान्य पुनरावर्ती फलन" शीर्षक वाले एक आगामी पेपर में, यह इस प्रकार है कि वर्तमान अर्थ में प्रत्येक पुनरावर्ती फलन भी गोडेल (1934) के अर्थ में पुनरावर्ती है और इसके विपरीत है। चर्च के पेपर एन अनसोल्वेबल प्रॉब्लम ऑफ एलीमेंट्री नंबर थ्योरी (1936) से कुछ समय पहले गोडेल और चर्च के बीच एक बातचीत हुई कि क्या "एल्गोरिथ्म" और "प्रभावी गणना" की धारणा की परिभाषा के लिए λ-परिभाषा पर्याप्त थी या नहीं। चर्च (1936) में हम देखते हैं, अध्याय §7 के तहत प्रभावी गणना की धारणा, एक फुटनोट 18 जो निम्नलिखित बताता हैः "18 प्रभावी गणना और पुनरावृत्ति के बीच संबंध का सवाल (जिसका उत्तर यहाँ दो धारणाओं की पहचान करके प्रस्तावित किया गया है) लेखक के साथ बातचीत में गोडेल द्वारा उठाया गया था। प्रभावी गणना और λ-परिभाषा के बीच संबंध का संबंधित प्रश्न पहले लेखक द्वारा स्वतंत्र रूप से प्रस्तावित किया गया था। चर्च की "पहचान" करने का अर्थ है-"पहचान स्थापित करना" नहीं-बल्कि "समान होने या बनने का कारण बनना", "एकजुट होने की कल्पना करना" (जैसा कि आत्मा, दृष्टिकोण या सिद्धांत में) (वी. टी. रूप में), और (वी. आई. रूप में) "समान होना या बनना"। "प्राकृतिक कानून" के रूप में पोस्ट और "प्रभावी गणना" के बारे में पोस्ट के संदेह कि क्या पुनरावृत्ति "प्रभावी गणना" की पर्याप्त परिभाषा थी या नहीं, साथ ही चर्च के पेपर के प्रकाशन ने उन्हें 1936 के अंत में "मनोवैज्ञानिक निष्ठा" के साथ एक "सूत्रीकरण" का प्रस्ताव करने के लिए प्रोत्साहित कियाः एक कार्यकर्ता प्रत्येक बॉक्स में कागज की एक शीट पर मशीन जैसे "आदिम कृत्यों" का प्रदर्शन करते हुए "रिक्त स्थान या बक्से के एक अनुक्रम" से गुजरता है। कर्मचारी "दिशाओं के एक निश्चित अपरिवर्तनीय समूह" से सुसज्जित है। प्रत्येक निर्देश में तीन या चार प्रतीक होते हैंः (1) एक पहचान लेबल/संख्या, (2) एक ऑपरेशन, (3) अगला निर्देश जी; हालाँकि, यदि निर्देश प्रकार (ई) का है और निर्धारण "हाँ" है तो निर्देश जी "अन्यथा" यदि यह "नहीं" निर्देश जी है। "आदिम कार्य" 5 में से केवल 1 प्रकार के होते हैंः (ए) कागज को उस डिब्बे में चिह्नित करें जिसमें वह है (या पहले से ही एक निशान को अधिक चिह्नित करें), (बी) निशान को मिटा दें (या अधिक मिटा दें), (सी) एक कमरे को दाईं ओर ले जाएं, (डी) एक कमरे को बाईं ओर ले जाएं, (ई) यह निर्धारित करें कि कागज चिह्नित है या खाली है। कर्मचारी प्रारंभिक कक्ष में चरण 1 से शुरू करता है, और वही करता है जो निर्देश उन्हें करने के लिए निर्देशित करते हैं। (पोस्ट-ट्यूरिंग मशीन पर अधिक देखें।) "अंतर्ज्ञानी सिद्धांतों" के बारे में परिचय में उल्लिखित इस मामले ने पोस्ट को चर्च पर एक शक्तिशाली प्रहार करने के लिए प्रेरित कियाः "लेखक को उम्मीद है कि वर्तमान सूत्रीकरण गोडेल-चर्च development.7 के अर्थ में तार्किक रूप से पुनरावृत्ति के बराबर होगा, हालांकि, इसका उद्देश्य न केवल एक निश्चित तार्किक शक्ति की प्रणाली को प्रस्तुत करना है, बल्कि इसके सीमित क्षेत्र में, मनोवैज्ञानिक निष्ठा भी है। बाद के अर्थ में व्यापक और व्यापक सूत्रीकरणों पर विचार किया जाता है। दूसरी ओर, हमारा उद्देश्य यह दिखाना होगा कि ऐसे सभी सूत्रीकरण 1 के लिए तार्किक रूप से कम करने योग्य हैं। हम वर्तमान समय में इस निष्कर्ष को एक कार्यशील परिकल्पना के रूप में प्रस्तुत करते हैं। और हमारे दिमाग में ऐसा है कि चर्च की प्रभावी गणना की पहचान recursiveness.8 "(मूल में इटैलिक) 7 [वह एक प्रमाण के लिए एक दृष्टिकोण को स्केच करता है] 8" Cf। चर्च, ताला। सीट, पीपी। 346, 356-358। वास्तव में चर्च और अन्य लोगों द्वारा पहले से किए गए कार्य इस पहचान को कार्यशील परिकल्पना चरण से काफी आगे ले जाते हैं। लेकिन एक परिभाषा के तहत इस पहचान को छिपाने के लिए इस तथ्य को छिपाया जाता है कि होमो सेपियन्स की गणितीय शक्ति की सीमाओं में एक मौलिक खोज की गई है और हमें इसके निरंतर सत्यापन की आवश्यकता के लिए अंधा कर देती है। दूसरे शब्दों में पोस्ट कह रहा है "सिर्फ इसलिए कि आपने इसे परिभाषित किया है, इसलिए यह वास्तव में ऐसा नहीं है; आपकी परिभाषा एक अंतर्ज्ञान से अधिक कुछ नहीं है।" पोस्ट एक से अधिक परिभाषा की खोज कर रहा थाः "उपरोक्त कार्यक्रम की सफलता, हमारे लिए, इस परिकल्पना को एक परिभाषा या स्वयंसिद्ध में नहीं बल्कि एक प्राकृतिक नियम में बदल देगी। लेखक को ऐसा ही लगता है कि गोडेल की प्रमेय और चर्च के परिणामों को सभी प्रतीकात्मक तर्कों और समाधान के सभी तरीकों से संबंधित निष्कर्षों में बदला जा सकता है। इस विवादास्पद रुख को एलन ट्यूरिंग 1939 में क्रोधी अभिव्यक्ति मिलती है, और यह गोडेल, गैंडी और सीग के साथ फिर से दिखाई देगा। ट्यूरिंग एंड कम्प्यूटेबिलिटी ए. एम. ट्यूरिंग का पेपर ऑन कम्प्यूटेबल नंबर्स, विद एन एप्लीकेशन टू द एंटशेइडंग्सप्रॉब्लम नवंबर 1936 में लंदन मैथमेटिकल सोसाइटी को दिया गया था। फिर से पाठक को एक सावधानी को ध्यान में रखना चाहिएः जैसा कि ट्यूरिंग द्वारा उपयोग किया गया है, "कंप्यूटर" शब्द एक इंसान है, और एक "कंप्यूटर" की क्रिया जिसे वह "कंप्यूटिंग" कहते हैं; उदाहरण के लिए, वे कहते हैं "कम्प्यूटिंग आमतौर पर कागज पर कुछ प्रतीकों को लिखकर की जाती है" (पृष्ठ 135)। लेकिन वह अपनी मशीन-परिभाषा के संदर्भ में "गणना" शब्द का उपयोग करते हैं, और "कम्प्यूटेबल" संख्याओं की उनकी परिभाषा इस प्रकार हैः "कम्प्यूटेबल" संख्याओं को संक्षेप में वास्तविक संख्याओं के रूप में वर्णित किया जा सकता है जिनकी दशमलव के रूप में अभिव्यक्तियाँ सीमित साधनों से गणना की जा सकती हैं। मेरी परिभाषा के अनुसार, एक संख्या गणना योग्य है यदि उसके दशमलव को एक मशीन द्वारा लिखा जा सकता है। " ट्यूरिंग की "मशीन" की परिभाषा क्या है? ट्यूरिंग दो परिभाषाएँ देते हैं, पहला §1 कम्प्यूटिंग मशीनों में एक सारांश और दूसरा §9 में बहुत समान है। अपनी परिभाषा §1 के संबंध में वे कहते हैं कि "औचित्य इस तथ्य में निहित है कि मानव स्मृति आवश्यक रूप से सीमित है", और उन्होंने "सभी" शब्द के उपयोग के साथ अपनी प्रस्तावित मशीन के गंजे दावे के साथ §1 को समाप्त किया "यह मेरा तर्क है कि ये संचालन [टेप-वर्ग पर प्रतीक लिखें, प्रतीक मिटा दें, एक वर्ग को बाएं स्थानांतरित करें, एक वर्ग को दाएं स्थानांतरित करें, प्रतीक के लिए वर्ग स्कैन करें और एक स्कैन किए गए प्रतीक के परिणामस्वरूप मशीन-कॉन्फ़िगरेशन बदलें] में वे सभी शामिल हैं जो एक संख्या की गणना में उपयोग किए जाते हैं।" उपरोक्त कोष्ठकों में एक शब्द का जोर जानबूझकर दिया गया है। धारा 9. I के संबंध में वह मशीन को अधिक वर्गों की जांच करने की अनुमति देता है; यह अधिक वर्ग प्रकार का व्यवहार है जो वह दावा करता है कि एक कंप्यूटर (व्यक्ति) के कार्यों को दर्शाता हैः "मशीन कंप्यूटर द्वारा देखे गए बी वर्गों के अनुरूप बी वर्गों को स्कैन करती है। किसी भी चाल में मशीन स्कैन किए गए वर्ग पर एक प्रतीक को बदल सकती है या स्कैन किए गए वर्गों में से किसी एक को दूसरे वर्ग में बदल सकती है जो दूसरे स्कैन किए गए वर्गों में से एक से एल वर्ग से अधिक दूर नहीं है। अभी वर्णित मशीनें §2 [sic] में परिभाषित कंप्यूटिंग मशीनों से बहुत अनिवार्य रूप से भिन्न नहीं हैं, और इस प्रकार की किसी भी मशीन के अनुरूप एक कंप्यूटिंग मशीन का निर्माण उसी अनुक्रम की गणना करने के लिए किया जा सकता है, अर्थात कंप्यूटर द्वारा गणना की गई अनुक्रम। ट्यूरिंग ने §2 में एक "कंप्यूटिंग मशीन" को परिभाषित किया है (i) "ए-मशीन" ("स्वचालित मशीन") जैसा कि §1 में अतिरिक्त प्रतिबंध के साथ परिभाषित किया गया है (ii): (ii) यह दो प्रकार के प्रतीकों-अंकों 0 और 1-और अन्य प्रतीकों को छापता है। अंक 0 और 1 "मशीन द्वारा गणना किए गए अनुक्रम" का प्रतिनिधित्व करेंगे। इसके अलावा, यह परिभाषित करने के लिए कि क्या संख्या को "कम्प्यूटेबल" माना जाना है, मशीन को 0 और 1 की एक अनंत संख्या छापनी चाहिए; यदि नहीं तो इसे "गोलाकार" माना जाता है; अन्यथा इसे "वृत्त-मुक्त" माना जाता हैः "एक संख्या कम्प्यूटेबल है यदि यह एक वृत्त-मुक्त मशीन द्वारा गणना की गई संख्या से एक पूर्णांक से अलग है"। हालांकि वह इसे अपना "थीसिस" नहीं कहते हैं, ट्यूरिंग एक प्रमाण का प्रस्ताव करते हैं कि उनकी "गणना" चर्च की "प्रभावी गणना" के बराबर हैः "हाल के एक पेपर में अलोंजो चर्च ने" प्रभावी गणना "का एक विचार पेश किया है, जो मेरी" गणना "के बराबर है, लेकिन इसे बहुत अलग तरीके से परिभाषित किया गया है। "कम्प्यूटेबिलिटी" और "प्रभावी गणना" के बीच समानता का प्रमाण वर्तमान पेपर के एक परिशिष्ट में रेखांकित किया गया है। परिशिष्टः संगणनीयता और प्रभावी गणना निम्नलिखित तरीके से शुरू होती है; ध्यान दें कि वह यहाँ पुनरावृत्ति का उल्लेख नहीं करता है, और वास्तव में उसके प्रूफ-स्केच में उसकी मशीन में λ-कैलकुलस में प्रतीकों के तार हैं और कैलकुलस में उसकी मशीन के "पूर्ण विन्यास" हैं, और कहीं भी पुनरावृत्ति का उल्लेख नहीं है। मशीन-संगणनीयता और पुनरावृत्ति की समानता का प्रमाण क्लेन 1943 और 1952 के लिए इंतजार करना चाहिएः "यह प्रमेय कि सभी प्रभावी रूप से गणना करने योग्य (λ-परिभाषित) अनुक्रम संगणनीय हैं और इसके विपरीत रूपरेखा में नीचे साबित किए गए हैं।" गैंडी (1960) इस बोल्ड प्रूफ-स्केच को चर्च के थीसिस के साथ भ्रमित करता प्रतीत होता है; नीचे 1960 और 1995 देखें। इसके अलावा ट्यूरिंग की परिभाषाओं को ध्यान से पढ़ने से पाठक को पता चलता है कि ट्यूरिंग इस बात पर जोर दे रहे थे कि §1 में उनकी प्रस्तावित मशीन के "संचालन" किसी भी कम्प्यूटेबल संख्या की गणना करने के लिए पर्याप्त हैं, और वह मशीन जो §9 में प्रस्तुत मानव "कंप्यूटर" की क्रिया का अनुकरण करती है। 1939 में ट्यूरिंग द्वारा इस बात को दोहराया जाएगा। ट्यूरिंग मशीन गणना के साथ प्रभावी गणना की पहचान करता है एलन ट्यूरिंग की विशाल प्रिंसटन पीएचडी थीसिस (अलोंजो चर्च के तहत) ऑर्डिनल्स पर आधारित तर्क की प्रणालियों के रूप में दिखाई देती है। इसमें वे "प्रभावी रूप से गणना योग्य" की परिभाषा की खोज का सारांश देते हैं। उन्होंने एक परिभाषा का प्रस्ताव किया जैसा कि बोल्डफेस प्रकार में दिखाया गया है जो विशेष रूप से "मशीन गणना" और "प्रभावी रूप से गणना योग्य" की धारणाओं की पहचान करता है (समान रूप से प्रस्तुत करता है)। "एक फलन को" प्रभावी रूप से गणना योग्य "कहा जाता है यदि इसके मान किसी विशुद्ध रूप से यांत्रिक प्रक्रिया द्वारा पाए जा सकते हैं। हालाँकि इस विचार की सहज समझ प्राप्त करना काफी आसान है, फिर भी कुछ और निश्चित, गणितीय रूप से व्यक्त करने योग्य परिभाषा होना वांछनीय है। इस तरह की परिभाषा पहली बार 1934 में प्रिंसटन में गोडेल द्वारा दी गई थी। इन कार्यों को गोडेल द्वारा "सामान्य पुनरावर्ती" के रूप में वर्णित किया गया है। प्रभावी गणना की एक और परिभाषा चर्च द्वारा दी गई है. जो इसे λ-परिभाषा के साथ पहचानता है। लेखक ने हाल ही में सहज ज्ञान युक्त विचार के अधिक निकटता से संबंधित एक परिभाषा का सुझाव दिया है (ट्यूरिंग [1], पोस्ट का [1] भी देखें)। यह ऊपर कहा गया था कि "एक फलन प्रभावी रूप से गणना योग्य है यदि इसके मान किसी विशुद्ध रूप से यांत्रिक प्रक्रिया द्वारा पाए जा सकते हैं।" हम इस कथन को शाब्दिक रूप से एक विशुद्ध रूप से यांत्रिक प्रक्रिया द्वारा समझ सकते हैं जिसे एक मशीन द्वारा किया जा सकता है। इन मशीनों की संरचनाओं का एक निश्चित सामान्य रूप में गणितीय विवरण देना संभव है। इन विचारों के विकास से लेखक की एक संगणनीय कार्य की परिभाषा और प्रभावी गणना के साथ संगणनीयता की पहचान होती है। यह साबित करना मुश्किल नहीं है, हालांकि कुछ श्रमसाध्य है कि ये तीन परिभाषाएँ समान हैं। हम "कम्प्यूटेबल फ़ंक्शन" अभिव्यक्ति का उपयोग एक मशीन द्वारा गणना योग्य फ़ंक्शन का अर्थ करने के लिए करेंगे, और हम "प्रभावी रूप से गणना योग्य" को इन परिभाषाओं में से किसी एक के साथ विशेष पहचान के बिना सहज ज्ञान युक्त विचार को संदर्भित करने देते हैं। हम एक संगणकीय फलन द्वारा लिए गए मूल्यों को प्राकृतिक संख्या के रूप में प्रतिबंधित नहीं करते हैं; उदाहरण के लिए हमारे पास संगणनीय प्रस्तावात्मक फलन हो सकते हैं। यह एक शक्तिशाली अभिव्यक्ति है। क्योंकि "समानता" वास्तव में आवश्यक और पर्याप्त स्थितियों का एक स्पष्ट कथन है, दूसरे शब्दों में पहचान के लिए कोई अन्य आकस्मिकताएं नहीं हैं "सिवाय इसके कि" फ़ंक्शन "," मशीन "," कम्प्यूटेबल "और" प्रभावी रूप से गणना योग्य "शब्दों की क्या व्याख्या की गई हैः सभी कार्यों के लिएः यदि" यह फ़ंक्शन मशीन द्वारा गणना योग्य है "तो" यह फ़ंक्शन प्रभावी रूप से गणना योग्य है "और यदि" यह फ़ंक्शन प्रभावी रूप से गणना योग्य है "तो" यह फ़ंक्शन एक मशीन द्वारा गणना योग्य है। रॉसरः रिकर्शन, λ-कैलकुलस, और ट्यूरिंग-मशीन कम्प्यूटेशन आइडेंटिटी जे। बी. रॉसर के पेपर एन इनफॉर्मल एक्सपोजिशन ऑफ प्रूफ्स ऑफ गोडेल के प्रमेय और चर्च के प्रमेय में निम्नलिखित कहा गया हैः 'प्रभावी विधि' का उपयोग यहां एक विधि के विशेष अर्थ में किया जाता है जिसका प्रत्येक चरण सटीक रूप से पूर्व निर्धारित होता है और जो निश्चित रूप से उत्तर को सीमित संख्या में चरणों में उत्पन्न करता है। इस विशेष अर्थ के साथ, तिथि 5 को तीन अलग-अलग सटीक परिभाषाएँ दी गई हैं। इनमें से सबसे सरल कथन (पोस्ट और ट्यूरिंग के कारण) अनिवार्य रूप से कहता है कि समस्याओं के एक निश्चित समूह को हल करने का एक प्रभावी तरीका मौजूद है यदि कोई एक ऐसी मशीन का निर्माण कर सकता है जो प्रश्न डालने और (बाद में) उत्तर पढ़ने के अलावा किसी भी मानवीय हस्तक्षेप के बिना सेट की किसी भी समस्या को हल कर सकती है। तीनों परिभाषाएँ समान हैं, इसलिए इससे कोई फर्क नहीं पड़ता कि किसका उपयोग किया जाता है। इसके अलावा, यह तथ्य कि तीनों समान हैं, किसी भी एक की शुद्धता के लिए एक बहुत मजबूत तर्क है। 5 चर्च द्वारा I में एक परिभाषा दी गई है। चर्च 1936 प्राथमिक संख्या सिद्धांत की एक अनसुलझी समस्या]। एक अन्य परिभाषा जैक्स हरब्रांड और कर्ट गोडेल के कारण है। यह I, फुटनोट 3, पृष्ठ 346 में बताया गया है। तीसरी परिभाषा ई. एल. पोस्ट और ए. एम. ट्यूरिंग द्वारा स्वतंत्र रूप से दो अलग-अलग रूपों में दी गई थी। पहली दो परिभाषाएँ I में समतुल्य साबित हुई हैं। तीसरा ए. एम. ट्यूरिंग, कम्प्यूटेबिलिटी एंड λ-डेफिनेबिलिटी [जर्नल ऑफ सिम्बोलिक लॉजिक, वॉल्यूम। 2 (1937), पृ. 153-163] "। क्लेन और थीसिस I क्लेन ने अपने पेपर रिकर्सिव प्रेडिकेट्स एंड क्वांटिफायर्स में "सामान्य पुनरावर्ती" कार्यों और "आंशिक पुनरावर्ती कार्यों" को परिभाषित किया है। प्रतिनिधित्व कार्य, म्यू-ऑपरेटर, आदि अपनी उपस्थिति बनाते हैं। वह अपने प्रसिद्ध थीसिस I को बताने के लिए §12 एल्गोरिदम सिद्धांतों में आगे बढ़ते हैं, जिसे वे 1952 में चर्च के थीसिस कहने के लिए आते हैंः "इस शोध तथ्य के साथ-साथ प्रतीकात्मक एल्गोरिदमिक प्रक्रियाओं की प्रकृति पर कुछ प्रतिबिंबों ने चर्च को निम्नलिखित थीसिस 22 बताने के लिए प्रेरित किया। यही थीसिस ट्यूरिंग के कंप्यूटिंग मशीनों के विवरण में निहित है। "थीसिस I. प्रत्येक प्रभावी रूप से गणना योग्य कार्य (प्रभावी रूप से निर्णायक विधेय) सामान्य पुनरावर्ती होता है। "चूंकि प्रभावी रूप से गणना योग्य (प्रभावी रूप से निर्णायक) शब्द की एक सटीक गणितीय परिभाषा की आवश्यकता है, इसलिए हम इस शोध प्रबंध को, पहले से ही स्वीकार किए गए उस सिद्धांत के साथ, जो इसके विपरीत है, एक परिभाषा के रूप में ले सकते हैं। शोध प्रबंध में एक परिकल्पना का चरित्र है-एक बिंदु जिस पर पोस्ट और चर्च 24 द्वारा जोर दिया गया है। 22 चर्च [1] [प्राथमिक संख्या सिद्धांत की एक अनसुलझी समस्या] 23 ट्यूरिंग [1] [कम्प्यूटेबल संख्याओं पर, एंटशेइडंग समस्या (1936) के लिए एक आवेदन के साथ] 24 पोस्ट [1, पृष्ठ 105], और चर्च [2] क्लेन का चर्च, ट्यूरिंग और चर्च-ट्यूरिंग थीसिस अपने अध्याय § 60 में, क्लेन ने "चर्च की थीसिस" को निम्नानुसार परिभाषित कियाः ". शोधात्मक साक्ष्य और अन्य विचारों ने चर्च 1936 को निम्नलिखित थीसिस का प्रस्ताव करने के लिए प्रेरित किया। "थीसिस I. प्रत्येक प्रभावी रूप से गणना योग्य कार्य (प्रभावी रूप से निर्णायक विधेय) सामान्य पुनरावर्ती होता है। "यह थीसिस ट्यूरिंग 1936-7 और 1936 के बाद द्वारा तैयार की गई एक कंप्यूटिंग मशीन की अवधारणा में भी निहित है।" पृष्ठ 317 पर वह स्पष्ट रूप से उपरोक्त थीसिस को "चर्च की थीसिस" कहते हैंः "§62। चर्च की थीसिस। इसके और अगले अध्याय के मुख्य उद्देश्यों में से एक चर्च के शोध प्रबंध (थीसिस I § 60) के लिए साक्ष्य प्रस्तुत करना है। ट्यूरिंग के "सूत्रीकरण" के बारे में, क्लेन कहते हैंः "ट्यूरिंग का सूत्रीकरण इसलिए चर्च के शोध प्रबंध (समकक्ष शब्दों में) का एक स्वतंत्र बयान है। 1936 के बाद एक समान सूत्रीकरण दिया गया। क्लेन ने प्रस्ताव दिया कि ट्यूरिंग ने जो दिखायाः "ट्यूरिंग के संगणनीय कार्य (1936-1937) वे हैं जिनकी गणना एक प्रकार की मशीन द्वारा की जा सकती है, जिसे उनके विश्लेषण के अनुसार, उन सभी प्रकार के कार्यों को पुनः पेश करने के लिए डिज़ाइन किया गया है जो एक मानव कंप्यूटर पूर्व निर्धारित निर्देशों के अनुसार काम कर सकता है।" क्लेन ट्यूरिंग के थीसिस को इस प्रकार परिभाषित करते हैंः "§70। ट्यूरिंग की थीसिस। ट्यूरिंग की थीसिस है कि प्रत्येक कार्य जिसे स्वाभाविक रूप से उनकी परिभाषा के तहत संगणनीय माना जाएगा, अर्थात। उनकी एक मशीन द्वारा, प्रमेय XXX द्वारा चर्च की थीसिस के बराबर है। वास्तव में इस कथन से तुरंत पहले, क्लेन प्रमेय XXX को बताता हैः "प्रमेय XXX (= प्रमेय XXVIII + XXIX)। आंशिक कार्यों के निम्नलिखित वर्ग सह-विस्तारित हैं, अर्थात। समान सदस्य होते हैंः (ए) आंशिक पुनरावर्ती कार्य, (बी) संगणनीय कार्य, (सी) 1/1 संगणनीय कार्य। इसी तरह l [लोअर-केस L] के साथ पूरी तरह से परिभाषित मानित कार्य म्बा "। गोडेल, ट्यूरिंग मशीन, और प्रभावी रूप से गणना 1931 के अपने पेपर ऑन फॉर्मली अनडिसाइडेबल प्रपोसिशंस में, गोडेल ने 28 अगस्त 1963 को एक नोट जोड़ा जो "एक औपचारिक प्रणाली" के वैकल्पिक रूपों/अभिव्यक्ति के बारे में उनकी राय को स्पष्ट करता है। उन्होंने 1964 में अपनी राय को और भी स्पष्ट रूप से दोहराया (नीचे देखें): "नोट 28 अगस्त 1963 को जोड़ा गया। बाद की प्रगति के परिणामस्वरूप, विशेष रूप से इस तथ्य के कारण कि ए. एम. ट्यूरिंग के कार्य 69 के कारण औपचारिक प्रणाली 70 की सामान्य धारणा की एक सटीक और निर्विवाद रूप से पर्याप्त परिभाषा दी जा सकती है, प्रमेय VI और XI का एक पूरी तरह से सामान्य संस्करण अब संभव है। अर्थात्, यह कड़ाई से साबित किया जा सकता है कि प्रत्येक सुसंगत औपचारिक प्रणाली में जिसमें एक निश्चित मात्रा में परिमित संख्या सिद्धांत होता है, अनिश्चित अंकगणितीय प्रस्ताव मौजूद होते हैं और इसके अलावा, ऐसी किसी भी प्रणाली की स्थिरता को प्रणाली में साबित नहीं किया जा सकता है। "69 देखिए, पृ. 249। "70 मेरी राय में" औपचारिक प्रणाली "या" औपचारिकता "शब्द का उपयोग कभी भी इस धारणा के अलावा किसी और चीज के लिए नहीं किया जाना चाहिए। प्रिंसटन में एक व्याख्यान में (प्रिंसटन विश्वविद्यालय 1946 में उल्लिखित, पृष्ठ 11 [डेविस 1965, पृष्ठ देखें। 84-88 [अर्थात। डेविस पी. 84-88]), मैंने औपचारिकताओं के कुछ अनंत सामान्यीकरणों का सुझाव दिया, लेकिन ये शब्द के उचित अर्थ में औपचारिक प्रणालियों से मौलिक रूप से कुछ अलग हैं, जिनकी विशेषता यह है कि उनमें तर्क, सिद्धांत रूप में, पूरी तरह से यांत्रिक उपकरणों द्वारा प्रतिस्थापित किया जा सकता है। गोडेल 1964-गोडेल के पोस्टस्क्रिप्टम में प्रिंसटन में आई. ए. एस. में 1934 के अपने व्याख्यान के नोट्स में, वह दोहराते हैं, लेकिन और भी अधिक साहसिक शब्दों में दोहराते हैं, चर्च की λ-परिभाषा और पुनरावृत्ति द्वारा परिभाषित संगणनीयता की प्रभावकारिता के बारे में उनकी कम चमकती राय (हमें यह अनुमान लगाना होगा कि निम्नलिखित में बहुवचन "परिभाषाओं" के उपयोग के कारण दोनों को बदनाम किया गया है)। यह मार्टिन डेविस को लिखे एक पत्र में था (संभवतः जब वह द अनडिसिबल को इकट्ठा कर रहे थे)। कुछ वाक्यांशों की पुनरावृत्ति आश्चर्यजनक हैः "बाद की प्रगति के परिणामस्वरूप, विशेष रूप से इस तथ्य के कारण कि, ए. एम. ट्यूरिंग के काम के कारण, औपचारिक प्रणाली की सामान्य अवधारणा की एक सटीक और निर्विवाद रूप से पर्याप्त परिभाषा दी जा सकती है, अनिश्चित अंकगणितीय प्रस्तावों का अस्तित्व और एक ही प्रणाली में एक प्रणाली की स्थिरता की गैर-प्रदर्शनशीलता को अब प्रत्येक सुसंगत औपचारिक प्रणाली के लिए सख्ती से साबित किया जा सकता है जिसमें एक निश्चित मात्रा में परिमित संख्या सिद्धांत होता है। "ट्यूरिंग का काम" यांत्रिक प्रक्रिया "(उर्फ" एल्गोरिथ्म "या" गणना प्रक्रिया "या" परिमित संयोजन प्रक्रिया ") की अवधारणा का विश्लेषण देता है। इस अवधारणा को "ट्यूरिंग मशीन" के बराबर दिखाया गया है। एक औपचारिक प्रणाली को केवल सूत्रों के उत्पादन के लिए किसी भी यांत्रिक प्रक्रिया के रूप में परिभाषित किया जा सकता है, जिसे सिद्ध करने योग्य सूत्र कहा जाता है. औपचारिक प्रणाली की अवधारणा, जिसका सार यह है कि तर्क को पूरी तरह से सूत्रों पर यांत्रिक संचालन द्वारा प्रतिस्थापित किया जाता है। (ध्यान दें कि क्या कोई सीमित गैर-यांत्रिक प्रक्रियाएं मौजूद हैं. जो किसी भी एल्गोरिथ्म के बराबर नहीं हैं, इसका "औपचारिक प्रणाली" और "यांत्रिक प्रक्रिया" की परिभाषा की पर्याप्तता से कोई लेना-देना नहीं है। ". यदि" "परिमित प्रक्रिया" "का अर्थ" "यांत्रिक प्रक्रिया" "समझा जाता है, तो फुटनोट 3 में उठाए गए प्रश्न का उत्तर §9 में परिभाषित पुनरावृत्ति के लिए सकारात्मक रूप से दिया जा सकता है, जो आज परिभाषित सामान्य पुनरावृत्ति के बराबर है (देखें एस. सी. क्लेन (1936).)" "* देखें. और ई. एल. पोस्ट (1936) द्वारा लगभग एक साथ पेपर।" कम्प्यूटेबिलिटी की पिछली समतुल्य परिभाषाओं के लिए, जो हालांकि, हमारे उद्देश्य के लिए बहुत कम उपयुक्त हैं, ए देखें। चर्च 1936. फुटनोट 3 1934 के व्याख्यान के मुख्य भाग में लिखा हैः "3 विपरीत सच प्रतीत होता है, यदि योजना के अनुसार पुनरावृत्तियों के अलावा (2) अन्य रूपों की पुनरावृत्तियों (जैसे, एक साथ दो चर के संबंध में) को स्वीकार किया जाता है। यह साबित नहीं किया जा सकता है, क्योंकि परिमित गणना की धारणा को परिभाषित नहीं किया गया है, लेकिन यह एक शोध सिद्धांत के रूप में कार्य करता है। डेविस का मानना है कि "वास्तव में उनकी [गोडेल की] परिभाषा [पुनरावृत्ति की] और क्लेन की [1936] के बीच समानता बहुत मामूली नहीं है। इसलिए, इसके विपरीत दिखने के बावजूद, इन व्याख्यानों में से फुटनोट 3 चर्च की थीसिस का बयान नहीं है। गैंडीः "मशीन गणना", असतत, नियतात्मक, और प्रकाश गति द्वारा "स्थानीय कारण" तक सीमित रॉबिन गैंडी का प्रभावशाली पेपर चर्च के थीसिस और तंत्र के सिद्धांत बारवाइज एट अल में दिखाई देता है। गैंडी चर्च के थीसिस की एक अप्रत्याशित अभिव्यक्ति के साथ शुरू होता है, जिसे इस प्रकार बनाया गया हैः "1. परिचय "इस पूरे पेपर में हम कुछ सहज रूप से दी गई धारणा को संदर्भित करने के लिए" गणना योग्य "का उपयोग करेंगे और" कम्प्यूटेबल "का अर्थ है" ट्यूरिंग मशीन द्वारा गणना योग्य "; निश्चित रूप से" कम्प्यूटेबल "की कई समकक्ष परिभाषाएँ अब उपलब्ध हैं। "चर्च की थीसिस। जो प्रभावी रूप से गणना योग्य है वह गणना योग्य है। .. चर्च और ट्यूरिंग दोनों के दिमाग में कुछ यांत्रिक उपकरणों (जैसे कागज और पेंसिल) का उपयोग करके एक अमूर्त मानव द्वारा गणना की गई थी "रॉबर्ट सोरे (1995, नीचे देखें) को ट्यूरिंग के" परिशिष्ट प्रमाण "(1937) से पहले प्रकाशित चर्च के पेपर (1936) पर विचार करते हुए इस फ्रेमिंग के साथ समस्याएं थीं। गैंडी "यांत्रिक प्रक्रियाओं का विश्लेषण करने और इसलिए निम्नलिखित के लिए तर्क प्रदान करने का प्रयास करता हैः" थीसिस एम. एक मशीन द्वारा जो गणना की जा सकती है वह गणना योग्य है। " गैंडी "विचार करने वाले उपकरणों से बाहर हैं जो अनिवार्य रूप से एनालॉग मशीनें हैं। यांत्रिक उपकरणों के बारे में केवल भौतिक पूर्वधारणाएं (नीचे सी. एफ सिद्धांत IV) यह हैं कि उपकरण के प्रत्येक परमाणु भाग के रैखिक आयामों पर एक निचली सीमा होती है और परिवर्तन के प्रसार की गति पर एक ऊपरी सीमा (प्रकाश का वेग) होती है।" लेकिन फिर वह अपनी मशीनों को और भी सीमित करता हैः "(2) दूसरा, हम मानते हैं कि एक यांत्रिक उपकरण द्वारा गणना की प्रगति को अलग-अलग शब्दों में वर्णित किया जा सकता है, ताकि जिन उपकरणों पर विचार किया जाए, वे ढीले अर्थों में, डिजिटल कंप्यूटर हों। (3) अंत में हम मानते हैं कि उपकरण नियतात्मक हैः अर्थात, उपकरण का बाद का व्यवहार विशिष्ट रूप से निर्धारित किया जाता है जब इसकी प्रारंभिक स्थिति का पूरा विवरण दिया जाता है। वास्तव में वे इस "थीसिस एम" के लिए एक तर्क देते हैं कि वे अपना "प्रमेय" कहते हैं, जिसका सबसे महत्वपूर्ण "सिद्धांत" "सिद्धांत IV: स्थानीय कारण का सिद्धांत" हैः "अब हम अपने सबसे महत्वपूर्ण सिद्धांतों पर आते हैं। ट्यूरिंग के विश्लेषण में यह आवश्यकता कि कार्रवाई केवल रिकॉर्ड के एक सीमित हिस्से पर निर्भर थी, एक मानवीय सीमा पर आधारित थी। हम इसे एक भौतिक सीमा द्वारा प्रतिस्थापित करते हैं जिसे हम स्थानीय कार्यकारण का सिद्धांत कहते हैं। इसका औचित्य प्रभावों और संकेतों के प्रसार के सीमित वेग में निहित हैः समकालीन भौतिकी दूरी पर तात्कालिक कार्रवाई की संभावना को अस्वीकार करती है। 1985 में "थीसिस एम" को क्वांटम ट्यूरिंग मशीन के लिए अनुकूलित किया गया था, जिसके परिणामस्वरूप चर्च-ट्यूरिंग-डॉयच सिद्धांत बना। सोरे सोरे की कम्प्यूटेबिलिटी और रिकर्शन की गहन परीक्षा दिखाई देती है। उन्होंने कम्प्यूटेबिलिटी की "बहुत कम उपयुक्त" परिभाषा के संबंध में गोडेल की 1964 की राय (ऊपर) को उद्धृत किया, और आगे कहाः "क्लेन ने लिखा [1981बी, पी. 49]", ट्यूरिंग की कम्प्यूटेबिलिटी आंतरिक रूप से प्रेरक है "लेकिन" λ-परिभाषा आंतरिक रूप से प्रेरक नहीं है "और" सामान्य पुनरावृत्ति शायद ही ऐसा है (इसके लेखक गोडेल उस समय बिल्कुल भी आश्वस्त नहीं थे)। आज अधिकांश लोग ट्यूरिंग के थीसिस को स्वीकार करते हैं "सोरे का फुटनोट 7 (1995) भी गैंडी के" भ्रम "को पकड़ता है, लेकिन जाहिर है कि यह गैंडी (1988) में जारी है। यह भ्रम अनुसंधान और/या विचार की एक गंभीर त्रुटि का प्रतिनिधित्व करता है और उनके पूरे कार्यक्रम पर एक बादल मंडराता रहता हैः "7गैंडी ने वास्तव में" चर्च की थीसिस "लिखी थी न कि" ट्यूरिंग की थीसिस "जैसा कि यहां लिखा गया है, लेकिन निश्चित रूप से गैंडी का मतलब बाद वाला था, कम से कम इरादे से, क्योंकि ट्यूरिंग ने 1936 में या कहीं और सामान्य पुनरावर्ती कार्यों के बारे में कुछ भी साबित नहीं किया था।" ब्रेगर और टैसिट स्वयंसिद्धियों की समस्या एक समस्या की ओर इशारा करती है जब कोई "स्वयंसिद्ध रूप से" एक धारणा तक पहुंच रहा होता है, अर्थात, एक "स्वयंसिद्ध प्रणाली" में एक या अधिक टैसिट स्वयंसिद्ध हो सकते हैं जो स्वयंसिद्ध-सेट प्रस्तुत किए जाने पर अनकहे होते हैं। उदाहरण के लिए, ज्ञान (और क्षमता) के साथ एक सक्रिय प्रतिनिधि किसी भी स्वयंसिद्ध प्रणाली में एक (संभावित) मौलिक स्वयंसिद्ध हो सकता हैः "मनुष्य का ज्ञान आवश्यक है-एक ऐसा ज्ञान जो स्वयंसिद्धियों में औपचारिक नहीं है। Â. प्रतीकों की विशुद्ध रूप से औपचारिक प्रणाली के रूप में गणित बिना किसी मनुष्य के प्रतीकों के साथ ज्ञान के बिना असंभव है। "उन्होंने हिल्बर्ट को उद्धृत कियाः" 1905 में दिए गए एक विश्वविद्यालय व्याख्यान में, हिल्बर्ट ने तर्क में स्वयंसिद्धों को बताने से पहले "विचार का स्वयंसिद्ध" या "एक बुद्धि के अस्तित्व का स्वयंसिद्ध" होना "बिल्कुल आवश्यक" माना। पटकथा के बीच में, हिल्बर्ट ने बाद में कहाः "दार्शनिकों की प्राथमिकता"। उन्होंने इस स्वयंसिद्ध को इस प्रकार तैयार कियाः "मेरे पास वस्तुओं के बारे में सोचने और उन्हें a, b,., x, y जैसे सरल प्रतीकों के माध्यम से निरूपित करने की क्षमता है, ताकि उन्हें स्पष्ट रूप से पहचाना जा सके। मेरा विचार इन वस्तुओं के साथ कुछ नियमों के अनुसार एक निश्चित तरीके से काम करता है, और मेरी सोच खुद के अवलोकन से इन नियमों का पता लगाने में सक्षम है, और इन नियमों का पूरी तरह से वर्णन करने में सक्षम है "[(हिल्बर्ट 1905,219); यह भी देखें (पेखॉस 1990,62एफ और 227)]। ब्रेगर आगे ग्यूसेप वेरोनीज़ (1891) और हर्मन वेल (1930-1) के उदाहरणों के साथ अपने तर्क का समर्थन करते हैं। वह एक विशेष भाषा में एक स्वयंसिद्ध-समूह की अभिव्यक्ति की समस्या पर चर्चा करते हैंः अर्थात। अभिकर्ता द्वारा जानी जाने वाली भाषा, जैसे। जर्मन। एल्गोरिदम लक्षण वर्णन में इसके बारे में अधिक देखें, विशेष रूप से सियरले की राय है कि किसी भी गणना के बाहर एक पर्यवेक्षक होना चाहिए जो उपयोग किए गए प्रतीकों को अर्थ देता है। सीग और स्वयंसिद्ध परिभाषाएँ "फेफरफेस्ट" में-सोलोमन फेफरमैन के 70वें जन्मदिन पर-विल्फ्रेड सीग ने पहली बार दो साल पहले लिखा गया एक पेपर प्रस्तुत किया जिसका शीर्षक था "मैन एंड मशीन द्वारा गणनाः अवधारणात्मक विश्लेषण", जो (सीग एट अल) में पुनर्मुद्रित किया गया था। 2002:390-409)। इससे पहले सीग ने "मैकेनिकल प्रोसीजर्स एंड मैथमेटिकल एक्सपीरियंस" (जॉर्ज 1994 में, पृष्ठ 71एफएफ) प्रकाशित किया था, जिसमें "गणनाशीलता" का इतिहास प्रस्तुत किया गया था, जो रिचर्ड डेडेकिंड से शुरू हुआ और 1950 के दशक में एलन ट्यूरिंग और स्टीफन कोल क्लेन के बाद के शोध पत्रों के साथ समाप्त हुआ। फेफरफेस्ट पेपर अपने प्रमुख बिंदुओं के लिए पूर्व पेपर को अलग करता है और मुख्य रूप से 1980 के रॉबिन गैंडी के पेपर पर रहता है। सीग ट्यूरिंग की "स्ट्रिंग मशीन द्वारा कम्प्यूटेबिलिटी" (मानव "कम्प्यूटर") को गैंडी की समानांतर मशीनों के लिए तंत्र "लेटर मशीन द्वारा कम्प्यूटेबिलिटी" तक कम कर देता है। सीग ने "एल्गोरिदम पर कोल्मोगोरोव और उस्पेन्स्की के काम" और (डी पिसापिया 2000), विशेष रूप से, केयू-पॉइंटर मशीन-मॉडल और कृत्रिम तंत्रिका नेटवर्क सहित हाल के काम का हवाला दिया और दावा कियाः "अनौपचारिक वैचारिक विश्लेषण और गणितीय समानता प्रमाण का पृथक्करण यह पहचानने के लिए आवश्यक है कि ट्यूरिंग के थीसिस (सामान्य रूप से लिया गया) की शुद्धता दो स्तंभों पर निर्भर करती है; अर्थात् संगणकों के लिए सीमा और स्थानीय स्थितियों की शुद्धता और प्रासंगिक केंद्रीय थीसिस की शुद्धता पर। उत्तरार्द्ध स्पष्ट रूप से दावा करता है कि एक कम्प्यूटर की गणनाओं को सीधे एक विशेष प्रकार की मशीन द्वारा नकल किया जा सकता है। यद्यपि किसी को विश्लेषणात्मक तर्क की यह रेखा संतोषजनक लग सकती है, लेकिन दो कमजोर धब्बे हैंः प्रतिबंधात्मक स्थितियों की शिथिलता (प्रतीकात्मक विन्यास क्या हैं? यांत्रिक संचालन किन परिवर्तनों को प्रभावित कर सकते हैं?) और केंद्रीय शोध प्रबंध की संबंधित अस्पष्टता। हम, चाहे हम खुद को कैसे भी मोड़ लें, एक ऐसी स्थिति में हैं जो पद्धतिगत रूप से अभी भी असंतोषजनक है। "। वह "एक अधिक संतोषजनक रुख की ओर कदम बढ़ाने का दावा करता है. विशेष प्रकार के विन्यास और संचालन से और दूर सार निकालकर।" "यह अक्सर दावा किया गया है कि ट्यूरिंग ने मशीनों की गणनाओं का विश्लेषण किया। यह ऐतिहासिक और व्यवस्थित रूप से गलत है, क्योंकि मेरी व्याख्या से काफी स्पष्ट हो जाना चाहिए था। केवल 1980 में ट्यूरिंग के छात्र रॉबिन गैंडी ने मशीन गणनाओं की विशेषता बताई। उपरोक्त कथन सत्य है या नहीं, यह विचार करने के लिए पाठक पर छोड़ दिया गया है। सीग गैंडी के विश्लेषण का वर्णन करते हैं (ऊपर 1980 देखें)। ऐसा करते हुए वह औपचारिक रूप देने का प्रयास करता है जिसे वह "गैंडी मशीन" कहता है (एक परिशिष्ट में विस्तृत विश्लेषण के साथ)। गैंडी मशीनों के बारे मेंः गैंडी मशीन की परिभाषा एक अमूर्त गणितीय परिभाषा है जो समानांतर गणनाओं के गुणों को मूर्त रूप देती है। दूसरा, गैंडी मशीनें अमूर्त स्वयंसिद्ध परिभाषाओं की सामान्य विशेषता को समूहों और स्थलवैज्ञानिक रिक्त स्थान के साथ साझा करती हैं, अर्थात्, वे विभिन्न व्याख्याओं की एक विस्तृत विविधता को स्वीकार करती हैं। तीसरा, किसी भी गैंडी मशीन की गणना को एक अक्षर मशीन द्वारा अनुकरण किया जा सकता है, [और] स्वयंसिद्ध धारणा के लिए एक प्रतिनिधित्व प्रमेय के रूप में सबसे अच्छी तरह से समझा जाता है। [बोल्डफेस जोड़ा गया] "स्वयंसिद्ध दृष्टिकोण एक अमूर्त तरीके से गणना प्रक्रियाओं की आवश्यक प्रकृति को पकड़ता है। जिन दो प्रकार के कैलकुलेटरों का मैं वर्णन कर रहा हूं, उनके बीच का अंतर इस तथ्य तक कम हो गया है कि ट्यूरिंग कंप्यूटर एक अवस्था के एक बंधे हुए हिस्से को संशोधित करते हैं, जबकि गैंडी मशीनें मनमाने ढंग से कई बंधे हुए हिस्सों पर समानांतर रूप से काम करती हैं। प्रतिनिधित्व प्रमेय इस बात की गारंटी देते हैं कि स्वयंसिद्धियों के मॉडल अपनी अक्षर विविधता में कम्प्यूटेशनल रूप से ट्यूरिंग मशीनों के बराबर हैं। नोट्स संदर्भ बारवाइज, जॉन, एच. जे. कीस्लर, और के. कुनेन, संपादक, 1980, द क्लेन सिम्पोजियम, 426 पृष्ठ, नॉर्थ-हॉलैंड पब्लिशिंग कंपनी, एम्स्टर्डम, चर्च, ए., 1936ए, इन (डेविस 1965:88 एफएफ), "एन अनसोल्वेबल प्रॉब्लम ऑफ एलीमेंट्री नंबर थ्योरी" चर्च, ए., 1936बी, इन (डेविस 1965:108 एफएफ), "ए नोट ऑन द एंटशेइडंग्सप्रॉब्लम" चर्च, ए., 1938, द कंस्ट्रक्टिव सेकंड नंबर क्लास, बुल। आमेर। गणित। एस. सी. वॉल्यूम। 44, संख्या 4,1938, पृ. डेविस, मार्टिन संपादक, 1965, द अनडिडिबल, बेसिक पेपर्स ऑन अनडिडिबल प्रपोजिशन्स, अनसोल्वेबल प्रॉब्लेम्स एंड कम्प्यूटेबल फंक्शंस, रेवेन प्रेस, न्यूयॉर्क। इस लेख में उल्लिखित गोडेल, चर्च, ट्यूरिंग, रॉसर, क्लेन और पोस्ट सहित सभी मूल पत्र यहाँ हैं। डेविस की मूल्यवान टिप्पणी अधिकांश पत्रों से पहले आती है। डेविस, मार्टिन, 2001, इंजिन्स ऑफ लॉजिकः मैथमैटिशंस एंड द ओरिजिन ऑफ द कंप्यूटर, डब्ल्यू. डब्ल्यू. नॉर्टन एंड कंपनी, न्यूयॉर्क, पी. बी. के. डॉसन, जॉन विलियम, जूनियर, 1997, लॉजिकल डिलेमासः द लाइफ एंड वर्क ऑफ कर्ट गोडेल, 361 पृष्ठ, ए. के. पीटर्स, वेलेस्ली, एम. ए., QA29.058D39। डॉसन, जॉन विलियम और जॉन विलियम डॉसन, जूनियर, 2005, लॉजिकल डिलेमासः द लाइफ एंड वर्क ऑफ कर्ट गोडेल, 362 पृष्ठ, ए. के. पीटर्स, वेलेस्ली, एम. ए., डी पिसापिया, एन., 2000, गैंडी मशीन्सः ए अब्स्ट्रैक्ट मॉडल ऑफ पैरेलल कम्प्यूटेशन फॉर ट्यूरिंग मशीन्स, द गेम ऑफ लाइफ, एंड आर्टिफिशियल न्यूरल नेटवर्क्स, एम. एस. थीसिस, कार्नेगी मेलन विश्वविद्यालय, पिट्सबर्ग। डर्शोविट्ज़, नाचुम और गुरेविच, यूरी, 2007, चर्च के थीसिस का एक प्राकृतिक स्वयंसिद्धीकरण, http://research.microsoft.com ~ गुरेविच/ओपेरा/188. पी. डी. एफ. गैंडी, रॉबिन, 1978, चर्च के थीसिस और तंत्र के सिद्धांत, (बारवाइस एट अल। 1980:123-148) जॉर्ज, अलेक्जेंडर (+ संस्करण। ), 1994, गणित और मन, 216 पृष्ठ, न्यूयॉर्क, ऑक्सफोर्ड यूनिवर्सिटी प्रेस, गोडेल, के., 1930, में (वैन हेजेनोर्ट 1967:592 एफएफ), पूर्णता और स्थिरता पर कुछ मेटामेथेमैटिकल परिणाम गोडेल, के., 1931ए, में (डेविस 1965:4-38), प्रिंसिपिया मैथेमेटिका और संबंधित प्रणालियों के औपचारिक रूप से अनिर्णायक प्रस्तावों पर। I. Gödel, K., 1931b, in (van Heijenoort 1976:616 ff) पूर्णता और निरंतरता पर Gödel, K., 1934, में (डेविस 1965:39-74), औपचारिक गणितीय प्रणालियों के अनिर्णायक प्रस्तावों पर Gödel, K., 1936, में (डेविस 1965:82 ff), सबूतों की लंबाई पर, "संपादक द्वारा अनुवादित मूल लेख से Ergenbnisse eines Mathematishen Kolloquiums, Heft 7 (1936) pp। 23-24 "। क्लेन (1952) द्वारा एर्गेबनिसे आइन्स गणित में "über die Lāange von Beweisen" के रूप में उद्धृत किया गया है। कोल, आदि। गोडेल, के., 1964, (डेविस 1965:71 एफएफ), पोस्टस्क्रिप्टम ग्रोशोज़, एमिली और ब्रेगर, हर्बर्ट, 2000, द ग्रोथ ऑफ़ मैथमेटिकल नॉलेज, 416 पृष्ठ, क्लूवर एकेडेमिक पब्लिशर्स, डॉर्ड्रेक्ट, द नीदरलैंड,। हॉकिंग, स्टीफन, 2005, गॉड क्रिएटेड द इंटीजर्सः द मैथमेटिकल ब्रेकथ्रूज़ दैट चेंज्ड हिस्ट्री, एडिटेड, स्टीफन हॉकिंग द्वारा कमेंटरी के साथ, रनिंग प्रेस, फिलाडेल्फिया, हॉजेस, एंड्रयू, 1983, एलन ट्यूरिंगः द एनिग्मा, पहला संस्करण, साइमन एंड शूस्टर, न्यूयॉर्क, क्लेन, एस. सी., 1935, इन (डेविस 1965:236 एफ. एफ.) जनरल रिकर्सिव फ़ंक्शंस ऑफ़ नेचुरल नंबर्स क्लेन, एस. सी., 1971,1952 (10वीं छाप 1991) इंट्रोडक्शन टू मेटामेथेमैटिक्स, 550 पेज, नॉर्थ-हॉलैंड पब्लिशिंग कंपनी (वोल्टर्स-नॉर्डहॉफ़ पब्लिशिंग) मरियम-वेबस्टर इंक., 1983 1, नहीं। 3 (सितंबर, 1936), पृ. 103-105। रोसर। जे. बी., 1939, गोडेल के प्रमेय और चर्च के प्रमेय के प्रमाणों की एक अनौपचारिक व्याख्या, द जर्नल ऑफ सिम्बोलिक लॉजिक। खण्ड. 4. (1939), पृ. 53-60 और (डेविस 1967:223-230) में पुनर्मुद्रित। सीग, विल्फ्रेड, रिचर्ड सॉमर और कैरोलिन टैल्कॉट (संस्करण। ), 2002, गणित की नींव पर प्रतिबिंबः सोलोमन फेफरमैन के सम्मान में निबंध, तर्क में व्याख्यान टिप्पणियाँ 15,444 पृष्ठ, ए के पीटर्स, लिमिटेड, सोरे, रॉबर्ट, 1996, कम्प्यूटेबिलिटी एंड रिकर्शन, "बुलेटिन ऑफ सिम्बोलिक लॉजिक 2", खंड 2, संख्या 3, सितंबर 1996, पृष्ठ। और (यह भी देखिएः डेविस 1965:115 ff) ट्यूरिंग, ए., 1939, इन (डेविस 1965:154 ff), सिस्टम्स ऑफ लॉजिक बेस्ड ऑन ऑर्डिनल्स वैन हेजेनोर्ट, जीन, 1976, फ्रॉम फ्रेज टू गोडेलः ए सोर्स बुक इन मैथमेटिकल लॉजिक, 116 पेज, 1879-1931, थर्ड प्रिंटिंग, ओरिजिनल प्रिंटिंग 1967, हार्वर्ड यूनिवर्सिटी प्रेस, कैम्ब्रिज मैसाचुसेट्स, (pbk.)। बाहरी लिंक प्रतीकात्मक तर्क के बुलेटिन में ऑनलाइन कागजों के साथ सभी खंडों के लिंक हैं। अलोंजो चर्च, 1938, द कंस्ट्रक्टिव सेकंड नंबर क्लास "29 दिसंबर, 1937 को सोसाइटी की इंडियानापोलिस बैठक में कार्यक्रम समिति के निमंत्रण पर दिया गया एक संबोधन।" कर्ट गोडेल, 1931, प्रिंसिपिया मैथेमेटिका और संबंधित प्रणालियों के औपचारिक रूप से अनिश्चित प्रस्तावों पर I. मार्टिन हिरज़ेल द्वारा अनुवादित, 27 नवंबर 2000। एमिल एल. पोस्ट, 1946, ए वैरिएंट ऑफ ए रिकर्सिवली अनसोल्वेबल प्रॉब्लम, विल्फ्रेड सीग, 2005, चर्च विद विदाउट डॉग्माः एक्सिओम्स फॉर कम्प्यूटेबिलिटी, कार्नेगी मेलन यूनिवर्सिटी विल्फ्रेड सीग, 2000, कैल्क्युलेशन बाय मैन एंड मशीनः कॉन्सेप्चुअल एनालिसिस, कार्नेगी मेलन यूनिवर्सिटी रॉबर्ट आई. सोरे, 1995, कम्प्यूटेबिलिटी एंड रिकर्शन रॉबर्ट आई. सोरे, 1996, कम्प्यूटेबिलिटी एंड रिकर्शन जैसा कि द बुलेटिन ऑफ सिम्बोलिक लॉजिक, वॉल्यूम 2, वॉल्यूम 2, नंबर 3, सितंबर 1996 में दिखाई दिया। मासाको ताकाहाशी, 2004, सामान्य पुनरावर्ती कार्यों पर, अंतर्राष्ट्रीय ईसाई विश्वविद्यालय विशेष रूप से, संदर्भ देखें। ए. एम. ट्यूरिंग, 1936, ऑन कम्प्यूटेबल नंबर्स, विद एन एप्लीकेशन टू द एंटशेइडंग्सप्रॉब्लम चर्च-ट्यूरिंग थीसिस कम्प्यूटेबिलिटी थ्योरी एलन ट्यूरिंग थ्योरी ऑफ कम्प्यूटेशन