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

From Vigyanwiki
No edit summary
No edit summary
Line 2: Line 2:


{{turing}}
{{turing}}
[[ट्यूरिंग मशीन]] एक काल्पनिक कंप्यूटिंग डिवाइस है, जिसकी कल्पना सबसे पहले [[एलन ट्यूरिंग]] ने 1936 में की थी। ट्यूरिंग मशीनें नियमों की एक सीमित तालिका के अनुसार टेप की संभावित अनंत पट्टी पर प्रतीकों में हेरफेर करती हैं, और वे कंप्यूटर एल्गोरिदम की धारणा के लिए सैद्धांतिक आधार प्रदान करती हैं।
[[ट्यूरिंग मशीन]] काल्पनिक कंप्यूटिंग डिवाइस है, जिसकी कल्पना सबसे पहले [[एलन ट्यूरिंग]] ने 1936 में की थी। ट्यूरिंग मशीनें नियमों की सीमित तालिका के अनुसार टेप की संभावित अनंत पट्टी पर प्रतीकों में हेरफेर करती हैं, और वे कंप्यूटर एल्गोरिदम की धारणा के लिए सैद्धांतिक आधार प्रदान करती हैं।


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


कई मशीनें जिनके बारे में सोचा जा सकता है कि उनमें एक साधारण सार्वभौमिक ट्यूरिंग मशीन की तुलना में अधिक कम्प्यूटेशनल क्षमता है, उन्हें दिखाया जा सकता है कि उनमें अधिक शक्ति नहीं है।<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> वे शायद तेजी से गणना कर सकते हैं, या कम मेमोरी का उपयोग कर सकते हैं, या उनका निर्देश सेट छोटा हो सकता है, लेकिन वे अधिक शक्तिशाली तरीके से गणना नहीं कर सकते (यानी अधिक गणितीय कार्य)। (चर्च-ट्यूरिंग थीसिस इसे सत्य मानती है: कि किसी भी चीज़ की गणना किसी ट्यूरिंग मशीन द्वारा की जा सकती है।)
कई मशीनें जिनके बारे में सोचा जा सकता है कि उनमें साधारण सार्वभौमिक ट्यूरिंग मशीन की तुलना में अधिक कम्प्यूटेशनल क्षमता है, उन्हें दिखाया जा सकता है कि उनमें अधिक शक्ति नहीं है।<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 21: Line 21:
ट्यूरिंग का ''ए''-मशीन मॉडल
ट्यूरिंग का ''ए''-मशीन मॉडल


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


=== प्रतिबंधित प्रतीकों और/या प्रतिबंधित निर्देशों वाली एकल-टेप मशीनें ===
=== प्रतिबंधित प्रतीकों और/या प्रतिबंधित निर्देशों वाली एकल-टेप मशीनें ===
Line 29: Line 29:
{{details|Post–Turing machine}}
{{details|Post–Turing machine}}


[[एमिल पोस्ट]] ने एक कम्प्यूटेशनल प्रक्रिया के एक स्वतंत्र विवरण में, टेप पर चिह्नों के समकक्ष बाइनरी सेट के लिए अनुमत प्रतीकों को कम कर दिया है। उन्होंने टेप की धारणा को एक-तरफा अनंत से दाईं ओर अनंत कमरों के सेट में बदल दिया, जिनमें से प्रत्येक में दोनों दिशाओं में कागज की एक शीट थी। उन्होंने ट्यूरिंग 5-टुपल्स को 4-टुपल्स में विभाजित कर दिया - मोशन निर्देश प्रिंट/इरेज़ निर्देशों से अलग। हालाँकि उनका 1936 मॉडल इस बारे में अस्पष्ट है, पोस्ट के 1947 मॉडल को अनुक्रमिक निर्देश निष्पादन की आवश्यकता नहीं थी।
[[एमिल पोस्ट]] ने कम्प्यूटेशनल प्रक्रिया के स्वतंत्र विवरण में, टेप पर चिह्नों के समकक्ष बाइनरी सेट के लिए अनुमत प्रतीकों को कम कर दिया है। उन्होंने टेप की धारणा को एक-तरफा अनंत से दाईं ओर अनंत कमरों के सेट में बदल दिया, जिनमें से प्रत्येक में दोनों दिशाओं में कागज की शीट थी। उन्होंने ट्यूरिंग 5-टुपल्स को 4-टुपल्स में विभाजित कर दिया - मोशन निर्देश प्रिंट/इरेज़ निर्देशों से अलग। हालाँकि उनका 1936 मॉडल इस बारे में अस्पष्ट है, पोस्ट के 1947 मॉडल को अनुक्रमिक निर्देश निष्पादन की आवश्यकता नहीं थी।


उनका बेहद सरल मॉडल किसी भी ट्यूरिंग मशीन का अनुकरण कर सकता है, और हालांकि उनके 1936 फॉर्मूलेशन 1 में प्रोग्राम या मशीन शब्द का उपयोग नहीं किया गया है, यह प्रभावी रूप से एक बहुत ही आदिम प्रोग्राम योग्य कंप्यूटर और संबंधित [[प्रोग्रामिंग भाषा]] का फॉर्मूलेशन है, जिसमें बॉक्स एक अनबाउंड बिटस्ट्रिंग मेमोरी के रूप में कार्य करते हैं। , और एक प्रोग्राम का निर्माण करने वाले निर्देशों का सेट।
उनका बेहद सरल मॉडल किसी भी ट्यूरिंग मशीन का अनुकरण कर सकता है, और हालांकि उनके 1936 फॉर्मूलेशन 1 में प्रोग्राम या मशीन शब्द का उपयोग नहीं किया गया है, यह प्रभावी रूप से बहुत ही आदिम प्रोग्राम योग्य कंप्यूटर और संबंधित [[प्रोग्रामिंग भाषा]] का फॉर्मूलेशन है, जिसमें बॉक्स अनबाउंड बिटस्ट्रिंग मेमोरी के रूप में कार्य करते हैं। , और प्रोग्राम का निर्माण करने वाले निर्देशों का सेट।


==== वांग मशीनें ====
==== वांग मशीनें ====
{{details|Wang B-machine}}
{{details|Wang B-machine}}


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


: { शिफ्ट-बाएं, शिफ्ट-दाएं, मार्क-स्क्वायर, मिटाएं-स्क्वायर, जंप-इफ-स्क्वायर-चिह्नित-से xxx }
: { शिफ्ट-बाएं, शिफ्ट-दाएं, मार्क-स्क्वायर, मिटाएं-स्क्वायर, जंप-इफ-स्क्वायर-चिह्नित-से xxx }
Line 48: Line 48:
कई लेखकों ने बाद में वांग द्वारा चर्चा की गई मशीनों के वेरिएंट पेश किए:
कई लेखकों ने बाद में वांग द्वारा चर्चा की गई मशीनों के वेरिएंट पेश किए:


मिन्स्की ने (मल्टी-टेप) काउंटर मशीन मॉडल के अपने संस्करण के साथ वांग की धारणा को विकसित किया, जो अलग-अलग सिरों की SHIFT-LEFT और SHIFT-दाएँ गति की अनुमति देता है, लेकिन बिल्कुल भी मुद्रण नहीं करता है।<ref name="Marvin" />इस मामले में टेप बाएं सिरे वाले होंगे, प्रत्येक सिरे पर अंत को इंगित करने के लिए एक निशान होगा। वह इसे एक ही टेप तक सीमित करने में सक्षम था, लेकिन अधिक सरल {शिफ्ट-बाएं = कमी, शिफ्ट-दाएं = वृद्धि} के बजाय गुणन और विभाजन के समतुल्य मल्टी-टेप-स्क्वायर गति को शुरू करने की कीमत पर।
मिन्स्की ने (मल्टी-टेप) काउंटर मशीन मॉडल के अपने संस्करण के साथ वांग की धारणा को विकसित किया, जो अलग-अलग सिरों की SHIFT-LEFT और SHIFT-दाएँ गति की अनुमति देता है, लेकिन बिल्कुल भी मुद्रण नहीं करता है।<ref name="Marvin" />इस मामले में टेप बाएं सिरे वाले होंगे, प्रत्येक सिरे पर अंत को इंगित करने के लिए निशान होगा। वह इसे ही टेप तक सीमित करने में सक्षम था, लेकिन अधिक सरल {शिफ्ट-बाएं = कमी, शिफ्ट-दाएं = वृद्धि} के बजाय गुणन और विभाजन के समतुल्य मल्टी-टेप-स्क्वायर गति को शुरू करने की कीमत पर।


डेविस ने वांग द्वारा चर्चा की गई मशीनों में से एक में एक स्पष्ट एचएएलटी निर्देश जोड़कर निर्देश-सेट के साथ एक मॉडल का उपयोग किया
डेविस ने वांग द्वारा चर्चा की गई मशीनों में से में स्पष्ट एचएएलटी निर्देश जोड़कर निर्देश-सेट के साथ मॉडल का उपयोग किया


: {शिफ्ट-बाएं, शिफ्ट-दाएं, मिटाएं, चिह्नित करें, वर्ग-चिह्नित xxx पर कूदें, xxx पर कूदें, रुकें }
: {शिफ्ट-बाएं, शिफ्ट-दाएं, मिटाएं, चिह्नित करें, वर्ग-चिह्नित xxx पर कूदें, xxx पर कूदें, रुकें }
Line 58: Line 58:
====बोहम की सैद्धांतिक मशीनी भाषा पी ====
====बोहम की सैद्धांतिक मशीनी भाषा पी ====
{{details|P"}}
{{details|P"}}
बुनियादी संचालन में किफायती ट्यूरिंग-समतुल्य सिद्धांत की तलाश करने के लिए वांग की परियोजना को ध्यान में रखते हुए, और बिना शर्त छलांग से बचने की इच्छा रखते हुए, एक उल्लेखनीय सैद्धांतिक भाषा 1964 में कोराडो बोहम द्वारा शुरू की गई 4-निर्देश भाषा पी है - [[ट्यूरिंग-पूर्ण]] साबित होने वाली पहली गोटो-कम अनिवार्य [[संरचित प्रोग्रामिंग]] भाषा।
बुनियादी संचालन में किफायती ट्यूरिंग-समतुल्य सिद्धांत की तलाश करने के लिए वांग की परियोजना को ध्यान में रखते हुए, और बिना शर्त छलांग से बचने की इच्छा रखते हुए, उल्लेखनीय सैद्धांतिक भाषा 1964 में कोराडो बोहम द्वारा शुरू की गई 4-निर्देश भाषा पी है - [[ट्यूरिंग-पूर्ण]] साबित होने वाली पहली गोटो-कम अनिवार्य [[संरचित प्रोग्रामिंग]] भाषा।


=== मल्टी-टेप ट्यूरिंग मशीनें ===
=== मल्टी-टेप ट्यूरिंग मशीनें ===
Line 68: Line 68:
{{details|non-deterministic Turing machine}}
{{details|non-deterministic Turing machine}}


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


=== विस्मृत ट्यूरिंग मशीनें ===
=== विस्मृत ट्यूरिंग मशीनें ===


एक विस्मृत ट्यूरिंग मशीन एक ट्यूरिंग मशीन है, जहां प्रत्येक इनपुट लंबाई के लिए, विभिन्न शीर्षों की गति समय का एक निश्चित कार्य है, जो इनपुट से स्वतंत्र है। दूसरे शब्दों में, एक पूर्व निर्धारित क्रम होता है जिसमें विभिन्न टेपों को स्कैन किया जाता है, उन्नत किया जाता है और लिखा जाता है। किसी भी चरण पर टेप पर लिखे गए वास्तविक मान उस लंबाई के प्रत्येक इनपुट के लिए अभी भी भिन्न हो सकते हैं। पिप्पेंजर और फिशर ने दिखाया कि कोई भी गणना जो मल्टी-टेप ट्यूरिंग मशीन द्वारा एन चरणों में की जा सकती है, उसे एक अनजान दो-टेप ट्यूरिंग मशीन द्वारा एन चरणों में किया जा सकता है। {{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 }}
एक विस्मृत ट्यूरिंग मशीन ट्यूरिंग मशीन है, जहां प्रत्येक इनपुट लंबाई के लिए, विभिन्न शीर्षों की गति समय का निश्चित कार्य है, जो इनपुट से स्वतंत्र है। दूसरे शब्दों में, पूर्व निर्धारित क्रम होता है जिसमें विभिन्न टेपों को स्कैन किया जाता है, उन्नत किया जाता है और लिखा जाता है। किसी भी चरण पर टेप पर लिखे गए वास्तविक मान उस लंबाई के प्रत्येक इनपुट के लिए अभी भी भिन्न हो सकते हैं। पिप्पेंजर और फिशर ने दिखाया कि कोई भी गणना जो मल्टी-टेप ट्यूरिंग मशीन द्वारा एन चरणों में की जा सकती है, उसे अनजान दो-टेप ट्यूरिंग मशीन द्वारा एन चरणों में किया जा सकता है। {{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> जब संक्रमण तालिका की जटिलता को स्थिर माना जाता है, तो अनजान मशीनें संयोजन तर्क सर्किट के साथ चरण-वार रैखिक फैशन में मेल खाती हैं। इस प्रकार गणनाओं को आकार में सर्किट समस्याओं के रूप में समझना संभव है {{tmath|O(n \log n)}} और गहराई {{tmath|O(n)}} ([[सर्किट जटिलता]] देखें)। इससे मूल में सुधार होता है {{tmath|O(n^3)}} कुक-लेविन प्रमेय द्वारा परिणाम।
</ref> जब संक्रमण तालिका की जटिलता को स्थिर माना जाता है, तो अनजान मशीनें संयोजन तर्क सर्किट के साथ चरण-वार रैखिक फैशन में मेल खाती हैं। इस प्रकार गणनाओं को आकार में सर्किट समस्याओं के रूप में समझना संभव है {{tmath|O(n \log n)}} और गहराई {{tmath|O(n)}} ([[सर्किट जटिलता]] देखें)। इससे मूल में सुधार होता है {{tmath|O(n^3)}} कुक-लेविन प्रमेय द्वारा परिणाम।


Line 78: Line 78:
{{details|Register machine}}
{{details|Register machine}}


[[पीटर वैन एम्डे बोस]] इस प्रकार की सभी मशीनों को एक वर्ग, रजिस्टर मशीन में शामिल करते हैं।<ref name="Boas" />हालाँकि, ऐतिहासिक रूप से साहित्य ने इस समूह के सबसे आदिम सदस्य यानी काउंटर मशीन को रजिस्टर मशीन भी कहा है। और काउंटर मशीन के सबसे आदिम अवतार को कभी-कभी मिन्स्की मशीन कहा जाता है।
[[पीटर वैन एम्डे बोस]] इस प्रकार की सभी मशीनों को वर्ग, रजिस्टर मशीन में शामिल करते हैं।<ref name="Boas" />हालाँकि, ऐतिहासिक रूप से साहित्य ने इस समूह के सबसे आदिम सदस्य यानी काउंटर मशीन को रजिस्टर मशीन भी कहा है। और काउंटर मशीन के सबसे आदिम अवतार को कभी-कभी मिन्स्की मशीन कहा जाता है।


=== काउंटर मशीन, जिसे रजिस्टर मशीन मॉडल भी कहा जाता है ===
=== काउंटर मशीन, जिसे रजिस्टर मशीन मॉडल भी कहा जाता है ===
{{details|Counter machine}}
{{details|Counter machine}}


आदिम मॉडल रजिस्टर मशीन, वास्तव में, एक मल्टीटेप 2-प्रतीक पोस्ट-ट्यूरिंग मशीन है जिसका व्यवहार प्रतिबंधित है इसलिए इसके टेप साधारण काउंटर की तरह काम करते हैं।
आदिम मॉडल रजिस्टर मशीन, वास्तव में, मल्टीटेप 2-प्रतीक पोस्ट-ट्यूरिंग मशीन है जिसका व्यवहार प्रतिबंधित है इसलिए इसके टेप साधारण काउंटर की तरह काम करते हैं।


मेल्ज़ाक, लैम्बेक और मिन्स्की के समय तक कंप्यूटर प्रोग्राम की धारणा ने एक अलग प्रकार की सरल मशीन का निर्माण किया, जिसमें पोस्ट-ट्यूरिंग टेप से कई बाएं छोर वाले टेप काटे गए थे। सभी मामलों में मॉडल केवल दो टेप प्रतीकों {चिह्न, रिक्त} की अनुमति देते हैं।<ref name="Marvin" />
मेल्ज़ाक, लैम्बेक और मिन्स्की के समय तक कंप्यूटर प्रोग्राम की धारणा ने अलग प्रकार की सरल मशीन का निर्माण किया, जिसमें पोस्ट-ट्यूरिंग टेप से कई बाएं छोर वाले टेप काटे गए थे। सभी मामलों में मॉडल केवल दो टेप प्रतीकों {चिह्न, रिक्त} की अनुमति देते हैं।<ref name="Marvin" />


कुछ संस्करण सकारात्मक पूर्णांकों को केवल एक रजिस्टर में अनुमत अंकों की एक स्ट्रिंग/स्टैक के रूप में दर्शाते हैं (अर्थात बाएं सिरे वाला टेप), और गिनती 0 द्वारा दर्शाए गए एक खाली टेप के रूप में। मिन्स्की ने अपने मॉडल को प्रत्येक टेप के बाएं छोर पर एक अनिवार्य एकल चिह्न प्रदान करने की कीमत पर प्रिंट निर्देश को समाप्त कर दिया।<ref name="Marvin" />
कुछ संस्करण सकारात्मक पूर्णांकों को केवल रजिस्टर में अनुमत अंकों की स्ट्रिंग/स्टैक के रूप में दर्शाते हैं (अर्थात बाएं सिरे वाला टेप), और गिनती 0 द्वारा दर्शाए गए खाली टेप के रूप में। मिन्स्की ने अपने मॉडल को प्रत्येक टेप के बाएं छोर पर अनिवार्य एकल चिह्न प्रदान करने की कीमत पर प्रिंट निर्देश को समाप्त कर दिया।<ref name="Marvin" />


इस मॉडल में सिंगल-एंडेड टेप-एज़-रजिस्टर को काउंटर के रूप में माना जाता है, उनके निर्देश केवल दो तक सीमित होते हैं (या यदि टेस्ट/डिक्रीमेंट निर्देश को परमाणुकृत किया जाता है तो तीन)। दो सामान्य निर्देश सेट निम्नलिखित हैं:
इस मॉडल में सिंगल-एंडेड टेप-एज़-रजिस्टर को काउंटर के रूप में माना जाता है, उनके निर्देश केवल दो तक सीमित होते हैं (या यदि टेस्ट/डिक्रीमेंट निर्देश को परमाणुकृत किया जाता है तो तीन)। दो सामान्य निर्देश सेट निम्नलिखित हैं:
Line 109: Line 109:
| 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>).
(हालांकि, निर्देशों की गोडेल नंबरिंग के साथ मिन्स्की ने सबूत पेश किया कि ऐसी नंबरिंग के साथ सामान्य [[रिकर्सन (कंप्यूटर विज्ञान)]] वास्तव में संभव था; वह सबूत पेश करता है कि μ रिकर्सन वास्तव में संभव है<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>).


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


वैन एम्डे बोस विभिन्न रैम मॉडल को कई उप-प्रकारों में विभाजित करता है:<ref name="Boas" />* SRAM, केवल एक अंकगणितीय निर्देश के साथ उत्तराधिकारी RAM, उत्तराधिकारी (वृद्धि h)। अन्य में CLEAR h और एक IF समानता-बीच-रजिस्टर शामिल है, फिर xxx पर जाएं।
वैन एम्डे बोस विभिन्न रैम मॉडल को कई उप-प्रकारों में विभाजित करता है:<ref name="Boas" />* SRAM, केवल अंकगणितीय निर्देश के साथ उत्तराधिकारी RAM, उत्तराधिकारी (वृद्धि h)। अन्य में CLEAR h और IF समानता-बीच-रजिस्टर शामिल है, फिर xxx पर जाएं।
* रैम: जोड़ और घटाव के साथ मानक मॉडल
* रैम: जोड़ और घटाव के साथ मानक मॉडल
* एमआरएएम: रैम गुणा और भाग के साथ संवर्धित होती है
* एमआरएएम: रैम गुणा और भाग के साथ संवर्धित होती है
Line 124: Line 124:
{{details|Random-access stored-program machine}}
{{details|Random-access stored-program machine}}


आरएएसपी एक रैम है जिसमें निर्देश उनके डेटा के साथ एक ही 'स्पेस' में संग्रहीत होते हैं - यानी रजिस्टरों का क्रम। आरएएसपी की धारणा का वर्णन कम से कम किफेंगस्ट में किया गया था। उनके मॉडल में एक मिल थी - एक संचायक, लेकिन अब निर्देश डेटा के साथ रजिस्टरों में थे - तथाकथित [[वॉन न्यूमैन वास्तुकला]]। जब आरएएसपी में बारी-बारी से सम और विषम रजिस्टर होते हैं - यहां तक ​​​​कि ऑपरेशन कोड (निर्देश) को पकड़ना और विषम को इसके ऑपरेंड (पैरामीटर) को पकड़ना, तो अप्रत्यक्ष पते को केवल एक निर्देश के ऑपरेंड को संशोधित करके प्राप्त किया जाता है।<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>[[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> लेकिन उन्होंने उन्हें अपने डेटा के साथ रजिस्टर स्थान में रखा। (यहां COPY CLEAR का स्थान लेता है जब कोई रजिस्टर जैसे z या 0 से शुरू होता है और हमेशा 0 होता है। यह ट्रिक असामान्य नहीं है। रजिस्टर यूनिट या 1 में यूनिट 1 भी उपयोगी है।)
एल्गॉट और रॉबिन्सन के मूल आरएएसपी मॉडल में रजिस्टर-मशीन मॉडल के फैशन में केवल तीन निर्देश थे,<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> लेकिन उन्होंने उन्हें अपने डेटा के साथ रजिस्टर स्थान में रखा। (यहां COPY CLEAR का स्थान लेता है जब कोई रजिस्टर जैसे z या 0 से शुरू होता है और हमेशा 0 होता है। यह ट्रिक असामान्य नहीं है। रजिस्टर यूनिट या 1 में यूनिट 1 भी उपयोगी है।)
: { INC ( r ), कॉपी ( r )<sub>i</sub>, आर<sub>j</sub> ), जेई (आर<sub>i</sub>, आर<sub>i</sub>, z ) }
: { INC ( r ), कॉपी ( r )<sub>i</sub>, आर<sub>j</sub> ), जेई (आर<sub>i</sub>, आर<sub>i</sub>, z ) }


आरएएसपी मॉडल अप्रत्यक्ष के साथ-साथ प्रत्यक्ष-संबोधन की भी अनुमति देते हैं; कुछ लोग तत्काल निर्देशों की भी अनुमति देते हैं, उदा. संचायक को स्थिरांक 3 के साथ लोड करें। निर्देश अत्यधिक प्रतिबंधित सेट के हो सकते हैं जैसे कि हार्टमैनिस के निम्नलिखित 16 निर्देश।<ref>[[J. Hartmanis]] (1971), "Computational Complexity of Random Access Stored Program Machines," Mathematical Systems Theory 5, 3 (1971) pp. 232–245.</ref> यह मॉडल एक संचायक ए का उपयोग करता है। निमोनिक्स वे हैं जिनका उपयोग लेखकों ने किया है (उनका सीएलए स्थिर या रजिस्टर से लोड संचायक है; एसटीओ स्टोर संचायक है)। जंप को छोड़कर, उनका सिंटैक्स निम्नलिखित है: n, <n>, <<n>> तत्काल, प्रत्यक्ष और अप्रत्यक्ष के लिए)। जंप दो ट्रांसफर निर्देशों टीआरए के माध्यम से होते हैं - सीधे एन या परोक्ष रूप से बिना शर्त जंप < एन > निर्देश काउंटर, टीआरजेड में रजिस्टर एन की सामग्री को जाम करना (यदि टीआरए के समान ही एक्युमुलेटर शून्य है तो सशर्त जंप):
आरएएसपी मॉडल अप्रत्यक्ष के साथ-साथ प्रत्यक्ष-संबोधन की भी अनुमति देते हैं; कुछ लोग तत्काल निर्देशों की भी अनुमति देते हैं, उदा. संचायक को स्थिरांक 3 के साथ लोड करें। निर्देश अत्यधिक प्रतिबंधित सेट के हो सकते हैं जैसे कि हार्टमैनिस के निम्नलिखित 16 निर्देश।<ref>[[J. Hartmanis]] (1971), "Computational Complexity of Random Access Stored Program Machines," Mathematical Systems Theory 5, 3 (1971) pp. 232–245.</ref> यह मॉडल संचायक ए का उपयोग करता है। निमोनिक्स वे हैं जिनका उपयोग लेखकों ने किया है (उनका सीएलए स्थिर या रजिस्टर से लोड संचायक है; एसटीओ स्टोर संचायक है)। जंप को छोड़कर, उनका सिंटैक्स निम्नलिखित है: n, <n>, <<n>> तत्काल, प्रत्यक्ष और अप्रत्यक्ष के लिए)। जंप दो ट्रांसफर निर्देशों टीआरए के माध्यम से होते हैं - सीधे एन या परोक्ष रूप से बिना शर्त जंप < एन > निर्देश काउंटर, टीआरजेड में रजिस्टर एन की सामग्री को जाम करना (यदि टीआरए के समान ही एक्युमुलेटर शून्य है तो सशर्त जंप):
:{ n जोड़ें, जोड़ें < n >, जोड़ें << 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 >, रुकें }
:{ n जोड़ें, जोड़ें < n >, जोड़ें << 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 >, रुकें }


Line 134: Line 134:
{{details|Pointer machine}}
{{details|Pointer machine}}


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


==इनपुट और आउटपुट वाली मशीनें==
==इनपुट और आउटपुट वाली मशीनें==
उपरोक्त टेप-आधारित मशीनों में से कोई भी इनपुट और आउटपुट टेप से सुसज्जित हो सकती है; उपरोक्त रजिस्टर-आधारित मशीनों में से कोई भी समर्पित इनपुट और आउटपुट रजिस्टरों से सुसज्जित हो सकती है। उदाहरण के लिए, शॉनहेज पॉइंटर-मशीन मॉडल में दो निर्देश हैं जिन्हें इनपुट λ कहा जाता है<sub>0</sub>,एल<sub>1</sub>और आउटपुट β।
उपरोक्त टेप-आधारित मशीनों में से कोई भी इनपुट और आउटपुट टेप से सुसज्जित हो सकती है; उपरोक्त रजिस्टर-आधारित मशीनों में से कोई भी समर्पित इनपुट और आउटपुट रजिस्टरों से सुसज्जित हो सकती है। उदाहरण के लिए, शॉनहेज पॉइंटर-मशीन मॉडल में दो निर्देश हैं जिन्हें इनपुट λ कहा जाता है<sub>0</sub>,एल<sub>1</sub>और आउटपुट β।


पारंपरिक मॉडल के साथ मल्टी-टेप मशीनों पर [[अधरेखीय]] स्पेस जटिलता का अध्ययन करना मुश्किल है, क्योंकि आकार n का इनपुट पहले से ही स्पेस n लेता है। इस प्रकार, छोटी [[DSPACE]] कक्षाओं का अध्ययन करने के लिए, हमें एक अलग मॉडल का उपयोग करना चाहिए। कुछ अर्थों में, यदि हम इनपुट टेप पर कभी नहीं लिखते हैं, तो हम इस स्थान के लिए स्वयं को चार्ज नहीं करना चाहते हैं। और यदि हम अपने आउटपुट टेप से कभी नहीं पढ़ते हैं, तो हम इस स्थान के लिए स्वयं को चार्ज नहीं करना चाहते हैं।
पारंपरिक मॉडल के साथ मल्टी-टेप मशीनों पर [[अधरेखीय]] स्पेस जटिलता का अध्ययन करना मुश्किल है, क्योंकि आकार n का इनपुट पहले से ही स्पेस n लेता है। इस प्रकार, छोटी [[DSPACE]] कक्षाओं का अध्ययन करने के लिए, हमें अलग मॉडल का उपयोग करना चाहिए। कुछ अर्थों में, यदि हम इनपुट टेप पर कभी नहीं लिखते हैं, तो हम इस स्थान के लिए स्वयं को चार्ज नहीं करना चाहते हैं। और यदि हम अपने आउटपुट टेप से कभी नहीं पढ़ते हैं, तो हम इस स्थान के लिए स्वयं को चार्ज नहीं करना चाहते हैं।


हम इनपुट और आउटपुट के साथ के-स्ट्रिंग ट्यूरिंग मशीन पेश करके इस समस्या का समाधान करते हैं। यह एक साधारण के-स्ट्रिंग ट्यूरिंग मशीन के समान है, सिवाय ट्रांज़िशन फ़ंक्शन के {{mvar|δ}} प्रतिबंधित है ताकि इनपुट टेप को कभी भी बदला न जा सके, और ताकि आउटपुट हेड कभी भी बाईं ओर न घूम सके। यह मॉडल हमें रैखिक से छोटे नियतात्मक अंतरिक्ष वर्गों को परिभाषित करने की अनुमति देता है। इनपुट-और-आउटपुट वाली ट्यूरिंग मशीनों में भी अन्य ट्यूरिंग मशीनों की तरह ही समय जटिलता होती है; पापादिमित्रिउ 1994 प्रस्ताव 2.2 के शब्दों में:
हम इनपुट और आउटपुट के साथ के-स्ट्रिंग ट्यूरिंग मशीन पेश करके इस समस्या का समाधान करते हैं। यह साधारण के-स्ट्रिंग ट्यूरिंग मशीन के समान है, सिवाय ट्रांज़िशन फ़ंक्शन के {{mvar|δ}} प्रतिबंधित है ताकि इनपुट टेप को कभी भी बदला न जा सके, और ताकि आउटपुट हेड कभी भी बाईं ओर न घूम सके। यह मॉडल हमें रैखिक से छोटे नियतात्मक अंतरिक्ष वर्गों को परिभाषित करने की अनुमति देता है। इनपुट-और-आउटपुट वाली ट्यूरिंग मशीनों में भी अन्य ट्यूरिंग मशीनों की तरह ही समय जटिलता होती है; पापादिमित्रिउ 1994 प्रस्ताव 2.2 के शब्दों में:


:किसी भी के-स्ट्रिंग ट्यूरिंग मशीन एम के लिए समय सीमा के भीतर काम करना {{tmath|f(n)}} वहां एक है {{tmath|(k+2)}}-स्ट्रिंग ट्यूरिंग मशीन एम' इनपुट और आउटपुट के साथ, जो समय सीमा के भीतर संचालित होती है {{tmath|O(f(n))}}.
:किसी भी के-स्ट्रिंग ट्यूरिंग मशीन एम के लिए समय सीमा के भीतर काम करना {{tmath|f(n)}} वहां है {{tmath|(k+2)}}-स्ट्रिंग ट्यूरिंग मशीन एम' इनपुट और आउटपुट के साथ, जो समय सीमा के भीतर संचालित होती है {{tmath|O(f(n))}}.


इनपुट और आउटपुट के साथ के-स्ट्रिंग ट्यूरिंग मशीनों का उपयोग जटिलता संसाधन DSPACE की औपचारिक परिभाषा में किया जा सकता है।<ref>{{cite book|author = [[Christos Papadimitriou]] | year = 1993 | title = अभिकलनात्मक जटिलता| publisher = Addison Wesley | edition = 1st | isbn = 0-201-53082-1}} Chapter 2: Turing machines, pp.&nbsp;19–56.</ref>
इनपुट और आउटपुट के साथ के-स्ट्रिंग ट्यूरिंग मशीनों का उपयोग जटिलता संसाधन DSPACE की औपचारिक परिभाषा में किया जा सकता है।<ref>{{cite book|author = [[Christos Papadimitriou]] | year = 1993 | title = अभिकलनात्मक जटिलता| publisher = Addison Wesley | edition = 1st | isbn = 0-201-53082-1}} Chapter 2: Turing machines, pp.&nbsp;19–56.</ref>
Line 150: Line 150:
== अन्य समकक्ष मशीनें और विधियाँ ==
== अन्य समकक्ष मशीनें और विधियाँ ==


* बहुआयामी ट्यूरिंग मशीन: उदाहरण के लिए, शॉनहेज का एक मॉडल चार हेड-मूवमेंट कमांड {उत्तर, दक्षिण, पूर्व, पश्चिम} का उपयोग करता है।<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 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:
  |pages=437–455
  |pages=437–455
  |doi=10.2307/1970290|issue=3|jstor=1970290
  |doi=10.2307/1970290|issue=3|jstor=1970290
}}</ref><ref>[[John C. Shepherdson]] and [[H. E. Sturgis]] received December 1961 ''Computability of Recursive Functions'', [[Journal of the ACM]] 10:217-255, 1963</ref> * [[मार्कोव एल्गोरिथ्म]] एक और उल्लेखनीय सरल कम्प्यूटेशनल मॉडल है, जो ट्यूरिंग मशीनों के समकक्ष स्ट्रिंग पुनर्लेखन पर आधारित है।
}}</ref><ref>[[John C. Shepherdson]] and [[H. E. Sturgis]] received December 1961 ''Computability of Recursive Functions'', [[Journal of the ACM]] 10:217-255, 1963</ref> * [[मार्कोव एल्गोरिथ्म]] और उल्लेखनीय सरल कम्प्यूटेशनल मॉडल है, जो ट्यूरिंग मशीनों के समकक्ष स्ट्रिंग पुनर्लेखन पर आधारित है।
* [[लैम्ब्डा कैलकुलस]]
* [[लैम्ब्डा कैलकुलस]]
* कतार स्वचालित
* कतार स्वचालित

Revision as of 11:17, 9 August 2023

Turing machines
Machine
Variants
Science

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

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

ट्यूरिंग मशीन मॉडल के समतुल्य मशीनें

ट्यूरिंग तुल्यता

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

'अनुक्रमिक-मशीन मॉडल'

निम्नलिखित सभी को समानांतर मशीन मॉडल से अलग करने के लिए अनुक्रमिक मशीन मॉडल कहा जाता है।[2]


टेप-आधारित ट्यूरिंग मशीनें

ट्यूरिंग का ए-मशीन मॉडल

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

प्रतिबंधित प्रतीकों और/या प्रतिबंधित निर्देशों वाली एकल-टेप मशीनें

निम्नलिखित मॉडल एकल टेप ट्यूरिंग मशीनें हैं, लेकिन (i) प्रतिबंधित टेप प्रतीकों {चिह्न, रिक्त}, और/या (ii) अनुक्रमिक, कंप्यूटर-जैसे निर्देश, और/या (iii) पूरी तरह से परमाणुकृत मशीन-क्रियाओं से प्रतिबंधित हैं।

पोस्ट का सूत्रीकरण 1 गणना का मॉडल

Further information: Post–Turing machine

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

उनका बेहद सरल मॉडल किसी भी ट्यूरिंग मशीन का अनुकरण कर सकता है, और हालांकि उनके 1936 फॉर्मूलेशन 1 में प्रोग्राम या मशीन शब्द का उपयोग नहीं किया गया है, यह प्रभावी रूप से बहुत ही आदिम प्रोग्राम योग्य कंप्यूटर और संबंधित प्रोग्रामिंग भाषा का फॉर्मूलेशन है, जिसमें बॉक्स अनबाउंड बिटस्ट्रिंग मेमोरी के रूप में कार्य करते हैं। , और प्रोग्राम का निर्माण करने वाले निर्देशों का सेट।

वांग मशीनें

Further information: Wang B-machine

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

{ शिफ्ट-बाएं, शिफ्ट-दाएं, मार्क-स्क्वायर, मिटाएं-स्क्वायर, जंप-इफ-स्क्वायर-चिह्नित-से xxx }

और निर्देश-सेट के साथ उनकी सबसे गंभीर रूप से कम की गई 4-निर्देश वांग बी-मशीन (बेसिक के लिए बी)

{ शिफ्ट-बाएं, शिफ्ट-दाएं, मार्क-स्क्वायर, जंप-इफ-स्क्वायर-चिह्नित-से xxx }

जिसमें ERASE-SQUARE निर्देश भी नहीं है।

कई लेखकों ने बाद में वांग द्वारा चर्चा की गई मशीनों के वेरिएंट पेश किए:

मिन्स्की ने (मल्टी-टेप) काउंटर मशीन मॉडल के अपने संस्करण के साथ वांग की धारणा को विकसित किया, जो अलग-अलग सिरों की SHIFT-LEFT और SHIFT-दाएँ गति की अनुमति देता है, लेकिन बिल्कुल भी मुद्रण नहीं करता है।[3]इस मामले में टेप बाएं सिरे वाले होंगे, प्रत्येक सिरे पर अंत को इंगित करने के लिए निशान होगा। वह इसे ही टेप तक सीमित करने में सक्षम था, लेकिन अधिक सरल {शिफ्ट-बाएं = कमी, शिफ्ट-दाएं = वृद्धि} के बजाय गुणन और विभाजन के समतुल्य मल्टी-टेप-स्क्वायर गति को शुरू करने की कीमत पर।

डेविस ने वांग द्वारा चर्चा की गई मशीनों में से में स्पष्ट एचएएलटी निर्देश जोड़कर निर्देश-सेट के साथ मॉडल का उपयोग किया

{शिफ्ट-बाएं, शिफ्ट-दाएं, मिटाएं, चिह्नित करें, वर्ग-चिह्नित xxx पर कूदें, xxx पर कूदें, रुकें }

और 2 से बड़े आकार के टेप-अक्षरों वाले संस्करणों पर भी विचार किया गया।

बोहम की सैद्धांतिक मशीनी भाषा पी

Further information: P"

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

मल्टी-टेप ट्यूरिंग मशीनें

Further information: Multitape Turing machine

व्यावहारिक विश्लेषण में, विभिन्न प्रकार की मल्टी-टेप ट्यूरिंग मशीनों का अक्सर उपयोग किया जाता है। मल्टी-टेप मशीनें सिंगल-टेप मशीनों के समान होती हैं, लेकिन कुछ स्थिर k संख्या में स्वतंत्र टेप होते हैं।

नियतात्मक और गैर-नियतात्मक ट्यूरिंग मशीनें

Further information: non-deterministic Turing machine

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

विस्मृत ट्यूरिंग मशीनें

एक विस्मृत ट्यूरिंग मशीन ट्यूरिंग मशीन है, जहां प्रत्येक इनपुट लंबाई के लिए, विभिन्न शीर्षों की गति समय का निश्चित कार्य है, जो इनपुट से स्वतंत्र है। दूसरे शब्दों में, पूर्व निर्धारित क्रम होता है जिसमें विभिन्न टेपों को स्कैन किया जाता है, उन्नत किया जाता है और लिखा जाता है। किसी भी चरण पर टेप पर लिखे गए वास्तविक मान उस लंबाई के प्रत्येक इनपुट के लिए अभी भी भिन्न हो सकते हैं। पिप्पेंजर और फिशर ने दिखाया कि कोई भी गणना जो मल्टी-टेप ट्यूरिंग मशीन द्वारा एन चरणों में की जा सकती है, उसे अनजान दो-टेप ट्यूरिंग मशीन द्वारा एन चरणों में किया जा सकता है। कदम।[4] जब संक्रमण तालिका की जटिलता को स्थिर माना जाता है, तो अनजान मशीनें संयोजन तर्क सर्किट के साथ चरण-वार रैखिक फैशन में मेल खाती हैं। इस प्रकार गणनाओं को आकार में सर्किट समस्याओं के रूप में समझना संभव है और गहराई (सर्किट जटिलता देखें)। इससे मूल में सुधार होता है कुक-लेविन प्रमेय द्वारा परिणाम।

मशीन मॉडल पंजीकृत करें

Further information: Register machine

पीटर वैन एम्डे बोस इस प्रकार की सभी मशीनों को वर्ग, रजिस्टर मशीन में शामिल करते हैं।[2]हालाँकि, ऐतिहासिक रूप से साहित्य ने इस समूह के सबसे आदिम सदस्य यानी काउंटर मशीन को रजिस्टर मशीन भी कहा है। और काउंटर मशीन के सबसे आदिम अवतार को कभी-कभी मिन्स्की मशीन कहा जाता है।

काउंटर मशीन, जिसे रजिस्टर मशीन मॉडल भी कहा जाता है

Further information: Counter machine

आदिम मॉडल रजिस्टर मशीन, वास्तव में, मल्टीटेप 2-प्रतीक पोस्ट-ट्यूरिंग मशीन है जिसका व्यवहार प्रतिबंधित है इसलिए इसके टेप साधारण काउंटर की तरह काम करते हैं।

मेल्ज़ाक, लैम्बेक और मिन्स्की के समय तक कंप्यूटर प्रोग्राम की धारणा ने अलग प्रकार की सरल मशीन का निर्माण किया, जिसमें पोस्ट-ट्यूरिंग टेप से कई बाएं छोर वाले टेप काटे गए थे। सभी मामलों में मॉडल केवल दो टेप प्रतीकों {चिह्न, रिक्त} की अनुमति देते हैं।[3]

कुछ संस्करण सकारात्मक पूर्णांकों को केवल रजिस्टर में अनुमत अंकों की स्ट्रिंग/स्टैक के रूप में दर्शाते हैं (अर्थात बाएं सिरे वाला टेप), और गिनती 0 द्वारा दर्शाए गए खाली टेप के रूप में। मिन्स्की ने अपने मॉडल को प्रत्येक टेप के बाएं छोर पर अनिवार्य एकल चिह्न प्रदान करने की कीमत पर प्रिंट निर्देश को समाप्त कर दिया।[3]

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

(1): { INC ( r ), DEC ( r ), JZ ( r,z ) }, यानी।
{रजिस्टर #r की सामग्री में वृद्धि; रजिस्टर #r की कमी सामग्री; यदि #r=शून्य की सामग्री है तो निर्देश पर जाएं #z}
(2): {सीएलआर (आर); इंक (आर); जेई (आरi, आरj, z ) }, अर्थात्।
{रजिस्टर आर की स्पष्ट सामग्री; आर की सामग्री में वृद्धि; आर की सामग्री की तुलना करेंi आर कोj और यदि समान है तो निर्देश z पर जाएं}

यद्यपि उनका मॉडल इस सरल विवरण से अधिक जटिल है, मेल्ज़ाक कंकड़ मॉडल ने बहु-विषयकता की अनुमति देने के लिए काउंटर की इस धारणा को बढ़ाया। कंकड़ जोड़ता और घटाता है।

रैंडम-एक्सेस मशीन (रैम) मॉडल

Further information: Random-access machine

मेल्ज़ाक ने अपने रजिस्टर/काउंटर-मशीन मॉडल में कुछ गंभीर दोषों को पहचाना:[5] (i) अप्रत्यक्ष संबोधन के बिना वह आसानी से यह नहीं दिखा पाएगा कि मॉडल ट्यूरिंग पूर्णता है, (ii) प्रोग्राम और रजिस्टर अलग-अलग स्थानों पर थे, इसलिए प्रोग्राम को स्व-संशोधित करना आसान नहीं होगा। जब मेल्ज़ाक ने अपने मॉडल में अप्रत्यक्ष संबोधन जोड़ा तो उन्होंने रैंडम एक्सेस मशीन मॉडल बनाया।

(हालांकि, निर्देशों की गोडेल नंबरिंग के साथ मिन्स्की ने सबूत पेश किया कि ऐसी नंबरिंग के साथ सामान्य रिकर्सन (कंप्यूटर विज्ञान) वास्तव में संभव था; वह सबूत पेश करता है कि μ रिकर्सन वास्तव में संभव है[3]).

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

वैन एम्डे बोस विभिन्न रैम मॉडल को कई उप-प्रकारों में विभाजित करता है:[2]* SRAM, केवल अंकगणितीय निर्देश के साथ उत्तराधिकारी RAM, उत्तराधिकारी (वृद्धि h)। अन्य में CLEAR h और IF समानता-बीच-रजिस्टर शामिल है, फिर xxx पर जाएं।

  • रैम: जोड़ और घटाव के साथ मानक मॉडल
  • एमआरएएम: रैम गुणा और भाग के साथ संवर्धित होती है
  • ब्रैम, एमबीआरएएम: रैम और एमआरएएम के बिटवाइज़ बूलियन संस्करण
  • एन****: नाम से पहले एन के साथ उपरोक्त में से किसी का गैर-नियतात्मक संस्करण

रैंडम-एक्सेस संग्रहीत प्रोग्राम (आरएएसपी) मशीन मॉडल

Further information: Random-access stored-program machine

आरएएसपी रैम है जिसमें निर्देश उनके डेटा के साथ ही 'स्पेस' में संग्रहीत होते हैं - यानी रजिस्टरों का क्रम। आरएएसपी की धारणा का वर्णन कम से कम किफेंगस्ट में किया गया था। उनके मॉडल में मिल थी - संचायक, लेकिन अब निर्देश डेटा के साथ रजिस्टरों में थे - तथाकथित वॉन न्यूमैन वास्तुकला। जब आरएएसपी में बारी-बारी से सम और विषम रजिस्टर होते हैं - यहां तक ​​​​कि ऑपरेशन कोड (निर्देश) को पकड़ना और विषम को इसके ऑपरेंड (पैरामीटर) को पकड़ना, तो अप्रत्यक्ष पते को केवल निर्देश के ऑपरेंड को संशोधित करके प्राप्त किया जाता है।[6] एल्गॉट और रॉबिन्सन के मूल आरएएसपी मॉडल में रजिस्टर-मशीन मॉडल के फैशन में केवल तीन निर्देश थे,[7] लेकिन उन्होंने उन्हें अपने डेटा के साथ रजिस्टर स्थान में रखा। (यहां COPY CLEAR का स्थान लेता है जब कोई रजिस्टर जैसे z या 0 से शुरू होता है और हमेशा 0 होता है। यह ट्रिक असामान्य नहीं है। रजिस्टर यूनिट या 1 में यूनिट 1 भी उपयोगी है।)

{ INC ( r ), कॉपी ( r )i, आरj ), जेई (आरi, आरi, z ) }

आरएएसपी मॉडल अप्रत्यक्ष के साथ-साथ प्रत्यक्ष-संबोधन की भी अनुमति देते हैं; कुछ लोग तत्काल निर्देशों की भी अनुमति देते हैं, उदा. संचायक को स्थिरांक 3 के साथ लोड करें। निर्देश अत्यधिक प्रतिबंधित सेट के हो सकते हैं जैसे कि हार्टमैनिस के निम्नलिखित 16 निर्देश।[8] यह मॉडल संचायक ए का उपयोग करता है। निमोनिक्स वे हैं जिनका उपयोग लेखकों ने किया है (उनका सीएलए स्थिर या रजिस्टर से लोड संचायक है; एसटीओ स्टोर संचायक है)। जंप को छोड़कर, उनका सिंटैक्स निम्नलिखित है: n, <n>, <<n>> तत्काल, प्रत्यक्ष और अप्रत्यक्ष के लिए)। जंप दो ट्रांसफर निर्देशों टीआरए के माध्यम से होते हैं - सीधे एन या परोक्ष रूप से बिना शर्त जंप < एन > निर्देश काउंटर, टीआरजेड में रजिस्टर एन की सामग्री को जाम करना (यदि टीआरए के समान ही एक्युमुलेटर शून्य है तो सशर्त जंप):

{ n जोड़ें, जोड़ें < n >, जोड़ें << 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 >, रुकें }

पॉइंटर मशीन मॉडल

Further information: Pointer machine

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

इनपुट और आउटपुट वाली मशीनें

उपरोक्त टेप-आधारित मशीनों में से कोई भी इनपुट और आउटपुट टेप से सुसज्जित हो सकती है; उपरोक्त रजिस्टर-आधारित मशीनों में से कोई भी समर्पित इनपुट और आउटपुट रजिस्टरों से सुसज्जित हो सकती है। उदाहरण के लिए, शॉनहेज पॉइंटर-मशीन मॉडल में दो निर्देश हैं जिन्हें इनपुट λ कहा जाता है0,एल1और आउटपुट β।

पारंपरिक मॉडल के साथ मल्टी-टेप मशीनों पर अधरेखीय स्पेस जटिलता का अध्ययन करना मुश्किल है, क्योंकि आकार n का इनपुट पहले से ही स्पेस n लेता है। इस प्रकार, छोटी DSPACE कक्षाओं का अध्ययन करने के लिए, हमें अलग मॉडल का उपयोग करना चाहिए। कुछ अर्थों में, यदि हम इनपुट टेप पर कभी नहीं लिखते हैं, तो हम इस स्थान के लिए स्वयं को चार्ज नहीं करना चाहते हैं। और यदि हम अपने आउटपुट टेप से कभी नहीं पढ़ते हैं, तो हम इस स्थान के लिए स्वयं को चार्ज नहीं करना चाहते हैं।

हम इनपुट और आउटपुट के साथ के-स्ट्रिंग ट्यूरिंग मशीन पेश करके इस समस्या का समाधान करते हैं। यह साधारण के-स्ट्रिंग ट्यूरिंग मशीन के समान है, सिवाय ट्रांज़िशन फ़ंक्शन के δ प्रतिबंधित है ताकि इनपुट टेप को कभी भी बदला न जा सके, और ताकि आउटपुट हेड कभी भी बाईं ओर न घूम सके। यह मॉडल हमें रैखिक से छोटे नियतात्मक अंतरिक्ष वर्गों को परिभाषित करने की अनुमति देता है। इनपुट-और-आउटपुट वाली ट्यूरिंग मशीनों में भी अन्य ट्यूरिंग मशीनों की तरह ही समय जटिलता होती है; पापादिमित्रिउ 1994 प्रस्ताव 2.2 के शब्दों में:

किसी भी के-स्ट्रिंग ट्यूरिंग मशीन एम के लिए समय सीमा के भीतर काम करना वहां है -स्ट्रिंग ट्यूरिंग मशीन एम' इनपुट और आउटपुट के साथ, जो समय सीमा के भीतर संचालित होती है .

इनपुट और आउटपुट के साथ के-स्ट्रिंग ट्यूरिंग मशीनों का उपयोग जटिलता संसाधन DSPACE की औपचारिक परिभाषा में किया जा सकता है।[9]


अन्य समकक्ष मशीनें और विधियाँ

  • बहुआयामी ट्यूरिंग मशीन: उदाहरण के लिए, शॉनहेज का मॉडल चार हेड-मूवमेंट कमांड {उत्तर, दक्षिण, पूर्व, पश्चिम} का उपयोग करता है।[10]
  • सिंगल-टेप, मल्टी-हेड ट्यूरिंग मशीन: टैग की समस्या के अनिर्णय प्रमाण में, मिन्स्की और शेफर्डसन और स्टर्गिस ने ही टेप वाली मशीनों का वर्णन किया जो हेड के साथ टेप के साथ पढ़ सकती थीं और दूसरे के साथ टेप के साथ आगे लिख सकती थीं।[11][12] * मार्कोव एल्गोरिथ्म और उल्लेखनीय सरल कम्प्यूटेशनल मॉडल है, जो ट्यूरिंग मशीनों के समकक्ष स्ट्रिंग पुनर्लेखन पर आधारित है।
  • लैम्ब्डा कैलकुलस
  • कतार स्वचालित

संदर्भ

  1. ↑ John Hopcroft and Jeffrey Ullman (1979). ऑटोमेटा सिद्धांत, भाषाएँ और संगणना का परिचय (1st ed.). Addison–Wesley, Reading Mass. ISBN 0-201-02988-X.
  2. ↑ 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. ↑ 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."
  4. ↑ 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
  5. ↑ 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.
  6. ↑ Stephen A. Cook and Robert A. Reckhow (1972), Time-bounded random access machines, Journal of Computer Systems Science 7 (1973), 354–375.
  7. ↑ 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.
  8. ↑ J. Hartmanis (1971), "Computational Complexity of Random Access Stored Program Machines," Mathematical Systems Theory 5, 3 (1971) pp. 232–245.
  9. ↑ Christos Papadimitriou (1993). अभिकलनात्मक जटिलता (1st ed.). Addison Wesley. ISBN 0-201-53082-1. Chapter 2: Turing machines, pp. 19–56.
  10. ↑ A. Schōnhage (1980), Storage Modification Machines, Society for Industrial and Applied Mathematics, SIAM J. Comput. Vol. 9, No. 3, August 1980.
  11. ↑ 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.
  12. ↑ John C. Shepherdson and H. E. Sturgis received December 1961 Computability of Recursive Functions, Journal of the ACM 10:217-255, 1963
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=ट्यूरिंग_मशीन_समकक्ष&oldid=249448’