यूनिवर्सल ट्यूरिंग मशीन

"सार्वभौमिक मशीन" redirects here. For other uses, see सार्वभौमिक मशीन (disambiguation).

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

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

परिचय

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

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

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

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

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

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

पहली व्याख्यात्मक दिनचर्या को "यूनिवर्सल ट्यूरिंग मशीन" कहा जा सकता है ... पारंपरिक अर्थों में व्याख्यात्मक दिनचर्या का उल्लेख जॉन मौचली ने मूर] में अपने व्याख्यान में किया था। स्कूल 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)$ सिमुलेशन है। समय-जटिलता के अतिरिक्त अंतरिक्ष-जटिलता के लिए एक संबंधित परिणाम यह है कि हम इस तरह से अनुकरण कर सकते है जो गणना के किसी भी चरण में अधिकांश सीएन कोशिकाओं का उपयोग करता है, एक ${\mathcal {O}}(N)$ सिमुलेशन है।

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

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

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

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

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

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

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

यह भी देखें

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

संदर्भ

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.