हॉल्टिंग समस्या

संगणनीयता सिद्धांत (कंप्यूटर विज्ञान) में, हॉल्टिंग की समस्या कंप्यूटर प्रोग्राम और इनपुट के विवरण से निर्धारित करने की समस्या है, जिसमे प्रोग्राम चलना समाप्त हो जाएगा, या सदैव के लिए चलना प्रारंभ रहेगा। हॉल्टिंग समस्या अनिर्णायक समस्या है, जिसका अर्थ है कि कोई भी सामान्य कलन विधि उपस्तिथ नहीं है जो सभी संभावित प्रोग्राम-इनपुट जोड़े के लिए हॉल्टिंग समस्या का समाधान करता है।

समस्या के औपचारिक विवरण का महत्वपूर्ण भाग कंप्यूटर और प्रोग्राम की गणितीय परिभाषा है, सामान्यतः ट्यूरिंग मशीन के माध्यम से प्रमाण तब दिखाता है, किसी भी प्रोग्राम f के लिए जो यह निर्धारित कर सकता है कि क्या प्रोग्राम रुके हैं या नहीं, यह पैथोलॉजिकल प्रोग्राम g है, जिसे कुछ इनपुट के साथ कहा जाता है, अपने स्वयं के स्रोत और इसके इनपुट को f पास कर सकता है और फिर विशेष रूप से इसके विपरीत करता है जो f भविष्यवाणी करता है। कोई f उपस्तिथ नहीं हो सकता है जो इस स्थिति को संभालता है, इस प्रकार अनिर्णीतता दिखाता है। यह प्रमाण व्यावहारिक कंप्यूटिंग प्रयासों के लिए महत्वपूर्ण है, जो अनुप्रयोगों की श्रेणी को परिभाषित करता है, कि प्रोग्रामिंग आविष्कार संभवतः पूर्ण रूप से प्रदर्शन नहीं कर सकता।

बैकग्राउंड

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

उदाहरण के लिए, स्यूडोकोड में, प्रोग्राम

while (true) continue

रुकता नहीं है; अन्यथा, यह अनंत लूप में सदैव के लिए चला जाता है। दूसरी ओर, प्रोग्राम

print "Hello, world!"

रुकता है।

यह तय करते समय कि क्या इन प्रोग्रामों को रोकना सरल है, अधिक जटिल प्रोग्राम समस्याग्रस्त सिद्ध होते हैं। समस्या की विधि यह हो सकती है कि प्रोग्राम को कुछ चरणों के लिए चलाया जाए और परीक्षण किया जाए कि क्या यह रुकता है। चूँकि, जब तक प्रोग्राम चल रहा है, यह अज्ञात है कि यह अंततः रुक जाएगा या सदैव के लिए चलेगा। ट्यूरिंग ने सिद्ध किया कि कोई एल्गोरिदम उपस्तिथ नहीं है जो सदैव उत्तम रूप से तय करता है कि किसी दिए गए प्रोग्राम और इनपुट के लिए, उस इनपुट के साथ चलने पर प्रोग्राम रुक जाता है या नहीं। ट्यूरिंग के प्रमाण का सार यह है कि ऐसा कोई भी एल्गोरिदम विरोधाभासी आउटपुट उत्पन्न करने के लिए बनाया जा सकता है और इसलिए सही नहीं हो सकता है।

प्रोग्रामिंग परिणाम

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

कभी-कभी ये प्रोग्रामर कुछ सामान्य-उद्देश्य (ट्यूरिंग-पूर्ण स्पार्क (प्रोग्रामिंग भाषा) का उपयोग करते हैं, किंतु प्रतिबंधित शैली में लिखने का प्रयास करते हैं- जैसे कि मिश्रा सी या स्पार्क (प्रोग्रामिंग भाषा) जिससे यह सिद्ध करना सरल हो जाता है कि परिणामी सबरूटीन्स दी गई समय सीमा से पूर्व समाप्त हो जाती हैं।

दूसरी बार ये प्रोग्रामर कम से कम शक्ति के नियम को प्रारम्भ करते हैं- वे निश्चयपूर्वक कंप्यूटर भाषा का उपयोग करते हैं जो पूर्ण रूप से ट्यूरिंग-पूर्ण नहीं है। प्रायः, ये ऐसी भाषाएँ होती हैं जो सभी सबरूटीन्स के समाप्त होने का आश्वासन देती हैं, जैसे कोक इत्यादि।

सामान्य हानि

हॉल्टिंग समस्या में कठिनाई इस आवश्यकता में निहित है कि निर्णय प्रक्रिया को सभी प्रोग्रामों और इनपुट के लिए कार्य करना चाहिए। विशेष प्रोग्राम या तो किसी दिए गए इनपुट पर रुकता है या रुकता नहीं है। एल्गोरिथ्म पर विचार करें जो सदैव "हॉल्टिंग" का उत्तर देता है और दूसरा जो सदैव "नहीं रोकता" का उत्तर देता है। किसी भी विशिष्ट प्रोग्राम और इनपुट के लिए, इन दो एल्गोरिदम में से सही उत्तर देता है, भले ही किसी को पता न हो कि कौन सा है। फिर भी न तो एल्गोरिदम सामान्यतः हॉल्टिंग समस्या को समाधान करता है।

ऐसे प्रोग्राम (दुभाषिया (कंप्यूटिंग)) हैं जो उन्हें दिए गए किसी भी स्रोत कोड के निष्पादन का अनुकरण करते हैं। इस प्रकार के प्रोग्राम प्रदर्शित कर सकते हैं कि यदि ऐसा है तो प्रोग्राम रुक जाता है: दुभाषिया अंततः अपने अनुकरण को रोक देगा, जो दर्शाता है कि मूल प्रोग्राम रुका हुआ है। चूँकि, दुभाषिया बंद नहीं होगा यदि उसका इनपुट प्रोग्राम रुकता नहीं है, इसलिए यह दृष्टिकोण रुकने की समस्या को समाधान नहीं कर सकता जैसा कि कहा गया है; यह उन प्रोग्रामों के लिए सफलतापूर्वक उत्तर नहीं देता है जो रुकते नहीं हैं।

हॉल्टिंग समस्या सैद्धांतिक रूप से रैखिक परिबद्ध ऑटोमेटा (LBAs) या परिमित मेमोरी वाली नियतात्मक मशीनों के लिए निर्णायक है। परिमित मेमोरी वाली मशीन में विन्यास की सीमित संख्या होती है, और इस प्रकार उस पर किसी भी नियतात्मक प्रोग्राम को अंततः पूर्व कॉन्फ़िगरेशन को रोकना या दोहराना चाहिए:

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

चूँकि, दस लाख छोटे भागों वाले कंप्यूटर, प्रत्येक में दो अवस्थाएं, कम से कम 21,000,000 संभावित अवस्थाएं होंगी:

यह 1 है जिसके पश्चात लगभग तीन लाख शून्य हैं भले ही ऐसी मशीन ब्रह्मांडीय किरणों की आवृत्तियों पर कार्य करती हो, गांगेय विकास के कल्प इस प्रकार के चक्र के माध्यम से यात्रा के समय की तुलना में कुछ भी नहीं होंगे:

चूँकि मशीन परिमित हो सकती है, और परिमित ऑटोमेटा की कई सैद्धांतिक सीमाएँ हैं:

इसमें सम्मिलित परिमाणों से किसी को यह संदेह होना चाहिए कि मुख्य रूप से केवल परिमितता [के] स्थिति आरेख पर आधारित प्रमेय और तर्क अधिक महत्व नहीं रख सकते हैं।

यह स्वचालित रूप से तय किया जा सकता है कि प्रत्येक संभावित निर्णय के पश्चात स्थिति की गणना करके, परिमित मेमोरी वाली गैर-नियतात्मक मशीन किसी भी या गैर-नियतात्मक निर्णयों के सभी संभावित अनुक्रमों पर रुकती है या नहीं।

इतिहास

Further information: एल्गोरिथम § इतिहास: "एल्गोरिदम" की धारणा का विकास

अप्रैल 1936 में, अलोंजो चर्च ने लैम्ब्डा कैलकुलस में समस्या की अनिर्णयता का अपना प्रमाण प्रकाशित किया। ट्यूरिंग का प्रमाण पश्चात में जनवरी 1937 में प्रकाशित किया गया था। तब से, कई अन्य अनिर्णीत समस्याओं का वर्णन किया गया है, जिसमें हॉल्टिंग समस्या भी सम्मिलित है, जो 1950 के दशक में सामने आई थी।

समयरेखा

• Template:आरंभ करने की तिथि: डेविड हिल्बर्ट पेरिस में दूसरे गणितज्ञों की अंतर्राष्ट्रीय कांग्रेस में अपने "23 प्रश्न" (अब हिल्बर्ट की समस्याओं के रूप में जाने जाते हैं) प्रस्तुत करते हैं। "इनमें से, दूसरा 'पियानो एक्सिओम्स' की निरंतरता को साबित करने का था, जिस पर, जैसा कि उन्होंने दिखाया था, गणित की कठोरता निर्भर थी"।
• Template:आरंभ करने की तिथि – Template:अंतिम तिथि: एमिल पोस्ट टैग सिस्टम के लिए हॉल्टिंग समस्या की परीक्षण करता है, इसे समाधान न होने के लिए उम्मीदवार के रूप में देखता है।इसकी अघुलनशीलता [[मार्विन मिन्स्की द्वारा अधिक पश्चात तक स्थापित नहीं किया गया था

]].

• Template:आरंभ करने की तिथि: बोलोग्ना इंटरनेशनल कांग्रेस में हिल्बर्ट ने अपनी 'दूसरी समस्या' का पुनर्पाठ किया। उन्होंने तीन प्रश्न किए: अर्थात 1: क्या गणित पूर्ण था? 2: क्या गणित संगत था? 3: क्या गणित निर्णायक था तीसरे प्रश्न को एन्त्शेइडुंग्स समस्या (निर्णय समस्या) के रूप में जाना जाता है।
• Template:आरंभ करने की तिथि: कर्ट गोडेल हिल्बर्ट के 1928 के पहले दो प्रश्नों के उत्तर के रूप में प्रमाण की घोषणा करता है।

"सबसे पहले वह [हिल्बर्ट] केवल क्रोधित और निराश था, किन्तु फिर उसने समस्या से रचनात्मक रूप से निवारण का प्रयत्न प्रारंभ कर दिया, गोडेल ने स्वयं अनुभूत किया- और अपने पेपर में विचार व्यक्त किया- कि उनका कार्य हिल्बर्ट के औपचारिक बिंदु के विपरीत नहीं देखना था"

• Template:आरंभ करने की तिथि: गोडेल ने "प्रिंसिपिया मैथेमेटिका और संबंधित प्रणाली के औपचारिक रूप से अनिर्णायक प्रस्तावों पर" प्रकाशित किया
• 19 April 1935 (1935-04-19): अलोंजो चर्च "प्राथमिक संख्या सिद्धांत की अघुलनशील समस्या" प्रकाशित करता है, जो प्रस्तावित करता है कि प्रभावी रूप से गणना योग्य फ़ंक्शन की सहज धारणा को सामान्य पुनरावर्ती कार्यों या समकक्ष रूप से औपचारिक रूप दिया जा सकता है। लैम्ब्डा-निश्चित कार्यों द्वारा वह सिद्ध करता है कि लैम्ब्डा कैलकुलस के लिए हॉल्टिंग समस्या (अर्थात, क्या किसी दिए गए लैम्ब्डा-एक्सप्रेशन का बीटा सामान्य रूप है) प्रभावी रूप से गणना योग्य नहीं है।
• 1936 (1936): कम्प्यूटेबल फंक्शन द्वारा गणना की धारणा का उपयोग करते हुए, चर्च प्रथम प्रमाण प्रकाशित करता है कि एन्त्शेइडुंग्स समस्या अघुलनशील है।
• 7 October 1936 (1936-10-07): एमिल पोस्ट का पेपर "फिनिट कॉम्बिनेटरी प्रोसेसेस फॉर्म्युलेशन I" प्राप्त हुआ है। पोस्ट उनकी "प्रक्रिया" में निर्देश "(सी) स्टॉप" जोड़ता है। उन्होंने इस प्रकार की प्रक्रिया को "टाइप 1 यदि यह प्रक्रिया निर्धारित करती है तो प्रत्येक विशिष्ट समस्या के लिए समाप्त हो जाती है।"
• May 1936 (1936-05) – January 1937 (1937-01): एलन ट्यूरिंग का पेपर ऑन कम्प्यूटेबल नंबर्स विथ ए एप्लीकेशन टू द एंट्सचेइडुंग्सप्रोब्लेम मई 1936 में प्रेस में गया और जनवरी 1937 में प्रिंट तक पहुंचा। ट्यूरिंग तीन समस्याओं को अनिर्णीत सिद्ध करता है: "संतुष्टि" समस्या, "प्रिंटिंग" समस्या, और 'एंट्सचिडंग स्प्रोब्लेम'

. ट्यूरिंग का प्रमाण मशीन द्वारा संगणना की धारणा को प्रस्तुत करके चर्च के प्रमाण से भिन्न है। यह "निर्णय समस्याओं के पहले उदाहरणों में से सिद्ध नहीं हुआ"।

• 1939 (1939): जे। बार्कले रोसेर गोडेल, चर्च और ट्यूरिंग द्वारा परिभाषित "प्रभावी विधि" की आवश्यक समानता को देखता है
• 1943 (1943): एक पेपर में, स्टीफन क्लेन ने कहा है कि "पूर्ण एल्गोरिथम सिद्धांत की स्थापना में, प्रक्रिया का वर्णन करते हैं जो प्रक्रिया आवश्यक रूप से समाप्त हो जाती है और इस प्रकार से कि परिणाम से हम निश्चित उत्तर पढ़ सकते हैं, प्रश्न के लिए 'हाँ' या 'नहीं', 'क्या विधेय मान सत्य है?'
• 1952 (1952): क्लेन में ट्यूरिंग मशीनों के लिए हॉल्टिंग समस्या की असम्भाव्यता की चर्चा सम्मिलित है और मशीनों के संदर्भ में इसे फिर से तैयार करता है जो "अंततः रुक जाती है" यह तय करने के लिए कोई एल्गोरिदम नहीं है कि क्या किसी दिए गए मशीन से प्रारंभ किया गया है या नहीं स्थिति, अंततः रुक जाती है."
• 1952 (1952): मार्टिन डेविस ने 1952 में इलिनोइस विश्वविद्यालय में नियंत्रण प्रणाली प्रयोगशाला में व्याख्यान की श्रृंखला में 'हॉल्टिंग प्रॉब्लम' शब्द का प्रयोग किया। यह संभावना है कि इस शब्द का यह प्रथम प्रयोग है।

हॉल्टिंग की समस्या की उत्पत्ति

कई प्रलेख और पाठ्यपुस्तकों ने ट्यूरिंग के 1936 के पेपर में हॉल्टिंग समस्या की अनिर्णयता की परिभाषा और प्रमाण का उल्लेख किया है। चूँकि, यह सही नहीं है। ट्यूरिंग ने अपने 1936 के पेपर सहित अपनी किसी भी प्रकाशित रचना में हॉल्ट या हॉल्टिंग शब्दों का प्रयोग नहीं किया। 1936 से 1958 तक अकादमिक साहित्य की के आविष्कार से ज्ञात से हुआ कि "हॉल्टिंग प्रॉब्लम" शब्द का उपयोग करने वाली प्रथम प्रकाशित सामग्री थी रोजर्स (1957) थी। चूँकि, रोजर्स का कहना है कि उनके पास डेविस (1958) उसके पास उपलब्ध है, और मार्टिन डेविस प्रस्तावना में कहते हैं कि विशेषज्ञ संभवतः विषयों की व्यवस्था और प्रणाली में कुछ नवीनता पाएंगे, इसलिए शब्दावली का श्रेय डेविस को दिया जाना चाहिए। डेविस ने पत्र में कहा कि वह 1952 से हॉल्टिंग समस्या की बात कर रहे थे।डेविस की किताब में उपयोग इस प्रकार है:

"[...] हम यह निर्धारित करना चाहते हैं कि [ट्यूरिंग मशीन] Z, यदि किसी प्रारंभिक अवस्था में रखा गया है, तो अंततः रुक जाएगा। हम इस समस्या को Z के लिए रुकने की समस्या कहते हैं। [...]

प्रमेय 2.2 एक ट्यूरिंग मशीन उपस्तिथ है जिसकी हॉल्टिंग समस्या पुनरावर्ती रूप से अघुलनशील है।
प्रतीक के संबंध में एक साधारण ट्यूरिंग मशीन Z के लिए एक संबंधित समस्या 'प्रिंटिंग समस्या' है

S_i".

डेविस के सूत्रीकरण का संभावित अग्रदूत क्लेन का 1952 का व्याख्यान है, जो केवल शब्दों में भिन्न है:

यह तय करने के लिए कोई एल्गोरिद्म नहीं है कि क्या कोई दी गई मशीन, जब किसी दी गई स्थिति से प्रारंभ की जाती है, अंततः बंद हो जाती है।

रुकने की समस्या दोनों डेविस की प्रिंटिंग समस्या समान है (क्या किसी दिए गए स्थिति से प्रारंभ होने वाली ट्यूरिंग मशीन कभी किसी दिए गए प्रतीक को प्रिंट करती है?) और ट्यूरिंग के 1936 के पेपर में विचार की गई प्रिंटिंग समस्या ("क्या ट्यूरिंग मशीन एक रिक्त से प्रारंभ होती है?" टेप कभी दिए गए प्रतीक को प्रिंट करता है?")। चूँकि, ट्यूरिंग तुल्यता अन्यथा ढीली है और इसका अर्थ यह नहीं है कि दो समस्याएं समान हैं। ऐसी मशीनें हैं जो प्रिंट करती हैं किंतु रुकती नहीं हैं और रुकती हैं किंतु प्रिंट नहीं करती हैं। छपाई और रुकने की समस्याएँ विभिन्न उद्देश्य को संबोधित करती हैं और महत्वपूर्ण वैचारिक और तकनीकी अंतर प्रदर्शित करती हैं। इस प्रकार, डेविस केवल विनम्र थे जब उन्होंने कहा:

यह भी उल्लेख किया जा सकता है कि अनिवार्य रूप से इन समस्याओं की अघुलनशीलता को सबसे पहले ट्यूरिंग द्वारा प्राप्त किया गया था।

औपचारिकता

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

जो महत्वपूर्ण है वह यह है कि औपचारिकता कुछ डेटा प्रकारों के लिए एल्गोरिदम की सीधी मैपिंग की अनुमति देती है जिस पर एल्गोरिदम कार्य कर सकता है। उदाहरण के लिए, यदि औपचारिकता (गणित) एल्गोरिदम को स्ट्रिंग्स (जैसे ट्यूरिंग मशीन) पर फलन को परिभाषित करने देता है, तो स्ट्रिंग्स के लिए इन एल्गोरिदम की मैपिंग होनी चाहिए, और यदि औपचारिकता एल्गोरिदम को प्राकृतिक संख्याओं (जैसे गणना योग्य फलन) पर फलन परिभाषित करने देती है। फिर प्राकृतिक संख्याओं के लिए एल्गोरिदम की मैपिंग होनी चाहिए। स्ट्रिंग्स की मैपिंग सामान्यतः सबसे सीधी होती है, किंतु n वर्णों (कंप्यूटिंग) के साथ वर्णमाला पर स्ट्रिंग्स को n-आरी अंक प्रणाली में संख्याओं के रूप में व्याख्या करके संख्याओं में मैप किया जा सकता है।

सेट के रूप में प्रतिनिधित्व

Main article: निर्णय समस्या

निर्णय समस्याओं का पारंपरिक प्रतिनिधित्व उन वस्तुओं का समूह है जिनके पास संपत्ति है। हॉल्टिंग सेट

K = {(i, x) इनपुट x पर चलाए जाने पर प्रोग्राम i हाल्ट हो जाता है}

हॉल्टिंग की समस्या का प्रतिनिधित्व करता है।

यह सेट पुनरावर्ती रूप से गणना योग्य है, जिसका अर्थ है कि संगणनीय कार्य है जो इसमें सम्मिलित सभी जोड़े (i, x) को सूचीबद्ध करता है। चूँकि, इस सेट का पूरक पुनरावर्ती गणना योग्य नहीं है।

हॉल्टिंग समस्या के कई समतुल्य सूत्रीकरण हैं; कोई भी सेट जिसकी ट्यूरिंग डिग्री रुकने की समस्या के समान होती है, ऐसा सूत्रीकरण है। ऐसे सेट के उदाहरणों में सम्मिलित हैं:

• {i| प्रोग्राम I अंतत: तक रुक जाता है जब इनपुट 0 के साथ चलाया जाता है}
• {i| इनपुट x है जैसे कि इनपुट x के साथ चलने पर प्रोग्राम i अंततः रुक जाता है}।

प्रमाण अवधारणा

क्रिस्टोफर स्ट्रेची ने विरोधाभास द्वारा प्रमाण को रेखांकित किया कि हॉल्टिंग समस्या समाधान करने योग्य नहीं है। प्रमाण निम्नानुसार अग्रसर होता है: मान लीजिए कि कुल संगणनीय फ़ंक्शन हाल्ट (f) उपस्तिथ है, जो सबरूटीन f हाल्ट पर उचित रिटर्न देता है (जब बिना इनपुट के रन करवाया जाता है) और अन्यथा त्रुटिपूर्ण रिटर्न देता है। अब निम्नलिखित सबरूटीन पर विचार करें:

def g():
    if halts(g):
        loop_forever()

हाल्ट (g) का या तो उचित या अनुचित रिटर्न आना चाहिए, क्योंकि हॉल्ट को कुल फंक्शन माना जाता था। यदि हाल्ट (g) उचित रिटर्न देता है, तो जी लूप_फॉरएवर को कॉल करेगा और कभी नहीं रुकेगा, जो विरोधाभास है। यदि हाल्ट (g) अनुचित रिटर्न देता है, तो g रुक जाएगा, क्योंकि यह लूप_फॉरएवर को कॉल नहीं करेगा; यह भी विरोधाभास है। पूर्ण रूप से, g इसके विपरीत करता है जो हाल्ट्स कहता है कि g को करना चाहिए, इसलिए हाल्ट (g) सत्य मान रिटर्न नहीं करता है जो g के हाल्ट के अनुरूप होता है। इसलिए, प्रारंभिक धारणा है कि हॉल्ट कुल संगणनीय फंक्शन अनुचित होना चाहिए।

कठोर प्रमाण का रेखाचित्र

उपरोक्त अवधारणा प्रमाण की सामान्य विधि को दर्शाती है, किंतु संगणनीय फंक्शन हाल्ट आर्गुमेंट के रूप में सबरूटीन नहीं लेता है; इसके अतिरिक्त यह प्रोग्राम का सोर्स कोड लेता है। इसके अतिरिक्त, g की परिभाषा स्व-संदर्भित है। कठोर प्रमाण इन उद्देश्यों को संबोधित करता है। समग्र लक्ष्य यह दर्शाना है कि कोई कुल संगणनीय फंक्शन नहीं है जो यह निश्चित करता है कि क्या आर्बिट्ररी प्रोग्राम i आर्बिट्ररी इनपुट x पर रुकता है; अर्थात्, निम्न फंक्शन h (हॉल्ट्स के लिए) संगणनीय नहीं है:

$h(i,x)={\begin{cases}1&{\text{if }}{\text{ program }}i{\text{ halts on input }}x,\\0&{\text{otherwise.}}\end{cases}}$

यहाँ प्रोग्राम i का तात्पर्य गणना के निश्चित ट्यूरिंग-पूर्ण मॉडल के सभी प्रोग्रामों की गणना में i वें प्रोग्राम से है।

f(i,j)		i
		1	2	3	4	5	6
j	1	1	0	0	1	0	1
	2	0	0	0	1	0	0
	3	0	1	0	1	0	1
	4	1	0	0	1	0	0
	5	0	0	0	1	1	1
	6	1	1	0	0	1	0
	f(i,i)	1	0	0	1	1	0
	g(i)	U	0	0	U	U	0

2डी ऐरे में व्यवस्थित कुल संगणनीय फ़ंक्शन f के लिए संभावित मान हैं। नारंगी सेल विकर्ण हैं। f(i,i) और g(i) के मान नीचे दर्शाये गए हैं; U दर्शाता है कि फ़ंक्शन g किसी विशेष इनपुट मान के लिए अपरिभाषित है।

प्रमाण यह स्थापित करके अग्रसर होता है कि दो तर्कों के साथ कुल संगणनीय फ़ंक्शन आवश्यक फ़ंक्शन h नहीं हो सकता है। जैसा कि अवधारणा के रेखाचित्र में है कि कुल संगणनीय बाइनरी फ़ंक्शन f दिया गया है, निम्न आंशिक फ़ंक्शन g भी कुछ प्रोग्राम e द्वारा संगणनीय है:

$g(i)={\begin{cases}0&{\text{if }}f(i,i)=0,\\{\text{undefined}}&{\text{otherwise.}}\end{cases}}$

g संगणनीय है, यह सत्यापन निम्नलिखित निर्माणों (या उनके समतुल्य) पर निर्भर करता है:

• कंप्यूटेबल सबप्रोग्राम (वह प्रोग्राम जो f की गणना करता है, प्रोग्राम e में सबप्रोग्राम है),
• मानों का दोहराव (प्रोग्राम e, g के लिए इनपुट i से f के लिए इनपुट i की गणना करता है),
• कंडीशनल ब्रांचिंग (प्रोग्राम e दो परिणामों के मध्य चयन करता है जो कि f(i,i) के लिए गणना किए गए मान के आधार पर होता है),
• परिभाषित परिणाम नहीं दे रहा है (उदाहरण के लिए, सदैव के लिए लूप करके),
• 0 रिटर्न करता है।

e के लिए निम्नलिखित स्यूडोकोड g की गणना करने की सरल विधि दर्शाता है:

procedure e(i):
    if f(i, i) == 0 then
        return 0
    else
        loop forever

चूँकि g आंशिक संगणनीय है इसलिए प्रोग्राम e होना चाहिए जो g की गणना इस धारणा से करता है कि संगणना का मॉडल ट्यूरिंग-पूर्ण है। यह प्रोग्राम उन सभी प्रोग्रामों में से है जिन पर हॉल्टिंग फंक्शन h परिभाषित किया गया है। प्रमाण का अग्र चरण दर्शाता है कि h(e,e) का मान f(e,e) के समान नहीं होगा।

यह g की परिभाषा से अनुसरण करता है कि वास्तव में निम्नलिखित दो स्तिथियों में से एक होनी चाहिए:

• एफ (ई, ई) = 0 और इसलिए जी (ई) = 0। इस मामले में ई इनपुट ई पर रुकता है, इसलिए एच (ई, ई) = 1।
• f(e,e) ≠ 0 और इसलिए g(e) अपरिभाषित है। इस मामले में प्रोग्राम ई इनपुट ई पर नहीं रुकता है, इसलिए एच (ई, ई) = 0।

किसी भी स्थिति में, f, h के समान कार्य नहीं हो सकता। क्योंकि f दो तर्कों के साथ मनमाना कुल संगणनीय कार्य था, ऐसे सभी कार्यों को h से भिन्न होना चाहिए।

यह प्रमाण कैंटर के विकर्ण तर्क के अनुरूप है। जैसा कि ऊपर दी गई तालिका में दर्शाया गया है, प्रत्येक प्राकृतिक संख्या के लिए स्तंभ और पंक्ति के साथ द्वि-आयामी सरणी की कल्पना की जा सकती है। f(i,j) का मान कॉलम i, पंक्ति j पर रखा गया है। क्योंकि f को कुल संगणनीय कार्य माना जाता है, सरणी के किसी भी तत्व की गणना f का उपयोग करके की जा सकती है। इस सरणी के मुख्य विकर्ण का उपयोग करके फलन g के निर्माण की कल्पना की जा सकती है। यदि सरणी की स्थिति (i,i) पर 0 है, तो g(i) 0 है। अन्यथा, g(i) अपरिभाषित है। विरोधाभास इस तथ्य से आता है कि जी के अनुरूप सरणी का कुछ स्तंभ ई है। अब मान लें कि f हॉल्टिंग फंक्शन h था, अगर g(e) परिभाषित है (इस मामले में g(e) = 0), g(e) रुकता है तो f(e,e) = 1. किंतु g(e) = 0 केवल जब f(e,e) = 0, f(e,e) = 1 के विपरीत। ) = 0 जी के निर्माण के तहत। यह g(e) परिभाषित नहीं होने की धारणा के विपरीत है। दोनों ही स्थितियों में विरोधाभास उत्पन्न होता है। इसलिए कोई भी मनमाना संगणनीय फलन f हॉल्टिंग फलन h नहीं हो सकता।

कम्प्यूटेबिलिटी सिद्धांत

Main article: संगणनीयता सिद्धांत

किसी समस्या को अनिर्णीत सिद्ध करने का विशिष्ट विधि यह है कि इसे समाधान करने की समस्या में कमी (जटिलता) करना है। उदाहरण के लिए, कोई सामान्य एल्गोरिथम नहीं हो सकता है जो यह तय करे कि प्राकृतिक संख्याओं के बारे में दिया गया कथन सत्य है या असत्य। इसका कारण यह है कि यह प्रस्ताव कि निश्चित इनपुट दिए जाने पर निश्चित प्रोग्राम रुक जाएगा, प्राकृतिक संख्याओं के बारे में समान कथन में परिवर्तित किया जा सकता है। यदि एल्गोरिथ्म प्राकृतिक संख्याओं के बारे में प्रत्येक कथन का सत्य मान पा सकता है, तो वह निश्चित रूप से इसका सत्य मान खोज सकता है; किंतु यह निर्धारित करेगा कि मूल प्रोग्राम रुकता है या नहीं।

राइस की प्रमेय इस प्रमेय का सामान्यीकरण करती है कि रुकने की समस्या का समाधान नहीं किया जा सकता है। यह बताता है कि किसी भी गैर-तुच्छ संपत्ति के लिए, कोई सामान्य निर्णय प्रक्रिया नहीं है, जो सभी प्रोग्रामों के लिए, यह तय करती है कि इनपुट प्रोग्राम द्वारा कार्यान्वित आंशिक कार्य में वह संपत्ति है या नहीं। (आंशिक कार्य ऐसा कार्य है जो सदैव परिणाम नहीं दे सकता है, और इसलिए इसका उपयोग मॉडल प्रोग्राम के लिए किया जाता है, जो या तो परिणाम उत्पन्न कर सकता है या रुकने में विफल हो सकता है।) उदाहरण के लिए, इनपुट 0 के लिए संपत्ति पड़ाव अनिर्णीत है। यहाँ, गैर-तुच्छ का अर्थ है कि संपत्ति को संतुष्ट करने वाले आंशिक कार्यों का सेट न तो रिक्त सेट है और न ही सभी आंशिक कार्यों का सेट। उदाहरण के लिए, इनपुट 0 पर रुकने या रुकने में विफल सभी आंशिक कार्यों के लिए स्पष्ट रूप से सही है, इसलिए यह तुच्छ संपत्ति है, और एल्गोरिथ्म द्वारा तय किया जा सकता है जो केवल सच की रिपोर्ट करता है। साथ ही, यह प्रमेय केवल प्रोग्राम द्वारा कार्यान्वित आंशिक कार्य के गुणों के लिए है; चावल की प्रमेय प्रोग्राम के गुणों पर ही प्रारम्भ नहीं होती है। उदाहरण के लिए, 100 चरणों के भीतर इनपुट 0 पर रुकना प्रोग्राम द्वारा प्रारम्भ किए गए आंशिक फलन की संपत्ति नहीं है - यह आंशिक फलन को प्रारम्भ करने वाले प्रोग्राम की संपत्ति है और यह बहुत ही निर्णायक है।

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

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

सन्निकटन

ट्यूरिंग के प्रमाण से पता चलता है कि यह निर्धारित करने के लिए कि एल्गोरिदम रुकता है या नहीं, कोई यांत्रिक, सामान्य विधि (यानी, ट्यूरिंग मशीन या गणना के कुछ समकक्ष मॉडल में प्रोग्राम) नहीं हो सकती है। चूँकि, हॉल्टिंग समस्या के प्रत्येक व्यक्तिगत उदाहरण का निश्चित उत्तर होता है, जो व्यावहारिक रूप से संगणनीय हो भी सकता है और नहीं भी। विशिष्ट एल्गोरिथ्म और इनपुट को देखते हुए, कोई प्रायः दिखा सकता है कि यह रुकता है या नहीं रुकता है, और वास्तव में कंप्यूटर वैज्ञानिक प्रायः शुद्धता (कंप्यूटर विज्ञान) के हिस्से के रूप में ऐसा ही करते हैं। कुछ ह्युरिस्टिक (कंप्यूटर विज्ञान) हैं जिनका उपयोग प्रमाण के निर्माण के प्रयास के लिए स्वचालित रूप से किया जा सकता है, जो प्रायः विशिष्ट प्रोग्रामों में सफल होते हैं। अनुसंधान के इस क्षेत्र को स्वचालित समाप्ति विश्लेषण के रूप में जाना जाता है।

हॉल्टिंग प्रॉब्लम ह्यूरिस्टिक्स के सैद्धांतिक प्रदर्शन पर कुछ परिणाम स्थापित किए गए हैं, विशेष रूप से किसी दिए गए आकार के प्रोग्रामों के अंश जिन्हें पुनरावर्ती एल्गोरिथम द्वारा सही रूप से वर्गीकृत किया जा सकता है। ये परिणाम सटीक संख्या नहीं देते हैं क्योंकि अंश अगणनीय हैं और आकार निर्धारित करने के लिए उपयोग किए जाने वाले प्रोग्राम एन्कोडिंग की पसंद पर अत्यधिक निर्भर हैं। उदाहरण के लिए, प्रोग्रामों को उनके राज्यों की संख्या के आधार पर वर्गीकृत करने पर विचार करें और गणना के विशिष्ट ट्यूरिंग सेमी-अनंत टेप मॉडल का उपयोग करें कि यदि प्रोग्राम टेप के बाईं ओर चलता है तो त्रुटियां (बिना रुके)। तब $\lim _{n\to \infty }P(x\,{\text{halts is decidable}}\mid x\,{\text{has}}\,n\,{\text{states}})=1$, प्रोग्रामों पर $x$ राज्यों की संख्या द्वारा समान रूप से चुना गया। किंतु यह परिणाम कुछ अर्थों में तुच्छ है क्योंकि ये निर्णायक प्रोग्राम केवल वही हैं जो टेप से गिर जाते हैं, और अनुमानी केवल त्रुटि के कारण रुकने की भविष्यवाणी करने के लिए है। इस प्रकार प्रतीत होता है अप्रासंगिक विवरण, अर्थात् त्रुटियों वाले प्रोग्रामों का उपचार, प्रोग्रामों के अंश को निर्धारित करने में निर्णायक कारक बन सकता है। इन उद्देश्य से बचने के लिए, प्रोग्राम के आकार की कई प्रतिबंधित धारणाएँ विकसित की गई हैं। सघन गोडेल क्रमांकन प्रोग्रामों को संख्याएँ प्रदान करता है जैसे कि प्रत्येक संगणनीय फलन 1 से n तक के सूचकांकों के प्रत्येक अनुक्रम में धनात्मक अंश होता है, अर्थात सभी के लिए गोडेलाइज़ेशन φ सघन होता है। $i$, वहाँ उपस्तिथ है $c>0$ ऐसा है कि $\liminf _{n\to \infty }\#\{j\in \mathbb {N} :0\leq j<n,\phi _{i}=\phi _{j}\}/n\geq c$. उदाहरण के लिए, क्रमांकन जो अनुक्रमित करता है $2^{n}$ गैर-तुच्छ प्रोग्रामों और अन्य सभी सूचकांकों के लिए त्रुटि स्थिति सघन नहीं है, किंतु सिंटैक्टिक रूप से सही ब्रेनफक प्रोग्रामों की सघन गोडेल संख्या उपस्तिथ है। किसी भी अन्य गोडेल नंबरिंग के लिए सघन गोडेल नंबरिंग को इष्टतम कहा जाता है $\alpha$, 1-1 कुल पुनरावर्ती कार्य है $f$ और स्थिर $c$ ऐसा कि सभी के लिए $i$, $\alpha _{i}=\phi _{f(i)}$ और $f(i)\leq ci$. यह स्थिति सुनिश्चित करती है कि सभी प्रोग्रामों के सूचकांक किसी भी अन्य गोडेल नंबरिंग में उनके सूचकांकों की तुलना में बहुत बड़े नहीं हैं। यूनिवर्सल ट्यूरिंग मशीन के इनपुट को नंबर देकर इष्टतम गोडेल नंबरिंग का निर्माण किया जाता है। आकार की तीसरी धारणा बाइनरी स्ट्रिंग्स पर चलने वाली सार्वभौमिक मशीनों का उपयोग करती है और इनपुट प्रोग्राम का वर्णन करने के लिए आवश्यक स्ट्रिंग की लंबाई को मापती है। सार्वभौमिक मशीन यू ऐसी मशीन है जिसके लिए हर दूसरी मशीन वी में कुल गणना योग्य कार्य एच उपस्तिथ है $V(x)=U(h(x))$. इष्टतम मशीन सार्वभौमिक मशीन है जो कोल्मोगोरोव जटिलता को प्राप्त करती है#अपरिवर्तनीय प्रमेय, यानी प्रत्येक मशीन वी के लिए, सी उपस्तिथ है जैसे कि सभी आउटपुट एक्स के लिए, यदि लंबाई एन आउटपुट एक्स का वी-प्रोग्राम है, तो यू-प्रोग्राम उपस्तिथ है अधिकतम लंबाई का $n+c$ आउटपुट एक्स। हम आंशिक संगणनीय कार्यों (एल्गोरिदम) पर विचार करते हैं $A$. प्रत्येक के लिए $n$ हम अंश पर विचार करते हैं $\epsilon _{n}(A)$ अधिकतम आकार मीट्रिक के सभी प्रोग्रामों में त्रुटियों की संख्या $n$, प्रत्येक प्रोग्राम की गिनती $x$ जिसके लिए $A$ समाप्त करने में विफल रहता है, अज्ञात उत्तर उत्पन्न करता है, या गलत उत्तर उत्पन्न करता है, अर्थात $x$ रुकता है और $A(x)$ आउटपुट DOES_NOT_HALT, या $x$ रुकता नहीं है और $A(x)$ आउटपुट HALTS. सघन गोडेलाइजेशन और इष्टतम मशीनों के लिए व्यवहार को निम्नानुसार वर्णित किया जा सकता है:

• प्रत्येक एल्गोरिदम के लिए $A$, $\liminf _{n\to \infty }\epsilon _{n}(A)>0$
• वहां उपस्तिथ $\epsilon >0$ ऐसा है कि हर एल्गोरिदम के लिए $A$, $\limsup _{n\to \infty }\epsilon _{n}(A)\geq \epsilon$
• $\inf _{A}\liminf _{n\to \infty }\epsilon _{n}(A)=0$. चूँकि, इसमें एल्गोरिदम सम्मिलित हैं जो गलत उत्तर उत्पन्न करते हैं।
• यदि हम केवल ईमानदार एल्गोरिदम पर विचार करते हैं जो अपरिभाषित हो सकते हैं किंतु कभी भी गलत उत्तर नहीं देते हैं, तो यह मीट्रिक पर निर्भर करता है $\inf _{A\,{\textrm {honest}}}\liminf _{n\to \infty }\epsilon _{n}(A)$ 0 हो सकता है या नहीं भी हो सकता है। विशेष रूप से यह बाएं-कुल सार्वभौमिक मशीनों के लिए 0 है, किंतु प्रभावी रूप से इष्टतम मशीनों के लिए यह 0 से अधिक है।

इन सीमाओं की जटिल प्रकृति के दोलनशील व्यवहार के कारण है $\epsilon _{n}(A)$. मनमाने रूप से बड़े ब्लॉकों में आने वाले प्रोग्रामों की नई किस्में और दोहराव का लगातार बढ़ता अंश प्रायः होता है। यदि नई किस्मों के ब्लॉक पूरी तरह से सम्मिलित हैं, तो त्रुटि दर कम से कम है $\epsilon$, किंतु ब्लॉक के बीच सही रूप से वर्गीकृत दोहराव का अंश मनमाने रूप से अधिक हो सकता है। विशेष रूप से टैली ह्यूरिस्टिक जो केवल पहले एन इनपुट को याद करता है और उनके समकक्षों को पहचानता है, मनमाने रूप से कम त्रुटि दर तक पहुंचने की अनुमति देता है।

गोडेल की अपूर्णता प्रमेय

{{#lsth:Undecidable problem|Relationship with Gödel's incompleteness theorem}}

सामान्यीकरण

कम्प्यूटेबिलिटी पाठ्यपुस्तकों में हॉल्टिंग समस्या के कई प्रकार पाए जा सकते हैं। सामान्यतः, ये समस्याएँ RE-पूर्ण होती हैं और जटिलता के सेट का वर्णन करती हैं $\Sigma _{1}^{0}$ अंकगणितीय पदानुक्रम में, मानक हॉल्टिंग समस्या के समान। वेरिएंट इस प्रकार अनिर्णीत हैं, और मानक हॉल्टिंग प्रॉब्लम कमी (पुनरावृत्ति सिद्धांत) प्रत्येक वेरिएंट के लिए और इसके विपरीत। चूँकि, कुछ प्रकारों में उच्च स्तर की अघुलनशीलता होती है और इसे मानक हॉल्टिंग समस्या में कम नहीं किया जा सकता है। अगले दो उदाहरण आम हैं।

सभी इनपुट्स पर रोक

सार्वभौमिक हॉल्टिंग समस्या, जिसे समग्रता के रूप में भी जाना जाता है (पुनरावृत्ति सिद्धांत में), यह निर्धारित करने की समस्या है कि क्या दिया गया कंप्यूटर प्रोग्राम सदैव रुकने वाली मशीन करेगा (संपूर्णता का नाम समतुल्य प्रश्न से आता है कि क्या परिकलित फलन कुल फलन है)। यह समस्या न केवल अनिर्णीत है, जैसा कि हॉल्टिंग समस्या है, अन्यथा अत्यधिक अनिर्णनीय है। अंकगणितीय पदानुक्रम के संदर्भ में, यह है $\Pi _{2}^{0}$-पूरा।

इसका अर्थ है, विशेष रूप से, यह समाधान करने की समस्या के लिए ऑरेकल मशीन के साथ भी तय नहीं किया जा सकता है।

आंशिक समाधान को पहचानना

ऐसे कई प्रोग्राम हैं, जो कुछ इनपुट के लिए हॉल्टिंग समस्या का सही उत्तर देते हैं, जबकि अन्य इनपुट के लिए वे बिल्कुल भी उत्तर नहीं देते हैं। चूँकि दी गई समस्या p, क्या यह आंशिक हॉल्टिंग सॉल्वर है (वर्णित अर्थ में) कम से कम हॉल्टिंग समस्या जितनी कठिन है। इसे देखने के लिए, मान लें कि ऐसा करने के लिए एल्गोरिथ्म PHSR (आंशिक हॉल्टिंग सॉल्वर पहचानकर्ता) है। तब इसका उपयोग रुकने की समस्या को समाधान करने के लिए किया जा सकता है, निम्नलिखित नुसार: यह जांचने के लिए कि क्या इनपुट प्रोग्राम x y पर रुकता है, प्रोग्राम p का निर्माण करें जो इनपुट (x, y) पर सही रिपोर्ट करता है और अन्य सभी इनपुटों पर विचलन करता है। फिर PHSR के साथ p का परीक्षण करें।

उपरोक्त तर्क PHS मान्यता के लिए हॉल्टिंग समस्या का न्यूनीकरण (पुनरावृत्ति सिद्धांत) है, और उसी तरह, कठिन समस्याओं जैसे कि सभी इनपुटों पर रोक को भी कम किया जा सकता है, जिसका अर्थ है कि PHS मान्यता न केवल अनिर्णीत है, अन्यथा अंकगणितीय पदानुक्रम में उच्चतर है, विशेष रूप से $\Pi _{2}^{0}$-पूरा।

हानिपूर्ण संगणना

हानिकारक ट्यूरिंग मशीन ट्यूरिंग मशीन है जिसमें टेप का भाग गैर-नियतात्मक रूप से गायब हो सकता है। हानिपूर्ण ट्यूरिंग मशीन के लिए रुकने की समस्या निर्णायक है किंतु गैर-आदिम पुनरावर्ती है।

ओरेकल मशीनें

See also: ट्यूरिंग जम्प

हॉल्टिंग समस्या के लिए ऑरेकल मशीन वाली मशीन यह निर्धारित कर सकती है कि क्या विशेष ट्यूरिंग मशीनें विशेष इनपुट पर रुकेंगी, किंतु वे सामान्य रूप से यह निर्धारित नहीं कर सकतीं कि क्या उनके समकक्ष मशीनें रुकेंगी।

यह भी देखें

• व्यस्त ऊदबिलाव
• गोडेल की अपूर्णता प्रमेय
• ब्रौवर-हिल्बर्ट विवाद
• कोलमोगोरोव जटिलता
• पी बनाम एनपी समस्या
• समाप्ति विश्लेषण
• सबसे खराब स्थिति निष्पादन समय

संदर्भ

• Church, Alonzo (1936). "An Unsolvable Problem of Elementary Number Theory". American Journal of Mathematics. 58 (2): 345–363. doi:10.2307/2371045. JSTOR 2371045.
• Copeland, B. Jack, ed. (2004). The essential Turing : seminal writings in computing, logic, philosophy, artificial intelligence, and artificial life, plus the secrets of Enigma. Oxford: Clarendon Press. ISBN 0-19-825079-7.
• Davis, Martin (1965). The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions. New York: Raven Press.. Turing's paper is #3 in this volume. Papers include those by Godel, Church, Rosser, Kleene, and Post.
• Davis, Martin (1958). Computability and Unsolvability. New York: McGraw-Hill..
• Rogers, Hartley (Jr.) (1957). Theory of Recursive Functions and Effective Computability (in English). Massachusetts Institute of Technology.
• Kleene, Stephen Cole (1952). Introduction to metamathematics. North-Holland. ISBN 0923891579.. Chapter XIII ("Computable Functions") includes a discussion of the unsolvability of the halting problem for Turing machines. In a departure from Turing's terminology of circle-free nonhalting machines, Kleene refers instead to machines that "stop", i.e. halt.
• Lucas, Salvador (June 2021). "The origins of the halting problem". Journal of Logical and Algebraic Methods in Programming. 121: 100687. doi:10.1016/j.jlamp.2021.100687.
• Minsky, Marvin (1967). Computation: finite and infinite machines. Englewood Cliffs, NJ: Prentice-Hall. ISBN 0131655639.. See chapter 8, Section 8.2 "Unsolvability of the Halting Problem."
• Moore, Cristopher; Mertens, Stephan (2011). The Nature of Computation. Oxford University Press. doi:10.1093/acprof:oso/9780199233212.001.0001. ISBN 978-0-19-923321-2.
• Reid, Constance (1996). Hilbert. New York: Copernicus. ISBN 0387946748.. First published in 1970, a fascinating history of German mathematics and physics from 1880s through 1930s. Hundreds of names familiar to mathematicians, physicists and engineers appear in its pages. Perhaps marred by no overt references and few footnotes: Reid states her sources were numerous interviews with those who personally knew Hilbert, and Hilbert's letters and papers.
• Sipser, Michael (2006). "Section 4.2: The Halting Problem". Introduction to the Theory of Computation (Second ed.). PWS Publishing. pp. 173–182. ISBN 0-534-94728-X.
• Turing, A. M. (1937). "On Computable Numbers, with an Application to the Entscheidungsproblem". Proceedings of the London Mathematical Society. Wiley. s2-42 (1): 230–265. doi:10.1112/plms/s2-42.1.230. ISSN 0024-6115. S2CID 73712., Turing, A. M. (1938). "On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction". Proceedings of the London Mathematical Society. Wiley. s2-43 (1): 544–546. doi:10.1112/plms/s2-43.6.544. ISSN 0024-6115. This is the epochal paper where Turing defines Turing machines, formulates the halting problem, and shows that it (as well as the Entscheidungsproblem) is unsolvable.
• Penrose, Roger (1989). The emperor's new mind: concerning computers, minds, and the laws of physics (1990 corrected reprint ed.). Oxford: Oxford University Press. ISBN 0192861980.. Cf. Chapter 2, "Algorithms and Turing Machines". An over-complicated presentation (see Davis's paper for a better model), but a thorough presentation of Turing machines and the halting problem, and Church's Lambda Calculus.
• Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation (1st ed.). Addison-Wesley. ISBN 81-7808-347-7.. See Chapter 7 "Turing Machines." A book centered around the machine-interpretation of "languages", NP-Completeness, etc.
• Hodges, Andrew (1983). Alan Turing: the enigma. New York: Simon and Schuster. ISBN 0-671-49207-1.. Cf. Chapter "The Spirit of Truth" for a history leading to, and a discussion of, his proof.
• Börger, Egon (1989). Computability, complexity, logic. Amsterdam: North-Holland. ISBN 008088704X.
• Abdulla, Parosh Aziz; Jonsson, Bengt (1996). "Verifying Programs with Unreliable Channels". Information and Computation. 127 (2): 91–101. doi:10.1006/inco.1996.0053.
• Collected works of A.M. Turing
  • Good, Irving John, ed. (1992). Pure Mathematics (in English). North-Holland. ISBN 978-0-444-88059-8.
  • Gandy, R. O.; Yates, C. E. M., eds. (5 December 2001). Mathematical Logic (in English). Elsevier. ISBN 978-0-08-053592-0.
  • Ince, D.C., ed. (1992). Mechanical Intelligence (in English). North-Holland. ISBN 978-0-444-88058-1.
  • Saunders, P. T., ed. (26 November 1992). Morphogenesis (in English). Elsevier. ISBN 978-0-08-093405-1.

अग्रिम पठन

• c2:HaltingProblem
• Alfred North Whitehead and Bertrand Russell, Principia Mathematica to *56, Cambridge at the University Press, 1962. Re: the problem of paradoxes, the authors discuss the problem of a set not be an object in any of its "determining functions", in particular "Introduction, Chap. 1 p. 24 "...difficulties which arise in formal logic", and Chap. 2.I. "The Vicious-Circle Principle" p. 37ff, and Chap. 2.VIII. "The Contradictions" p. 60ff.
• Martin Davis, "What is a computation", in Mathematics Today, Lynn Arthur Steen, Vintage Books (Random House), 1980. A wonderful little paper, perhaps the best ever written about Turing Machines for the non-specialist. Davis reduces the Turing Machine to a far-simpler model based on Post's model of a computation. Discusses Chaitin proof. Includes little biographies of Emil Post, Julia Robinson.
• Edward Beltrami, What is Random? Chance and order in mathematics and life, Copernicus: Springer-Verlag, New York, 1999. Nice, gentle read for the mathematically inclined non-specialist, puts tougher stuff at the end. Has a Turing-machine model in it. Discusses the Chaitin contributions.
• Ernest Nagel and James R. Newman, Godel’s Proof, New York University Press, 1958. Wonderful writing about a very difficult subject. For the mathematically inclined non-specialist. Discusses Gentzen's proof on pages 96–97 and footnotes. Appendices discuss the Peano Axioms briefly, gently introduce readers to formal logic.
• Daras, Nicholas J.; Rassias, Themistocles M. (2018). Modern discrete mathematics and analysis: with applications in cryptography, information systems and modeling. Cham, Switzerland. ISBN 978-3319743240.{{cite book}}: CS1 maint: location missing publisher (link). Chapter 3 Section 1 contains a quality description of the halting problem, a proof by contradiction, and a helpful graphic representation of the Halting Problem.
• Taylor Booth, Sequential Machines and Automata Theory, Wiley, New York, 1967. Cf. Chapter 9, Turing Machines. Difficult book, meant for electrical engineers and technical specialists. Discusses recursion, partial-recursion with reference to Turing Machines, halting problem. Has a Turing Machine model in it. References at end of Chapter 9 catch most of the older books (i.e. 1952 until 1967 including authors Martin Davis, F. C. Hennie, H. Hermes, S. C. Kleene, M. Minsky, T. Rado) and various technical papers. See note under Busy-Beaver Programs.
• Busy Beaver Programs are described in Scientific American, August 1984, also March 1985 p. 23. A reference in Booth attributes them to Rado, T.(1962), On non-computable functions, Bell Systems Tech. J. 41. Booth also defines Rado's Busy Beaver Problem in problems 3, 4, 5, 6 of Chapter 9, p. 396.
• David Bolter, Turing’s Man: Western Culture in the Computer Age, The University of North Carolina Press, Chapel Hill, 1984. For the general reader. May be dated. Has yet another (very simple) Turing Machine model in it.
• Sven Köhler, Christian Schindelhauer, Martin Ziegler, On approximating real-world halting problems, pp.454-466 (2005) ISBN 3540281932 Springer Lecture Notes in Computer Science volume 3623: Undecidability of the Halting Problem means that not all instances can be answered correctly; but maybe "some", "many" or "most" can? On the one hand the constant answer "yes" will be correct infinitely often, and wrong also infinitely often. To make the question reasonable, consider the density of the instances that can be solved. This turns out to depend significantly on the Programming System under consideration.
• Logical Limitations to Machine Ethics, with Consequences to Lethal Autonomous Weapons - paper discussed in: Does the Halting Problem Mean No Moral Robots?

बाहरी संबंध

• Scooping the loop snooper - a poetic proof of undecidability of the halting problem
• animated movie - an animation explaining the proof of the undecidability of the halting problem
• A 2-Minute Proof of the 2nd-Most Important Theorem of the 2nd Millennium - a proof in only 13 lines