हॉल्टिंग प्रॉब्लम

इस लेख में सुधार किया जा रहा है। इसकी भाषा को सरल बना दी जाएगा, और सन्दर्भ भी जोड़ दिए जाएंगे। थोड़ा समय दीजिए।

सैद्धांतिक कंप्यूटर विज्ञान में हॉल्टिंग प्रॉब्लम (अंग्रेज़ी: Halting problem) इस निर्णय प्रॉब्लम को कहते हैं कि क्या दिया गया कंप्यूटर प्रोग्राम दिए गए इनपुट के लिए कोई उत्तर देगा या हमेशा चलता ही रहेगा।

हर कंप्यूटर प्रोग्राम एक इनपुट या निर्देश लेता है और एक आउटपुट देता है। पर, कुछ कंप्यूटर प्रोग्रम कोई ख़ास इनपुट मिलने पर आउटपुट की खोज करते रह जाते हैं, और कभी आउटपुट दे ही नहीं पाते हैं (कभी हॉल्ट (समाप्त) नहीं हो पाते हैं)। ऐसे कंप्यूटर प्रोग्राम ये ख़ास इनपुट मिलने पर कंप्यूटर को हैंग कर देते हैं। इसलिए इनकी पहचान करना बहुत जरुरी होता है, ताकि इन्हें ठुकराया जा सके। इन न रूकने वाले या ना हॉल्ट करने वाले कंप्यूटर प्रोग्रामों की पहचान करने की प्रॉब्लम को हॉल्टिंग प्रॉब्लम कहते हैं।

हॉल्टिंग प्रॉब्लम की औपचारिक परिभाषा यह है: "ऐसा कंप्यूटर प्रोग्राम P बनाइए जो दो इनपुट लेता हो, पहला इनपुट एक कंप्यूटर प्रोग्राम Q और दूसरा Q का कोई इनपुट i; और P बताता हो कि क्या कंप्यूटर प्रोग्राम Q इनपुट i मिलने पर हॉल्ट होता है या नहीं"।

एलेन ट्यूरिंग ने 1936 में ये साबित किया था कि हाल्टिंग प्रॉब्लम एक अनिर्णनीय प्रॉब्लम है। इसका मतलब है कि ऐसा कंप्यूटर प्रोग्राम बनाना असंभव है जो हर एक कंप्यूटर प्रोग्राम Q और इनपुट i पर सही से बताता हो कि क्या कंप्यूटर प्रोग्राम Q इनपुट i मिलने पर हॉल्ट होता है या नहीं।