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

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

समस्या के औपचारिक विवरण का महत्वपूर्ण भाग कंप्यूटर और प्रोग्राम की गणितीय परिभाषा है, सामान्यतः ट्यूरिंग मशीन के माध्यम से प्रमाण तब दिखाता है, किसी भी प्रोग्राम 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 के हाल्ट के अनुरूप होता है। इसलिए, प्रारंभिक धारणा है कि हॉल्ट कुल संगणनीय फंक्शन अनुचित होना चाहिए।

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

उपरोक्त अवधारणा प्रमाण की सामान्य विधि को दर्शाती है, किंतु संगणनीय फंक्शन हाल्ट आर्गुमेंट के रूप में सबरूटीन नहीं लेता है; इसके अतिरिक्त यह प्रोग्राम का सोर्स कोड लेता है। इसके अतिरिक्त, 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 की परिभाषा से अनुसरण करता है कि वास्तव में निम्नलिखित दो स्तिथियों में से एक होनी चाहिए:

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

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

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

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

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

किसी समस्या P को अनिर्णीत सिद्ध करने की विशिष्ट विधि हॉल्टिंग समस्या को P तक कम (जटिलता) करना है।

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

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

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

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

सन्निकटन

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

हॉल्टिंग समस्या ह्यूरिस्टिक्स के सैद्धांतिक प्रदर्शन पर कुछ परिणाम स्थापित किए गए हैं, विशेष रूप से किसी दिए गए आकार के प्रोग्रामों के अंश जिन्हें रिकर्सिव एल्गोरिथम द्वारा उचित रूप से वर्गीकृत किया जा सकता है। ये परिणाम त्रुटिहीन संख्या नहीं देते हैं क्योंकि अंश अगणनीय हैं और आकार निर्धारित करने के लिए उपयोग किए जाने वाले प्रोग्राम एन्कोडिंग के चयन पर अत्यधिक निर्भर हैं। उदाहरण के लिए, प्रोग्रामों को उनकी स्थितियों की संख्या के आधार पर वर्गीकृत करने पर विचार करें और गणना के विशिष्ट ट्यूरिंग सेमी-अनंत टेप मॉडल का उपयोग करें कि यदि प्रोग्राम टेप के बाईं ओर रन करता है तो त्रुटियाँ होती हैं। तब $\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$ है। यह स्थिति सुनिश्चित करती है कि सभी प्रोग्रामों के सूचकांक किसी भी अन्य गोडेल क्रमांकन में उनके सूचकांकों की तुलना में अधिक बड़े नहीं हैं। यूनिवर्सल ट्यूरिंग मशीन के इनपुट को संख्या देकर इष्टतम गोडेल क्रमांकन का निर्माण किया जाता है। आकार की तृतीय धारणा बाइनरी स्ट्रिंग्स पर संचालित होने वाली यूनिवर्सल मशीनों का उपयोग करती है और इनपुट प्रोग्राम का वर्णन करने के लिए आवश्यक स्ट्रिंग की लंबाई को मापती है। यूनिवर्सल मशीन U ऐसी मशीन है जिसके लिए प्रत्येक दूसरी मशीन V में कुल संगणनीय फ़ंक्शन h उपस्तिथ है जैसे कि $V(x)=U(h(x))$, इष्टतम मशीन यूनिवर्सल मशीन है जो कोल्मोगोरोव जटिलता को प्राप्त करती है, अर्थात प्रत्येक मशीन V के लिए c उपस्थित है जैसे कि सभी आउटपुट x के लिए, यदि लंबाई n आउटपुट x का V-प्रोग्राम है, तो अधिकतम लंबाई $n+c$ आउटपुट x का U-प्रोग्राम उपस्थित है।

हम आंशिक संगणनीय फ़ंक्शन (एल्गोरिदम) $A$ पर विचार करते हैं। प्रत्येक $n$ के लिए हम आकार मीट्रिक के सभी प्रोग्रामों के मध्य त्रुटियों के अंश $\epsilon _{n}(A)$ पर विचार करते हैं, प्रत्येक प्रोग्राम 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$ है, किंतु ब्लॉक के मध्य उचित रूप से वर्गीकृत दोहराव का अंश आर्बिट्ररी रूप से अधिक हो सकता है। विशेष रूप से टैली ह्यूरिस्टिक जो केवल प्रथम N इनपुट को याद करता है और उनके समकक्षों को पहचानता है, आर्बिट्ररी रूप से कम त्रुटि दर तक पहुंचने की अनुमति देता है।

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

{{#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