ट्यूरिंग कंप्यूटिंग मशीनें

मैं आपके ध्यान में 1936 से एलन ट्यूरिंग के लेख “ऑन कंप्यूटेबल नंबर्स विद एन एप्लीकेशन टू द प्रॉब्लम ऑफ रिजॉल्यूशन” के पहले पन्नों का अनुवाद प्रस्तुत करता हूं। पहले अध्याय में कंप्यूटर का विवरण है, जो बाद में आधुनिक कंप्यूटिंग का आधार बन गया।

लेख और स्पष्टीकरण का पूरा अनुवाद अमेरिकी लोकप्रिय चार्ल्स पेटज़ोल्ड की पुस्तक में पढ़ा जा सकता है, जिसका शीर्षक है “रीडिंग ट्यूरिंग: ए जर्नी थ्रू ट्यूरिंग हिस्टोरिकल आर्टिकल ऑन कम्प्यूटेबिलिटी एंड ट्यूरिंग मशीन्स” (आईएसबीएन 978-5-97060-231-7, 978-0-470-22905-7)

मूल लेख:
https://www.astro.puc.cl/~rparra/tools/PAPERS/turing_1936.pdf

समाधान समस्या के अनुप्रयोग के साथ गणनीय संख्याओं पर

ए. एम. ट्यूरिंग

[28 मई 1936 को प्राप्त – 12 नवंबर 1936 को पढ़ें]

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

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

यद्यपि गणना योग्य संख्याओं का वर्ग बहुत बड़ा है और कई मामलों में वास्तविक संख्याओं के वर्ग के समान है, फिर भी यह गणना योग्य है। §8 में मैं कुछ ऐसे तर्कों पर विचार करता हूं जो इसके विपरीत तर्क देते प्रतीत होंगे। जब इनमें से किसी एक तर्क को सही ढंग से लागू किया जाता है, तो ऐसे निष्कर्ष निकाले जाते हैं जो पहली नज़र में गोडेल* के समान होते हैं। इन परिणामों का अत्यंत महत्वपूर्ण अनुप्रयोग है। विशेष रूप से, जैसा कि नीचे दिखाया गया है (§11), समाधान समस्या का कोई समाधान नहीं हो सकता।

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

1. कंप्यूटर

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

आइए वास्तविक संख्या की गणना करने की प्रक्रिया में एक व्यक्ति की तुलना एक ऐसी मशीन से करें जो केवल सीमित संख्या में शर्तों q1, q2, …, qR को पूरा करने में सक्षम है; आइए इन स्थितियों को “एम-कॉन्फिगरेशन” कहें। यह (अर्थात, इस प्रकार परिभाषित) मशीन एक “टेप” (कागज के अनुरूप) से सुसज्जित है। मशीन से गुजरने वाली यह बेल्ट खंडों में विभाजित है। आइए उन्हें “वर्ग” कहें। ऐसे प्रत्येक वर्ग में किसी न किसी प्रकार का “प्रतीक” हो सकता है। किसी भी क्षण, केवल एक ही ऐसा वर्ग होता है, मान लीजिए कि वां, जिसमें वह प्रतीक होता है जो “इस मशीन में है।” आइए ऐसे वर्ग को “स्कैन किया हुआ प्रतीक” कहें। एक “स्कैन किया हुआ पात्र” एकमात्र ऐसा पात्र है जिसके बारे में मशीन को, ऐसा कहा जा सकता है, “सीधे पता” होता है। हालाँकि, अपने एम-कॉन्फ़िगरेशन को बदलकर, मशीन उन कुछ पात्रों को प्रभावी ढंग से याद रख सकती है जिन्हें उसने पहले “देखा” (स्कैन किया है)। किसी भी क्षण मशीन का संभावित व्यवहार एम-कॉन्फ़िगरेशन क्यूएन और स्कैन किए गए प्रतीक*** द्वारा निर्धारित किया जाता है। आइए प्रतीकों की इस जोड़ी को qn, “कॉन्फ़िगरेशन” कहते हैं। इस प्रकार निर्दिष्ट कॉन्फ़िगरेशन किसी दी गई मशीन के संभावित व्यवहार को निर्धारित करता है। इनमें से कुछ कॉन्फ़िगरेशन में, जिनमें स्कैन किया गया वर्ग खाली है (यानी, कोई वर्ण नहीं है), मशीन स्कैन किए गए वर्ग पर एक नया वर्ण लिखती है, और इनमें से अन्य कॉन्फ़िगरेशन में यह स्कैन किए गए वर्ण को मिटा देती है। यह मशीन दूसरे वर्ग को स्कैन करने के लिए भी जाने में सक्षम है, लेकिन इस तरह यह केवल दाएं या बाएं बगल वाले वर्ग तक ही जा सकती है। इनमें से किसी भी ऑपरेशन के अलावा, मशीन का एम-कॉन्फ़िगरेशन बदला जा सकता है। इस मामले में, कुछ लिखित वर्ण अंकों का एक क्रम बनाएंगे, जो गणना की जा रही वास्तविक संख्या का दशमलव भाग है। उनमें से बाकी “स्मृति की सहायता” के लिए गलत चिह्नों से अधिक कुछ नहीं होंगे। इस स्थिति में, केवल उपर्युक्त गलत चिह्नों को ही मिटाया जा सकता है।

मेरा दावा है कि यहां जिन ऑपरेशनों पर विचार किया गया है उनमें वे सभी ऑपरेशन शामिल हैं जिनका उपयोग गणना में किया जाता है। मशीन सिद्धांत की समझ रखने वाले पाठक के लिए इस कथन का तर्क समझना आसान है। इसलिए, अगले भाग में मैं “मशीन”, “टेप”, “स्कैन” आदि शब्दों के अर्थ की समझ के आधार पर संबंधित सिद्धांत को विकसित करना जारी रखूंगा।

*गोडेल “प्रिंसिपिया गणित के औपचारिक रूप से अनिर्णीत वाक्यों पर (व्हाइटहेड और रसेल द्वारा 1910, 1912 और 1913 में प्रकाशित) और संबंधित सिस्टम, भाग I,” गणित का जर्नल। भौतिकी, जर्मन में मासिक बुलेटिन संख्या 38 (1931 के लिए, पृ. 173-198)।
** अलोंजो चर्च, “प्राथमिक संख्या सिद्धांत में एक अनिर्णीत समस्या,” गणित के अमेरिकी जे., नंबर 58 (1936), पीपी. 345-363।
*** अलोंजो चर्च, “रिज़ॉल्यूशन की समस्या पर एक नोट,” सिम्बोलिक लॉजिक के जे., नंबर 1 (1936), पीपी. 40-41