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

"सार्वभौमिक मशीन" 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-ट्यूपल को एन्कोडिंग के बाद एक स्ट्रिंग में "इकट्ठा" किया जाता है:

Current m‑configuration	Tape symbol	Print-operation	Tape-motion	Final m‑configuration	Current m‑configuration code	Tape symbol code	Print-operation code	Tape-motion code	Final m‑configuration code	5-tuple assembled code
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.