ट्यूरिंग मशीन समकक्ष: Difference between revisions
No edit summary |
No edit summary |
||
| (7 intermediate revisions by 3 users not shown) | |||
| Line 2: | Line 2: | ||
{{turing}} | {{turing}} | ||
[[ट्यूरिंग मशीन|'''ट्यूरिंग मशीन''']] हैपोथेटिकल कंप्यूटिंग डिवाइस है, जिसकी कल्पना | [[ट्यूरिंग मशीन|'''ट्यूरिंग मशीन''']] हैपोथेटिकल कंप्यूटिंग डिवाइस है, जिसकी कल्पना सर्वप्रथम [[एलन ट्यूरिंग]] ने 1936 में की थी। ट्यूरिंग मशीन नियमों की सीमित टेबल के अनुसार टेप की संभावित इनफिनिट स्ट्रिप पर प्रतीकों में परिवर्तित करती हैं और वह कंप्यूटर एल्गोरिदम की धारणा के लिए सैद्धांतिक आदान-प्रदान करती हैं। | ||
जबकि निम्नलिखित में से किसी भी मॉडल में सिंगल-टेप, वन-वे इनफिनिट, मल्टी-सिंबल ट्यूरिंग-मशीन मॉडल की तुलना में अधिक शक्ति नहीं दिखाई गई है, उनके लेखकों ने उन्हें परिभाषित किया और प्रश्नों की जांच करने और समस्याओं को अधिक सरलता से हल करने के लिए उपयोग किया | जबकि निम्नलिखित में से किसी भी मॉडल में सिंगल-टेप, वन-वे इनफिनिट, मल्टी-सिंबल ट्यूरिंग-मशीन मॉडल की तुलना में अधिक शक्ति नहीं दिखाई गई है, उनके लेखकों ने उन्हें परिभाषित किया और प्रश्नों की जांच करने और समस्याओं को अधिक सरलता से हल करने के लिए उपयोग किया था। यदि वह ट्यूरिंग के a-मशीन मॉडल के साथ बने रहते है। | ||
== ट्यूरिंग मशीन मॉडल के समतुल्य मशीन == | == ट्यूरिंग मशीन मॉडल के समतुल्य मशीन == | ||
==== ट्यूरिंग तुल्यता ==== | ==== ट्यूरिंग तुल्यता ==== | ||
विभिन्न मशीन जिनके | विभिन्न मशीन जिनके विषय में सोचा जा सकता है कि उनमें साधारण सार्वभौमिक ट्यूरिंग मशीन की तुलना में अधिक कम्प्यूटेशनल क्षमता है, उन्हें दिखाया जा सकता है कि उनमें अधिक शक्ति नहीं है।<ref>{{cite book| author = [[John Hopcroft]] and [[Jeffrey Ullman]]| year = 1979| title = ऑटोमेटा सिद्धांत, भाषाएँ और संगणना का परिचय| publisher = Addison–Wesley, Reading Mass| edition = 1st| isbn = 0-201-02988-X| url-access = registration| url = https://archive.org/details/introductiontoau00hopc}}</ref> वह संभवतः तेजी से गणना कर सकते हैं या कम मेमोरी का उपयोग कर सकते हैं या उनका निर्देश समुच्चय छोटा हो सकता है, किन्तु वह अधिक शक्तिशाली विधि से गणना नहीं कर सकते (अर्थात अधिक गणितीय कार्य)। (चर्च-ट्यूरिंग थीसिस इसे सत्य मानती है: जो कुछ भी "गणना" किया जा सकता है उसकी गणना कुछ ट्यूरिंग मशीन द्वारा की जा सकती है।) | ||
==== अनुक्रमिक-मशीन मॉडल' ==== | ==== अनुक्रमिक-मशीन मॉडल' ==== | ||
| Line 16: | Line 16: | ||
==== ट्यूरिंग का ''ए''-मशीन मॉडल ==== | ==== ट्यूरिंग का ''ए''-मशीन मॉडल ==== | ||
ट्यूरिंग की मशीन (जैसा कि उन्होंने इसे कहा था) बाएँ किनारे वाली, दाएँ किनारे वाली इनफिनिट थी। उन्होंने बाएं छोर को चिह्नित करने के लिए əə प्रतीक प्रदान किए थे। टेप प्रतीकों की सीमित संख्या की अनुमति थी। निर्देश (यदि सार्वभौमिक मशीन) | ट्यूरिंग की मशीन (जैसा कि उन्होंने इसे कहा था) बाएँ किनारे वाली, दाएँ किनारे वाली इनफिनिट थी। उन्होंने बाएं छोर को चिह्नित करने के लिए əə प्रतीक प्रदान किए थे। टेप प्रतीकों की सीमित संख्या की अनुमति थी। निर्देश (यदि सार्वभौमिक मशीन) और इनपुट और आउट केवल F-स्क्वायर पर लिखे गए थे और मार्कर E-स्क्वायर पर दिखाई देने थे। संक्षेप में उन्होंने अपनी मशीन को दो टेपों में विभाजित किया जो सदैव साथ घूमते थे। निर्देश 5-टुपल्स नामक सारणीबद्ध रूप में प्रकट हुए और क्रमिक रूप से निष्पादित नहीं किए गए थे। | ||
=== प्रतिबंधित प्रतीकों और/या प्रतिबंधित निर्देशों वाली एकल-टेप मशीन === | === प्रतिबंधित प्रतीकों और/या प्रतिबंधित निर्देशों वाली एकल-टेप मशीन === | ||
निम्नलिखित मॉडल एकल टेप ट्यूरिंग मशीन हैं, किन्तु (i) प्रतिबंधित टेप प्रतीकों {चिह्न, रिक्त}, और/या (ii) अनुक्रमिक, कंप्यूटर-जैसे निर्देश, और | यह निम्नलिखित मॉडल एकल टेप ट्यूरिंग मशीन हैं, किन्तु (i) प्रतिबंधित टेप प्रतीकों {चिह्न, रिक्त}, और/या (ii) अनुक्रमिक, कंप्यूटर-जैसे निर्देश, और (iii) पूर्णतः परमाणुकृत मशीन-क्रियाओं से प्रतिबंधित हैं। | ||
==== पोस्ट का सूत्रीकरण 1 गणना का मॉडल ==== | ==== पोस्ट का सूत्रीकरण 1 गणना का मॉडल ==== | ||
{{details|पोस्ट-ट्यूरिंग मशीन}} | {{details|पोस्ट-ट्यूरिंग मशीन}} | ||
[[एमिल पोस्ट]] ने कम्प्यूटेशनल प्रक्रिया के स्वतंत्र विवरण में, टेप पर चिह्नों के समकक्ष बाइनरी सेट के लिए अनुमत प्रतीकों को कम कर दिया है। उन्होंने टेप की धारणा को एक-पक्षीय इनफिनिट से दाईं ओर इनफिनिट कमरों के | [[एमिल पोस्ट]] ने कम्प्यूटेशनल प्रक्रिया के स्वतंत्र विवरण में, टेप पर चिह्नों के समकक्ष बाइनरी सेट के लिए अनुमत प्रतीकों को कम कर दिया है। उन्होंने टेप की धारणा को एक-पक्षीय इनफिनिट से दाईं ओर इनफिनिट कमरों के समुच्चय में परिवर्तित कर दिया था| जिनमें से प्रत्येक में दोनों दिशाओं में पेपर की शीट थी। इस प्रकार उन्होंने ट्यूरिंग 5-टुपल्स को 4-टुपल्स में विभाजित कर दिया था मोशन निर्देश प्रिंट/इरेज़ निर्देशों से प्रथक चूँकि उनका 1936 मॉडल इस विषय में अस्पष्ट है, पोस्ट के 1947 मॉडल को अनुक्रमिक निर्देश निष्पादन की आवश्यकता नहीं थी। | ||
उनका अत्यधिक सरल मॉडल किसी भी ट्यूरिंग मशीन का अनुकरण कर सकता है | उनका अत्यधिक सरल मॉडल किसी भी ट्यूरिंग मशीन का अनुकरण कर सकता है और चूँकि उनके 1936 फॉर्मूलेशन 1 में प्रोग्राम या मशीन शब्द का उपयोग नहीं किया गया है, यह प्रभावी रूप से बहुत ही मौलिक प्रोग्राम योग्य कंप्यूटर और संबंधित [[प्रोग्रामिंग भाषा|प्रोग्रामिंग]] लैंग्वेज का फॉर्मूलेशन है, जिसमें बॉक्स अनबाउंड बिटस्ट्रिंग मेमोरी के रूप में कार्य करते हैं और प्रोग्राम का निर्माण करने वाले निर्देशों का समुच्चय प्रयुक्त होते है। | ||
==== वांग मशीन ==== | ==== वांग मशीन ==== | ||
{{details|वांग बी-मशीन}} | {{details|वांग बी-मशीन}} | ||
प्रभावशाली पेपर में, हाओ वांग (अकादमिक) ने पोस्ट की पोस्ट-ट्यूरिंग मशीन 1936: पोस्ट मॉडल को उन मशीनों में परिवर्तित कर दिया था जो अभी भी दो-पक्षीय इनफिनिट बाइनरी टेप का उपयोग करते हैं, किन्तु जिनके निर्देश सरल हैं पोस्ट के निर्देशों के परमाणु अवयव होने के सम्बन्ध में और डिफ़ॉल्ट रूप से क्रमिक रूप से निष्पादित होते हैं ( कंप्यूटर प्रोग्राम की तरह)। उनका घोषित मुख्य उद्देश्य, ट्यूरिंग के सिद्धांत के विकल्प के रूप में | प्रभावशाली पेपर में, हाओ वांग (अकादमिक) ने पोस्ट की पोस्ट-ट्यूरिंग मशीन 1936: पोस्ट मॉडल को उन मशीनों में परिवर्तित कर दिया था जो अभी भी दो-पक्षीय इनफिनिट बाइनरी टेप का उपयोग करते हैं, किन्तु जिनके निर्देश सरल हैं, पोस्ट के निर्देशों के परमाणु अवयव होने के सम्बन्ध में और डिफ़ॉल्ट रूप से क्रमिक रूप से निष्पादित होते हैं ( कंप्यूटर प्रोग्राम की तरह)। उनका घोषित मुख्य उद्देश्य, ट्यूरिंग के सिद्धांत के विकल्प के रूप में ऐसा सिद्धांत प्रस्तुत करना था, जो मूलभूत संचालन में अधिक प्रभावकारी होता है। उनके परिणाम विभिन्न प्रकार की ऐसी मशीनों के प्रोग्राम फॉर्मूलेशन थे, जिनमें निर्देश-समुच्चय के साथ 5-निर्देश वांग डब्ल्यू-मशीन भी सम्मिलित थी | ||
: { शिफ्ट-बाएं, शिफ्ट-दाएं, मार्क-स्क्वायर, इरेज-स्क्वायर, जंप-इफ-स्क्वायर-चिह्नित-से xxx } | : { शिफ्ट-बाएं, शिफ्ट-दाएं, मार्क-स्क्वायर, इरेज-स्क्वायर, जंप-इफ-स्क्वायर-चिह्नित-से xxx } | ||
और निर्देश- | और निर्देश-समुच्चय के साथ उनकी सबसे कठोरता से कम की गई 4-निर्देश [[वांग बी-मशीन]] (बेसिक के लिए बी) | ||
: { शिफ्ट-बाएं, शिफ्ट-दाएं, मार्क-स्क्वायर, जंप-इफ-स्क्वायर-चिह्नित-से xxx } | : { शिफ्ट-बाएं, शिफ्ट-दाएं, मार्क-स्क्वायर, जंप-इफ-स्क्वायर-चिह्नित-से xxx } | ||
| Line 43: | Line 43: | ||
विभिन्न लेखकों ने पश्चात में वांग द्वारा विचार की गई मशीनों के वेरिएंट प्रस्तुत किए: | विभिन्न लेखकों ने पश्चात में वांग द्वारा विचार की गई मशीनों के वेरिएंट प्रस्तुत किए: | ||
मिन्स्की ने (मल्टी-टेप) काउंटर मशीन मॉडल के अपने | मिन्स्की ने (मल्टी-टेप) काउंटर मशीन मॉडल के अपने संस्करण के साथ वांग की धारणा को विकसित किया था| इस प्रकार जो भिन्न-भिन्न सिरों की शिफ्ट-बाएं और शिफ्ट-दाएं गति की अनुमति देता है, किन्तु बिल्कुल भी मुद्रण नहीं करता है।<ref name="Marvin" /> इस स्थिति में टेप बाएं किनारे वाले होंगे, प्रत्येक किनारे पर अंत को संकेत करने के लिए चिन्ह होगा। वह इसे ही टेप तक सीमित करने में सक्षम था, किन्तु अधिक सरल {शिफ्ट-बाएं = कमी, शिफ्ट-दाएं = इन्क्रीमेंट} के अतिरिक्त गुणन और विभाजन के समतुल्य मल्टी-टेप-स्क्वायर गति को प्रयुक्त करने की मूल्य पर प्रयुक्त किया जाता है। | ||
डेविस ने वांग द्वारा विचार की गई मशीनों में से में स्पष्ट एचएएलटी निर्देश जोड़कर निर्देश- | डेविस ने वांग द्वारा विचार की गई मशीनों में से में स्पष्ट एचएएलटी निर्देश जोड़कर निर्देश-समुच्चय के साथ मॉडल का उपयोग किया था | ||
: {शिफ्ट-बाएं, शिफ्ट-दाएं, इरेज, चिह्नित करें, वर्ग-चिह्नित xxx पर जम्प, xxx पर जम्प, रुकें } | : {शिफ्ट-बाएं, शिफ्ट-दाएं, इरेज, चिह्नित करें, वर्ग-चिह्नित xxx पर जम्प, xxx पर जम्प, रुकें } | ||
| Line 54: | Line 54: | ||
{{details|पी"}} | {{details|पी"}} | ||
मूलभूत संचालन में प्रभावकारी ट्यूरिंग-समतुल्य सिद्धांत की | मूलभूत संचालन में प्रभावकारी ट्यूरिंग-समतुल्य सिद्धांत की खोज करने के लिए वांग की परियोजना को ध्यान में रखते हुए और बिना नियम जम्प से बचने की इच्छा रखते हुए, उल्लेखनीय सैद्धांतिक लैंग्वेज 1964 में कोराडो बोहम द्वारा प्रयुक्त की गई 4-निर्देश लैंग्वेज पी है - [[ट्यूरिंग-पूर्ण]] सिद्ध होने वाली पहली गोटो-कम अनिवार्य [[संरचित प्रोग्रामिंग|स्ट्रक्चर्ड प्रोग्रामिंग]] लैंग्वेज होती है। | ||
=== मल्टी-टेप ट्यूरिंग मशीन === | === मल्टी-टेप ट्यूरिंग मशीन === | ||
{{details|मल्टीटेप ट्यूरिंग मशीन}} | {{details|मल्टीटेप ट्यूरिंग मशीन}} | ||
व्यावहारिक विश्लेषण में | व्यावहारिक विश्लेषण में विभिन्न प्रकार की मल्टी-टेप ट्यूरिंग मशीनों का अधिकांशतः उपयोग किया जाता है। मल्टी-टेप मशीन सिंगल-टेप मशीनों के समान होती हैं, किन्तु कुछ स्थिर k संख्या में स्वतंत्र टेप होते हैं। | ||
===नियतात्मक और गैर-नियतात्मक ट्यूरिंग मशीन=== | ===नियतात्मक और गैर-नियतात्मक ट्यूरिंग मशीन=== | ||
{{details|गैर-नियतात्मक ट्यूरिंग मशीन}} | {{details|गैर-नियतात्मक ट्यूरिंग मशीन}} | ||
यदि क्रिया टेबल में प्रतीक और स्थिति के प्रत्येक संयोजन के लिए अधिकतम प्रविष्टि है | यदि क्रिया टेबल में प्रतीक और स्थिति के प्रत्येक संयोजन के लिए अधिकतम प्रविष्टि है| तब मशीन नियतात्मक ट्यूरिंग मशीन (डीटीएम) है। यदि क्रिया टेबल में प्रतीक और स्थिति के संयोजन के लिए एकाधिक प्रविष्टियाँ हैं इस प्रकार मशीन गैर-नियतात्मक ट्यूरिंग मशीन (एनडीटीएम) है। यह दोनों कम्प्यूटेशनल रूप से समतुल्य हैं, अर्थात किसी भी एनडीटीएम को डीटीएम (और इसके विपरीत) में परिवर्तित करना संभव है, चूँकि उनके निकट सामान्यतः भिन्न-भिन्न रनटाइम होते हैं। इसे निर्माण के माध्यम से सिद्ध किया जा सकता है। | ||
=== ओब्लिवियस ट्यूरिंग मशीन === | === ओब्लिवियस ट्यूरिंग मशीन === | ||
ओब्लिवियस ट्यूरिंग मशीन ट्यूरिंग मशीन है, जहां प्रत्येक इनपुट लंबाई के लिए, विभिन्न शीर्षों की गति समय का निश्चित कार्य है, जो इनपुट से स्वतंत्र है। दूसरे शब्दों में | ओब्लिवियस ट्यूरिंग मशीन ट्यूरिंग मशीन है, जहां प्रत्येक इनपुट लंबाई के लिए, विभिन्न शीर्षों की गति समय का निश्चित कार्य है, जो इनपुट से स्वतंत्र है। दूसरे शब्दों में पूर्व निर्धारित क्रम होता है, जिसमें विभिन्न टेपों को स्कैन किया जाता है, उन्नत किया जाता है और लिखा जाता है। इस प्रकार किसी भी स्टेज पर टेप पर लिखे गए वास्तविक मान उस लंबाई के प्रत्येक इनपुट के लिए अभी भी भिन्न हो सकते हैं। पिप्पेंजर और फिशर ने दिखाया कि कोई भी गणना जो मल्टी-टेप ट्यूरिंग मशीन द्वारा एन स्टेज में की जा सकती है, उसे ओब्लिवियस दो-टेप ट्यूरिंग मशीन द्वारा n स्टेज में किया जा सकता है। {{tmath|O(n \log n)}} स्टेज <ref>{{Citation|first1=Nicholas|last1=Pippenger|authorlink=Nick Pippenger|first2=Michael J.|last2=Fischer|authorlink2=Michael J. Fischer|title=Relations Among Complexity Measures|journal=[[Journal of the ACM]]|year=1979|volume=26|issue=3|pages=361–381|doi=10.1145/322123.322138|s2cid=2432526 |url=http://dl.acm.org/citation.cfm?id=322138 }} | ||
</ref> ऑब्लिवियस मशीनें कॉम्बिनेशन लॉजिक परिपथ के साथ स्टेज-वार रैखिक फैशन में मेल खाती हैं, जब संक्रमण टेबल की | </ref> ऑब्लिवियस मशीनें कॉम्बिनेशन लॉजिक परिपथ के साथ स्टेज-वार रैखिक फैशन में मेल खाती हैं, जब संक्रमण टेबल की काम्प्लेक्स को स्थिर माना जाता है। इस प्रकार आकार {{tmath|O(n \log n)}} और डेप्थ {{tmath|O(n)}} में परिपथ समस्याओं के रूप में गणना करना संभव है (परिपथ काम्प्लेक्स देखें)। यह कुक और लेविन के मूल {{tmath|O(n^3)}} परिणाम में सुधार करता है। | ||
== रजिस्टर मशीन मॉडल == | == रजिस्टर मशीन मॉडल == | ||
{{details|रजिस्टर मशीन}} | {{details|रजिस्टर मशीन}} | ||
[[पीटर वैन एम्डे बोस]] इस प्रकार की सभी मशीनों को वर्ग, रजिस्टर मशीन में सम्मिलित करते हैं।<ref name="Boas" /> चूँकि, ऐतिहासिक रूप से साहित्य ने इस समूह के सबसे मौलिक सदस्य अर्थात काउंटर मशीन को रजिस्टर मशीन भी कहा | [[पीटर वैन एम्डे बोस]] इस प्रकार की सभी मशीनों को वर्ग, रजिस्टर मशीन में सम्मिलित करते हैं।<ref name="Boas" /> चूँकि, ऐतिहासिक रूप से साहित्य ने इस समूह के सबसे मौलिक सदस्य अर्थात काउंटर मशीन को रजिस्टर मशीन भी कहा है और काउंटर मशीन के सबसे मौलिक आगमन को कभी-कभी मिन्स्की मशीन कहा जाता है। | ||
=== काउंटर मशीन, जिसे रजिस्टर मशीन मॉडल भी कहा जाता है === | === काउंटर मशीन, जिसे रजिस्टर मशीन मॉडल भी कहा जाता है === | ||
{{details|काउंटर मशीन}} | {{details|काउंटर मशीन}} | ||
मौलिक मॉडल रजिस्टर मशीन | मौलिक मॉडल रजिस्टर मशीन मल्टीटेप 2-प्रतीक पोस्ट-ट्यूरिंग मशीन है| जिसका व्यवहार प्रतिबंधित है, इसलिए इसके टेप साधारण काउंटर के समान कार्य करते हैं। | ||
मेल्ज़ाक, लैम्बेक और मिन्स्की के समय तक कंप्यूटर प्रोग्राम की धारणा ने पृथक प्रकार की सरल मशीन का निर्माण किया था, इस प्रकार जिसमें पोस्ट-ट्यूरिंग टेप से विभिन्न बाएं छोर वाले टेप काटे गए थे। सभी स्थितियों में मॉडल केवल दो टेप प्रतीकों {चिह्न, रिक्त} की अनुमति देते हैं।<ref name="Marvin" /> | मेल्ज़ाक, लैम्बेक और मिन्स्की के समय तक कंप्यूटर प्रोग्राम की धारणा ने पृथक प्रकार की सरल मशीन का निर्माण किया था, इस प्रकार जिसमें पोस्ट-ट्यूरिंग टेप से विभिन्न बाएं छोर वाले टेप काटे गए थे। सभी स्थितियों में मॉडल केवल दो टेप प्रतीकों {चिह्न, रिक्त} की अनुमति देते हैं।<ref name="Marvin" /> | ||
| Line 85: | Line 85: | ||
कुछ वर्जन धनात्मक पूर्णांकों को केवल रजिस्टर में अनुमत अंकों की स्ट्रिंग/स्टैक के रूप में दर्शाते हैं (अर्थात बाएं किनारे वाला टेप), और गिनती 0 द्वारा दर्शाए गए रिक्त टेप के रूप में मिन्स्की ने अपने मॉडल को प्रत्येक टेप के बाएं छोर पर अनिवार्य एकल चिह्न प्रदान करने की मूल्य पर प्रिंट निर्देश को समाप्त कर दिया था।<ref name="Marvin" /> | कुछ वर्जन धनात्मक पूर्णांकों को केवल रजिस्टर में अनुमत अंकों की स्ट्रिंग/स्टैक के रूप में दर्शाते हैं (अर्थात बाएं किनारे वाला टेप), और गिनती 0 द्वारा दर्शाए गए रिक्त टेप के रूप में मिन्स्की ने अपने मॉडल को प्रत्येक टेप के बाएं छोर पर अनिवार्य एकल चिह्न प्रदान करने की मूल्य पर प्रिंट निर्देश को समाप्त कर दिया था।<ref name="Marvin" /> | ||
इस मॉडल में सिंगल-एंडेड टेप-एज़-रजिस्टर को काउंटर के रूप में माना जाता है, उनके निर्देश केवल दो तक सीमित होते हैं (या यदि टेस्ट/डिक्रीमेंट निर्देश को परमाणुकृत किया जाता है | इस मॉडल में सिंगल-एंडेड टेप-एज़-रजिस्टर को काउंटर के रूप में माना जाता है, उनके निर्देश केवल दो तक सीमित होते हैं (या यदि टेस्ट/डिक्रीमेंट निर्देश को परमाणुकृत किया जाता है तब तीन)। दो सामान्य निर्देश समुच्चय निम्नलिखित हैं: | ||
:(1): { INC ( r ), DEC ( r ), JZ ( r,z ) }, अर्थात। | :(1): { INC ( r ), DEC ( r ), JZ ( r,z ) }, अर्थात। | ||
::{रजिस्टर #r की कंटेंट में इन्क्रीमेंट; रजिस्टर #r की कमी | ::{रजिस्टर #r की कंटेंट में इन्क्रीमेंट; रजिस्टर #r की कंटेंट में कमी ; यदि #r=शून्य की कंटेंट है| तब निर्देश #z पर जाएं} | ||
:(2): { CLR ( r ); INC ( r ); JE ( r<sub>i</sub>, r<sub>j</sub>, z ) }, i.e., अर्थात्। | :(2): { CLR ( r ); INC ( r ); JE ( r<sub>i</sub>, r<sub>j</sub>, z ) }, i.e., अर्थात्। | ||
::{रजिस्टर | ::{रजिस्टर r की स्पष्ट कंटेंट; r की कंटेंट में इन्क्रीमेंट; r<sub>i</sub> को r<sub>j</sub> की कंटेंट की तुलना करें और यदि समान है| तब निर्देश z पर जाएं} | ||
यद्यपि उनका मॉडल इस सरल विवरण से अधिक सम्मिश्र है, मेल्ज़ाक पेब्बल मॉडल ने बहु-विषयकता की अनुमति देने के लिए काउंटर की इस धारणा को बढ़ाया | यद्यपि उनका मॉडल इस सरल विवरण से अधिक सम्मिश्र है, मेल्ज़ाक पेब्बल मॉडल ने बहु-विषयकता की अनुमति देने के लिए काउंटर की इस धारणा को बढ़ाया था। इस स्थिति में पेब्बल जोड़ता और घटाता है। | ||
=== रैंडम-एक्सेस मशीन (रैम) मॉडल === | === रैंडम-एक्सेस मशीन (रैम) मॉडल === | ||
| Line 104: | Line 104: | ||
| date=September 1961 | | date=September 1961 | ||
| pages=279–293 | | pages=279–293 | ||
| doi=10.4153/CMB-1961-031-9 | doi-access=free}}</ref> (i) अप्रत्यक्ष संबोधन के बिना वह सरलता से यह नहीं दिखा पाएगा कि मॉडल [[ट्यूरिंग पूर्णता]] है, (ii) प्रोग्राम और रजिस्टर भिन्न-भिन्न स्थानों पर थे, इसलिए प्रोग्राम को स्व-संशोधित करना सरल नहीं होगा। जब मेल्ज़ाक ने अपने मॉडल में अप्रत्यक्ष संबोधन जोड़ा | | doi=10.4153/CMB-1961-031-9 | doi-access=free}}</ref> (i) अप्रत्यक्ष संबोधन के बिना वह सरलता से यह नहीं दिखा पाएगा कि मॉडल [[ट्यूरिंग पूर्णता]] है, (ii) प्रोग्राम और रजिस्टर भिन्न-भिन्न स्थानों पर थे, इसलिए प्रोग्राम को स्व-संशोधित करना सरल नहीं होगा। जब मेल्ज़ाक ने अपने मॉडल में अप्रत्यक्ष संबोधन जोड़ा, तब उन्होंने रैंडम एक्सेस मशीन मॉडल बनाया था। | ||
(चूँकि | (चूँकि निर्देशों की गोडेल नंबरिंग के साथ मिन्स्की ने प्रमाण प्रस्तुत किया कि ऐसी नंबरिंग के साथ सामान्य [[रिकर्सन (कंप्यूटर विज्ञान)]] वास्तव में संभव था| वह प्रमाण प्रस्तुत करता है कि μ रिकर्सन वास्तव में संभव है<ref name="Marvin">[[Marvin Minsky]], ''Computation: Finite and Infinite Machines'', Prentice–Hall, Inc., N.J., 1967. See Chapter 8, Section 8.2 "Unsolvability of the Halting Problem."</ref>). | ||
आरएएसपी मॉडल के विपरीत, रैम मॉडल मशीन के कार्यों को उसके निर्देशों को संशोधित करने की अनुमति नहीं देता है। कभी-कभी मॉडल बिना किसी संचायक के केवल रजिस्टर-टू-रजिस्टर पर कार्य करता है, किन्तु अधिकांश मॉडलों में संचायक सम्मिलित होता है। | आरएएसपी मॉडल के विपरीत, रैम मॉडल मशीन के कार्यों को उसके निर्देशों को संशोधित करने की अनुमति नहीं देता है। कभी-कभी मॉडल बिना किसी संचायक के केवल रजिस्टर-टू-रजिस्टर पर कार्य करता है, किन्तु अधिकांश मॉडलों में संचायक सम्मिलित होता है। | ||
| Line 115: | Line 115: | ||
* रैम: जोड़ और घटाव के साथ मानक मॉडल | * रैम: जोड़ और घटाव के साथ मानक मॉडल | ||
* | * एमरैम: रैम गुणा और भाग के साथ संवर्धित होती है | ||
* | * बीरैम एमबीरैम: बीरैम और एमबीरैम के बिटवाइज़ बूलियन वर्जन | ||
* एन****: नाम से पहले | * एन****: नाम से पहले N के साथ उपरोक्त में से किसी का गैर-नियतात्मक वर्जन | ||
=== रैंडम-एक्सेस स्टोर्ड प्रोग्राम (आरएएसपी) मशीन मॉडल === | === रैंडम-एक्सेस स्टोर्ड प्रोग्राम (आरएएसपी) मशीन मॉडल === | ||
{{details|रैंडम-एक्सेस स्टोर्ड-प्रोग्राम मशीन}} | {{details|रैंडम-एक्सेस स्टोर्ड-प्रोग्राम मशीन}} | ||
आरएएसपी रैम है जिसमें निर्देश उनके डेटा के साथ ही 'स्पेस' में संग्रहीत होते हैं अर्थात रजिस्टरों का क्रम आरएएसपी की धारणा का वर्णन कम से कम किफेंगस्ट में किया गया था। उनके मॉडल में मिल थी संचायक, किन्तु अब निर्देश डेटा के साथ रजिस्टरों में थे | आरएएसपी रैम है, जिसमें निर्देश उनके डेटा के साथ ही 'स्पेस' में संग्रहीत होते हैं अर्थात रजिस्टरों का क्रम आरएएसपी की धारणा का वर्णन कम से कम किफेंगस्ट में किया गया था। उनके मॉडल में मिल थी संचायक, किन्तु अब निर्देश डेटा के साथ रजिस्टरों में थे| जो कि [[वॉन न्यूमैन वास्तुकला|वॉन न्यूमैन आर्किटेक्चर]] जब आरएएसपी में एकांतर से सम और विषम रजिस्टर होते हैं| यहां तक कि ऑपरेशन कोड (निर्देश) को पकड़ना और विषम को इसके ऑपरेंड (पैरामीटर) को पकड़ना, तब अप्रत्यक्ष एड्रेस को केवल निर्देश के ऑपरेंड को संशोधित करके प्राप्त किया जाता है।<ref>[[Stephen Cook|Stephen A. Cook]] and Robert A. Reckhow (1972), ''Time-bounded random access machines'', Journal of Computer Systems Science 7 (1973), 354–375.</ref> | ||
एल्गॉट और रॉबिन्सन के मूल आरएएसपी मॉडल में रजिस्टर-मशीन मॉडल के फैशन में केवल तीन निर्देश थे,<ref>[[Calvin Elgot]] and [[Abraham Robinson]] (1964), ''Random-Access Stored-Program Machines, an Approach to Programming Languages'', Journal of the Association for Computing Machinery, Vol. 11, No. 4 (October 1964), pp. 365–399.</ref> किन्तु उन्होंने उन्हें अपने डेटा के साथ रजिस्टर स्थान में रखा। (यहां | एल्गॉट और रॉबिन्सन के मूल आरएएसपी मॉडल में रजिस्टर-मशीन मॉडल के फैशन में केवल तीन निर्देश थे,<ref>[[Calvin Elgot]] and [[Abraham Robinson]] (1964), ''Random-Access Stored-Program Machines, an Approach to Programming Languages'', Journal of the Association for Computing Machinery, Vol. 11, No. 4 (October 1964), pp. 365–399.</ref> किन्तु उन्होंने उन्हें अपने डेटा के साथ रजिस्टर स्थान में रखा। (यहां कॉपी क्लियर का स्थान लेता है, जब कोई रजिस्टर जैसे z या 0 से प्रयुक्त होता है और सदैव 0 होता है। यह ट्रिक असामान्य नहीं है। रजिस्टर यूनिट या 1 में यूनिट 1 भी उपयोगी है।) | ||
: { INC ( r ), COPY ( r<sub>i</sub>, r<sub>j</sub> ), JE ( r<sub>i</sub>, r<sub>i</sub>, z ) } | : { INC ( r ), COPY ( r<sub>i</sub>, r<sub>j</sub> ), JE ( r<sub>i</sub>, r<sub>i</sub>, z ) } | ||
आरएएसपी मॉडल अप्रत्यक्ष के साथ-साथ प्रत्यक्ष-संबोधन की भी अनुमति देते हैं; कुछ लोग तत्काल निर्देशों की भी अनुमति देते हैं, उदा. संचायक को स्थिरांक 3 के साथ लोड करें। निर्देश अत्यधिक प्रतिबंधित | आरएएसपी मॉडल अप्रत्यक्ष के साथ-साथ प्रत्यक्ष-संबोधन की भी अनुमति देते हैं; कुछ लोग तत्काल निर्देशों की भी अनुमति देते हैं, उदा. संचायक को स्थिरांक 3 के साथ लोड करें। निर्देश अत्यधिक प्रतिबंधित समुच्चय के हो सकते हैं, जैसे कि हार्टमैनिस के निम्नलिखित 16 निर्देश <ref>[[J. Hartmanis]] (1971), "Computational Complexity of Random Access Stored Program Machines," Mathematical Systems Theory 5, 3 (1971) pp. 232–245.</ref> यह मॉडल संचायक a का उपयोग करता है। निमोनिक्स वह हैं जिनका उपयोग लेखकों ने किया है (उनका सीएलए स्थिर या रजिस्टर से लोड संचायक है; एसटीओ स्टोर संचायक है)। इस प्रकार जंप को छोड़कर, उनका सिंटैक्स निम्नलिखित है: n, <n>, <<n>> तत्काल, प्रत्यक्ष और अप्रत्यक्ष के लिए)। जंप दो ट्रांसफर निर्देशों टीआरए के माध्यम से होते हैं सीधे n या परोक्ष रूप से बिना नियम जंप < n > निर्देश काउंटर, टीआरजेड में रजिस्टर n की कंटेंट को जैमिंग करना (यदि टीआरए के समान ही एक्युमुलेटर शून्य है, तब नियमबद्ध जंप है|): | ||
:{ ADD n , ADD < n >, ADD << n >>, SUB n, SUB < n >, SUB << n >>, CLA n, CLA < n >, CLA << n >>, STO < n >, STO << n >>, TRA n, TRA < n >, TRZ n, TRA < n >, HALT } | :{ ADD n , ADD < n >, ADD << n >>, SUB n, SUB < n >, SUB << n >>, CLA n, CLA < n >, CLA << n >>, STO < n >, STO << n >>, TRA n, TRA < n >, TRZ n, TRA < n >, HALT } | ||
| Line 133: | Line 133: | ||
{{details|पॉइंटर मशीन}} | {{details|पॉइंटर मशीन}} | ||
अपेक्षाकृत देर से आने वाली मशीन शॉनहेज की स्टोरेज मॉडिफिकेशन मशीन या [[ सूचक मशीन |सूचक मशीन]] है। अन्य वर्जन कोलमोगोरोव-उसपेन्स्की मशीन और नथ लिंकिंग ऑटोमेटन प्रस्ताव है। (संदर्भ के लिए पॉइंटर मशीन देखें)। स्टेट-मशीन आरेख | अपेक्षाकृत देर से आने वाली मशीन शॉनहेज की स्टोरेज मॉडिफिकेशन मशीन या [[ सूचक मशीन |सूचक मशीन]] है। अन्य वर्जन कोलमोगोरोव-उसपेन्स्की मशीन और नथ लिंकिंग ऑटोमेटन प्रस्ताव है। (संदर्भ के लिए पॉइंटर मशीन देखें)। स्टेट-मशीन आरेख के समान, नोड कम से कम दो लेबल वाले किनारों (तीर) का उत्सर्जन करता है, जो दूसरे नोड या नोड्स को संकेत करता है| जो परिवर्तित करने में अन्य नोड्स आदि को संकेत करता है। बाहरी संसार केंद्र नोड पर संकेत करती है। | ||
==इनपुट और आउटपुट वाली मशीन== | ==इनपुट और आउटपुट वाली मशीन== | ||
उपरोक्त टेप-आधारित मशीनों में से कोई भी इनपुट और आउटपुट टेप से सुसज्जित हो सकती है; उपरोक्त रजिस्टर-आधारित मशीनों में से कोई भी समर्पित इनपुट और आउटपुट रजिस्टरों से सुसज्जित हो सकती है। उदाहरण के लिए | उपरोक्त टेप-आधारित मशीनों में से कोई भी इनपुट और आउटपुट टेप से सुसज्जित हो सकती है; उपरोक्त रजिस्टर-आधारित मशीनों में से कोई भी समर्पित इनपुट और आउटपुट रजिस्टरों से सुसज्जित हो सकती है। उदाहरण के लिए शॉनहेज पॉइंटर-मशीन मॉडल में दो निर्देश हैं, जिन्हें इनपुट λ<sub>0</sub>,L<sub>1</sub>और आउटपुट β कहा जाता है | ||
ट्रेडिशनल मॉडल के साथ मल्टी-टेप मशीनों पर सबलीनियर स्पेस काम्प्लेक्स का अध्ययन करना कठिन है क्योंकि आकार n का इनपुट पहले से ही स्पेस n लेता है। इस प्रकार छोटी [[DSPACE|डीएसपीएसीई]] कक्षाओं का अध्ययन करने के लिए हमें पृथक मॉडल का उपयोग करना चाहिए। कुछ अर्थों में यदि हम इनपुट टेप पर कभी नहीं लिखते हैं, तब हम इस स्थान के लिए स्वयं को चार्ज नहीं करना चाहते हैं और यदि हम अपने आउटपुट टेप से कभी नहीं पढ़ते हैं, तब हम इस स्थान के लिए स्वयं को आवेशित नहीं करना चाहते हैं। | |||
हम इनपुट और आउटपुट के साथ K-स्ट्रिंग ट्यूरिंग मशीन प्रस्तुत करके इस समस्या का समाधान करते हैं। यह साधारण K-स्ट्रिंग ट्यूरिंग मशीन के समान है, अतिरिक्त ट्रांज़िशन फ़ंक्शन के {{mvar|δ}} प्रतिबंधित है जिससे इनपुट टेप को कभी भी परिवर्तित नही किया जा सकता है | हम इनपुट और आउटपुट के साथ K-स्ट्रिंग ट्यूरिंग मशीन प्रस्तुत करके इस समस्या का समाधान करते हैं। यह साधारण K-स्ट्रिंग ट्यूरिंग मशीन के समान है, अतिरिक्त ट्रांज़िशन फ़ंक्शन के {{mvar|δ}} प्रतिबंधित है, जिससे इनपुट टेप को कभी भी परिवर्तित नही किया जा सकता है और जिससे आउटपुट हेड कभी भी बाईं ओर न घूम सके। यह मॉडल हमें रैखिक से छोटे नियतात्मक अंतरिक्ष वर्गों को परिभाषित करने की अनुमति देता है। इनपुट-और-आउटपुट वाली ट्यूरिंग मशीनों में भी अन्य ट्यूरिंग मशीनों के समान ही समय काम्प्लेक्स होती है; पापादिमित्रिउ 1994 प्रस्ताव 2.2 के शब्दों में: | ||
:किसी भी k-स्ट्रिंग ट्यूरिंग मशीन M के लिए जो समयबद्ध {{tmath|f(n)}} के अन्दर कार्य करती है, इनपुट और आउटपुट के साथ {{tmath|(k+2)}}-स्ट्रिंग ट्यूरिंग मशीन M' है जो समयबद्ध {{tmath|O(f(n))}} के अन्दर कार्य करती है। | :किसी भी k-स्ट्रिंग ट्यूरिंग मशीन M के लिए जो समयबद्ध {{tmath|f(n)}} के अन्दर कार्य करती है, इनपुट और आउटपुट के साथ {{tmath|(k+2)}}-स्ट्रिंग ट्यूरिंग मशीन M' है, जो समयबद्ध {{tmath|O(f(n))}} के अन्दर कार्य करती है। | ||
इनपुट और आउटपुट के साथ K-स्ट्रिंग ट्यूरिंग मशीनों का उपयोग | इनपुट और आउटपुट के साथ K-स्ट्रिंग ट्यूरिंग मशीनों का उपयोग काम्प्लेक्स संसाधन डीएसपीएसीई की फॉर्मल परिभाषा में किया जा सकता है।<ref>{{cite book|author = [[Christos Papadimitriou]] | year = 1993 | title = अभिकलनात्मक जटिलता| publisher = Addison Wesley | edition = 1st | isbn = 0-201-53082-1}} Chapter 2: Turing machines, pp. 19–56.</ref> | ||
== अन्य समकक्ष मशीन और विधियाँ == | == अन्य समकक्ष मशीन और विधियाँ == | ||
* बहुआयामी ट्यूरिंग मशीन: उदाहरण के लिए | * बहुआयामी ट्यूरिंग मशीन: उदाहरण के लिए शॉनहेज का मॉडल चार हेड-मूवमेंट कमांड {उत्तर, दक्षिण, पूर्व, पश्चिम} का उपयोग करता है।<ref name="Schonage80">A. [[Schōnhage]] (1980), ''Storage Modification Machines'', Society for Industrial and Applied Mathematics, SIAM J. Comput. Vol. 9, No. 3, August 1980.</ref> | ||
* सिंगल-टेप, मल्टी-हेड ट्यूरिंग मशीन: टैग की समस्या के अनिर्णय प्रमाण में, मिन्स्की और शेफर्डसन और स्टर्गिस ने ही टेप वाली मशीनों का वर्णन किया था जो हेड के साथ टेप के साथ पढ़ सकती थीं और दूसरे के साथ टेप के साथ आगे लिख सकती थीं।<ref>{{cite journal|author=[[Marvin Minsky]] | * सिंगल-टेप, मल्टी-हेड ट्यूरिंग मशीन: टैग की समस्या के अनिर्णय प्रमाण में, मिन्स्की और शेफर्डसन और स्टर्गिस ने ही टेप वाली मशीनों का वर्णन किया था| जो हेड के साथ टेप के साथ पढ़ सकती थीं और दूसरे के साथ टेप के साथ आगे लिख सकती थीं।<ref>{{cite journal|author=[[Marvin Minsky]] | ||
|title=Recursive Unsolvability of Post's Problem of 'Tag' and Other Topics in Theory of Turing Machines | |title=Recursive Unsolvability of Post's Problem of 'Tag' and Other Topics in Theory of Turing Machines | ||
|journal=Annals of Mathematics | |journal=Annals of Mathematics | ||
| Line 158: | Line 158: | ||
*[[मार्कोव एल्गोरिथ्म]] और उल्लेखनीय सरल कम्प्यूटेशनल मॉडल है, जो ट्यूरिंग मशीनों के समकक्ष स्ट्रिंग पुनर्लेखन पर आधारित है। | *[[मार्कोव एल्गोरिथ्म]] और उल्लेखनीय सरल कम्प्यूटेशनल मॉडल है, जो ट्यूरिंग मशीनों के समकक्ष स्ट्रिंग पुनर्लेखन पर आधारित है। | ||
* [[लैम्ब्डा कैलकुलस]] | * [[लैम्ब्डा कैलकुलस]] | ||
* केवे | * केवे ऑटोमेशन | ||
== संदर्भ == | == संदर्भ == | ||
{{reflist}} | {{reflist}} | ||
{{DEFAULTSORT:Turing Machine Equivalents}} | {{DEFAULTSORT:Turing Machine Equivalents}} | ||
[[Category:Articles with hatnote templates targeting a nonexistent page|Turing Machine Equivalents]] | |||
[[Category:Created On 27/07/2023|Turing Machine Equivalents]] | |||
[[Category: Machine | [[Category:Lua-based templates|Turing Machine Equivalents]] | ||
[[Category:Created On 27/07/2023]] | [[Category:Machine Translated Page|Turing Machine Equivalents]] | ||
[[Category:Pages with script errors|Turing Machine Equivalents]] | |||
[[Category:Short description with empty Wikidata description|Turing Machine Equivalents]] | |||
[[Category:Templates Vigyan Ready|Turing Machine Equivalents]] | |||
[[Category:Templates that add a tracking category|Turing Machine Equivalents]] | |||
[[Category:Templates that generate short descriptions|Turing Machine Equivalents]] | |||
[[Category:Templates using TemplateData|Turing Machine Equivalents]] | |||
[[Category:गणना का सिद्धांत|Turing Machine Equivalents]] | |||
[[Category:गणना के मॉडल|Turing Machine Equivalents]] | |||
[[Category:ट्यूरिंग मशीन|Turing Machine Equivalents]] | |||
Latest revision as of 17:11, 21 August 2023
ट्यूरिंग मशीन हैपोथेटिकल कंप्यूटिंग डिवाइस है, जिसकी कल्पना सर्वप्रथम एलन ट्यूरिंग ने 1936 में की थी। ट्यूरिंग मशीन नियमों की सीमित टेबल के अनुसार टेप की संभावित इनफिनिट स्ट्रिप पर प्रतीकों में परिवर्तित करती हैं और वह कंप्यूटर एल्गोरिदम की धारणा के लिए सैद्धांतिक आदान-प्रदान करती हैं।
जबकि निम्नलिखित में से किसी भी मॉडल में सिंगल-टेप, वन-वे इनफिनिट, मल्टी-सिंबल ट्यूरिंग-मशीन मॉडल की तुलना में अधिक शक्ति नहीं दिखाई गई है, उनके लेखकों ने उन्हें परिभाषित किया और प्रश्नों की जांच करने और समस्याओं को अधिक सरलता से हल करने के लिए उपयोग किया था। यदि वह ट्यूरिंग के a-मशीन मॉडल के साथ बने रहते है।
ट्यूरिंग मशीन मॉडल के समतुल्य मशीन
ट्यूरिंग तुल्यता
विभिन्न मशीन जिनके विषय में सोचा जा सकता है कि उनमें साधारण सार्वभौमिक ट्यूरिंग मशीन की तुलना में अधिक कम्प्यूटेशनल क्षमता है, उन्हें दिखाया जा सकता है कि उनमें अधिक शक्ति नहीं है।[1] वह संभवतः तेजी से गणना कर सकते हैं या कम मेमोरी का उपयोग कर सकते हैं या उनका निर्देश समुच्चय छोटा हो सकता है, किन्तु वह अधिक शक्तिशाली विधि से गणना नहीं कर सकते (अर्थात अधिक गणितीय कार्य)। (चर्च-ट्यूरिंग थीसिस इसे सत्य मानती है: जो कुछ भी "गणना" किया जा सकता है उसकी गणना कुछ ट्यूरिंग मशीन द्वारा की जा सकती है।)
अनुक्रमिक-मशीन मॉडल'
निम्नलिखित सभी को समानांतर मशीन मॉडल से पृथक करने के लिए अनुक्रमिक मशीन मॉडल कहा जाता है।[2]
टेप-आधारित ट्यूरिंग मशीन
ट्यूरिंग का ए-मशीन मॉडल
ट्यूरिंग की मशीन (जैसा कि उन्होंने इसे कहा था) बाएँ किनारे वाली, दाएँ किनारे वाली इनफिनिट थी। उन्होंने बाएं छोर को चिह्नित करने के लिए əə प्रतीक प्रदान किए थे। टेप प्रतीकों की सीमित संख्या की अनुमति थी। निर्देश (यदि सार्वभौमिक मशीन) और इनपुट और आउट केवल F-स्क्वायर पर लिखे गए थे और मार्कर E-स्क्वायर पर दिखाई देने थे। संक्षेप में उन्होंने अपनी मशीन को दो टेपों में विभाजित किया जो सदैव साथ घूमते थे। निर्देश 5-टुपल्स नामक सारणीबद्ध रूप में प्रकट हुए और क्रमिक रूप से निष्पादित नहीं किए गए थे।
प्रतिबंधित प्रतीकों और/या प्रतिबंधित निर्देशों वाली एकल-टेप मशीन
यह निम्नलिखित मॉडल एकल टेप ट्यूरिंग मशीन हैं, किन्तु (i) प्रतिबंधित टेप प्रतीकों {चिह्न, रिक्त}, और/या (ii) अनुक्रमिक, कंप्यूटर-जैसे निर्देश, और (iii) पूर्णतः परमाणुकृत मशीन-क्रियाओं से प्रतिबंधित हैं।
पोस्ट का सूत्रीकरण 1 गणना का मॉडल
एमिल पोस्ट ने कम्प्यूटेशनल प्रक्रिया के स्वतंत्र विवरण में, टेप पर चिह्नों के समकक्ष बाइनरी सेट के लिए अनुमत प्रतीकों को कम कर दिया है। उन्होंने टेप की धारणा को एक-पक्षीय इनफिनिट से दाईं ओर इनफिनिट कमरों के समुच्चय में परिवर्तित कर दिया था| जिनमें से प्रत्येक में दोनों दिशाओं में पेपर की शीट थी। इस प्रकार उन्होंने ट्यूरिंग 5-टुपल्स को 4-टुपल्स में विभाजित कर दिया था मोशन निर्देश प्रिंट/इरेज़ निर्देशों से प्रथक चूँकि उनका 1936 मॉडल इस विषय में अस्पष्ट है, पोस्ट के 1947 मॉडल को अनुक्रमिक निर्देश निष्पादन की आवश्यकता नहीं थी।
उनका अत्यधिक सरल मॉडल किसी भी ट्यूरिंग मशीन का अनुकरण कर सकता है और चूँकि उनके 1936 फॉर्मूलेशन 1 में प्रोग्राम या मशीन शब्द का उपयोग नहीं किया गया है, यह प्रभावी रूप से बहुत ही मौलिक प्रोग्राम योग्य कंप्यूटर और संबंधित प्रोग्रामिंग लैंग्वेज का फॉर्मूलेशन है, जिसमें बॉक्स अनबाउंड बिटस्ट्रिंग मेमोरी के रूप में कार्य करते हैं और प्रोग्राम का निर्माण करने वाले निर्देशों का समुच्चय प्रयुक्त होते है।
वांग मशीन
प्रभावशाली पेपर में, हाओ वांग (अकादमिक) ने पोस्ट की पोस्ट-ट्यूरिंग मशीन 1936: पोस्ट मॉडल को उन मशीनों में परिवर्तित कर दिया था जो अभी भी दो-पक्षीय इनफिनिट बाइनरी टेप का उपयोग करते हैं, किन्तु जिनके निर्देश सरल हैं, पोस्ट के निर्देशों के परमाणु अवयव होने के सम्बन्ध में और डिफ़ॉल्ट रूप से क्रमिक रूप से निष्पादित होते हैं ( कंप्यूटर प्रोग्राम की तरह)। उनका घोषित मुख्य उद्देश्य, ट्यूरिंग के सिद्धांत के विकल्प के रूप में ऐसा सिद्धांत प्रस्तुत करना था, जो मूलभूत संचालन में अधिक प्रभावकारी होता है। उनके परिणाम विभिन्न प्रकार की ऐसी मशीनों के प्रोग्राम फॉर्मूलेशन थे, जिनमें निर्देश-समुच्चय के साथ 5-निर्देश वांग डब्ल्यू-मशीन भी सम्मिलित थी
- { शिफ्ट-बाएं, शिफ्ट-दाएं, मार्क-स्क्वायर, इरेज-स्क्वायर, जंप-इफ-स्क्वायर-चिह्नित-से xxx }
और निर्देश-समुच्चय के साथ उनकी सबसे कठोरता से कम की गई 4-निर्देश वांग बी-मशीन (बेसिक के लिए बी)
- { शिफ्ट-बाएं, शिफ्ट-दाएं, मार्क-स्क्वायर, जंप-इफ-स्क्वायर-चिह्नित-से xxx }
जिसमें इरेज-स्क्वायर निर्देश भी नहीं है।
विभिन्न लेखकों ने पश्चात में वांग द्वारा विचार की गई मशीनों के वेरिएंट प्रस्तुत किए:
मिन्स्की ने (मल्टी-टेप) काउंटर मशीन मॉडल के अपने संस्करण के साथ वांग की धारणा को विकसित किया था| इस प्रकार जो भिन्न-भिन्न सिरों की शिफ्ट-बाएं और शिफ्ट-दाएं गति की अनुमति देता है, किन्तु बिल्कुल भी मुद्रण नहीं करता है।[3] इस स्थिति में टेप बाएं किनारे वाले होंगे, प्रत्येक किनारे पर अंत को संकेत करने के लिए चिन्ह होगा। वह इसे ही टेप तक सीमित करने में सक्षम था, किन्तु अधिक सरल {शिफ्ट-बाएं = कमी, शिफ्ट-दाएं = इन्क्रीमेंट} के अतिरिक्त गुणन और विभाजन के समतुल्य मल्टी-टेप-स्क्वायर गति को प्रयुक्त करने की मूल्य पर प्रयुक्त किया जाता है।
डेविस ने वांग द्वारा विचार की गई मशीनों में से में स्पष्ट एचएएलटी निर्देश जोड़कर निर्देश-समुच्चय के साथ मॉडल का उपयोग किया था
- {शिफ्ट-बाएं, शिफ्ट-दाएं, इरेज, चिह्नित करें, वर्ग-चिह्नित xxx पर जम्प, xxx पर जम्प, रुकें }
और 2 से बड़े आकार के टेप-अक्षरों वाले वर्जन पर भी विचार किया गया।
बोहम की सैद्धांतिक मशीनी लैंग्वेज पी
मूलभूत संचालन में प्रभावकारी ट्यूरिंग-समतुल्य सिद्धांत की खोज करने के लिए वांग की परियोजना को ध्यान में रखते हुए और बिना नियम जम्प से बचने की इच्छा रखते हुए, उल्लेखनीय सैद्धांतिक लैंग्वेज 1964 में कोराडो बोहम द्वारा प्रयुक्त की गई 4-निर्देश लैंग्वेज पी है - ट्यूरिंग-पूर्ण सिद्ध होने वाली पहली गोटो-कम अनिवार्य स्ट्रक्चर्ड प्रोग्रामिंग लैंग्वेज होती है।
मल्टी-टेप ट्यूरिंग मशीन
व्यावहारिक विश्लेषण में विभिन्न प्रकार की मल्टी-टेप ट्यूरिंग मशीनों का अधिकांशतः उपयोग किया जाता है। मल्टी-टेप मशीन सिंगल-टेप मशीनों के समान होती हैं, किन्तु कुछ स्थिर k संख्या में स्वतंत्र टेप होते हैं।
नियतात्मक और गैर-नियतात्मक ट्यूरिंग मशीन
यदि क्रिया टेबल में प्रतीक और स्थिति के प्रत्येक संयोजन के लिए अधिकतम प्रविष्टि है| तब मशीन नियतात्मक ट्यूरिंग मशीन (डीटीएम) है। यदि क्रिया टेबल में प्रतीक और स्थिति के संयोजन के लिए एकाधिक प्रविष्टियाँ हैं इस प्रकार मशीन गैर-नियतात्मक ट्यूरिंग मशीन (एनडीटीएम) है। यह दोनों कम्प्यूटेशनल रूप से समतुल्य हैं, अर्थात किसी भी एनडीटीएम को डीटीएम (और इसके विपरीत) में परिवर्तित करना संभव है, चूँकि उनके निकट सामान्यतः भिन्न-भिन्न रनटाइम होते हैं। इसे निर्माण के माध्यम से सिद्ध किया जा सकता है।
ओब्लिवियस ट्यूरिंग मशीन
ओब्लिवियस ट्यूरिंग मशीन ट्यूरिंग मशीन है, जहां प्रत्येक इनपुट लंबाई के लिए, विभिन्न शीर्षों की गति समय का निश्चित कार्य है, जो इनपुट से स्वतंत्र है। दूसरे शब्दों में पूर्व निर्धारित क्रम होता है, जिसमें विभिन्न टेपों को स्कैन किया जाता है, उन्नत किया जाता है और लिखा जाता है। इस प्रकार किसी भी स्टेज पर टेप पर लिखे गए वास्तविक मान उस लंबाई के प्रत्येक इनपुट के लिए अभी भी भिन्न हो सकते हैं। पिप्पेंजर और फिशर ने दिखाया कि कोई भी गणना जो मल्टी-टेप ट्यूरिंग मशीन द्वारा एन स्टेज में की जा सकती है, उसे ओब्लिवियस दो-टेप ट्यूरिंग मशीन द्वारा n स्टेज में किया जा सकता है। स्टेज [4] ऑब्लिवियस मशीनें कॉम्बिनेशन लॉजिक परिपथ के साथ स्टेज-वार रैखिक फैशन में मेल खाती हैं, जब संक्रमण टेबल की काम्प्लेक्स को स्थिर माना जाता है। इस प्रकार आकार और डेप्थ में परिपथ समस्याओं के रूप में गणना करना संभव है (परिपथ काम्प्लेक्स देखें)। यह कुक और लेविन के मूल परिणाम में सुधार करता है।
रजिस्टर मशीन मॉडल
पीटर वैन एम्डे बोस इस प्रकार की सभी मशीनों को वर्ग, रजिस्टर मशीन में सम्मिलित करते हैं।[2] चूँकि, ऐतिहासिक रूप से साहित्य ने इस समूह के सबसे मौलिक सदस्य अर्थात काउंटर मशीन को रजिस्टर मशीन भी कहा है और काउंटर मशीन के सबसे मौलिक आगमन को कभी-कभी मिन्स्की मशीन कहा जाता है।
काउंटर मशीन, जिसे रजिस्टर मशीन मॉडल भी कहा जाता है
मौलिक मॉडल रजिस्टर मशीन मल्टीटेप 2-प्रतीक पोस्ट-ट्यूरिंग मशीन है| जिसका व्यवहार प्रतिबंधित है, इसलिए इसके टेप साधारण काउंटर के समान कार्य करते हैं।
मेल्ज़ाक, लैम्बेक और मिन्स्की के समय तक कंप्यूटर प्रोग्राम की धारणा ने पृथक प्रकार की सरल मशीन का निर्माण किया था, इस प्रकार जिसमें पोस्ट-ट्यूरिंग टेप से विभिन्न बाएं छोर वाले टेप काटे गए थे। सभी स्थितियों में मॉडल केवल दो टेप प्रतीकों {चिह्न, रिक्त} की अनुमति देते हैं।[3]
कुछ वर्जन धनात्मक पूर्णांकों को केवल रजिस्टर में अनुमत अंकों की स्ट्रिंग/स्टैक के रूप में दर्शाते हैं (अर्थात बाएं किनारे वाला टेप), और गिनती 0 द्वारा दर्शाए गए रिक्त टेप के रूप में मिन्स्की ने अपने मॉडल को प्रत्येक टेप के बाएं छोर पर अनिवार्य एकल चिह्न प्रदान करने की मूल्य पर प्रिंट निर्देश को समाप्त कर दिया था।[3]
इस मॉडल में सिंगल-एंडेड टेप-एज़-रजिस्टर को काउंटर के रूप में माना जाता है, उनके निर्देश केवल दो तक सीमित होते हैं (या यदि टेस्ट/डिक्रीमेंट निर्देश को परमाणुकृत किया जाता है तब तीन)। दो सामान्य निर्देश समुच्चय निम्नलिखित हैं:
- (1): { INC ( r ), DEC ( r ), JZ ( r,z ) }, अर्थात।
- {रजिस्टर #r की कंटेंट में इन्क्रीमेंट; रजिस्टर #r की कंटेंट में कमी ; यदि #r=शून्य की कंटेंट है| तब निर्देश #z पर जाएं}
- (2): { CLR ( r ); INC ( r ); JE ( ri, rj, z ) }, i.e., अर्थात्।
- {रजिस्टर r की स्पष्ट कंटेंट; r की कंटेंट में इन्क्रीमेंट; ri को rj की कंटेंट की तुलना करें और यदि समान है| तब निर्देश z पर जाएं}
यद्यपि उनका मॉडल इस सरल विवरण से अधिक सम्मिश्र है, मेल्ज़ाक पेब्बल मॉडल ने बहु-विषयकता की अनुमति देने के लिए काउंटर की इस धारणा को बढ़ाया था। इस स्थिति में पेब्बल जोड़ता और घटाता है।
रैंडम-एक्सेस मशीन (रैम) मॉडल
मेल्ज़ाक ने अपने रजिस्टर/काउंटर-मशीन मॉडल में कुछ गंभीर दोषों को पहचाना:[5] (i) अप्रत्यक्ष संबोधन के बिना वह सरलता से यह नहीं दिखा पाएगा कि मॉडल ट्यूरिंग पूर्णता है, (ii) प्रोग्राम और रजिस्टर भिन्न-भिन्न स्थानों पर थे, इसलिए प्रोग्राम को स्व-संशोधित करना सरल नहीं होगा। जब मेल्ज़ाक ने अपने मॉडल में अप्रत्यक्ष संबोधन जोड़ा, तब उन्होंने रैंडम एक्सेस मशीन मॉडल बनाया था।
(चूँकि निर्देशों की गोडेल नंबरिंग के साथ मिन्स्की ने प्रमाण प्रस्तुत किया कि ऐसी नंबरिंग के साथ सामान्य रिकर्सन (कंप्यूटर विज्ञान) वास्तव में संभव था| वह प्रमाण प्रस्तुत करता है कि μ रिकर्सन वास्तव में संभव है[3]).
आरएएसपी मॉडल के विपरीत, रैम मॉडल मशीन के कार्यों को उसके निर्देशों को संशोधित करने की अनुमति नहीं देता है। कभी-कभी मॉडल बिना किसी संचायक के केवल रजिस्टर-टू-रजिस्टर पर कार्य करता है, किन्तु अधिकांश मॉडलों में संचायक सम्मिलित होता है।
वैन एम्डे बोस विभिन्न रैम मॉडल को विभिन्न उप-प्रकारों में विभाजित करता है:[2]
- एसआरएएम, केवल अंकगणितीय निर्देश के साथ सकसेस्सर रैम, सकसेस्सर (इन्क्रीमेंट h) अन्य में क्लियर h और IF समानता-मध्य-रजिस्टर सम्मिलित है, फिर xxx पर जाएं।
- रैम: जोड़ और घटाव के साथ मानक मॉडल
- एमरैम: रैम गुणा और भाग के साथ संवर्धित होती है
- बीरैम एमबीरैम: बीरैम और एमबीरैम के बिटवाइज़ बूलियन वर्जन
- एन****: नाम से पहले N के साथ उपरोक्त में से किसी का गैर-नियतात्मक वर्जन
रैंडम-एक्सेस स्टोर्ड प्रोग्राम (आरएएसपी) मशीन मॉडल
आरएएसपी रैम है, जिसमें निर्देश उनके डेटा के साथ ही 'स्पेस' में संग्रहीत होते हैं अर्थात रजिस्टरों का क्रम आरएएसपी की धारणा का वर्णन कम से कम किफेंगस्ट में किया गया था। उनके मॉडल में मिल थी संचायक, किन्तु अब निर्देश डेटा के साथ रजिस्टरों में थे| जो कि वॉन न्यूमैन आर्किटेक्चर जब आरएएसपी में एकांतर से सम और विषम रजिस्टर होते हैं| यहां तक कि ऑपरेशन कोड (निर्देश) को पकड़ना और विषम को इसके ऑपरेंड (पैरामीटर) को पकड़ना, तब अप्रत्यक्ष एड्रेस को केवल निर्देश के ऑपरेंड को संशोधित करके प्राप्त किया जाता है।[6]
एल्गॉट और रॉबिन्सन के मूल आरएएसपी मॉडल में रजिस्टर-मशीन मॉडल के फैशन में केवल तीन निर्देश थे,[7] किन्तु उन्होंने उन्हें अपने डेटा के साथ रजिस्टर स्थान में रखा। (यहां कॉपी क्लियर का स्थान लेता है, जब कोई रजिस्टर जैसे z या 0 से प्रयुक्त होता है और सदैव 0 होता है। यह ट्रिक असामान्य नहीं है। रजिस्टर यूनिट या 1 में यूनिट 1 भी उपयोगी है।)
- { INC ( r ), COPY ( ri, rj ), JE ( ri, ri, z ) }
आरएएसपी मॉडल अप्रत्यक्ष के साथ-साथ प्रत्यक्ष-संबोधन की भी अनुमति देते हैं; कुछ लोग तत्काल निर्देशों की भी अनुमति देते हैं, उदा. संचायक को स्थिरांक 3 के साथ लोड करें। निर्देश अत्यधिक प्रतिबंधित समुच्चय के हो सकते हैं, जैसे कि हार्टमैनिस के निम्नलिखित 16 निर्देश [8] यह मॉडल संचायक a का उपयोग करता है। निमोनिक्स वह हैं जिनका उपयोग लेखकों ने किया है (उनका सीएलए स्थिर या रजिस्टर से लोड संचायक है; एसटीओ स्टोर संचायक है)। इस प्रकार जंप को छोड़कर, उनका सिंटैक्स निम्नलिखित है: n, <n>, <<n>> तत्काल, प्रत्यक्ष और अप्रत्यक्ष के लिए)। जंप दो ट्रांसफर निर्देशों टीआरए के माध्यम से होते हैं सीधे n या परोक्ष रूप से बिना नियम जंप < n > निर्देश काउंटर, टीआरजेड में रजिस्टर n की कंटेंट को जैमिंग करना (यदि टीआरए के समान ही एक्युमुलेटर शून्य है, तब नियमबद्ध जंप है|):
- { ADD n , ADD < n >, ADD << n >>, SUB n, SUB < n >, SUB << n >>, CLA n, CLA < n >, CLA << n >>, STO < n >, STO << n >>, TRA n, TRA < n >, TRZ n, TRA < n >, HALT }
पॉइंटर मशीन मॉडल
अपेक्षाकृत देर से आने वाली मशीन शॉनहेज की स्टोरेज मॉडिफिकेशन मशीन या सूचक मशीन है। अन्य वर्जन कोलमोगोरोव-उसपेन्स्की मशीन और नथ लिंकिंग ऑटोमेटन प्रस्ताव है। (संदर्भ के लिए पॉइंटर मशीन देखें)। स्टेट-मशीन आरेख के समान, नोड कम से कम दो लेबल वाले किनारों (तीर) का उत्सर्जन करता है, जो दूसरे नोड या नोड्स को संकेत करता है| जो परिवर्तित करने में अन्य नोड्स आदि को संकेत करता है। बाहरी संसार केंद्र नोड पर संकेत करती है।
इनपुट और आउटपुट वाली मशीन
उपरोक्त टेप-आधारित मशीनों में से कोई भी इनपुट और आउटपुट टेप से सुसज्जित हो सकती है; उपरोक्त रजिस्टर-आधारित मशीनों में से कोई भी समर्पित इनपुट और आउटपुट रजिस्टरों से सुसज्जित हो सकती है। उदाहरण के लिए शॉनहेज पॉइंटर-मशीन मॉडल में दो निर्देश हैं, जिन्हें इनपुट λ0,L1और आउटपुट β कहा जाता है
ट्रेडिशनल मॉडल के साथ मल्टी-टेप मशीनों पर सबलीनियर स्पेस काम्प्लेक्स का अध्ययन करना कठिन है क्योंकि आकार n का इनपुट पहले से ही स्पेस n लेता है। इस प्रकार छोटी डीएसपीएसीई कक्षाओं का अध्ययन करने के लिए हमें पृथक मॉडल का उपयोग करना चाहिए। कुछ अर्थों में यदि हम इनपुट टेप पर कभी नहीं लिखते हैं, तब हम इस स्थान के लिए स्वयं को चार्ज नहीं करना चाहते हैं और यदि हम अपने आउटपुट टेप से कभी नहीं पढ़ते हैं, तब हम इस स्थान के लिए स्वयं को आवेशित नहीं करना चाहते हैं।
हम इनपुट और आउटपुट के साथ K-स्ट्रिंग ट्यूरिंग मशीन प्रस्तुत करके इस समस्या का समाधान करते हैं। यह साधारण K-स्ट्रिंग ट्यूरिंग मशीन के समान है, अतिरिक्त ट्रांज़िशन फ़ंक्शन के δ प्रतिबंधित है, जिससे इनपुट टेप को कभी भी परिवर्तित नही किया जा सकता है और जिससे आउटपुट हेड कभी भी बाईं ओर न घूम सके। यह मॉडल हमें रैखिक से छोटे नियतात्मक अंतरिक्ष वर्गों को परिभाषित करने की अनुमति देता है। इनपुट-और-आउटपुट वाली ट्यूरिंग मशीनों में भी अन्य ट्यूरिंग मशीनों के समान ही समय काम्प्लेक्स होती है; पापादिमित्रिउ 1994 प्रस्ताव 2.2 के शब्दों में:
- किसी भी k-स्ट्रिंग ट्यूरिंग मशीन M के लिए जो समयबद्ध के अन्दर कार्य करती है, इनपुट और आउटपुट के साथ -स्ट्रिंग ट्यूरिंग मशीन M' है, जो समयबद्ध के अन्दर कार्य करती है।
इनपुट और आउटपुट के साथ K-स्ट्रिंग ट्यूरिंग मशीनों का उपयोग काम्प्लेक्स संसाधन डीएसपीएसीई की फॉर्मल परिभाषा में किया जा सकता है।[9]
अन्य समकक्ष मशीन और विधियाँ
- बहुआयामी ट्यूरिंग मशीन: उदाहरण के लिए शॉनहेज का मॉडल चार हेड-मूवमेंट कमांड {उत्तर, दक्षिण, पूर्व, पश्चिम} का उपयोग करता है।[10]
- सिंगल-टेप, मल्टी-हेड ट्यूरिंग मशीन: टैग की समस्या के अनिर्णय प्रमाण में, मिन्स्की और शेफर्डसन और स्टर्गिस ने ही टेप वाली मशीनों का वर्णन किया था| जो हेड के साथ टेप के साथ पढ़ सकती थीं और दूसरे के साथ टेप के साथ आगे लिख सकती थीं।[11][12]
- मार्कोव एल्गोरिथ्म और उल्लेखनीय सरल कम्प्यूटेशनल मॉडल है, जो ट्यूरिंग मशीनों के समकक्ष स्ट्रिंग पुनर्लेखन पर आधारित है।
- लैम्ब्डा कैलकुलस
- केवे ऑटोमेशन
संदर्भ
- ↑ John Hopcroft and Jeffrey Ullman (1979). ऑटोमेटा सिद्धांत, भाषाएँ और संगणना का परिचय (1st ed.). Addison–Wesley, Reading Mass. ISBN 0-201-02988-X.
- ↑ 2.0 2.1 2.2 Peter van Emde Boas, Machine Models and Simulations; Jan van Leeuwen, ed. Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity, p. 3-66, The MIT Press/Elsevier, 1990. ISBN 0-262-72014-0 (volume A). QA76.H279 1990.
- ↑ 3.0 3.1 3.2 3.3 Marvin Minsky, Computation: Finite and Infinite Machines, Prentice–Hall, Inc., N.J., 1967. See Chapter 8, Section 8.2 "Unsolvability of the Halting Problem."
- ↑ Pippenger, Nicholas; Fischer, Michael J. (1979), "Relations Among Complexity Measures", Journal of the ACM, 26 (3): 361–381, doi:10.1145/322123.322138, S2CID 2432526
- ↑ Melzak, Z. A. (September 1961). "An informal Arithmetical Approach to Computability and Computation". Canadian Mathematical Bulletin. 4 (3): 279–293. doi:10.4153/CMB-1961-031-9.
- ↑ Stephen A. Cook and Robert A. Reckhow (1972), Time-bounded random access machines, Journal of Computer Systems Science 7 (1973), 354–375.
- ↑ Calvin Elgot and Abraham Robinson (1964), Random-Access Stored-Program Machines, an Approach to Programming Languages, Journal of the Association for Computing Machinery, Vol. 11, No. 4 (October 1964), pp. 365–399.
- ↑ J. Hartmanis (1971), "Computational Complexity of Random Access Stored Program Machines," Mathematical Systems Theory 5, 3 (1971) pp. 232–245.
- ↑ Christos Papadimitriou (1993). अभिकलनात्मक जटिलता (1st ed.). Addison Wesley. ISBN 0-201-53082-1. Chapter 2: Turing machines, pp. 19–56.
- ↑ A. Schōnhage (1980), Storage Modification Machines, Society for Industrial and Applied Mathematics, SIAM J. Comput. Vol. 9, No. 3, August 1980.
- ↑ Marvin Minsky (15 August 1960). "Recursive Unsolvability of Post's Problem of 'Tag' and Other Topics in Theory of Turing Machines". Annals of Mathematics. 74 (3): 437–455. doi:10.2307/1970290. JSTOR 1970290.
- ↑ John C. Shepherdson and H. E. Sturgis received December 1961 Computability of Recursive Functions, Journal of the ACM 10:217-255, 1963
