संगणनीयता (Computability): ट्यूरिंग मशीन और कंप्यूटर की सीमाएँ

संगणनीयता क्या है?

संगणनीयता (computability) पूछती है: असीमित समय और मेमोरी हो, तो कौन-सी समस्याएँ किसी एल्गोरिद्म से हल हो सकती हैं? यह जटिलता (complexity) से अलग है, जो पूछती है कि हल होने वाली समस्या कितनी जल्दी हल होती है।

जवाब के लिए एलन ट्यूरिंग (1936) ने एक बहुत सरल काल्पनिक मशीन सोची। अगर यह सरल मशीन वह सब कर सकती है जो कोई भी कंप्यूटर करता है, तो इसकी सीमाएँ सभी कंप्यूटरों की सीमाएँ हैं।

ट्यूरिंग मशीन के भाग: टेप, अवस्थाएँ, संक्रमण नियम

• टेप: कम से कम एक तरफ़ अनंत, खानों में बँटा। हर खाने में एक सीमित वर्णमाला (alphabet) का एक चिह्न (जैसे 0, 1 और ख़ाली _)।
• पढ़ने-लिखने वाला हेड: एक खाना देखता है, उसे बदल सकता है, फिर एक खाना बाएँ (L) या दाएँ (R) जाता है।
• सीमित अवस्थाएँ (states): एक शुरुआती अवस्था और एक या अधिक रुकने (halt) वाली अवस्थाएँ।
• संक्रमण फलन (नियम): δ(अभी की अवस्था, पढ़ा चिह्न) = (नई अवस्था, लिखा चिह्न, चाल)।

नियमों को अवस्था संक्रमण आरेख (अवस्थाओं के गोले, तीरों पर पढ़ा / लिखा, चाल) या तालिका में लिखते हैं। मेमोरी असीमित है, इसीलिए ट्यूरिंग मशीन फ़ाइनाइट स्टेट मशीन से ज़्यादा ताक़तवर है।

ट्यूरिंग मशीन को ट्रेस करना

मशीन "बाइनरी संख्या में 1 जोड़ो"। हेड सबसे दाएँ अंक पर, अवस्था carry में शुरू।

• δ(carry, 1) = (carry, 0, L): 1 + हासिल = 0, हासिल बाएँ।
• δ(carry, 0) = (HALT, 1, –): 0 + हासिल = 1, काम पूरा।
• δ(carry, _) = (HALT, 1, –): अंक ख़त्म, आगे नया 1 लिखो।

1011 का ट्रेस: 1011 → 1010 → 1000 → 1100, HALT। 11 + 1 = 12 ✓। परीक्षा में हर क़दम के बाद टेप और अवस्था लिखते हैं।

सार्वभौमिक ट्यूरिंग मशीन और चर्च-ट्यूरिंग थीसिस

सार्वभौमिक ट्यूरिंग मशीन (UTM) अपने टेप पर किसी दूसरी ट्यूरिंग मशीन M का कोड किया हुआ विवरण और M का इनपुट लेती है। फिर ठीक M की तरह काम करती है। यानी एक तय मशीन कोई भी प्रोग्राम चला सकती है जो उसे डेटा की तरह दिया जाए।

यही संग्रहित-प्रोग्राम (वॉन न्यूमैन) कंप्यूटर का विचार है: प्रोग्राम और डेटा एक ही मेमोरी में, और एक प्रोसेसर कोई भी प्रोग्राम चलाता है। इंटरप्रेटर और एमुलेटर भी इसी से समझ आते हैं।

चर्च-ट्यूरिंग थीसिस: जो कुछ भी किसी चरण-दर-चरण तरीक़े से गणना हो सकता है, वह ट्यूरिंग मशीन से हो सकता है। यह थीसिस है (व्यापक रूप से मान्य), प्रमाण नहीं।

असंगणनीय समस्याएँ: हॉल्टिंग समस्या

हॉल्टिंग समस्या: कोई भी प्रोग्राम और उसका इनपुट दिया हो, तो बताओ वह कभी रुकेगा या हमेशा चलता रहेगा।

ट्यूरिंग ने साबित किया कि हर प्रोग्राम के लिए यह कोई एल्गोरिद्म नहीं बता सकता। प्रमाण का विचार: मान लो HALTS(P, x) हमेशा सही बताता है। TROUBLE(P) बनाओ: अगर HALTS(P, P) कहे "रुकेगा", तो हमेशा लूप करो; वरना रुक जाओ। अब TROUBLE(TROUBLE) का क्या? अगर रुका, तो उसे लूप करना था; अगर लूप किया, तो उसे रुकना था। विरोधाभास, इसलिए HALTS हो ही नहीं सकता।

हाँ/ना वाली जिस समस्या का कोई एल्गोरिद्म हमेशा जवाब न दे सके, वह अनिर्णेय (undecidable) है। एक और उदाहरण: क्या दो प्रोग्राम हमेशा एक जैसा आउटपुट देते हैं। यानी कुछ समस्याएँ असंगणनीय हैं, कंप्यूटर कितने भी तेज़ हो जाएँ।

निर्णेय, सुसाध्य और दुःसाध्य

• निर्णेय / संगणनीय (decidable): एल्गोरिद्म हमेशा सीमित समय में सही जवाब देता है।
• सुसाध्य (tractable): निर्णेय और बहुपद समय में हल (जैसे सॉर्टिंग)।
• दुःसाध्य (intractable): निर्णेय, पर बहुत ज़्यादा (जैसे घातांकी) समय; हम अनुमानी (heuristic) तरीक़े लगाते हैं।
• अनिर्णेय (undecidable): कोई एल्गोरिद्म है ही नहीं (हॉल्टिंग समस्या)।

करके देखो: ख़ुद मशीन बनो

काग़ज़ पर खानों में 0111 लिखो। आख़िरी अंक के नीचे एक सिक्का रखो: यही हेड है। "1 जोड़ो" के तीन नियम मानो, सिक्का खिसकाओ और अंक बदलो। आख़िर में 1000 आना चाहिए। फिर अपनी नियम-तालिका बनाओ जो दाएँ चलते हुए हर बिट उलट दे (0 ↔ 1), और 3D के आख़िरी चरण में जाँचो।

मुख्य सूत्र और परिभाषाएँ

• ट्यूरिंग मशीन = टेप + पढ़ने-लिखने वाला हेड + सीमित अवस्थाएँ + संक्रमण नियम
• δ(अवस्था, पढ़ा चिह्न) = (नई अवस्था, लिखा चिह्न, चाल L/R)
• सार्वभौमिक TM: इनपुट = मशीन M का विवरण + M का इनपुट
• चर्च-ट्यूरिंग थीसिस: एल्गोरिद्म से गणनीय ⇔ ट्यूरिंग मशीन से गणनीय
• हॉल्टिंग समस्या: अनिर्णेय (सभी प्रोग्रामों के लिए कोई एल्गोरिद्म नहीं)

हल किए गए उदाहरण

आम गलतियाँ

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