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

"सार्वभौमिक यंत्र" redirects here. For other uses, see सार्वभौमिक यंत्र (disambiguation).

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

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

परिचय

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

"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."

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

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

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

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

The first interpretive routine may be said to be the "Universal Turing Machine" ... Interpretive routines in the conventional sense were mentioned by John Mauchly in his lectures at the 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)।

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

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

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

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

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

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

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

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

दक्षता

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

उपरोक्त एन्कोडिंग से शुरू करते हुए, 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)। Rogozhin की (4, 6) मशीन केवल 22 निर्देशों का उपयोग करती है, और कम वर्णनात्मक जटिलता का कोई मानक UTM ज्ञात नहीं है।

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

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

यदि एक ट्यूरिंग मशीन पर कई शीर्षों की अनुमति है तो किसी आंतरिक स्थिति की आवश्यकता नहीं है; जैसा कि राज्यों को टेप में एन्कोड किया जा सकता है। उदाहरण के लिए, 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-ट्यूपल्स केवल N1, N2 और N3 प्रकार के हैं। प्रत्येक एम की संख्या‑कॉन्फ़िगरेशन (निर्देश, स्थिति) को डी द्वारा दर्शाया गया है जिसके बाद ए की एक एकल स्ट्रिंग है, उदा। क्यू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.::......

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

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.::......

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

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

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

प्रोग्रामिंग ट्यूरिंग मशीन

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

यह भी देखें

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

संदर्भ

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.