ट्यूरिंग मशीनें समझाई गईं

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

1 और खाली सेलों वाला एक टेप, जिसके एक सेल के ऊपर पढ़ने-लिखने वाला हेड है और उस पर उसकी अवस्था लिखी है
1 और खाली सेलों वाला एक टेप, जिसके एक सेल के ऊपर पढ़ने-लिखने वाला हेड है और उस पर उसकी अवस्था लिखी है

ट्यूरिंग का प्रश्न

1928 में डेविड हिल्बर्ट ने पूछा कि क्या कोई ऐसी यांत्रिक प्रक्रिया है जो गणित के हर कथन के लिए तय कर दे कि उसे सिद्ध किया जा सकता है या नहीं: यही Entscheidungsproblem है। इसका उत्तर देने के लिए किसी को ठीक-ठीक बताना था कि यांत्रिक प्रक्रिया क्या होती है। 1936 के अपने शोधपत्र On Computable Numbers में ट्यूरिंग ने पेंसिल और काग़ज़ से काम करते एक क्लर्क की कल्पना की, और उसके काम को सबसे छोटे कदमों तक घटा दिया: एक प्रतीक को देखो, उसे बदलो, बगल वाले प्रतीक पर जाओ, और थोड़ा-सा याद रखो कि तुम क्या कर रहे थे। परिणाम था ट्यूरिंग मशीन।

एक बॉम्बे मशीन (बाएँ) और एलन ट्यूरिंग का चित्र (दाएँ)
एक बॉम्बे मशीन (बाएँ) और एलन ट्यूरिंग का चित्र (दाएँ)

मशीन

ट्यूरिंग मशीन में सेलों में बँटा एक टेप होता है, जो दोनों दिशाओं में अंतहीन है, और हर सेल में एक प्रतीक होता है, आमतौर पर खाली। एक हेड किसी एक सेल पर होता है और मशीन सीमित संख्या की अवस्थाओं में से किसी एक में होती है। नियमों की एक तालिका हर अवस्था और हेड द्वारा पढ़े जा सकने वाले हर प्रतीक के लिए बताती है कि कौन-सा प्रतीक लिखना है, किस दिशा में चलना है और अगली अवस्था क्या है। मशीन हर कदम पर एक नियम लागू करती है। जब वह किसी रुकने वाली अवस्था में प्रवेश करती है तो रुक जाती है, और टेप पर जो कुछ बचता है वही उसका उत्तर है।

नियम-तालिकाओं के रूप में प्रोग्राम

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

सार्वभौमिक मशीन

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

चर्च–ट्यूरिंग थीसिस

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

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

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

बिज़ी बीवर

1962 में तिबोर रादो ने हॉल्टिंग समस्या को एक खेल में बदल दिया: n अवस्थाओं और प्रतीकों 0 और 1 वाली उन सभी मशीनों में से, जो खाली टेप पर शुरू करने पर रुक जाती हैं, कौन-सी सबसे ज़्यादा 1 लिखती है, और ऐसी मशीन कितने कदम चल सकती है? ये संख्याएँ, यानी बिज़ी बीवर मान, किसी भी संगणनीय फ़ंक्शन से तेज़ बढ़ती हैं, क्योंकि उनकी गणना करने का कोई तरीका हॉल्टिंग समस्या को हल कर देता। ज्ञात मान दो, तीन और चार अवस्थाओं के लिए 6, 21 और 107 कदम हैं; पाँच अवस्थाओं के लिए हाइनर मार्क्सन और युर्गन बुंट्रॉक का चैंपियन 4,71,76,870 कदम चलता है, एक मान जिसे 2024 में ऑनलाइन bbchallenge सहयोग ने कंप्यूटर से जाँचे गए प्रमाण के साथ सिद्ध किया। छह अवस्थाओं के लिए ऐसी मशीनें ज्ञात हैं जो इतने कदम चलती हैं जितने सामान्य संकेतन में लिखे भी नहीं जा सकते।

इसे आज़माएँ

आठ तैयार प्रोग्राम चलाने या अपना प्रोग्राम लिखने के लिए ट्यूरिंग मशीन सिम्युलेटर खोलें। हेड को कदम-दर-कदम देखें और जानें कि कौन-सा नियम लागू होता है, कभी न रुकने वाले काउंटर को देखें, पैलिंड्रोम जाँचें, और बिज़ी बीवर चलाएँ: चार अवस्थाओं वाले चैंपियन के 107 कदम आरेख में समा जाते हैं, और पाँच अवस्थाओं वाले चैंपियन के 4.7 करोड़ कदम सबसे तेज़ गति पर कुछ ही सेकंड लेते हैं।

अक्सर पूछे जाने वाले प्रश्न

क्या ट्यूरिंग मशीन कभी बनाई गई?

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

तीन अवस्थाओं के लिए कदमों की संख्या 14 और 21 में क्या अंतर है?

बिज़ी बीवर के दो प्रश्न हैं: सबसे ज़्यादा 1 लिखना और सबसे ज़्यादा कदम चलना। तीन अवस्थाओं के लिए, सिम्युलेटर की मशीन 14 कदमों में अधिकतम छह 1 लिखती है, जबकि तीन अवस्थाओं वाली एक दूसरी मशीन अधिकतम 21 कदम चलती है लेकिन केवल पाँच 1 छोड़ती है। दो, चार और पाँच अवस्थाओं के लिए एक ही मशीन दोनों में जीतती है।

क्या ट्यूरिंग-पूर्ण का मतलब शक्तिशाली है?

इसका मतलब है पर्याप्त समय और मेमोरी मिलने पर हर संगणनीय चीज़ की गणना कर पाना, जो गति के बारे में कुछ नहीं कहता। ट्यूरिंग मशीन को सरल अंकगणित के लिए बहुत सारे कदम चाहिए, और कुछ प्रणालियाँ लगभग संयोग से ट्यूरिंग-पूर्ण हैं, जैसे ताश के खेल, स्प्रेडशीट फ़ॉर्मूले और Minecraft रेडस्टोन।

कंप्यूटर बस प्रोग्राम चलाकर क्यों नहीं देख सकता कि वह रुकता है या नहीं?

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

आज़माने के लिए तैयार?

अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।

ट्यूरिंग मशीन सिम्युलेटर खोलें