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

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

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

पृष्ठभूमि

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

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

while (true) continue

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

print "Hello, world!"

रुकता है।

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

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

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

दूसरी बार ये प्रोग्रामर कम से कम शक्ति के नियम को लागू करते हैं - वे जानबूझकर एक कंप्यूटर भाषा का उपयोग करते हैं जो पूरी तरह से ट्यूरिंग-पूर्ण नहीं है। अक्सर, ये ऐसी भाषाएँ होती हैं जो सभी सबरूटीन्स के खत्म होने की गारंटी देती हैं, जैसे Coq।

सामान्य नुकसान

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

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

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

...any finite-state machine, if left completely to itself, will fall eventually into a perfectly periodic repetitive pattern. The duration of this repeating pattern cannot exceed the number of internal states of the machine...

हालाँकि, एक कंप्यूटर जिसमें एक लाख छोटे हिस्से होते हैं, जिनमें से प्रत्येक में दो राज्य होते हैं, कम से कम 2 होते हैं^1,000,000 संभावित अवस्थाएँ:

This is a 1 followed by about three hundred thousand zeroes ... Even if such a machine were to operate at the frequencies of cosmic rays, the aeons of galactic evolution would be as nothing compared to the time of a journey through such a cycle:

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

...the magnitudes involved should lead one to suspect that theorems and arguments based chiefly on the mere finiteness [of] the state diagram may not carry a great deal of significance.

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

इतिहास

Further information: Algorithm § History: Development of the notion of "algorithm"

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

समयरेखा

• 1900 (1900): David Hilbert poses his "23 questions" (now known as Hilbert's problems) at the Second International Congress of Mathematicians in Paris. "Of these, the second was that of proving the consistency of the 'Peano axioms' on which, as he had shown, the rigour of mathematics depended".
• 1920 (1920) – 1921 (1921): Emil Post explores the halting problem for tag systems, regarding it as a candidate for unsolvability. Its unsolvability was not established until much later, by Marvin Minsky.
• 1928 (1928): Hilbert recasts his 'Second Problem' at the Bologna International Congress. He posed three questions: i.e. #1: Was mathematics complete? #2: Was mathematics consistent? #3: Was mathematics decidable? The third question is known as the Entscheidungsproblem (Decision Problem).
• 1930 (1930): Kurt Gödel announces a proof as an answer to the first two of Hilbert's 1928 questions. "At first he [Hilbert] was only angry and frustrated, but then he began to try to deal constructively with the problem... Gödel himself felt—and expressed the thought in his paper—that his work did not contradict Hilbert's formalistic point of view"
• 1931 (1931): Gödel publishes "On Formally Undecidable Propositions of Principia Mathematica and Related Systems I"
• 19 April 1935 (1935-04-19): Alonzo Church publishes "An Unsolvable Problem of Elementary Number Theory", which proposes that the intuitive notion of an effectively calculable function can be formalized by the general recursive functions or equivalently by the lambda-definable functions. He proves that the halting problem for lambda calculus (i.e., whether a given lambda-expression has a normal form) is not effectively calculable.
• 1936 (1936): Church publishes the first proof that the Entscheidungsproblem is unsolvable, using a notion of calculation by recursive functions.
• 7 October 1936 (1936-10-07): Emil Post's paper "Finite Combinatory Processes. Formulation I" is received. Post adds to his "process" an instruction "(C) Stop". He called such a process "type 1 ... if the process it determines terminates for each specific problem."
• May 1936 (1936-05) – January 1937 (1937-01): Alan Turing's paper On Computable Numbers With an Application to the Entscheidungsproblem goes to press in May 1936 and reaches print in January 1937. Turing proves three problems undecidable: the "satisfaction" problem, the "printing" problem, and the Entscheidungsproblem. Turing's proof differs from Church's by introducing the notion of computation by machine. This is one of the "first examples of decision problems proved unsolvable".
• 1939 (1939): J. Barkley Rosser observes the essential equivalence of "effective method" defined by Gödel, Church, and Turing
• 1943 (1943): In a paper, Stephen Kleene states that "In setting up a complete algorithmic theory, what we do is describe a procedure ... which procedure necessarily terminates and in such manner that from the outcome we can read a definite answer, 'Yes' or 'No,' to the question, 'Is the predicate value true?'."
• 1952 (1952): Kleene includes a discussion of the unsolvability of the halting problem for Turing machines and reformulates it in terms of machines that "eventually stop", i.e. halt: "... there is no algorithm for deciding whether any given machine, when started from any given situation, eventually stops."
• 1952 (1952): Martin Davis uses the term 'halting problem' in a series of lectures at the Control Systems Laboratory at the University of Illinois in 1952. It is likely that this is the first such use of the term.

रुकने की समस्या की उत्पत्ति

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

"[...] we wish to determine whether or not [a Turing machine] Z, if placed in a given initial state, will eventually halt. We call this problem the halting problem for Z. [...]

Theorem 2.2 There exists a Turing machine whose halting problem is recursively unsolvable.

A related problem is the printing problem for a simple Turing machine Z with respect to a symbol S_i".

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

there is no algorithm for deciding whether any given machine, when started from any given situation, eventually stops.

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

It might also be mentioned that the unsolvability of essentially these problems was first obtained by Turing.

औपचारिकता

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

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

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

Main article: Decision problem

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

के = {(i, x) | इनपुट एक्स पर चलाए जाने पर कार्यक्रम मैं रुक जाता हूं}

रुकने की समस्या का प्रतिनिधित्व करता है।

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

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

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

सबूत अवधारणा

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

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

हाल्ट (जी) को या तो सही या गलत वापस आना चाहिए, क्योंकि हॉल्ट को कुल कार्य माना जाता था। यदि हाल्ट(जी) सही रिटर्न देता है, तो जी लूप_फॉरएवर को कॉल करेगा और कभी नहीं रुकेगा, जो एक विरोधाभास है। यदि हाल्ट (जी) गलत रिटर्न देता है, तो जी रुक जाएगा, क्योंकि यह लूप_फॉरएवर को कॉल नहीं करेगा; यह भी एक विरोधाभास है। कुल मिलाकर, 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

Possible values for a total computable function f arranged in a 2D array. The orange cells are the diagonal. The values of f(i,i) and g(i) are shown at the bottom; U indicates that the function g is undefined for a particular input value.

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

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

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

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

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

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

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

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

• एफ (ई, ई) = 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: Computability theory

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

राइस की प्रमेय इस प्रमेय का सामान्यीकरण करती है कि रुकने की समस्या का समाधान नहीं किया जा सकता है। यह बताता है कि किसी भी गैर-तुच्छ संपत्ति के लिए, कोई सामान्य निर्णय प्रक्रिया नहीं है, जो सभी कार्यक्रमों के लिए, यह तय करती है कि इनपुट प्रोग्राम द्वारा कार्यान्वित आंशिक कार्य में वह संपत्ति है या नहीं। (एक आंशिक कार्य एक ऐसा कार्य है जो हमेशा एक परिणाम नहीं दे सकता है, और इसलिए इसका उपयोग मॉडल प्रोग्राम के लिए किया जाता है, जो या तो परिणाम उत्पन्न कर सकता है या रुकने में विफल हो सकता है।) उदाहरण के लिए, इनपुट 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: Turing jump

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

यह भी देखें

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

संदर्भ

• 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