चर्च-ट्यूरिंग थीसिस

चर्च-ट्यूरिंग थीसिस यह दावा करती है कि किसी भी प्रभावी प्रक्रिया द्वारा गणना योग्य प्रत्येक फलन एक ट्यूरिंग मशीन द्वारा गणना योग्य है, जो एल्गोरिथम के अनौपचारिक विचार को एक सटीक गणितीय मॉडल के साथ समान करता है।

Definition

चर्च-ट्यूरिंग थीसिस यह दावा है कि सहज रूप से गणना योग्य फलन ठीक वही फलन हैं जो एक ट्यूरिंग मशीन द्वारा गणना योग्य हैं, जो लैम्डा कैलकुलस या सामान्य पुनरावर्ती फलनों के समतुल्य हैं; यह एक प्रमेय के बजाय एक थीसिस है क्योंकि सहज धारणा औपचारिक रूप से परिभाषित नहीं है।

Scope

यह विषय थीसिस के कथन, स्वतंत्र रूप से प्रस्तावित मॉडलों से अभिसारी साक्ष्य, प्रभावी गणनाशीलता के बारे में मूल थीसिस और मजबूत भौतिक या जटिलता-सैद्धांतिक वेरिएंट के बीच के अंतर, और गणनाशीलता सिद्धांत में अंतर्ज्ञान और औपचारिक प्रमाण के बीच एक सेतु के रूप में थीसिस की भूमिका को शामिल करता है।

Core questions

• एल्गोरिथम की अनौपचारिक धारणा को एक औपचारिक मॉडल के साथ पहचानने का क्या अर्थ है?
• स्वतंत्र मॉडलों के अभिसरण को थीसिस के लिए एक मजबूत सबूत के रूप में क्यों लिया जाता है?
• क्या थीसिस एक गणितीय प्रमेय है, एक परिभाषा है, या एक अनुभवजन्य दावा है?
• भौतिक और जटिलता-सैद्धांतिक संस्करण मूल कथन से आगे कैसे जाते हैं?

Key theories

गणना मॉडलों का अभिसरण

ट्यूरिंग मशीनें, चर्च का लैम्डा कैलकुलस, और गोडेल और हरब्रांड के पुनरावर्ती फलन को फलनों के ठीक उसी वर्ग को परिभाषित करने के लिए दिखाया गया था, और यह स्वतंत्र समझौता थीसिस के लिए पेश किया गया मुख्य प्रमाण है।

एक थीसिस के रूप में स्थिति, प्रमेय के रूप में नहीं

क्योंकि प्रभावी प्रक्रिया की सहज धारणा औपचारिक नहीं है, दावे को साबित नहीं किया जा सकता है; इसे एक मूलभूत पहचान के रूप में स्वीकार किया जाता है जो अनौपचारिक एल्गोरिथम तर्कों को औपचारिक ट्यूरिंग-मशीन निर्माणों के लिए खड़ा होने देता है।

Clinical relevance

यह थीसिस ट्यूरिंग मशीनों के बजाय उच्च-स्तरीय स्यूडोकोड में एल्गोरिदम का वर्णन करने की रोजमर्रा की प्रथा को लाइसेंस देती है, क्योंकि प्रभावी प्रक्रिया की कोई भी उचित धारणा ट्यूरिंग-समतुल्य मानी जाती है; यह इस बारे में भी बहस को फ्रेम करती है कि क्या भौतिक या क्वांटम उपकरण कभी ट्यूरिंग-गणना योग्य से परे गणना कर सकते हैं।

History

1936 में चर्च ने प्रभावी गणनाशीलता को लैम्डा-परिभाषा के साथ पहचानने का प्रस्ताव दिया, और ट्यूरिंग ने स्वतंत्र रूप से अपने मशीन मॉडल के लिए तर्क दिया, जिसके बाद ट्यूरिंग, क्लीने और अन्य ने इन्हें और पुनरावर्ती फलनों को समतुल्य साबित किया। गोडेल, शुरू में संशयवादी थे, ट्यूरिंग के विश्लेषण को निर्णायक मानने लगे, और संयुक्त दावे को चर्च-ट्यूरिंग थीसिस के रूप में जाना जाने लगा।

Debates

क्या भौतिक गणना ट्यूरिंग सीमा को पार कर सकती है?

मूल थीसिस प्रभावी प्रक्रियाओं से संबंधित है, लेकिन मजबूत भौतिक संस्करण दावा करते हैं कि कोई भी भौतिक रूप से साकार करने योग्य उपकरण गैर-ट्यूरिंग-गणना योग्य फलनों की गणना नहीं कर सकता है। हाइपरकंप्यूटेशन के प्रस्ताव और क्वांटम यांत्रिकी के निहितार्थ इस विस्तारित दावे को विवादित रखते हैं, भले ही शास्त्रीय थीसिस अनिवार्य रूप से अप्रतिबंधित बनी हुई है।

Key figures

• Alonzo Church
• Alan Turing
• Kurt Gödel
• Stephen Kleene

Seminal works

• church1936
• turing1937

Frequently asked questions

इसे प्रमेय के बजाय थीसिस क्यों कहा जाता है?

यह एक औपचारिक मॉडल को एक प्रभावी प्रक्रिया के अनौपचारिक विचार से जोड़ता है, और उस अनौपचारिक विचार की कोई गणितीय परिभाषा नहीं है जिसके बारे में चीजें साबित की जा सकें। मजबूत सबूत यह है कि गणना को औपचारिक बनाने के हर स्वतंत्र प्रयास ने फलनों के एक ही वर्ग को जन्म दिया है, लेकिन यह समर्थन एक प्रमाण के बजाय वैचारिक है।

क्या क्वांटम कंप्यूटर चर्च-ट्यूरिंग थीसिस का खंडन करते हैं?

नहीं। क्वांटम कंप्यूटर कुछ समस्याओं को तेजी से हल कर सकते हैं, लेकिन वे ट्यूरिंग मशीनों के समान ही फलनों के वर्ग की गणना करते हैं, इसलिए गणना योग्य होने के बारे में मूल थीसिस कायम है। वे गणनाशीलता के बजाय दक्षता से संबंधित मजबूत जटिलता-सैद्धांतिक संस्करण पर असर डालते हैं।