यूनिवर्सल ट्यूरिंग मशीन: Difference between revisions

Latest revision as of 17:24, 15 February 2023

कंप्यूटर विज्ञान में, सार्वभौमिक ट्यूरिंग मशीन (यूटीएम) एक ऐसा यंत्र है जो मनमाना इनपुट पर एक मनमानी ट्यूरिंग यंत्र का अनुकरण करता है। सार्वभौमिक यंत्र अनिवार्य रूप से सिम्युलेटेड होने वाले यंत्र के विवरण और साथ ही यंत्र के टेप से इनपुट दोनों को पढ़कर प्राप्त करती है। एलन ट्यूरिंग ने 1936-1937 में इस यंत्र का विचार प्रस्तुत किया था। इस सिद्धांत को "इलेक्ट्रॉनिक कंप्यूटिंग इंस्ट्रूमेंट" के लिए 1946 में जॉन वॉन न्यूमैन द्वारा उपयोग किए जाने वाले एक संग्रहीत योजना कंप्यूटर के विचार का मूल माना जाता है, जो अब वॉन न्यूमैन वास्तुकला के नाम को धारण करता है।^[1]

कम्प्यूटेशनल जटिलता सिद्धांत के संदर्भ में, एक बहु-टेप सार्वभौमिक ट्यूरिंग यंत्र को केवल उन यंत्रों की तुलना में लॉगरिदमिक कारक द्वारा केवल उपरि (कंप्यूटिंग) की आवश्यकता होती है।^[2]

परिचय

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

"एक ऐसा यंत्र का आविष्कार करना संभव है जिसका उपयोग किसी भी गणना योग्य अनुक्रम की गणना करने के लिए किया जा सकता है। यदि यह यंत्र यू' एक टेप के साथ आपूर्ति की जाती है जिसकी शुरुआत में एसडी ["मानक विवरण" लिखा जाता है क्रिया तालिका] कुछ कंप्यूटिंग यंत्र एम की, तो यू एम के समान अनुक्रम की गणना करता है।"^[3]

संग्रहीत कार्यक्रम कंप्यूटर

मार्टिन डेविस (गणितज्ञ) एक प्रेरक तर्क देते है कि ट्यूरिंग की अवधारणा जिसे अब "संग्रहीत योजना कंप्यूटर" के रूप में जाने जाते है, "कार्य टेबल" रखने के लिए - यंत्र के लिए निर्देश - इनपुट डेटा के समान "मेमोरी" में, जॉन को दृढ़ता से प्रभावित करते है। पहले अमेरिकी असतत-प्रतीक (एनालॉग के विपरीत) कंप्यूटर- EDVAC की वॉन न्यूमैन की अवधारणा है। डेविस टाइम पत्रिका को इस आशय का उद्धरण देते है, कि "हर कोई जो एक कीबोर्ड पर टैप करता है ... एक ट्यूरिंग यंत्र के अवतार पर काम करता है", और यह कि "जॉन वॉन न्यूमैन एलन ट्यूरिंग के काम पर" (डेविस 2000: 193 29 मार्च 1999 की टाइम पत्रिका के हवाले है)।

डेविस एक स्थिति बनाते है कि ट्यूरिंग के स्वचालित कंप्यूटिंग इंजन (एसीई) कंप्यूटर ने माइक्रोयोजना (माइक्रोकोड) और आरआईएससी प्रोसेसर (डेविस 2000: 188) के विचारों को "प्रत्याशित" किया। डोनाल्ड नुथ एसीई कंप्यूटर पर ट्यूरिंग के काम को "सबरूटीन लिंकेज की सुविधा के लिए हार्डवेयर" के रूप में प्रारूप करने का हवाला दिया (नथ 1973: 225), डेविस इस काम को ट्यूरिंग द्वारा हार्डवेयर "स्टैक" के उपयोग के रूप में भी संदर्भित करते है (डेविस 2000: 237 फुटनोट 18)।

चूंकि ट्यूरिंग यंत्र कंप्यूटर के निर्माण को प्रोत्साहित करता था, यूटीएम नवाचारी कंप्यूटर विज्ञान के विकास को प्रोत्साहित करता था। EDVAC (डेविस 2000: 192) के लिए "एक युवा हॉट-शॉट योजना द्वारा" एक प्रारंभिक, असेंबलर प्रस्तावित किया गया था। वॉन न्यूमैन का "पहला गंभीर कार्यक्रम केवल डेटा को कुशलतापूर्वक क्रमबद्ध करता था" (डेविस 2000:184)। नुथ ने देखा कि विशेष रजिस्टरों के अतिरिक्त योजना में एम्बेडेड सबरूटीन रिटर्न वॉन न्यूमैन और गोल्डस्टाइन के लिए जिम्मेदार होते थे।^[4] नुथ आगे कहते है कि

पहली व्याख्यात्मक दिनचर्या को "यूनिवर्सल ट्यूरिंग यंत्र" कहा जा सकता है ... पारंपरिक अर्थों में व्याख्यात्मक दिनचर्या का उल्लेख जॉन मौचली ने मूर] में अपने व्याख्यान में किया था। स्कूल 1946 में ... ट्यूरिंग ने इस विकास में भी भाग लिया; पायलट एसीई कंप्यूटर के लिए व्याख्यात्मक प्रणाली उनके निर्देशन में लिखी गई थी।
— नुथ 1973:226

डेविस संक्षेप में डेटा के रूप में योजना की धारणा के परिणामों के रूप में परिचालन प्रणाली और संकलनकर्ता का उल्लेख करते है (डेविस 2000:185)।

चूँकि, कुछ लोग इस आकलन के साथ समस्याएँ उठा सकते है। उस समय (1940 के दशक के मध्य से 1950 के दशक के मध्य तक) शोधकर्ताओं का एक अपेक्षाकृत छोटा कैडर नए "डिजिटल कंप्यूटर" की वास्तुकला के साथ घनिष्ठ रूप से जुड़ा हुआ था। हाओ वांग (1954), इस समय के एक युवा शोधकर्ता ने निम्नलिखित अवलोकन किया:

कम्प्यूटेशनल कार्यों के ट्यूरिंग के सिद्धांत को पुराना लेकिन डिजिटल कंप्यूटरों के व्यापक वास्तविक निर्माण को ज्यादा प्रभावित नहीं किया था। सिद्धांत और व्यवहार के इन दो पहलुओं को लगभग पूरी तरह से एक दूसरे से स्वतंत्र रूप से विकसित किया जाता था। मुख्य कारण निस्संदेह यह है कि तर्कशास्त्री उन प्रश्नों में रुचि रखते थे जो लागू गणितज्ञों और विद्युत इंजीनियरों से प्राथमिक रूप से संबंधित होते थे। चूँकि, यह किसी को भी अजीब लगने में विफल नहीं हो सकते थे कि अक्सर एक ही अवधारणा को दो विकासों में बहुत भिन्न शब्दों द्वारा व्यक्त किया गया था।
— वैंग 1954, 1957:63

वांग ने आशा व्यक्त की कि उनका पेपर "दो दृष्टिकोणों को जोड़ देगा"। वास्तव में, मिंस्की ने इसकी पुष्टि की: "कंप्यूटर जैसे मॉडल में ट्यूरिंग-यंत्र सिद्धांत का पहला सूत्रीकरण वैंग (1957) में दिखाई देता है" (मिन्स्की 1967: 200)। मिंस्की एक काउंटर यंत्र के ट्यूरिंग तुल्यता को प्रदर्शित करने के लिए आगे बढ़ाते है।

कंप्यूटर को सरल ट्यूरिंग समकक्ष मॉडल की कमी के संबंध में, मिन्स्की का वांग का पदनाम "पहला फॉर्मूलेशन" बहस के लिए खुला था। जबकि 1961 के मिन्स्की के पेपर और 1957 के वांग के पेपर को शेफर्डसन और स्टर्गिस (1963) द्वारा उद्धृत किया गया था, वे यूरोपीय गणितज्ञों केफेंस्ट (1959), एर्शोव (1959) और पेटर (1958) के काम का भी कुछ विस्तार से हवाला देते थे और संक्षेप में बताते थे। गणितज्ञ हेमीज़ (1954, 1955, 1961) और काफेन्स्ट (1959) के नाम शेपर्डसन-स्टर्गिस (1963) और एलगॉट-रॉबिन्सन (1961) दोनों की ग्रंथ सूची में दिखाई देते थे। महत्व के दो अन्य नाम कनाडाई शोधकर्ता मेल्ज़क (1961) और लैम्बेक (1961) है और अधिक के लिए ट्यूरिंग यंत्र समकक्ष देखें, संदर्भ रजिस्टर यंत्र पर पाए जा सकते है।

गणितीय सिद्धांत

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

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

सार्वभौमिक ट्यूरिंग यंत्र का एक सार संस्करण सार्वभौमिक कार्य होता है, एक कंप्यूटेबल कार्य जिसका उपयोग किसी अन्य कंप्यूटेशनल कार्य की गणना के लिए किया जा सकता है। यूटीएम प्रमेय ऐसे फलन के अस्तित्व को सिद्ध करता है।

दक्षता

व्यापकता के नुकसान के बिना, ट्यूरिंग यंत्र का इनपुट वर्णमाला {0, 1} में माना जा सकता है, किसी भी अन्य परिमित वर्णमाला को {0, 1} पर एन्कोड किया जा सकता है। एक ट्यूरिंग यंत्र एम का व्यवहार उसके संक्रमण समारोह द्वारा निर्धारित किया जाता है। इस कार्य को अक्षर {0, 1} पर स्ट्रिंग के रूप में भी आसानी से एन्कोड किया जा सकता है। एम के वर्णमाला का आकार, इसमें टेप की संख्या, और राज्य स्थान का आकार संक्रमण कार्य की तालिका से घटाया जा सकता है। विशिष्ट राज्यों और प्रतीकों को उनकी स्थिति से पहचाना जा सकता है। कन्वेंशन द्वारा पहले दो राज्य स्टार्ट और स्टॉप स्टेट हो सकते है। परिणाम स्वरुप, प्रत्येक ट्यूरिंग यंत्र को वर्णमाला {0, 1} पर स्ट्रिंग के रूप में एन्कोड किया जा सकता है। इसके अतिरिक्त, हम यह कहते है कि प्रत्येक अमान्य एन्कोडिंग मानचित्र एक तुच्छ ट्यूरिंग यंत्र के लिए है जो तुरंत रुक जाती है, और यह कि प्रत्येक ट्यूरिंग यंत्र में एन्कोडिंग की एक अनंत संख्या हो सकती है, जैसे कि टिप्पणियों की तरह अंत में (कहते है) 1 की मनमानी संख्या के साथ एन्कोडिंग एक योजना भाषा में काम करता है। इसमें कोई आश्चर्य नहीं होना चाहिए कि गोडेल संख्या के अस्तित्व और ट्यूरिंग यंत्रों और μ-पुनरावर्ती कार्यों के बीच कम्प्यूटेशनल समानता को देखते हुए हम इस एन्कोडिंग को प्राप्त कर सकते है। इसी तरह, हमारा निर्माण प्रत्येक बाइनरी स्ट्रिंग α, एक ट्यूरिंग यंत्र M_α से जुड़ता है।

उपरोक्त एन्कोडिंग से प्रारंभ करते हुए, 1966 में एफ.सी. हेनी और रिचर्ड ई. स्टर्न्स ने दिखाया कि एक ट्यूरिंग यंत्र एम_α जो N चरणों के भीतर इनपुट x पर रुकता है, तो एक बहु-टेप सार्वभौमिक ट्यूरिंग यंत्र उपस्तिथ होता है जो CN लॉग N में इनपुट α, x पर रुकती है, जहाँ C एक यंत्र-विशिष्ट स्थिरांक है जो इनपुट x की लंबाई पर निर्भर नहीं करता है, लेकिन यह M के वर्णमाला के आकार, टेपों की संख्या और राज्यों की संख्या पर निर्भर करता है। प्रभावी रूप से यह डोनाल्ड नुथ के बिग ओ नोटेशन का उपयोग करते हुए एक ${\mathcal {O}}\left(N\log {N}\right)$ सिमुलेशन है।^[5] समय-जटिलता के अतिरिक्त अंतरिक्ष-जटिलता के लिए एक संबंधित परिणाम यह है कि हम इस तरह से अनुकरण कर सकते है जो गणना के किसी भी चरण में अधिकांश सीएन कोशिकाओं का उपयोग करता है, एक ${\mathcal {O}}(N)$ सिमुलेशन है।^[6]

सबसे छोटी यंत्रें

जब एलन ट्यूरिंग एक सार्वभौमिक यंत्र के विचार के साथ आए तो उनके दिमाग में सबसे सरल कंप्यूटिंग मॉडल था जो संभावित कार्यों की गणना करने के लिए पर्याप्त शक्तिशाली था। क्लाउड शैनन ने पहली बार 1956 में सबसे छोटी संभव सार्वभौमिक ट्यूरिंग यंत्र खोजने का सवाल उठाया था। उन्होंने दिखाया कि दो प्रतीक पर्याप्त थे जब तक कि पर्याप्त राज्यों का उपयोग किया गया था, और यह कि प्रतीकों के लिए राज्यों का आदान-प्रदान करना हमेशा संभव होता है। उन्होंने यह भी दिखाया कि एक राज्य की कोई सार्वभौमिक ट्यूरिंग यंत्र उपस्तिथ नहीं हो सकती है।

मार्विन मिंस्की ने 1962 में 2-टैग प्रणाली का उपयोग करके 7-राज्य 4-प्रतीक सार्वभौमिक ट्यूरिंग यंत्र की खोज की थी। टैग प्रणाली सिमुलेशन के इस दृष्टिकोण को विस्तारित करके यूरी रोगोज़िन और अन्य लोगों द्वारा अन्य छोटी सार्वभौमिक ट्यूरिंग यंत्रों को तब से पाया गया था। यदि हम (एम, एन) एम राज्यों और एन प्रतीकों के साथ यूटीएम के वर्ग को निरूपित करते है, तो निम्नलिखित टपल पाए जाते है: (15, 2), (9, 3), (6, 4), (5, 5), (4, 6), (3, 9), और (2, 18)।^[7]^[8]^[9] रोगोज़िन की (4, 6) यंत्र केवल 22 निर्देशों का उपयोग करती है, और कम वर्णनात्मक जटिलता का कोई मानक यूटीएम ज्ञात नहीं होता है।

चूँकि, मानक ट्यूरिंग यंत्र मॉडल का सामान्यीकरण और भी छोटे यूटीएम को स्वीकार करता है। इस तरह का एक सामान्यीकरण ट्यूरिंग यंत्र इनपुट के एक या दोनों तरफ एक असीम रूप से दोहराए जाने वाले शब्द की अनुमति देता है, इस प्रकार सार्वभौमिकता की परिभाषा को विस्तारित करना और क्रमशः "अर्ध-कमजोर" या "कमजोर" सार्वभौमिकता के रूप में जाना जाता है। नियम 110 सेलुलर ऑटोमेटन का अनुकरण करने वाली छोटी कमजोर सार्वभौमिक ट्यूरिंग यंत्रें (6, 2), (3, 3), और (2, 4) राज्य-प्रतीक जोड़े के लिए दिए गए थे।^[10] वोल्फ्राम की 2-राज्य 3-प्रतीक ट्यूरिंग यंत्र के लिए सार्वभौमिकता का प्रमाण कुछ गैर-आवधिक प्रारंभिक विन्यासों की अनुमति देकर कमजोर सार्वभौमिकता की धारणा को आगे बढ़ाते है। मानक ट्यूरिंग यंत्र मॉडल पर अन्य वेरिएंट जो छोटे यूटीएम उत्पन्न करते है, उनमें कई टेप वाली यंत्रें या कई आयामों के टेप और एक परिमित ऑटोमेटन के साथ युग्मित यंत्र सम्मलित होते है।

कोई आंतरिक स्थिति वाली यंत्रें

यदि एक ट्यूरिंग यंत्र पर कई शीर्षों की अनुमति होती है तो किसी आंतरिक स्थिति की आवश्यकता नहीं होती है, जैसे कि "राज्यों" को टेप में एन्कोड किया जा सकता है। उदाहरण के लिए, 6 रंगों वाले टेप पर विचार करें: 0, 1, 2, 0A, 1A, 2A। 0,0,1,2,2A,0,2,1 जैसे टेप पर विचार करें जहां एक 3-सिर वाली ट्यूरिंग यंत्र ट्रिपल (2,2A,0) पर स्थित होते है। फिर नियम किसी भी ट्रिपल को दूसरे ट्रिपल में बदलते है और 3-हेड्स को बाएं या दाएं घुमाते है। उदाहरण के लिए, नियम (2,2A,0) को (2,1,0) में बदल सकते है और सिर को बाईं ओर ले जा सकते है। इस प्रकार इस उदाहरण में, यंत्र आंतरिक अवस्थाओं A और B के साथ 3-रंग की ट्यूरिंग यंत्र की तरह (बिना किसी अक्षर के) काम करती है । 2-सिर वाली ट्यूरिंग यंत्र का स्थिति बहुत समान होती है। इस प्रकार एक 2-सिर वाली ट्यूरिंग यंत्र 6 रंगों के साथ सार्वभौमिक हो सकती है। यह ज्ञात नहीं है कि बहु-हेडेड ट्यूरिंग यंत्र के लिए आवश्यक रंगों की सबसे छोटी संख्या क्या होती है या यदि 2-रंग वाली सार्वभौमिक ट्यूरिंग यंत्र कई हेड्स के साथ संभव होती है। इसका अर्थ यह भी है कि पुनर्लेखन नियम ट्यूरिंग पूर्ण होते है क्योंकि ट्रिपल नियम पुनर्लेखन नियमों के बराबर होते है। एक अक्षर और उसके 8 निकटतम के नमूने के साथ टेप को दो आयामों तक विस्तारित करना, केवल 2 रंगों की आवश्यकता होती है, उदाहरण के लिए, एक रंग को 110 जैसे लंबवत ट्रिपल नमूने में एन्कोड किया जा सकता है।

सार्वभौमिक-यंत्र कोडिंग का उदाहरण

उन लोगों के लिए जो ट्यूरिंग निर्दिष्ट यूटीएम को प्रारूप करने की चुनौती का सामना करते है, कोपलैंड में डेविस द्वारा लेख देखें (2004:103ff)। डेविस मूल में त्रुटियों को ठीक करता है और दिखाता है कि एक नमूना रन कैसे करता है। उनका प्रमाणित है कि उन्होंने एक (कुछ सरलीकृत) अनुकरण सफलतापूर्वक चलाया है।

निम्नलिखित उदाहरण ट्यूरिंग (1936) से लिया गया है। इस उदाहरण के बारे में अधिक जानकारी के लिए, ट्यूरिंग यंत्र के उदाहरण देखें।

ट्यूरिंग ने सात प्रतीकों {ए, सी, डी, आर, एल, एन} प्रत्येक 5-ट्यूपल को एनकोड करने के लिए है, जैसा कि ट्यूरिंग यंत्रों के लेख में वर्णित है, इसके 5-टुपल्स केवल एन 1, एन 2 और एन 3 प्रकार के होते है। प्रत्येक "एम-विन्यास" (निर्देश, स्थिति) की संख्या को "डी" द्वारा दर्शाया जाता है, जिसके बाद ए की एक स्ट्रिंग होती है, "क्यू3" = डीएएए। इसी तरह, यह रिक्त प्रतीकों को "डी", प्रतीक "0" को "डीसी", प्रतीक "1" को डीसीसी, आदि के रूप में एन्कोड करता है। प्रतीक "आर", "एल", और "एन" जैसा है वैसा ही रहता है।

निम्नलिखित तालिका में दिखाए गए अनुसार प्रत्येक 5-ट्यूपल को एन्कोडिंग के बाद एक स्ट्रिंग में "इकट्ठा" किया जाता है:

वर्तमान एम-विन्यास	टेप प्रतीक	छपाई-कार्यवाही	टेप-गति	अंतिम एम-विन्यास	वर्तमान एम-विन्यास कोड	टेप प्रतीक कोड	छपाई-कार्यवाही कोड	टेप-गति कोड	अंतिम एम-विन्यास कोड	5-टुपल इकट्ठे कोड
q1	blank	P0	R	q2	DA	D	DC	R	DAA	DADDCRDAA
q2	blank	E	R	q3	DAA	D	D	R	DAAA	DAADDRDAAA
q3	blank	P1	R	q4	DAAA	D	DCC	R	DAAAA	DAAADDCCRDAAAA
q4	blank	E	R	q1	DAAAA	D	D	R	DA	DAAAADDRDA

अंत में, सभी चार 5-टुपल्स के कोड ";" द्वारा प्रारंभ किए गए कोड में एक साथ जुड़े हुए है और ";" द्वारा अलग किया गया है अर्थात:

;DADDCRDAA;DAADDRDAAA;DAAADDCCRDAAAA;DAAAADDRDA

यह कोड उन्होंने वैकल्पिक वर्गों - "एफ-स्क्वायर" पर रखा - "ई-स्क्वायर" (जो मिटने के लिए उत्तरदायी है) को खाली छोड़ दिया जाता है। यू-यंत्र के लिए टेप पर कोड की अंतिम असेंबली में दो विशेष प्रतीकों ("ई") को एक के बाद एक रखा जाता है, फिर कोड वैकल्पिक वर्गों पर अलग हो जाता है, और अंत में डबल-कोलन प्रतीक "::" (स्पष्टता के लिए यहां "।" के साथ दिखाया गया रिक्त स्थान):

ee.;.D.A.D.D.C.R.D.A.A.;.D.A.A.D.D.R.D.A.A.A.;.D.A.A.A.D.D.C.C.R.D.A.A.A.A.;.D.A.A.A.A.D.D.R.D.A.::......

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

ee.; .D.A.D.D.C.R.D.A.A. ; zD.A.AxD.D.R.D.A.A.A.;.D.A.A.A.D.D.C.C.R.D.A.A.A.A.;.D.A.A.A.A.D.D.R.D.A.::......

ट्यूरिंग की यू-यंत्र के लिए कार्य-टेबल बहुत सम्मलित होते है।

कई अन्य टिप्पणीकार (विशेष रूप से पेनरोज़ 1989) सार्वभौमिक यंत्र के लिए निर्देशों को एन्कोड करने के तरीकों के उदाहरण प्रदान किये है। पेनरोज़ की तरह, अधिकांश टिप्पणीकार केवल बाइनरी प्रतीकों का उपयोग करते है, अर्थात केवल प्रतीक {0, 1}, या {रिक्त, चिह्न | } पेनरोज़ और आगे जाते है और अपना पूरा यू-यंत्र कोड लिखते है (पेनरोज़ 1989:71–73)। वह प्रमाणित करते है कि यह वास्तव में एक यू-यंत्र कोड होता, जिसमे एक विशाल संख्या होती है जो 1 और 0 के लगभग 2 पूर्ण पृष्ठों तक फैली हुई होती है। पोस्ट-ट्यूरिंग यंत्र के लिए सरल एनकोडिंग में रुचि रखने वाले पाठकों के लिए डेविस इन स्टीन (स्टीन 1980:251ff) की चर्चा उपयोगी होती है।

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

योजना ट्यूरिंग यंत्रें

विभिन्न उच्च स्तरीय भाषाओं को ट्यूरिंग यंत्र में संकलित करने के लिए प्रारुप किया गया है। उदाहरणों में लैकोनिक (योजना भाषा) और ट्यूरिंग यंत्र वर्णनकर्ता सम्मलित होते है।^[11]^[12]

यह भी देखें

वैकल्पिक ट्यूरिंग यंत्र
वॉन न्यूमैन सार्वभौमिक कंस्ट्रक्टर - एक स्व-प्रतिकृति ट्यूरिंग यंत्र बनाने का प्रयास
क्लेन का टी विधेय - μ-पुनरावर्ती कार्यों के लिए एक समान अवधारणा
ट्यूरिंग पूर्णता

संदर्भ

↑ Martin Davis, The universal computer : the road from Leibniz to Turing (2017)
↑ Arora and Barak, 2009, Theorem 1.9
↑ बोल्डफेस रिप्लेसिंग स्क्रिप्ट। डेविस 1965 में ट्यूरिंग 1936:127–128। एसडी की ट्यूरिंग की धारणा का एक उदाहरण इस लेख के अंत में दिया गया है।
↑ In particular: Burks, Goldstine, von Neumann (1946), Preliminary discussion of the logical design of an electronic computing instrument, reprinted in Bell and Newell 1971
↑ Arora and Barak, 2009, Theorem 1.9
↑ Arora and Barak, 2009, Exercises 4.1
↑ Rogozhin, 1996
↑ Kudlek and Rogozhin, 2002
↑ Neary and Woods, 2009
↑ Neary and Woods, 2009b
↑ "Shtetl-Optimized » Blog Archive » The 8000th Busy Beaver number eludes ZF set theory: new paper by Adam Yedidia and me". www.scottaaronson.com. 3 May 2016. Retrieved 2016-12-29.
↑ "Laconic - Esolang". esolangs.org. Retrieved 2016-12-29.

General references

Arora, Sanjeev; Barak, Boaz (2009). Complexity Theory: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4. section 1.4, "Machines as strings and the universal Turing machine" and 1.7, "Proof of theorem 1.9"

Original Paper

Turing, A. M. (1936). "On Computable Numbers, with an Application to the Entscheidungsproblem" (PDF).

Seminal papers

Hennie, F. C.; Stearns, R. E. (1966). "Two-Tape Simulation of Multitape Turing Machines". Journal of the ACM. 13 (4): 533. doi:10.1145/321356.321362. S2CID 2347143.

Implementation

Kamvysselis (Kellis), Manolis (1999). "Scheme Implementation of a Universal Turing Machine". Self-published.

Formal verification

Asperti, Andrea; Ricciotti, Wilmer (2015). "A formalization of multi-tape Turing machines" (PDF). Theoretical Computer Science. Elsevier. 603: 23–42. doi:10.1016/j.tcs.2015.07.013. ISSN 0304-3975.

Other references

Copeland, Jack, ed. (2004), The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma, Oxford UK: Oxford University Press, ISBN 0-19-825079-7
Davis, Martin (1980), "What is Computation?", in Steen, Lynn Arthur (ed.), Mathematics Today: Twelve Informal Essays, New York: Vintage Books (Random House), ISBN 978-0-394-74503-9.
Davis, Martin (2000), Engines of Logic: Mathematicians and the origin of the Computer (1st ed.), New York NY: W. W. Norton & Company, ISBN 0-393-32229-7, (pb.)
Goldstine, Herman H.; von Neumann, John. Planning and Coding of the Problems for an Electronic Computing Instrument. {{cite book}}: |work= ignored (help)
Bell, C. Gordon; Newell, Allen (1971). Computer Structures: Readings and Examples (Reprinted ed.). New York: McGraw-Hill Book Company. pp. 92–119. ISBN 0-07-004357-4.
Herken, Rolf (1995), The Universal Turing Machine – A Half-Century Survey, Springer Verlag, ISBN 3-211-82637-8
Knuth, Donald E. (1973), The Art of Computer Programming, vol. 1/Fundamental Algorithms (second ed.), Addison-Wesley Publishing Company The first of Knuth's series of three texts.
Kudlek, Manfred; Rogozhin, Yurii (2002), "A universal Turing machine with 3 states and 9 symbols", in Werner Kuich; Grzegorz Rozenberg; Arto Salomaa (eds.), Developments in Language Theory: 5th International Conference, DLT 2001 Wien, Austria, July 16–21, 2001, Revised Papers, Lecture Notes in Computer Science, vol. 2295, Springer, pp. 311–318, doi:10.1007/3-540-46011-x_27, ISBN 978-3-540-43453-5
Minsky, Marvin (1962), "Size and Structure of Universal Turing Machines using Tag Systems, Recursive Function Theory", Proc. Symp. Pure Mathematics, Providence RI: American Mathematical Society, 5: 229–238, doi:10.1090/pspum/005/0142452
Neary, Turlough; Woods, Damien (2009), "Four Small Universal Turing Machines" (PDF), Fundamenta Informaticae, 91 (1): 123–144, doi:10.3233/FI-2009-0036
Neary, Turlough; Woods, Damien (2009b), "Small Weakly Universal Turing Machines", 17th International Symposium on Fundamentals of Computation Theory, Lecture Notes in Computer Science, vol. 5699, Springer, pp. 262–273
Penrose, Roger (1989), The Emperor's New Mind, Oxford UK: Oxford University Press, ISBN 0-19-851973-7, (hc.), (pb.)
Rogozhin, Yurii (1996), "Small Universal Turing Machines", Theoretical Computer Science, 168 (2): 215–240, doi:10.1016/S0304-3975(96)00077-1
Shannon, Claude (1956), "A Universal Turing Machine with Two Internal States", Automata Studies, Princeton, NJ: Princeton University Press, pp. 157–165
Turing, A.M. (1936), "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, 2, vol. 42, pp. 230–65, doi:10.1112/plms/s2-42.1.230
Turing, A.M. (1938), "On Computable Numbers, with an Application to the Entscheidungsproblem: A correction", Proceedings of the London Mathematical Society, 2 (published 1937), vol. 43, no. 6, pp. 544–6, doi:10.1112/plms/s2-43.6.544)
Davis, Martin, ed. (1965). The Undecidable (Reprint ed.). Hewlett, NY: Raven Press. pp. 115–154. with corrections to Turing's UTM by Emil Post cf footnote 11 pg:299

बाहरी कड़ियाँ

Smith, Alvy Ray. "A Business Card Universal Turing Machine" (PDF). Retrieved 2 January 2020.

[Davis-1] Martin Davis, The universal computer : the road from Leibniz to Turing (2017)

[2] Arora and Barak, 2009, Theorem 1.9

[3] बोल्डफेस रिप्लेसिंग स्क्रिप्ट। डेविस 1965 में ट्यूरिंग 1936:127–128। एसडी की ट्यूरिंग की धारणा का एक उदाहरण इस लेख के अंत में दिया गया है।

[4] In particular: Burks, Goldstine, von Neumann (1946), Preliminary discussion of the logical design of an electronic computing instrument, reprinted in Bell and Newell 1971

[5] Arora and Barak, 2009, Theorem 1.9

[6] Arora and Barak, 2009, Exercises 4.1

[7] Rogozhin, 1996

[8] Kudlek and Rogozhin, 2002

[9] Neary and Woods, 2009

[10] Neary and Woods, 2009b

[11] "Shtetl-Optimized » Blog Archive » The 8000th Busy Beaver number eludes ZF set theory: new paper by Adam Yedidia and me". www.scottaaronson.com. 3 May 2016. Retrieved 2016-12-29.

[12] "Laconic - Esolang". esolangs.org. Retrieved 2016-12-29.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

@@ Line 1: / Line 1: @@
-{{Short description|Type of Turing machine}}
+[[कंप्यूटर विज्ञान]] में, [[ट्यूरिंग मशीन|'''सार्वभौमिक ट्यूरिंग मशीन''']] (यूटीएम) एक ऐसा यंत्र है जो मनमाना इनपुट पर एक मनमानी ट्यूरिंग यंत्र का अनुकरण करता है। सार्वभौमिक यंत्र अनिवार्य रूप से सिम्युलेटेड होने वाले यंत्र के विवरण और साथ ही यंत्र के टेप से इनपुट दोनों को पढ़कर प्राप्त करती है। [[एलन ट्यूरिंग]] ने 1936-1937 में इस यंत्र का विचार प्रस्तुत किया था। इस सिद्धांत को "इलेक्ट्रॉनिक कंप्यूटिंग इंस्ट्रूमेंट" के लिए 1946 में जॉन वॉन न्यूमैन द्वारा उपयोग किए जाने वाले एक [[संग्रहीत प्रोग्राम कंप्यूटर|संग्रहीत योजना कंप्यूटर]] के विचार का मूल माना जाता है, जो अब [[वॉन न्यूमैन वास्तुकला]] के नाम को धारण करता है।<ref name="Davis">[[Martin Davis (mathematician)|Martin Davis]], ''The universal computer : the road from Leibniz to Turing'' (2017)</ref>
-{{Redirect|सार्वभौमिक मशीन}}
-{{turing}}
+[[कम्प्यूटेशनल जटिलता सिद्धांत]] के संदर्भ में, एक [[मल्टीटेप ट्यूरिंग मशीन|बहु-टेप सार्वभौमिक ट्यूरिंग यंत्र]] को केवल उन यंत्रों की तुलना में लॉगरिदमिक कारक द्वारा केवल [[ओवरहेड (कंप्यूटिंग)|उपरि (कंप्यूटिंग)]] की आवश्यकता होती है।<ref>Arora and Barak, 2009, Theorem 1.9</ref>
-[[कंप्यूटर विज्ञान]] में, एक '''यूनिवर्सल [[ट्यूरिंग मशीन]]''' (यूटीएम) एक ट्यूरिंग मशीन है जो मनमाना इनपुट पर एक मनमानी ट्यूरिंग मशीन का अनुकरण कर सकती है। यूनिवर्सल मशीन अनिवार्य रूप से सिम्युलेटेड होने वाली मशीन के विवरण और साथ ही उस मशीन के अपने टेप से इनपुट दोनों को पढ़कर इसे प्राप्त करती है। [[एलन ट्यूरिंग]] ने 1936-1937 में ऐसी मशीन का विचार प्रस्तुत किया है। इस सिद्धांत को "इलेक्ट्रॉनिक कंप्यूटिंग इंस्ट्रूमेंट" के लिए 1946 में जॉन वॉन न्यूमैन द्वारा उपयोग किए जाने वाले एक [[संग्रहीत प्रोग्राम कंप्यूटर]] के विचार का मूल माना जाता है, जो अब वॉन न्यूमैन के नाम को धारण करता है: [[वॉन न्यूमैन वास्तुकला]]।<ref name="Davis">[[Martin Davis (mathematician)|Martin Davis]], ''The universal computer : the road from Leibniz to Turing'' (2017)</ref>
-[[कम्प्यूटेशनल जटिलता सिद्धांत]] के संदर्भ में, एक [[मल्टीटेप ट्यूरिंग मशीन|मल्टी-टेप यूनिवर्सल ट्यूरिंग मशीन]] को केवल उन मशीनों की तुलना में लॉगरिदमिक कारक द्वारा केवल [[ओवरहेड (कंप्यूटिंग)]] की आवश्यकता होती है।<ref>Arora and Barak, 2009, Theorem 1.9</ref>
 == परिचय ==
-[[File:Universal Turing machine.svg|500px|right]]प्रत्येक ट्यूरिंग मशीन अपने वर्णमाला पर इनपुट स्ट्रिंग्स से एक निश्चित आंशिक संगणनीय फ़ंक्शन की गणना करती है। इस अर्थ में यह एक निश्चित प्रोग्राम वाले कंप्यूटर की तरह व्यवहार करता है। चूँकि, हम किसी भी ट्यूरिंग मशीन की एक्शन टेबल को एक स्ट्रिंग में एनकोड कर सकते हैं। इस प्रकार हम एक ट्यूरिंग मशीन का निर्माण कर सकते हैं जो अपने टेप पर इनपुट टेप का वर्णन करने वाली एक स्ट्रिंग के बाद एक एक्शन टेबल का वर्णन करने वाली एक स्ट्रिंग की अपेक्षा करती है, और उस टेप की गणना करती है जिसे एन्कोडेड ट्यूरिंग मशीन ने गणना की होगी। ट्यूरिंग ने अपने 1936 के पेपर में इस तरह के निर्माण का पूरी तरह से वर्णन किया है:
+[[File:Universal Turing machine.svg|500px|right]]प्रत्येक ट्यूरिंग यंत्र अपने वर्णमाला पर इनपुट स्ट्रिंग्स से एक निश्चित आंशिक संगणनीय फ़ंक्शन की गणना करती है। इस अर्थ में यह एक निश्चित योजना वाले कंप्यूटर की तरह व्यवहार करता है। चूँकि, हम किसी भी ट्यूरिंग यंत्र की कार्य टेबल को एक स्ट्रिंग में एनकोड कर सकते हैं। इस प्रकार हम एक ट्यूरिंग यंत्र का निर्माण कर सकते हैं जो अपने टेप पर इनपुट टेप का वर्णन करने वाली एक स्ट्रिंग के बाद एक कार्य टेबल का वर्णन करने वाली एक स्ट्रिंग की अपेक्षा करती है, और उस टेप की गणना करती है जिसकी एन्कोडेड ट्यूरिंग मशीन ने गणना की होती है। ट्यूरिंग ने अपने 1936 के पेपर में इस तरह के निर्माण का पूरी तरह से वर्णन किया है:
-{{quote|"It is possible to invent a single machine which can be used to compute any computable sequence. If this machine '''U''' is supplied with a tape on the beginning of which is written the S.D ["standard description" of an action table] of some computing machine '''M''', then '''U''' will compute the same sequence as '''M'''."<ref>Boldface replacing script. Turing 1936 in Davis 1965:127–128. An example of Turing's notion of S.D is given at the end of this article.</ref>}}
+{{quote|"एक ऐसा यंत्र का आविष्कार करना संभव है जिसका उपयोग किसी भी गणना योग्य अनुक्रम की गणना करने के लिए किया जा सकता है। यदि यह यंत्र ''यू''' एक टेप के साथ आपूर्ति की जाती है जिसकी शुरुआत में एसडी ["मानक विवरण" लिखा जाता है क्रिया तालिका] कुछ कंप्यूटिंग यंत्र '''एम''' की, तो '''यू''' '''एम''' के समान अनुक्रम की गणना करता है।"<ref>बोल्डफेस रिप्लेसिंग स्क्रिप्ट। डेविस 1965 में ट्यूरिंग 1936:127–128। एसडी की ट्यूरिंग की धारणा का एक उदाहरण इस लेख के अंत में दिया गया है।</ref>}}
 <!-- In 1947, Turing said: <blockquote style="font-style:italic;">It can be shown that a single special machine of that type can be made to do the work of all. It could in fact be made to work as a model of any other machine. The special machine may be called the universal machine.</blockquote> -->
-== संग्रहीत कार्यक्रम [[कंप्यूटर]] ==
+== [[कंप्यूटर|संग्रहीत कार्यक्रम कंप्यूटर]] ==
-[[मार्टिन डेविस (गणितज्ञ)]] एक प्रेरक तर्क देते है कि ट्यूरिंग की अवधारणा जिसे अब "संग्रहीत प्रोग्राम कंप्यूटर" के रूप में जाने जाते है, "एक्शन टेबल" रखने के लिए - मशीन के लिए निर्देश - इनपुट डेटा के समान "मेमोरी" में, जॉन को दृढ़ता से प्रभावित किया। पहले अमेरिकी असतत-प्रतीक (एनालॉग के विपरीत) कंप्यूटर- [[EDVAC]] की वॉन न्यूमैन की अवधारणा है। डेविस टाइम पत्रिका को इस आशय का उद्धरण देते है, कि "हर कोई जो एक कीबोर्ड पर टैप करता है ... एक ट्यूरिंग मशीन के अवतार पर काम करता है", और यह कि "जॉन वॉन न्यूमैन [निर्मित] एलन ट्यूरिंग के काम पर" (डेविस 2000: 193 29 मार्च 1999 की टाइम पत्रिका के हवाले से है)।
+[[मार्टिन डेविस (गणितज्ञ)]] एक प्रेरक तर्क देते है कि ट्यूरिंग की अवधारणा जिसे अब "संग्रहीत योजना कंप्यूटर" के रूप में जाने जाते है, "कार्य टेबल" रखने के लिए - यंत्र के लिए निर्देश - इनपुट डेटा के समान "मेमोरी" में, जॉन को दृढ़ता से प्रभावित करते है। पहले अमेरिकी असतत-प्रतीक (एनालॉग के विपरीत) कंप्यूटर- [[EDVAC]] की वॉन न्यूमैन की अवधारणा है। डेविस टाइम पत्रिका को इस आशय का उद्धरण देते है, कि "हर कोई जो एक कीबोर्ड पर टैप करता है ... एक ट्यूरिंग यंत्र के अवतार पर काम करता है", और यह कि "जॉन वॉन न्यूमैन एलन ट्यूरिंग के काम पर" (डेविस 2000: 193 29 मार्च 1999 की टाइम पत्रिका के हवाले है)।
+डेविस एक स्थिति बनाते है कि ट्यूरिंग के [[स्वचालित कंप्यूटिंग इंजन]] (एसीई) कंप्यूटर ने माइक्रोयोजना ([[माइक्रोकोड]]) और आरआईएससी प्रोसेसर (डेविस 2000: 188) के विचारों को "प्रत्याशित" किया। [[डोनाल्ड नुथ]] एसीई कंप्यूटर पर ट्यूरिंग के काम को "सबरूटीन लिंकेज की सुविधा के लिए हार्डवेयर" के रूप में प्रारूप करने का हवाला दिया (नथ 1973: 225), डेविस इस काम को ट्यूरिंग द्वारा हार्डवेयर "स्टैक" के उपयोग के रूप में भी संदर्भित करते है (डेविस 2000: 237 फुटनोट 18)।
-डेविस एक स्थिति बनाते है कि ट्यूरिंग के [[स्वचालित कंप्यूटिंग इंजन]] (एसीई) कंप्यूटर ने माइक्रोप्रोग्रामिंग ([[माइक्रोकोड]]) और आरआईएससी प्रोसेसर (डेविस 2000: 188) के विचारों को "प्रत्याशित" किया। [[डोनाल्ड नुथ]] एसीई कंप्यूटर पर ट्यूरिंग के काम को "सबरूटीन लिंकेज की सुविधा के लिए हार्डवेयर" के रूप में प्रारूप करने का हवाला देते है (नथ 1973: 225), डेविस इस काम को ट्यूरिंग द्वारा हार्डवेयर "स्टैक" के उपयोग के रूप में भी संदर्भित करते है (डेविस 2000: 237 फुटनोट 18)।
+चूंकि ट्यूरिंग यंत्र कंप्यूटर के निर्माण को प्रोत्साहित करता था, यूटीएम नवाचारी कंप्यूटर विज्ञान के विकास को प्रोत्साहित करता था। EDVAC (डेविस 2000: 192) के लिए "एक युवा हॉट-शॉट योजना द्वारा" एक प्रारंभिक, असेंबलर प्रस्तावित किया गया था। वॉन न्यूमैन का "पहला गंभीर कार्यक्रम केवल डेटा को कुशलतापूर्वक क्रमबद्ध करता था" (डेविस 2000:184)। नुथ ने देखा कि विशेष रजिस्टरों के अतिरिक्त योजना में एम्बेडेड सबरूटीन रिटर्न वॉन न्यूमैन और गोल्डस्टाइन के लिए जिम्मेदार होते थे।<ref>In particular: Burks, Goldstine, von Neumann (1946), ''Preliminary discussion of the logical design of an electronic computing instrument'', reprinted in Bell and Newell 1971</ref> नुथ आगे कहते है कि
-चूंकि ट्यूरिंग मशीन कंप्यूटर के निर्माण को प्रोत्साहित कर रही थी, यूटीएम नवाचारी कंप्यूटर विज्ञान के विकास को प्रोत्साहित कर रहा था। EDVAC (डेविस 2000: 192) के लिए "एक युवा हॉट-शॉट प्रोग्रामर द्वारा" एक प्रारंभिक, यदि बहुत पहले नहीं, असेंबलर प्रस्तावित किया गया था। वॉन न्यूमैन का "पहला गंभीर कार्यक्रम ... [था] केवल डेटा को कुशलतापूर्वक क्रमबद्ध करना" (डेविस 2000:184)। नुथ ने देखा कि विशेष रजिस्टरों के अतिरिक्त प्रोग्राम में एम्बेडेड सबरूटीन रिटर्न वॉन न्यूमैन और गोल्डस्टाइन के लिए जिम्मेदार है।<ref>In particular: Burks, Goldstine, von Neumann (1946), ''Preliminary discussion of the logical design of an electronic computing instrument'', reprinted in Bell and Newell 1971</ref> नुथ आगे कहते है कि
+{{quote|पहली व्याख्यात्मक दिनचर्या को "यूनिवर्सल ट्यूरिंग यंत्र" कहा जा सकता है ... पारंपरिक अर्थों में व्याख्यात्मक दिनचर्या का उल्लेख [[जॉन मौचली|जॉन मौचली]] ने [[मूर स्कूल ऑफ विद्युतीय अभियांत्रिकी|मूर] में अपने व्याख्यान में किया था। स्कूल]] 1946 में ... ट्यूरिंग ने इस विकास में भी भाग लिया; पायलट एसीई कंप्यूटर के लिए व्याख्यात्मक प्रणाली उनके निर्देशन में लिखी गई थी।|नुथ 1973:226}}
-{{quote|The first interpretive routine may be said to be the "Universal Turing Machine" ... Interpretive routines in the conventional sense were mentioned by [[John Mauchly|John Mauchly]] in his lectures at the [[Moore School of Electrical Engineering|Moore School]] in 1946 ... Turing took part in this development also; interpretive systems for the Pilot ACE computer were written under his direction.|Knuth 1973:226}}
+डेविस संक्षेप में डेटा के रूप में योजना की धारणा के परिणामों के रूप में परिचालन प्रणाली और संकलनकर्ता का उल्लेख करते है (डेविस 2000:185)।
-डेविस संक्षेप में डेटा के रूप में प्रोग्राम की धारणा के परिणामों के रूप में ऑपरेटिंग सिस्टम और कंपाइलर्स का उल्लेख करते है (डेविस 2000:185)।
 चूँकि, कुछ लोग इस आकलन के साथ समस्याएँ उठा सकते है। उस समय (1940 के दशक के मध्य से 1950 के दशक के मध्य तक) शोधकर्ताओं का एक अपेक्षाकृत छोटा कैडर नए "डिजिटल कंप्यूटर" की वास्तुकला के साथ घनिष्ठ रूप से जुड़ा हुआ था। हाओ वांग (1954), इस समय के एक युवा शोधकर्ता ने निम्नलिखित अवलोकन किया:
-{{quote|Turing's theory of computable functions antedated but has not much influenced the extensive actual construction of digital computers. These two aspects of theory and practice have been developed almost entirely independently of each other. The main reason is undoubtedly that logicians are interested in questions radically different from those with which the applied mathematicians and electrical engineers are primarily concerned. It cannot, however, fail to strike one as rather strange that often the same concepts are expressed by very different terms in the two developments.|Wang 1954, 1957:63}}
+{{quote|कम्प्यूटेशनल कार्यों के ट्यूरिंग के सिद्धांत को पुराना लेकिन डिजिटल कंप्यूटरों के व्यापक वास्तविक निर्माण को ज्यादा प्रभावित नहीं किया था। सिद्धांत और व्यवहार के इन दो पहलुओं को लगभग पूरी तरह से एक दूसरे से स्वतंत्र रूप से विकसित किया जाता था। मुख्य कारण निस्संदेह यह है कि तर्कशास्त्री उन प्रश्नों में रुचि रखते थे जो लागू गणितज्ञों और विद्युत इंजीनियरों से प्राथमिक रूप से संबंधित होते थे। चूँकि, यह किसी को भी अजीब लगने में विफल नहीं हो सकते थे कि अक्सर एक ही अवधारणा को दो विकासों में बहुत भिन्न शब्दों द्वारा व्यक्त किया गया था।|वैंग 1954, 1957:63}}
-वांग ने आशा व्यक्त की कि उनका पेपर "दो दृष्टिकोणों को जोड़ देगा"। वास्तव में, मिंस्की ने इसकी पुष्टि की: "कंप्यूटर जैसे मॉडल में ट्यूरिंग-मशीन सिद्धांत का पहला सूत्रीकरण वैंग (1957) में दिखाई देता है" (मिन्स्की 1967: 200)। मिंस्की एक [[काउंटर मशीन]] के [[ट्यूरिंग पूर्णता|ट्यूरिंग तुल्यता]] को प्रदर्शित करने के लिए आगे बढ़ता है।
+वांग ने आशा व्यक्त की कि उनका पेपर "दो दृष्टिकोणों को जोड़ देगा"। वास्तव में, मिंस्की ने इसकी पुष्टि की: "कंप्यूटर जैसे मॉडल में ट्यूरिंग-यंत्र सिद्धांत का पहला सूत्रीकरण वैंग (1957) में दिखाई देता है" (मिन्स्की 1967: 200)। मिंस्की एक [[काउंटर मशीन|काउंटर यंत्र]] के [[ट्यूरिंग पूर्णता|ट्यूरिंग तुल्यता]] को प्रदर्शित करने के लिए आगे बढ़ाते है।
-कंप्यूटर को सरल ट्यूरिंग समकक्ष मॉडल (और इसके विपरीत) में कमी के संबंध में, मिन्स्की का वांग का पदनाम "पहला फॉर्मूलेशन" बना बहस के लिए खुला है। जबकि 1961 के मिन्स्की के पेपर और 1957 के वांग के पेपर को शेफर्डसन और स्टर्गिस (1963) द्वारा उद्धृत किया गया है, वे यूरोपीय गणितज्ञों केफेंस्ट (1959), एर्शोव (1959) और पेटर (1958) के काम का भी कुछ विस्तार से हवाला देते है और संक्षेप में बताते है। गणितज्ञ हेमीज़ (1954, 1955, 1961) और काफेन्स्ट (1959) के नाम शेपर्डसन-स्टर्गिस (1963) और एलगॉट-रॉबिन्सन (1961) दोनों की ग्रंथ सूची में दिखाई देते है। महत्व के दो अन्य नाम कनाडाई शोधकर्ता मेल्ज़क (1961) और लैम्बेक (1961) है और अधिक के लिए [[ट्यूरिंग मशीन समकक्ष]] देखें, संदर्भ [[रजिस्टर मशीन]] पर पाए जा सकते है।
+कंप्यूटर को सरल ट्यूरिंग समकक्ष मॉडल की कमी के संबंध में, मिन्स्की का वांग का पदनाम "पहला फॉर्मूलेशन" बहस के लिए खुला था। जबकि 1961 के मिन्स्की के पेपर और 1957 के वांग के पेपर को शेफर्डसन और स्टर्गिस (1963) द्वारा उद्धृत किया गया था, वे यूरोपीय गणितज्ञों केफेंस्ट (1959), एर्शोव (1959) और पेटर (1958) के काम का भी कुछ विस्तार से हवाला देते थे और संक्षेप में बताते थे। गणितज्ञ हेमीज़ (1954, 1955, 1961) और काफेन्स्ट (1959) के नाम शेपर्डसन-स्टर्गिस (1963) और एलगॉट-रॉबिन्सन (1961) दोनों की ग्रंथ सूची में दिखाई देते थे। महत्व के दो अन्य नाम कनाडाई शोधकर्ता मेल्ज़क (1961) और लैम्बेक (1961) है और अधिक के लिए [[ट्यूरिंग मशीन समकक्ष|ट्यूरिंग यंत्र समकक्ष]] देखें, संदर्भ [[रजिस्टर मशीन|रजिस्टर यंत्र]] पर पाए जा सकते है।
 == गणितीय सिद्धांत ==
-स्ट्रिंग्स के रूप में एक्शन टेबल के इस एन्कोडिंग के साथ, ट्यूरिंग मशीनों के लिए, अन्य ट्यूरिंग मशीनों के व्यवहार के बारे में सवालों के उत्तर देना सिद्धांत रूप में संभव हो जाता है। चूंकि, इनमें से अधिकांश प्रश्न [[अनिर्णीत समस्या|अनिर्णीत]] है, जिसका अर्थ है कि विचाराधीन कार्य की यांत्रिक रूप से गणना नहीं की जा सकती है। उदाहरण के लिए, यह निर्धारित करने की समस्या कि क्या एक मनमाना ट्यूरिंग मशीन किसी विशेष इनपुट पर रुकेगी, या सभी इनपुट पर रुकेगी, जिसे हाल्टिंग समस्या के रूप में जाना जाता है, सामान्यतः, ट्यूरिंग के मूल पेपर में अनिर्णीत दिखाया गया था। चावल के प्रमेय से पता चलता है कि ट्यूरिंग मशीन के आउटपुट के बारे में कोई भी गैर-तुच्छ प्रश्न अनिर्णीत है।
+स्ट्रिंग्स के रूप में कार्य टेबल के इस एन्कोडिंग के साथ, ट्यूरिंग यंत्रों के लिए, अन्य ट्यूरिंग यंत्रों के व्यवहार के बारे में सवालों के उत्तर देना सिद्धांत रूप में संभव हो जाता है। चूंकि, इनमें से अधिकांश प्रश्न [[अनिर्णीत समस्या|अनिर्णीत]] होते है, जिसका अर्थ है कि विचाराधीन कार्य की यांत्रिक रूप से गणना नहीं की जा सकती है। उदाहरण के लिए, यह निर्धारित करने की समस्या है कि क्या एक मनमाना ट्यूरिंग यंत्र किसी विशेष इनपुट पर रुकेगा, या सभी इनपुट पर रुकेगा, जिसे हाल्टिंग समस्या के रूप में जाना जाता है, सामान्यतः, ट्यूरिंग के मूल पेपर में अनिर्णीत दिखाया जाता है। चावल के प्रमेय से पता चलता है कि ट्यूरिंग यंत्र के आउटपुट के बारे में कोई भी गैर-तुच्छ प्रश्न अनिर्णीत हो जाते है।
-एक सार्वभौमिक ट्यूरिंग मशीन किसी भी पुनरावर्ती कार्य की गणना कर सकती है, किसी भी पुनरावर्ती भाषा का निर्धारण कर सकती है, और किसी भी [[पुनरावर्ती भाषा|पुनरावर्ती]] गणना योग्य भाषा को स्वीकार कर सकती है। चर्च-ट्यूरिंग थीसिस के अनुसार, सार्वभौमिक ट्यूरिंग मशीन द्वारा हल की जा सकने वाली समस्याएं वास्तव में उन शर्तों की किसी भी उचित परिभाषा के लिए [[कलन विधि]] या गणना की प्रभावी विधि द्वारा हल की जाने वाली समस्याएं है। इन कारणों से, एक सार्वभौमिक ट्यूरिंग मशीन एक मानक के रूप में कार्य करती है जिसके विरुद्ध कम्प्यूटेशनल सिस्टम की तुलना की जाती है, और एक प्रणाली जो एक सार्वभौमिक ट्यूरिंग मशीन का अनुकरण कर सकती है, [[ट्यूरिंग पूर्ण]] कहलाती है।
+सार्वभौमिक ट्यूरिंग यंत्र किसी भी पुनरावर्ती कार्य की गणना कर सकती है, किसी भी पुनरावर्ती भाषा का निर्धारण कर सकती है, और किसी भी [[पुनरावर्ती भाषा|पुनरावर्ती]] गणना योग्य भाषा को स्वीकार कर सकती है। चर्च-ट्यूरिंग थीसिस के अनुसार, सार्वभौमिक ट्यूरिंग यंत्र द्वारा हल की जाने वाली समस्याएं वास्तव में उन शर्तों की किसी भी उचित परिभाषा के लिए [[कलन विधि]] या गणना की प्रभावी विधि द्वारा हल की जाने वाली समस्याएं होती है। इन कारणों से, एक सार्वभौमिक ट्यूरिंग यंत्र एक मानक के रूप में कार्य करती है जिसके विरुद्ध कम्प्यूटेशनल प्रणाली की तुलना की जाती है, और एक प्रणाली जो सार्वभौमिक ट्यूरिंग यंत्र का अनुकरण करती है, [[ट्यूरिंग पूर्ण]] कहलाती है।
-यूनिवर्सल ट्यूरिंग मशीन का एक सार संस्करण यूनिवर्सल फ़ंक्शन है, एक कंप्यूटेबल फ़ंक्शन जिसका उपयोग किसी अन्य कंप्यूटेशनल फ़ंक्शन की गणना के लिए किया जा सकता है। यूटीएम प्रमेय ऐसे फलन के अस्तित्व को सिद्ध करता है।
+सार्वभौमिक ट्यूरिंग यंत्र का एक सार संस्करण सार्वभौमिक कार्य होता है, एक कंप्यूटेबल कार्य जिसका उपयोग किसी अन्य कंप्यूटेशनल कार्य की गणना के लिए किया जा सकता है। यूटीएम प्रमेय ऐसे फलन के अस्तित्व को सिद्ध करता है।
 == दक्षता ==
-व्यापकता के नुकसान के बिना, ट्यूरिंग मशीन का इनपुट वर्णमाला {0, 1} में माना जा सकता है; किसी भी अन्य परिमित वर्णमाला को {0, 1} पर एन्कोड किया जा सकता है। एक ट्यूरिंग मशीन एम का व्यवहार उसके संक्रमण समारोह द्वारा निर्धारित किया जाता है। इस फ़ंक्शन को अक्षर {0, 1} पर स्ट्रिंग के रूप में भी आसानी से एन्कोड किया जा सकता है। एम के वर्णमाला का आकार, इसमें टेप की संख्या, और राज्य स्थान का आकार संक्रमण फ़ंक्शन की तालिका से घटाया जा सकता है। विशिष्ट राज्यों और प्रतीकों को उनकी स्थिति से पहचाना जा सकता है, उदा। कन्वेंशन द्वारा पहले दो राज्य स्टार्ट और स्टॉप स्टेट हो सकते है। परिणाम स्वरुप, प्रत्येक ट्यूरिंग मशीन को वर्णमाला {0, 1} पर स्ट्रिंग के रूप में एन्कोड किया जा सकता है। इसके अतिरिक्त, हम यह कहते है कि प्रत्येक अमान्य एन्कोडिंग मानचित्र एक तुच्छ ट्यूरिंग मशीन के लिए है जो तुरंत रुक जाती है, और यह कि प्रत्येक ट्यूरिंग मशीन में एन्कोडिंग की एक अनंत संख्या हो सकती है, जैसे कि टिप्पणियों की तरह अंत में (कहते है) 1 की मनमानी संख्या के साथ एन्कोडिंग एक प्रोग्रामिंग भाषा में काम करें। इसमें कोई आश्चर्य नहीं होना चाहिए कि गोडेल संख्या के अस्तित्व और ट्यूरिंग मशीनों और μ-पुनरावर्ती कार्यों के बीच कम्प्यूटेशनल समानता को देखते हुए हम इस एन्कोडिंग को प्राप्त कर सकते है। इसी तरह, हमारा निर्माण प्रत्येक बाइनरी स्ट्रिंग α, एक ट्यूरिंग मशीन M<sub>α</sub> से जुड़ता है।
+व्यापकता के नुकसान के बिना, ट्यूरिंग यंत्र का इनपुट वर्णमाला {0, 1} में माना जा सकता है, किसी भी अन्य परिमित वर्णमाला को {0, 1} पर एन्कोड किया जा सकता है। एक ट्यूरिंग यंत्र एम का व्यवहार उसके संक्रमण समारोह द्वारा निर्धारित किया जाता है। इस कार्य को अक्षर {0, 1} पर स्ट्रिंग के रूप में भी आसानी से एन्कोड किया जा सकता है। एम के वर्णमाला का आकार, इसमें टेप की संख्या, और राज्य स्थान का आकार संक्रमण कार्य की तालिका से घटाया जा सकता है। विशिष्ट राज्यों और प्रतीकों को उनकी स्थिति से पहचाना जा सकता है। कन्वेंशन द्वारा पहले दो राज्य स्टार्ट और स्टॉप स्टेट हो सकते है। परिणाम स्वरुप, प्रत्येक ट्यूरिंग यंत्र को वर्णमाला {0, 1} पर स्ट्रिंग के रूप में एन्कोड किया जा सकता है। इसके अतिरिक्त, हम यह कहते है कि प्रत्येक अमान्य एन्कोडिंग मानचित्र एक तुच्छ ट्यूरिंग यंत्र के लिए है जो तुरंत रुक जाती है, और यह कि प्रत्येक ट्यूरिंग यंत्र में एन्कोडिंग की एक अनंत संख्या हो सकती है, जैसे कि टिप्पणियों की तरह अंत में (कहते है) 1 की मनमानी संख्या के साथ एन्कोडिंग एक योजना भाषा में काम करता है। इसमें कोई आश्चर्य नहीं होना चाहिए कि गोडेल संख्या के अस्तित्व और ट्यूरिंग यंत्रों और μ-पुनरावर्ती कार्यों के बीच कम्प्यूटेशनल समानता को देखते हुए हम इस एन्कोडिंग को प्राप्त कर सकते है। इसी तरह, हमारा निर्माण प्रत्येक बाइनरी स्ट्रिंग α, एक ट्यूरिंग यंत्र M<sub>α</sub> से जुड़ता है।
-उपरोक्त एन्कोडिंग से प्रारंभ करते हुए, 1966 में '''एफ.सी. हेनी''' और '''रिचर्ड ई. स्टर्न्स''' ने दिखाया कि एक ट्यूरिंग मशीन एम<sub>α</sub> जो N चरणों के भीतर इनपुट x पर रुकता है, तो एक मल्टी-टेप यूनिवर्सल ट्यूरिंग मशीन उपस्तिथ है जो CN लॉग N में इनपुट α, x पर रुकती है, जहाँ C एक मशीन-विशिष्ट स्थिरांक है जो इनपुट x की लंबाई पर निर्भर नहीं करता है, लेकिन यह M के वर्णमाला के आकार, टेपों की संख्या और राज्यों की संख्या पर निर्भर करता है। प्रभावी रूप से यह डोनाल्ड नुथ के [[बिग ओ नोटेशन]] का उपयोग करते हुए एक <math>\mathcal{O}\left ( N \log {N}\right )</math> सिमुलेशन है।<ref>Arora and Barak, 2009, Theorem 1.9</ref> समय-जटिलता के अतिरिक्त अंतरिक्ष-जटिलता के लिए एक संबंधित परिणाम यह है कि हम इस तरह से अनुकरण कर सकते है जो गणना के किसी भी चरण में अधिकांश सीएन कोशिकाओं का उपयोग करता है, एक <math>\mathcal{O}(N)</math> सिमुलेशन है।<ref>Arora and Barak, 2009, Exercises 4.1</ref>
+उपरोक्त एन्कोडिंग से प्रारंभ करते हुए, 1966 में '''एफ.सी. हेनी''' और '''रिचर्ड ई. स्टर्न्स''' ने दिखाया कि एक ट्यूरिंग यंत्र एम<sub>α</sub> जो N चरणों के भीतर इनपुट x पर रुकता है, तो एक बहु-टेप सार्वभौमिक ट्यूरिंग यंत्र उपस्तिथ होता है जो CN लॉग N में इनपुट α, x पर रुकती है, जहाँ C एक यंत्र-विशिष्ट स्थिरांक है जो इनपुट x की लंबाई पर निर्भर नहीं करता है, लेकिन यह M के वर्णमाला के आकार, टेपों की संख्या और राज्यों की संख्या पर निर्भर करता है। प्रभावी रूप से यह डोनाल्ड नुथ के [[बिग ओ नोटेशन]] का उपयोग करते हुए एक <math>\mathcal{O}\left ( N \log {N}\right )</math> सिमुलेशन है।<ref>Arora and Barak, 2009, Theorem 1.9</ref> समय-जटिलता के अतिरिक्त अंतरिक्ष-जटिलता के लिए एक संबंधित परिणाम यह है कि हम इस तरह से अनुकरण कर सकते है जो गणना के किसी भी चरण में अधिकांश सीएन कोशिकाओं का उपयोग करता है, एक <math>\mathcal{O}(N)</math> सिमुलेशन है।<ref>Arora and Barak, 2009, Exercises 4.1</ref>
-== सबसे छोटी मशीनें ==
+== सबसे छोटी यंत्रें ==
-जब एलन ट्यूरिंग एक सार्वभौमिक मशीन के विचार के साथ आए तो उनके दिमाग में सबसे सरल कंप्यूटिंग मॉडल था जो गणना किए जा सकने वाले सभी संभावित कार्यों की गणना करने के लिए पर्याप्त शक्तिशाली था। [[क्लाउड शैनन]] ने पहली बार 1956 में सबसे छोटी संभव सार्वभौमिक ट्यूरिंग मशीन खोजने का सवाल उठाया। उन्होंने दिखाया कि दो प्रतीक पर्याप्त थे जब तक कि पर्याप्त राज्यों (या इसके विपरीत) का उपयोग किया गया था, और यह कि प्रतीकों के लिए राज्यों का आदान-प्रदान करना हमेशा संभव था। उन्होंने यह भी दिखाया कि एक राज्य की कोई सार्वभौमिक ट्यूरिंग मशीन उपस्तिथ नहीं हो सकती।
+जब एलन ट्यूरिंग एक सार्वभौमिक यंत्र के विचार के साथ आए तो उनके दिमाग में सबसे सरल कंप्यूटिंग मॉडल था जो संभावित कार्यों की गणना करने के लिए पर्याप्त शक्तिशाली था। [[क्लाउड शैनन]] ने पहली बार 1956 में सबसे छोटी संभव सार्वभौमिक ट्यूरिंग यंत्र खोजने का सवाल उठाया था। उन्होंने दिखाया कि दो प्रतीक पर्याप्त थे जब तक कि पर्याप्त राज्यों का उपयोग किया गया था, और यह कि प्रतीकों के लिए राज्यों का आदान-प्रदान करना हमेशा संभव होता है। उन्होंने यह भी दिखाया कि एक राज्य की कोई सार्वभौमिक ट्यूरिंग यंत्र उपस्तिथ नहीं हो सकती है।
-[[मार्विन मिंस्की]] ने 1962 में 2-[[टैग प्रणाली]] का उपयोग करके 7-राज्य 4-प्रतीक सार्वभौमिक ट्यूरिंग मशीन की खोज की। टैग सिस्टम सिमुलेशन के इस दृष्टिकोण को विस्तारित करके [[यूरी रोगोज़िन]] और अन्य लोगों द्वारा अन्य छोटी सार्वभौमिक ट्यूरिंग मशीनों को तब से पाया गया है। यदि हम (एम, एन) एम राज्यों और एन प्रतीकों के साथ यूटीएम के वर्ग को निरूपित करते है, तो निम्नलिखित टपल पाए गए है: (15, 2), (9, 3), (6, 4), (5, 5), (4, 6), (3, 9), और (2, 18)।<ref>Rogozhin, 1996</ref><ref>Kudlek and Rogozhin, 2002</ref><ref>Neary and Woods, 2009</ref> रोगोज़िन की (4, 6) मशीन केवल 22 निर्देशों का उपयोग करती है, और कम वर्णनात्मक जटिलता का कोई मानक यूटीएम ज्ञात नहीं है।
+[[मार्विन मिंस्की]] ने 1962 में 2-[[टैग प्रणाली]] का उपयोग करके 7-राज्य 4-प्रतीक सार्वभौमिक ट्यूरिंग यंत्र की खोज की थी। टैग प्रणाली सिमुलेशन के इस दृष्टिकोण को विस्तारित करके [[यूरी रोगोज़िन]] और अन्य लोगों द्वारा अन्य छोटी सार्वभौमिक ट्यूरिंग यंत्रों को तब से पाया गया था। यदि हम (एम, एन) एम राज्यों और एन प्रतीकों के साथ यूटीएम के वर्ग को निरूपित करते है, तो निम्नलिखित टपल पाए जाते है: (15, 2), (9, 3), (6, 4), (5, 5), (4, 6), (3, 9), और (2, 18)।<ref>Rogozhin, 1996</ref><ref>Kudlek and Rogozhin, 2002</ref><ref>Neary and Woods, 2009</ref> रोगोज़िन की (4, 6) यंत्र केवल 22 निर्देशों का उपयोग करती है, और कम वर्णनात्मक जटिलता का कोई मानक यूटीएम ज्ञात नहीं होता है।
-चूँकि, मानक ट्यूरिंग मशीन मॉडल का सामान्यीकरण और भी छोटे यूटीएम को स्वीकार करता है। इस तरह का एक सामान्यीकरण ट्यूरिंग मशीन इनपुट के एक या दोनों तरफ एक असीम रूप से दोहराए जाने वाले शब्द की अनुमति देना है, इस प्रकार सार्वभौमिकता की परिभाषा को विस्तारित करना और क्रमशः "अर्ध-कमजोर" या "कमजोर" सार्वभौमिकता के रूप में जाना जाता है। [[नियम 110]] सेलुलर ऑटोमेटन का अनुकरण करने वाली छोटी कमजोर सार्वभौमिक ट्यूरिंग मशीनें (6, 2), (3, 3), और (2, 4) राज्य-प्रतीक जोड़े के लिए दी गई है।<ref>Neary and Woods, 2009b</ref> वोल्फ्राम की 2-राज्य 3-प्रतीक ट्यूरिंग मशीन के लिए सार्वभौमिकता का प्रमाण कुछ गैर-आवधिक प्रारंभिक विन्यासों की अनुमति देकर कमजोर सार्वभौमिकता की धारणा को आगे बढ़ाता है। मानक ट्यूरिंग मशीन मॉडल पर अन्य वेरिएंट जो छोटे यूटीएम उत्पन्न करते है, उनमें कई टेप वाली मशीनें या कई आयामों के टेप और एक परिमित ऑटोमेटन के साथ युग्मित मशीनें सम्मलित है।
+चूँकि, मानक ट्यूरिंग यंत्र मॉडल का सामान्यीकरण और भी छोटे यूटीएम को स्वीकार करता है। इस तरह का एक सामान्यीकरण ट्यूरिंग यंत्र इनपुट के एक या दोनों तरफ एक असीम रूप से दोहराए जाने वाले शब्द की अनुमति देता है, इस प्रकार सार्वभौमिकता की परिभाषा को विस्तारित करना और क्रमशः "अर्ध-कमजोर" या "कमजोर" सार्वभौमिकता के रूप में जाना जाता है। [[नियम 110]] सेलुलर ऑटोमेटन का अनुकरण करने वाली छोटी कमजोर सार्वभौमिक ट्यूरिंग यंत्रें (6, 2), (3, 3), और (2, 4) राज्य-प्रतीक जोड़े के लिए दिए गए थे।<ref>Neary and Woods, 2009b</ref> वोल्फ्राम की 2-राज्य 3-प्रतीक ट्यूरिंग यंत्र के लिए सार्वभौमिकता का प्रमाण कुछ गैर-आवधिक प्रारंभिक विन्यासों की अनुमति देकर कमजोर सार्वभौमिकता की धारणा को आगे बढ़ाते है। मानक ट्यूरिंग यंत्र मॉडल पर अन्य वेरिएंट जो छोटे यूटीएम उत्पन्न करते है, उनमें कई टेप वाली यंत्रें या कई आयामों के टेप और एक परिमित ऑटोमेटन के साथ युग्मित यंत्र सम्मलित होते है।
-== कोई आंतरिक स्थिति वाली मशीनें ==
+== कोई आंतरिक स्थिति वाली यंत्रें ==
-यदि एक ट्यूरिंग मशीन पर कई शीर्षों की अनुमति है तो किसी आंतरिक स्थिति की आवश्यकता नहीं है; जैसा कि "राज्यों" को टेप में एन्कोड किया जा सकता है। उदाहरण के लिए, 6 रंगों वाले टेप पर विचार करें: 0, 1, 2, 0A, 1A, 2A। 0,0,1,2,2A,0,2,1 जैसे टेप पर विचार करें जहां एक 3-सिर वाली ट्यूरिंग मशीन ट्रिपल (2,2A,0) पर स्थित है। फिर नियम किसी भी ट्रिपल को दूसरे ट्रिपल में बदलते है और 3-हेड्स को बाएं या दाएं घुमाते है। उदाहरण के लिए, नियम (2,2A,0) को (2,1,0) में बदल सकते है और सिर को बाईं ओर ले जा सकते है। इस प्रकार इस उदाहरण में, मशीन आंतरिक अवस्थाओं A और B के साथ 3-रंग की ट्यूरिंग मशीन की तरह काम करती है (बिना किसी अक्षर के)। 2-सिर वाली ट्यूरिंग मशीन का मामला बहुत समान है। इस प्रकार एक 2-सिर वाली ट्यूरिंग मशीन 6 रंगों के साथ यूनिवर्सल हो सकती है। यह ज्ञात नहीं है कि मल्टी-हेडेड ट्यूरिंग मशीन के लिए आवश्यक रंगों की सबसे छोटी संख्या क्या है या यदि 2-रंग वाली यूनिवर्सल ट्यूरिंग मशीन कई हेड्स के साथ संभव है। इसका अर्थ यह भी है कि [[पुनर्लेखन]] नियम ट्यूरिंग पूर्ण है क्योंकि ट्रिपल नियम पुनर्लेखन नियमों के बराबर है। एक अक्षर और उसके 8 पड़ोसियों के नमूने के साथ टेप को दो आयामों तक विस्तारित करना, केवल 2 रंगों की आवश्यकता होती है, उदाहरण के लिए, एक रंग को 110 जैसे लंबवत ट्रिपल पैटर्न में एन्कोड किया जा सकता है।
+यदि एक ट्यूरिंग यंत्र पर कई शीर्षों की अनुमति होती है तो किसी आंतरिक स्थिति की आवश्यकता नहीं होती है, जैसे कि "राज्यों" को टेप में एन्कोड किया जा सकता है। उदाहरण के लिए, 6 रंगों वाले टेप पर विचार करें: 0, 1, 2, 0A, 1A, 2A। 0,0,1,2,2A,0,2,1 जैसे टेप पर विचार करें जहां एक 3-सिर वाली ट्यूरिंग यंत्र ट्रिपल (2,2A,0) पर स्थित होते है। फिर नियम किसी भी ट्रिपल को दूसरे ट्रिपल में बदलते है और 3-हेड्स को बाएं या दाएं घुमाते है। उदाहरण के लिए, नियम (2,2A,0) को (2,1,0) में बदल सकते है और सिर को बाईं ओर ले जा सकते है। इस प्रकार इस उदाहरण में, यंत्र आंतरिक अवस्थाओं A और B के साथ 3-रंग की ट्यूरिंग यंत्र की तरह (बिना किसी अक्षर के) काम करती है । 2-सिर वाली ट्यूरिंग यंत्र का स्थिति बहुत समान होती है। इस प्रकार एक 2-सिर वाली ट्यूरिंग यंत्र 6 रंगों के साथ सार्वभौमिक हो सकती है। यह ज्ञात नहीं है कि बहु-हेडेड ट्यूरिंग यंत्र के लिए आवश्यक रंगों की सबसे छोटी संख्या क्या होती है या यदि 2-रंग वाली सार्वभौमिक ट्यूरिंग यंत्र कई हेड्स के साथ संभव होती है। इसका अर्थ यह भी है कि [[पुनर्लेखन]] नियम ट्यूरिंग पूर्ण होते है क्योंकि ट्रिपल नियम पुनर्लेखन नियमों के बराबर होते है। एक अक्षर और उसके 8 निकटतम के नमूने के साथ टेप को दो आयामों तक विस्तारित करना, केवल 2 रंगों की आवश्यकता होती है, उदाहरण के लिए, एक रंग को 110 जैसे लंबवत ट्रिपल नमूने में एन्कोड किया जा सकता है।
-== यूनिवर्सल-मशीन कोडिंग का उदाहरण ==
+== सार्वभौमिक-यंत्र कोडिंग का उदाहरण ==
-उन लोगों के लिए जो ट्यूरिंग निर्दिष्ट यूटीएम को प्रारूप करने की चुनौती का सामना करेंगे, कोपलैंड में डेविस द्वारा लेख देखें (2004:103ff)। डेविस मूल में त्रुटियों को ठीक करता है और दिखाता है कि एक नमूना रन कैसा दिखेगा। उनका प्रमाणित है कि उन्होंने एक (कुछ सरलीकृत) अनुकरण सफलतापूर्वक चलाया है।
+उन लोगों के लिए जो ट्यूरिंग निर्दिष्ट यूटीएम को प्रारूप करने की चुनौती का सामना करते है, कोपलैंड में डेविस द्वारा लेख देखें (2004:103ff)। डेविस मूल में त्रुटियों को ठीक करता है और दिखाता है कि एक नमूना रन कैसे करता है। उनका प्रमाणित है कि उन्होंने एक (कुछ सरलीकृत) अनुकरण सफलतापूर्वक चलाया है।
-निम्नलिखित उदाहरण ट्यूरिंग (1936) से लिया गया है। इस उदाहरण के बारे में अधिक जानकारी के लिए, [[ट्यूरिंग मशीन के उदाहरण]] देखें।
+निम्नलिखित उदाहरण ट्यूरिंग (1936) से लिया गया है। इस उदाहरण के बारे में अधिक जानकारी के लिए, [[ट्यूरिंग मशीन के उदाहरण|ट्यूरिंग यंत्र के उदाहरण]] देखें।
-ट्यूरिंग ने सात प्रतीकों {ए, सी, डी, आर, एल, एन,; } प्रत्येक 5-ट्यूपल को एनकोड करने के लिए; जैसा कि ट्यूरिंग मशीनों पर लेख में वर्णित है, इसके 5-टुपल्स केवल एन 1, एन 2 और एन 3 प्रकार के है। प्रत्येक "एम-कॉन्फ़िगरेशन" (निर्देश, स्थिति) की संख्या को "डी" द्वारा दर्शाया जाता है, जिसके बाद ए की एक स्ट्रिंग होती है, उदा। "क्यू3" = डीएएए। इसी तरह, यह रिक्त प्रतीकों को "डी", प्रतीक "0" को "डीसी", प्रतीक "1" को डीसीसी, आदि के रूप में एन्कोड करता है। प्रतीक "आर", "एल", और "एन" जैसा है वैसा ही रहता है।
+ट्यूरिंग ने सात प्रतीकों {ए, सी, डी, आर, एल, एन} प्रत्येक 5-ट्यूपल को एनकोड करने के लिए है, जैसा कि ट्यूरिंग यंत्रों के लेख में वर्णित है, इसके 5-टुपल्स केवल एन 1, एन 2 और एन 3 प्रकार के होते है। प्रत्येक "एम-विन्यास" (निर्देश, स्थिति) की संख्या को "डी" द्वारा दर्शाया जाता है, जिसके बाद ए की एक स्ट्रिंग होती है, "क्यू3" = डीएएए। इसी तरह, यह रिक्त प्रतीकों को "डी", प्रतीक "0" को "डीसी", प्रतीक "1" को डीसीसी, आदि के रूप में एन्कोड करता है। प्रतीक "आर", "एल", और "एन" जैसा है वैसा ही रहता है।
 निम्नलिखित तालिका में दिखाए गए अनुसार प्रत्येक 5-ट्यूपल को एन्कोडिंग के बाद एक स्ट्रिंग में "इकट्ठा" किया जाता है:
@@ Line 60: / Line 57: @@
 {|class="wikitable"
 |-
-! Current m{{nbh}}configuration
+! वर्तमान एम-विन्यास
-! Tape symbol
+! टेप प्रतीक
-! Print-operation
+! छपाई-कार्यवाही
-! Tape-motion
+! टेप-गति
-! Final m{{nbh}}configuration
+! अंतिम एम-विन्यास
-! Current m{{nbh}}configuration code
+! वर्तमान एम-विन्यास कोड
-! Tape symbol code
+! टेप प्रतीक कोड
-! Print-operation code
+! छपाई-कार्यवाही कोड
-! Tape-motion code
+! टेप-गति कोड
-! Final m{{nbh}}configuration code
+! अंतिम एम-विन्यास कोड
-! 5-tuple assembled code
+! 5-टुपल इकट्ठे कोड
 |-
 | q1
@@ Line 123: / Line 120: @@
 {{block indent| ''';'''DADDCRDAA''';'''DAADDRDAAA''';'''DAAADDCCRDAAAA''';'''DAAAADDRDA}}
-यह कोड उन्होंने वैकल्पिक वर्गों - "एफ-स्क्वायर" पर रखा - "ई-स्क्वायर" (जो मिटने के लिए उत्तरदायी है) को खाली छोड़ दिया। यू-मशीन के लिए टेप पर कोड की अंतिम असेंबली में दो विशेष प्रतीकों ("ई") को एक के बाद एक रखा जाता है, फिर कोड वैकल्पिक वर्गों पर अलग हो जाता है, और अंत में डबल-कोलन प्रतीक "::" (स्पष्टता के लिए यहां "।" के साथ दिखाया गया रिक्त स्थान):
+यह कोड उन्होंने वैकल्पिक वर्गों - "एफ-स्क्वायर" पर रखा - "ई-स्क्वायर" (जो मिटने के लिए उत्तरदायी है) को खाली छोड़ दिया जाता है। यू-यंत्र के लिए टेप पर कोड की अंतिम असेंबली में दो विशेष प्रतीकों ("ई") को एक के बाद एक रखा जाता है, फिर कोड वैकल्पिक वर्गों पर अलग हो जाता है, और अंत में डबल-कोलन प्रतीक "::" (स्पष्टता के लिए यहां "।" के साथ दिखाया गया रिक्त स्थान):
 {{block indent|ee.''';'''.D.A.D.D.C.R.D.A.A.''';'''.D.A.A.D.D.R.D.A.A.A.''';'''.D.A.A.A.D.D.C.C.R.D.A.A.A.A.''';'''.D.A.A.A.A.D.D.R.D.A.'''::'''......}}
-प्रतीकों को डिकोड करने के लिए यू-मशीन की एक्शन-टेबल (राज्य-संक्रमण तालिका) जिम्मेदार है। ट्यूरिंग की एक्शन टेबल मार्करों "यू", "वी", "एक्स", "वाई", "जेड" के साथ "चिह्नित प्रतीक" के दाईं ओर "ई-स्क्वायर" में रखकर अपनी जगह का ट्रैक रखती है - उदाहरण के लिए , वर्तमान निर्देश को चिह्नित करने के लिए z को ";" के दाईं ओर रखा गया है x वर्तमान "एम-कॉन्फ़िगरेशन" DAA के संबंध में स्थान रख रहा है। गणना की प्रगति के रूप में यू-मशीन की एक्शन टेबल इन प्रतीकों को चारों ओर शटल कर देगी (उन्हें मिटाकर अलग-अलग स्थानों पर रख देगी):
+प्रतीकों को डिकोड करने के लिए यू-यंत्र की कार्य-टेबल (राज्य-संक्रमण तालिका) जिम्मेदार होती है। ट्यूरिंग की कार्य टेबल मार्करों "यू", "वी", "एक्स", "वाई", "जेड" के साथ "चिह्नित प्रतीक" के दाईं ओर "ई-स्क्वायर" में रखकर अपनी जगह का ट्रैक रखती है। उदाहरण के लिए , वर्तमान निर्देश को चिह्नित करने के लिए z को ";" के दाईं ओर रखा गया है x वर्तमान "एम-विन्यास" DAA के संबंध में स्थान रख रहा है। गणना की प्रगति के रूप में यू-यंत्र की कार्य टेबल इन प्रतीकों को चारों ओर शटल कर देती है (उन्हें मिटाकर अलग-अलग स्थानों पर रख देती है):
 {{block indent|ee.''';''' .D.A.D.D.C.R.D.A.A. ''';''' '''z'''D.A.A'''x'''D.D.R.D.A.A.A.''';'''.D.A.A.A.D.D.C.C.R.D.A.A.A.A.''';'''.D.A.A.A.A.D.D.R.D.A.'''::'''......}}
-ट्यूरिंग की यू-मशीन के लिए एक्शन-टेबल बहुत सम्मलित है।
+ट्यूरिंग की यू-यंत्र के लिए कार्य-टेबल बहुत सम्मलित होते है।
-कई अन्य टिप्पणीकार (विशेष रूप से पेनरोज़ 1989) यूनिवर्सल मशीन के लिए निर्देशों को एन्कोड करने के तरीकों के उदाहरण प्रदान करते है। पेनरोज़ की तरह, अधिकांश टिप्पणीकार केवल बाइनरी प्रतीकों का उपयोग करते है, अर्थात केवल प्रतीक {0, 1}, या {रिक्त, चिह्न | }. पेनरोज़ और आगे जाता है और अपना पूरा यू-मशीन कोड लिखता है (पेनरोज़ 1989:71–73)। वह प्रमाणित करता है कि यह वास्तव में एक यू-मशीन कोड है, एक विशाल संख्या जो 1 और 0 के लगभग 2 पूर्ण पृष्ठों तक फैली हुई है। पोस्ट-ट्यूरिंग मशीन के लिए सरल एनकोडिंग में रुचि रखने वाले पाठकों के लिए डेविस इन स्टीन (स्टीन 1980:251ff) की चर्चा उपयोगी हो सकती है।
+कई अन्य टिप्पणीकार (विशेष रूप से पेनरोज़ 1989) सार्वभौमिक यंत्र के लिए निर्देशों को एन्कोड करने के तरीकों के उदाहरण प्रदान किये है। पेनरोज़ की तरह, अधिकांश टिप्पणीकार केवल बाइनरी प्रतीकों का उपयोग करते है, अर्थात केवल प्रतीक {0, 1}, या {रिक्त, चिह्न | } पेनरोज़ और आगे जाते है और अपना पूरा यू-यंत्र कोड लिखते है (पेनरोज़ 1989:71–73)। वह प्रमाणित करते है कि यह वास्तव में एक यू-यंत्र कोड होता, जिसमे एक विशाल संख्या होती है जो 1 और 0 के लगभग 2 पूर्ण पृष्ठों तक फैली हुई होती है। पोस्ट-ट्यूरिंग यंत्र के लिए सरल एनकोडिंग में रुचि रखने वाले पाठकों के लिए डेविस इन स्टीन (स्टीन 1980:251ff) की चर्चा उपयोगी होती है।
-Asperti और Ricciotti ने एक बहु-टेप UTM का वर्णन किया है, जो स्पष्ट रूप से इसकी पूर्ण क्रिया तालिका देने के अतिरिक्त बहुत ही सरल शब्दार्थ के साथ प्राथमिक मशीनों की रचना करके परिभाषित किया गया है। यह दृष्टिकोण पर्याप्त रूप से मॉड्यूलर था जिससे उन्हें [[पेंसिल]] प्रूफ असिस्टेंट में मशीन की शुद्धता को औपचारिक रूप से सिद्ध करने की अनुमति मिली।
+ऐस्पर्टी और रिक्कीओटी ने एक बहु-टेप यूटीएम का वर्णन किया है, जो स्पष्ट रूप से इसकी पूर्ण क्रिया तालिका देने के अतिरिक्त बहुत ही सरल शब्दार्थ के साथ प्राथमिक यंत्रों की रचना करके परिभाषित किया गया है। यह दृष्टिकोण पर्याप्त रूप से मॉड्यूलर है जिससे उन्हें [[पेंसिल]] प्रूफ सहायक में यंत्र की शुद्धता को औपचारिक रूप से सिद्ध करने की अनुमति मिलती है।
-== प्रोग्रामिंग ट्यूरिंग मशीनें ==
+== योजना ट्यूरिंग यंत्रें ==
-विभिन्न उच्च स्तरीय भाषाओं को ट्यूरिंग मशीन में संकलित करने के लिए प्रारुप किया गया है। उदाहरणों में [[लैकोनिक (प्रोग्रामिंग भाषा)]] और ट्यूरिंग मशीन डिस्क्रिप्टर सम्मलित है।<ref>{{Cite web|url=http://www.scottaaronson.com/blog/?p=2725|title=Shtetl-Optimized » Blog Archive » The 8000th Busy Beaver number eludes ZF set theory: new paper by Adam Yedidia and me|website=www.scottaaronson.com|date=3 May 2016|access-date=2016-12-29}}</ref><ref>{{Cite web|url=https://esolangs.org/wiki/Laconic|title=Laconic - Esolang|website=esolangs.org|access-date=2016-12-29}}</ref>
+विभिन्न उच्च स्तरीय भाषाओं को ट्यूरिंग यंत्र में संकलित करने के लिए प्रारुप किया गया है। उदाहरणों में [[लैकोनिक (प्रोग्रामिंग भाषा)|लैकोनिक (योजना भाषा)]] और ट्यूरिंग यंत्र वर्णनकर्ता सम्मलित होते है।<ref>{{Cite web|url=http://www.scottaaronson.com/blog/?p=2725|title=Shtetl-Optimized » Blog Archive » The 8000th Busy Beaver number eludes ZF set theory: new paper by Adam Yedidia and me|website=www.scottaaronson.com|date=3 May 2016|access-date=2016-12-29}}</ref><ref>{{Cite web|url=https://esolangs.org/wiki/Laconic|title=Laconic - Esolang|website=esolangs.org|access-date=2016-12-29}}</ref>
 == यह भी देखें ==
-* [[वैकल्पिक ट्यूरिंग मशीन]]
+* [[वैकल्पिक ट्यूरिंग मशीन|वैकल्पिक ट्यूरिंग यंत्र]]
-* [[वॉन न्यूमैन यूनिवर्सल कंस्ट्रक्टर]] - एक स्व-प्रतिकृति ट्यूरिंग मशीन बनाने का प्रयास<!-- see http://books.google.com/books?q=%22from+universal+turing+machines+to+self-reproduction%22&btnG=Search+Books -->
+* [[वॉन न्यूमैन यूनिवर्सल कंस्ट्रक्टर|वॉन न्यूमैन सार्वभौमिक कंस्ट्रक्टर]] - एक स्व-प्रतिकृति ट्यूरिंग यंत्र बनाने का प्रयास<!-- see http://books.google.com/books?q=%22from+universal+turing+machines+to+self-reproduction%22&btnG=Search+Books -->
 * क्लेन का टी विधेय - μ-पुनरावर्ती कार्यों के लिए एक समान अवधारणा
 * ट्यूरिंग पूर्णता
@@ Line 289: / Line 286: @@
 {{Authority control}}
-{{DEFAULTSORT:Universal Turing Machine}}[[Category: ट्यूरिंग मशीन]]
+{{DEFAULTSORT:Universal Turing Machine}}
-[[Category: Machine Translated Page]]
+[[Category:CS1|Universal Turing Machine]]
-[[Category:Created On 03/02/2023]]
+[[Category:Created On 03/02/2023|Universal Turing Machine]]
+[[Category:Machine Translated Page|Universal Turing Machine]]
+[[Category:Pages with script errors|Universal Turing Machine]]
+[[Category:Templates Vigyan Ready|Universal Turing Machine]]
+[[Category:ट्यूरिंग मशीन|Universal Turing Machine]]

Anonymous

Search

यूनिवर्सल ट्यूरिंग मशीन: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 17:24, 15 February 2023

Contents

परिचय

संग्रहीत कार्यक्रम कंप्यूटर

गणितीय सिद्धांत

दक्षता

सबसे छोटी यंत्रें

कोई आंतरिक स्थिति वाली यंत्रें

सार्वभौमिक-यंत्र कोडिंग का उदाहरण

योजना ट्यूरिंग यंत्रें

यह भी देखें

संदर्भ

बाहरी कड़ियाँ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

यूनिवर्सल ट्यूरिंग मशीन: Difference between revisions

Latest revision as of 17:24, 15 February 2023

परिचय

संग्रहीत कार्यक्रम कंप्यूटर

गणितीय सिद्धांत

दक्षता

सबसे छोटी यंत्रें

कोई आंतरिक स्थिति वाली यंत्रें

सार्वभौमिक-यंत्र कोडिंग का उदाहरण

योजना ट्यूरिंग यंत्रें

यह भी देखें

संदर्भ

बाहरी कड़ियाँ

Navigation

Wiki tools

Page tools

Other projects

Categories