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

Revision as of 12:25, 9 August 2023

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

वांग मशीन

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

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

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

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

जिसमें इरेज-स्क्वायर निर्देश भी नहीं है।

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

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

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

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

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

बोहम की सैद्धांतिक मशीनी लैंग्वेज पी

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

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

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

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

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

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

ओब्लिवियस ट्यूरिंग मशीन ट्यूरिंग मशीन है, जहां प्रत्येक इनपुट लंबाई के लिए, विभिन्न शीर्षों की गति समय का निश्चित कार्य है, जो इनपुट से स्वतंत्र है। दूसरे शब्दों में, पूर्व निर्धारित क्रम होता है जिसमें विभिन्न टेपों को स्कैन किया जाता है, उन्नत किया जाता है और लिखा जाता है। किसी भी स्टेज पर टेप पर लिखे गए वास्तविक मान उस लंबाई के प्रत्येक इनपुट के लिए अभी भी भिन्न हो सकते हैं। पिप्पेंजर और फिशर ने दिखाया कि कोई भी गणना जो मल्टी-टेप ट्यूरिंग मशीन द्वारा एन स्टेज में की जा सकती है, उसे ओब्लिवियस दो-टेप ट्यूरिंग मशीन द्वारा एन स्टेज में किया जा सकता है। $O(n\log n)$ स्टेज ^[4] ऑब्लिवियस मशीनें कॉम्बिनेशन लॉजिक परिपथ के साथ स्टेज-वार रैखिक फैशन में मेल खाती हैं, जब संक्रमण टेबल की सम्मिश्रता को स्थिर माना जाता है। इस प्रकार आकार $O(n\log n)$ और डेप्थ $O(n)$ में परिपथ समस्याओं के रूप में गणना करना संभव है (परिपथ सम्मिश्रता देखें)। यह कुक और लेविन के मूल $O(n^{3})$ परिणाम में सुधार करता है।

रजिस्टर मशीन मॉडल

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

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

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

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

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

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

(1): { INC ( r ), DEC ( r ), JZ ( r,z ) }, अर्थात।

{रजिस्टर #r की कंटेंट में वृद्धि; रजिस्टर #r की कमी कंटेंट; यदि #r=शून्य की कंटेंट है तो निर्देश पर जाएं #z}

(2): { CLR ( r ); INC ( r ); JE ( r_i, r_j, z ) }, i.e., अर्थात्।

{रजिस्टर आर की स्पष्ट कंटेंट; r की कंटेंट में वृद्धि; r_i को r_j की कंटेंट की तुलना करें और यदि समान है तो निर्देश z पर जाएं}

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

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

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

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

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

वैन एम्डे बोस विभिन्न रैम मॉडल को विभिन्न उप-प्रकारों में विभाजित करता है:^[2]

एसआरएएम, केवल अंकगणितीय निर्देश के साथ उत्तराधिकारी रैम, उत्तराधिकारी (वृद्धि h) अन्य में क्लियर h और IF समानता-मध्य-रजिस्टर सम्मिलित है, फिर xxx पर जाएं।

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

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

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

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

{ INC ( r ), COPY ( r_i, r_j ), JE ( r_i, r_i, z ) }

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

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

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

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

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

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

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

किसी भी k-स्ट्रिंग ट्यूरिंग मशीन M के लिए जो समयबद्ध

f(n)

के अन्दर कार्य करती है, इनपुट और आउटपुट के साथ एक

(k+2)

-स्ट्रिंग ट्यूरिंग मशीन M' है जो समयबद्ध

O(f(n))

के अन्दर कार्य करती है।

इनपुट और आउटपुट के साथ 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

[1] John Hopcroft and Jeffrey Ullman (1979). ऑटोमेटा सिद्धांत, भाषाएँ और संगणना का परिचय (1st ed.). Addison–Wesley, Reading Mass. ISBN 0-201-02988-X.

[Boas-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.

[Marvin-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.

[Schonage80-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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

@@ Line 2: / Line 2: @@
 {{turing}}
-[[ट्यूरिंग मशीन]] काल्पनिक कंप्यूटिंग डिवाइस है, जिसकी कल्पना सबसे पहले [[एलन ट्यूरिंग]] ने 1936 में की थी। ट्यूरिंग मशीनें नियमों की सीमित तालिका के अनुसार टेप की संभावित अनंत पट्टी पर प्रतीकों में हेरफेर करती हैं, और वे कंप्यूटर एल्गोरिदम की धारणा के लिए सैद्धांतिक आधार प्रदान करती हैं।
+[[ट्यूरिंग मशीन]] काल्पनिक कंप्यूटिंग डिवाइस है, जिसकी कल्पना सबसे पहले [[एलन ट्यूरिंग]] ने 1936 में की थी। ट्यूरिंग मशीन नियमों की सीमित टेबल के अनुसार टेप की संभावित इनफिनिट स्ट्रिप पर प्रतीकों में परिवर्तित करती हैं, और वह कंप्यूटर एल्गोरिदम की धारणा के लिए सैद्धांतिक आधार प्रदान करती हैं।
-जबकि निम्नलिखित में से किसी भी मॉडल में सिंगल-टेप, वन-वे अनंत, मल्टी-सिंबल ट्यूरिंग-मशीन मॉडल की तुलना में अधिक शक्ति नहीं दिखाई गई है, उनके लेखकों ने उन्हें परिभाषित किया और प्रश्नों की जांच करने और समस्याओं को अधिक आसानी से हल करने के लिए उपयोग किया, यदि वे ट्यूरिंग के ए-मशीन मॉडल के साथ बने रहते।
+जबकि निम्नलिखित में से किसी भी मॉडल में सिंगल-टेप, वन-वे इनफिनिट, मल्टी-सिंबल ट्यूरिंग-मशीन मॉडल की तुलना में अधिक शक्ति नहीं दिखाई गई है, उनके लेखकों ने उन्हें परिभाषित किया और प्रश्नों की जांच करने और समस्याओं को अधिक सरलता से हल करने के लिए उपयोग किया था, यदि वह ट्यूरिंग के ए-मशीन मॉडल के साथ बने रहते है।
-== ट्यूरिंग मशीन मॉडल के समतुल्य मशीनें ==
+== ट्यूरिंग मशीन मॉडल के समतुल्य मशीन ==
-ट्यूरिंग तुल्यता
+==== ट्यूरिंग तुल्यता ====
+विभिन्न मशीन जिनके बारे में सोचा जा सकता है कि उनमें साधारण सार्वभौमिक ट्यूरिंग मशीन की तुलना में अधिक कम्प्यूटेशनल क्षमता है, उन्हें दिखाया जा सकता है कि उनमें अधिक शक्ति नहीं है।<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> वे शायद तेजी से गणना कर सकते हैं, या कम मेमोरी का उपयोग कर सकते हैं, या उनका निर्देश सेट छोटा हो सकता है, लेकिन वे अधिक शक्तिशाली तरीके से गणना नहीं कर सकते (यानी अधिक गणितीय कार्य)। (चर्च-ट्यूरिंग थीसिस इसे सत्य मानती है: कि किसी भी चीज़ की गणना किसी ट्यूरिंग मशीन द्वारा की जा सकती है।)
+==== अनुक्रमिक-मशीन मॉडल' ====
+निम्नलिखित सभी को समानांतर मशीन मॉडल से पृथक करने के लिए अनुक्रमिक मशीन मॉडल कहा जाता है।<ref name="Boas">[[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.</ref>
-'अनुक्रमिक-मशीन मॉडल'
-निम्नलिखित सभी को समानांतर मशीन मॉडल से अलग करने के लिए अनुक्रमिक मशीन मॉडल कहा जाता है।<ref name="Boas">[[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.</ref>
+== टेप-आधारित ट्यूरिंग मशीन ==
+==== ट्यूरिंग का ''ए''-मशीन मॉडल ====
+ट्यूरिंग की मशीन (जैसा कि उन्होंने इसे कहा था) बाएँ किनारे वाली, दाएँ किनारे वाली इनफिनिट थी। उन्होंने बाएं छोर को चिह्नित करने के लिए əə प्रतीक प्रदान किए थे। टेप प्रतीकों की सीमित संख्या की अनुमति थी। निर्देश (यदि सार्वभौमिक मशीन), और इनपुट और आउट केवल एफ-स्क्वायर पर लिखे गए थे, और मार्कर ई-स्क्वायर पर दिखाई देने थे। संक्षेप में उन्होंने अपनी मशीन को दो टेपों में विभाजित किया जो सदैव साथ घूमते थे। निर्देश 5-टुपल्स नामक सारणीबद्ध रूप में प्रकट हुए और क्रमिक रूप से निष्पादित नहीं किए गए थे।
-== टेप-आधारित ट्यूरिंग मशीनें ==
+=== प्रतिबंधित प्रतीकों और/या प्रतिबंधित निर्देशों वाली एकल-टेप मशीन ===
+निम्नलिखित मॉडल एकल टेप ट्यूरिंग मशीन हैं, किन्तु (i) प्रतिबंधित टेप प्रतीकों {चिह्न, रिक्त}, और/या (ii) अनुक्रमिक, कंप्यूटर-जैसे निर्देश, और/या (iii) पूर्णतः परमाणुकृत मशीन-क्रियाओं से प्रतिबंधित हैं।
-ट्यूरिंग का ''ए''-मशीन मॉडल
-ट्यूरिंग की मशीन (जैसा कि उन्होंने इसे कहा था) बाएँ सिरे वाली, दाएँ सिरे वाली अनंत थी। उन्होंने बाएं छोर को चिह्नित करने के लिए əə प्रतीक प्रदान किए। टेप प्रतीकों की सीमित संख्या की अनुमति थी। निर्देश (यदि सार्वभौमिक मशीन), और इनपुट और आउट केवल एफ-स्क्वायर पर लिखे गए थे, और मार्कर ई-स्क्वायर पर दिखाई देने थे। संक्षेप में उन्होंने अपनी मशीन को दो टेपों में विभाजित किया जो हमेशा साथ घूमते थे। निर्देश 5-टुपल्स नामक सारणीबद्ध रूप में प्रकट हुए और क्रमिक रूप से निष्पादित नहीं किए गए।
-=== प्रतिबंधित प्रतीकों और/या प्रतिबंधित निर्देशों वाली एकल-टेप मशीनें ===
-निम्नलिखित मॉडल एकल टेप ट्यूरिंग मशीनें हैं, लेकिन (i) प्रतिबंधित टेप प्रतीकों {चिह्न, रिक्त}, और/या (ii) अनुक्रमिक, कंप्यूटर-जैसे निर्देश, और/या (iii) पूरी तरह से परमाणुकृत मशीन-क्रियाओं से प्रतिबंधित हैं।
 ==== पोस्ट का सूत्रीकरण 1 गणना का मॉडल ====
-{{details|Post–Turing machine}}
+{{details|पोस्ट-ट्यूरिंग मशीन}}
-[[एमिल पोस्ट]] ने कम्प्यूटेशनल प्रक्रिया के स्वतंत्र विवरण में, टेप पर चिह्नों के समकक्ष बाइनरी सेट के लिए अनुमत प्रतीकों को कम कर दिया है। उन्होंने टेप की धारणा को एक-तरफा अनंत से दाईं ओर अनंत कमरों के सेट में बदल दिया, जिनमें से प्रत्येक में दोनों दिशाओं में कागज की शीट थी। उन्होंने ट्यूरिंग 5-टुपल्स को 4-टुपल्स में विभाजित कर दिया - मोशन निर्देश प्रिंट/इरेज़ निर्देशों से अलग। हालाँकि उनका 1936 मॉडल इस बारे में अस्पष्ट है, पोस्ट के 1947 मॉडल को अनुक्रमिक निर्देश निष्पादन की आवश्यकता नहीं थी।
+[[एमिल पोस्ट]] ने कम्प्यूटेशनल प्रक्रिया के स्वतंत्र विवरण में, टेप पर चिह्नों के समकक्ष बाइनरी सेट के लिए अनुमत प्रतीकों को कम कर दिया है। उन्होंने टेप की धारणा को एक-तरफा इनफिनिट से दाईं ओर इनफिनिट कमरों के सेट में परिवर्तित कर दिया था, जिनमें से प्रत्येक में दोनों दिशाओं में पेपर की शीट थी। उन्होंने ट्यूरिंग 5-टुपल्स को 4-टुपल्स में विभाजित कर दिया था मोशन निर्देश प्रिंट/इरेज़ निर्देशों से प्रथक चूँकि उनका 1936 मॉडल इस बारे में अस्पष्ट है, पोस्ट के 1947 मॉडल को अनुक्रमिक निर्देश निष्पादन की आवश्यकता नहीं थी।
-उनका बेहद सरल मॉडल किसी भी ट्यूरिंग मशीन का अनुकरण कर सकता है, और हालांकि उनके 1936 फॉर्मूलेशन 1 में प्रोग्राम या मशीन शब्द का उपयोग नहीं किया गया है, यह प्रभावी रूप से बहुत ही आदिम प्रोग्राम योग्य कंप्यूटर और संबंधित [[प्रोग्रामिंग भाषा]] का फॉर्मूलेशन है, जिसमें बॉक्स अनबाउंड बिटस्ट्रिंग मेमोरी के रूप में कार्य करते हैं। , और प्रोग्राम का निर्माण करने वाले निर्देशों का सेट।
+उनका अत्यधिक सरल मॉडल किसी भी ट्यूरिंग मशीन का अनुकरण कर सकता है, और चूँकि उनके 1936 फॉर्मूलेशन 1 में प्रोग्राम या मशीन शब्द का उपयोग नहीं किया गया है, यह प्रभावी रूप से बहुत ही मौलिक प्रोग्राम योग्य कंप्यूटर और संबंधित [[प्रोग्रामिंग भाषा|प्रोग्रामिंग]] लैंग्वेज का फॉर्मूलेशन है, जिसमें बॉक्स अनबाउंड बिटस्ट्रिंग मेमोरी के रूप में कार्य करते हैं। और प्रोग्राम का निर्माण करने वाले निर्देशों का सेट प्रयुक्त होते है।
-==== वांग मशीनें ====
+==== वांग मशीन ====
-{{details|Wang B-machine}}
+{{details|वांग बी-मशीन}}
-एक प्रभावशाली पेपर में, हाओ वांग (अकादमिक) ने पोस्ट की पोस्ट-ट्यूरिंग मशीन#1936: पोस्ट मॉडल को उन मशीनों में बदल दिया जो अभी भी दो-तरफा अनंत बाइनरी टेप का उपयोग करते हैं, लेकिन जिनके निर्देश सरल हैं - पोस्ट के निर्देशों के परमाणु घटक होने के नाते - और डिफ़ॉल्ट रूप से क्रमिक रूप से निष्पादित होते हैं (एक कंप्यूटर प्रोग्राम की तरह)। उनका घोषित मुख्य उद्देश्य, ट्यूरिंग के सिद्धांत के विकल्प के रूप में, ऐसा सिद्धांत पेश करना था जो बुनियादी संचालन में अधिक किफायती हो। उनके परिणाम विभिन्न प्रकार की ऐसी मशीनों के प्रोग्राम फॉर्मूलेशन थे, जिनमें निर्देश-सेट के साथ 5-निर्देश वांग डब्ल्यू-मशीन भी शामिल थी
+एक प्रभावशाली पेपर में, हाओ वांग (अकादमिक) ने पोस्ट की पोस्ट-ट्यूरिंग मशीन 1936: पोस्ट मॉडल को उन मशीनों में परिवर्तित कर दिया था जो अभी भी दो-तरफा इनफिनिट बाइनरी टेप का उपयोग करते हैं, किन्तु जिनके निर्देश सरल हैं पोस्ट के निर्देशों के परमाणु अवयव होने के सम्बन्ध में और डिफ़ॉल्ट रूप से क्रमिक रूप से निष्पादित होते हैं (एक कंप्यूटर प्रोग्राम की तरह)। उनका घोषित मुख्य उद्देश्य, ट्यूरिंग के सिद्धांत के विकल्प के रूप में, ऐसा सिद्धांत प्रस्तुत करना था जो मूलभूत संचालन में अधिक प्रभावकारी होता है। उनके परिणाम विभिन्न प्रकार की ऐसी मशीनों के प्रोग्राम फॉर्मूलेशन थे, जिनमें निर्देश-सेट के साथ 5-निर्देश वांग डब्ल्यू-मशीन भी सम्मिलित थी
-: { शिफ्ट-बाएं, शिफ्ट-दाएं, मार्क-स्क्वायर, मिटाएं-स्क्वायर, जंप-इफ-स्क्वायर-चिह्नित-से xxx }
+: { शिफ्ट-बाएं, शिफ्ट-दाएं, मार्क-स्क्वायर, इरेज-स्क्वायर, जंप-इफ-स्क्वायर-चिह्नित-से xxx }
-और निर्देश-सेट के साथ उनकी सबसे गंभीर रूप से कम की गई 4-निर्देश [[वांग बी-मशीन]] (बेसिक के लिए बी)
+और निर्देश-सेट के साथ उनकी सबसे कठोरता से कम की गई 4-निर्देश [[वांग बी-मशीन]] (बेसिक के लिए बी)
 : { शिफ्ट-बाएं, शिफ्ट-दाएं, मार्क-स्क्वायर, जंप-इफ-स्क्वायर-चिह्नित-से xxx }
-जिसमें ERASE-SQUARE निर्देश भी नहीं है।
+जिसमें इरेज-स्क्वायर निर्देश भी नहीं है।
-कई लेखकों ने बाद में वांग द्वारा चर्चा की गई मशीनों के वेरिएंट पेश किए:
+विभिन्न लेखकों ने पश्चात में वांग द्वारा विचार की गई मशीनों के वेरिएंट प्रस्तुत किए:
-मिन्स्की ने (मल्टी-टेप) काउंटर मशीन मॉडल के अपने संस्करण के साथ वांग की धारणा को विकसित किया, जो अलग-अलग सिरों की SHIFT-LEFT और SHIFT-दाएँ गति की अनुमति देता है, लेकिन बिल्कुल भी मुद्रण नहीं करता है।<ref name="Marvin" />इस मामले में टेप बाएं सिरे वाले होंगे, प्रत्येक सिरे पर अंत को इंगित करने के लिए निशान होगा। वह इसे ही टेप तक सीमित करने में सक्षम था, लेकिन अधिक सरल {शिफ्ट-बाएं = कमी, शिफ्ट-दाएं = वृद्धि} के बजाय गुणन और विभाजन के समतुल्य मल्टी-टेप-स्क्वायर गति को शुरू करने की कीमत पर।
+मिन्स्की ने (मल्टी-टेप) काउंटर मशीन मॉडल के अपने वर्जन के साथ वांग की धारणा को विकसित किया था, जो भिन्न-भिन्न सिरों की शिफ्ट-बाएं और शिफ्ट-दाएं गति की अनुमति देता है, किन्तु बिल्कुल भी मुद्रण नहीं करता है।<ref name="Marvin" /> इस स्थिति में टेप बाएं किनारे वाले होंगे, प्रत्येक किनारे पर अंत को संकेत करने के लिए निशान होगा। वह इसे ही टेप तक सीमित करने में सक्षम था, किन्तु अधिक सरल {शिफ्ट-बाएं = कमी, शिफ्ट-दाएं = वृद्धि} के अतिरिक्त गुणन और विभाजन के समतुल्य मल्टी-टेप-स्क्वायर गति को प्रयुक्त करने की मूल्य पर प्रयुक्त किया जाता है।
-डेविस ने वांग द्वारा चर्चा की गई मशीनों में से में स्पष्ट एचएएलटी निर्देश जोड़कर निर्देश-सेट के साथ मॉडल का उपयोग किया
+डेविस ने वांग द्वारा विचार की गई मशीनों में से में स्पष्ट एचएएलटी निर्देश जोड़कर निर्देश-सेट के साथ मॉडल का उपयोग किया था
-: {शिफ्ट-बाएं, शिफ्ट-दाएं, मिटाएं, चिह्नित करें, वर्ग-चिह्नित xxx पर कूदें, xxx पर कूदें, रुकें }
+: {शिफ्ट-बाएं, शिफ्ट-दाएं, इरेज, चिह्नित करें, वर्ग-चिह्नित xxx पर जम्प, xxx पर जम्प, रुकें }
-और 2 से बड़े आकार के टेप-अक्षरों वाले संस्करणों पर भी विचार किया गया।
+और 2 से बड़े आकार के टेप-अक्षरों वाले वर्जन पर भी विचार किया गया।
-====बोहम की सैद्धांतिक मशीनी भाषा पी ====
+====बोहम की सैद्धांतिक मशीनी लैंग्वेज पी ====
-{{details|P"}}
+{{details|पी"}}
-बुनियादी संचालन में किफायती ट्यूरिंग-समतुल्य सिद्धांत की तलाश करने के लिए वांग की परियोजना को ध्यान में रखते हुए, और बिना शर्त छलांग से बचने की इच्छा रखते हुए, उल्लेखनीय सैद्धांतिक भाषा 1964 में कोराडो बोहम द्वारा शुरू की गई 4-निर्देश भाषा पी है - [[ट्यूरिंग-पूर्ण]] साबित होने वाली पहली गोटो-कम अनिवार्य [[संरचित प्रोग्रामिंग]] भाषा।
-=== मल्टी-टेप ट्यूरिंग मशीनें ===
+मूलभूत संचालन में प्रभावकारी ट्यूरिंग-समतुल्य सिद्धांत की तलाश करने के लिए वांग की परियोजना को ध्यान में रखते हुए, और बिना नियम छलांग से बचने की इच्छा रखते हुए, उल्लेखनीय सैद्धांतिक लैंग्वेज 1964 में कोराडो बोहम द्वारा प्रयुक्त की गई 4-निर्देश लैंग्वेज पी है - [[ट्यूरिंग-पूर्ण]] सिद्ध होने वाली पहली गोटो-कम अनिवार्य [[संरचित प्रोग्रामिंग|स्ट्रक्चर्ड प्रोग्रामिंग]] लैंग्वेज होती है।
-{{details|Multitape Turing machine}}
-व्यावहारिक विश्लेषण में, विभिन्न प्रकार की मल्टी-टेप ट्यूरिंग मशीनों का अक्सर उपयोग किया जाता है। मल्टी-टेप मशीनें सिंगल-टेप मशीनों के समान होती हैं, लेकिन कुछ स्थिर k संख्या में स्वतंत्र टेप होते हैं।
+=== मल्टी-टेप ट्यूरिंग मशीन ===
+{{details|मल्टीटेप ट्यूरिंग मशीन}}
-===नियतात्मक और गैर-नियतात्मक ट्यूरिंग मशीनें===
+व्यावहारिक विश्लेषण में, विभिन्न प्रकार की मल्टी-टेप ट्यूरिंग मशीनों का अधिकांशतः उपयोग किया जाता है। मल्टी-टेप मशीन सिंगल-टेप मशीनों के समान होती हैं, किन्तु कुछ स्थिर k संख्या में स्वतंत्र टेप होते हैं।
-{{details|non-deterministic Turing machine}}
-यदि क्रिया तालिका में प्रतीक और स्थिति के प्रत्येक संयोजन के लिए अधिकतम प्रविष्टि है तो मशीन नियतात्मक ट्यूरिंग मशीन (DTM) है। यदि क्रिया तालिका में प्रतीक और स्थिति के संयोजन के लिए एकाधिक प्रविष्टियाँ हैं तो मशीन गैर-नियतात्मक ट्यूरिंग मशीन (एनडीटीएम) है। दोनों कम्प्यूटेशनल रूप से समतुल्य हैं, यानी, किसी भी एनडीटीएम को डीटीएम (और ''इसके विपरीत'') में बदलना संभव है, हालांकि उनके पास आमतौर पर अलग-अलग रनटाइम होते हैं। इसे निर्माण के माध्यम से सिद्ध किया जा सकता है।
+===नियतात्मक और गैर-नियतात्मक ट्यूरिंग मशीन===
+{{details|गैर-नियतात्मक ट्यूरिंग मशीन}}
-=== विस्मृत ट्यूरिंग मशीनें ===
+यदि क्रिया टेबल में प्रतीक और स्थिति के प्रत्येक संयोजन के लिए अधिकतम प्रविष्टि है तो मशीन नियतात्मक ट्यूरिंग मशीन (डीटीएम) है। यदि क्रिया टेबल में प्रतीक और स्थिति के संयोजन के लिए एकाधिक प्रविष्टियाँ हैं तो मशीन गैर-नियतात्मक ट्यूरिंग मशीन (एनडीटीएम) है। दोनों कम्प्यूटेशनल रूप से समतुल्य हैं, अर्थात, किसी भी एनडीटीएम को डीटीएम (और ''इसके विपरीत'') में परिवर्तित करना संभव है, चूँकि उनके निकट सामान्यतः भिन्न-भिन्न रनटाइम होते हैं। इसे निर्माण के माध्यम से सिद्ध किया जा सकता है।
-एक विस्मृत ट्यूरिंग मशीन ट्यूरिंग मशीन है, जहां प्रत्येक इनपुट लंबाई के लिए, विभिन्न शीर्षों की गति समय का निश्चित कार्य है, जो इनपुट से स्वतंत्र है। दूसरे शब्दों में, पूर्व निर्धारित क्रम होता है जिसमें विभिन्न टेपों को स्कैन किया जाता है, उन्नत किया जाता है और लिखा जाता है। किसी भी चरण पर टेप पर लिखे गए वास्तविक मान उस लंबाई के प्रत्येक इनपुट के लिए अभी भी भिन्न हो सकते हैं। पिप्पेंजर और फिशर ने दिखाया कि कोई भी गणना जो मल्टी-टेप ट्यूरिंग मशीन द्वारा एन चरणों में की जा सकती है, उसे अनजान दो-टेप ट्यूरिंग मशीन द्वारा एन चरणों में किया जा सकता है। {{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)}} कुक-लेविन प्रमेय द्वारा परिणाम।
-== मशीन मॉडल पंजीकृत करें ==
+ओब्लिवियस ट्यूरिंग मशीन ट्यूरिंग मशीन है, जहां प्रत्येक इनपुट लंबाई के लिए, विभिन्न शीर्षों की गति समय का निश्चित कार्य है, जो इनपुट से स्वतंत्र है। दूसरे शब्दों में, पूर्व निर्धारित क्रम होता है जिसमें विभिन्न टेपों को स्कैन किया जाता है, उन्नत किया जाता है और लिखा जाता है। किसी भी स्टेज पर टेप पर लिखे गए वास्तविक मान उस लंबाई के प्रत्येक इनपुट के लिए अभी भी भिन्न हो सकते हैं। पिप्पेंजर और फिशर ने दिखाया कि कोई भी गणना जो मल्टी-टेप ट्यूरिंग मशीन द्वारा एन स्टेज में की जा सकती है, उसे ओब्लिवियस दो-टेप ट्यूरिंग मशीन द्वारा एन स्टेज में किया जा सकता है। {{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 }}
-{{details|Register machine}}
+</ref> ऑब्लिवियस मशीनें कॉम्बिनेशन लॉजिक परिपथ के साथ स्टेज-वार रैखिक फैशन में मेल खाती हैं, जब संक्रमण टेबल की सम्मिश्रता को स्थिर माना जाता है। इस प्रकार आकार {{tmath|O(n \log n)}} और डेप्थ {{tmath|O(n)}} में परिपथ समस्याओं के रूप में गणना करना संभव है (परिपथ सम्मिश्रता देखें)। यह कुक और लेविन के मूल {{tmath|O(n^3)}} परिणाम में सुधार करता है।
-[[पीटर वैन एम्डे बोस]] इस प्रकार की सभी मशीनों को वर्ग, रजिस्टर मशीन में शामिल करते हैं।<ref name="Boas" />हालाँकि, ऐतिहासिक रूप से साहित्य ने इस समूह के सबसे आदिम सदस्य यानी काउंटर मशीन को रजिस्टर मशीन भी कहा है। और काउंटर मशीन के सबसे आदिम अवतार को कभी-कभी मिन्स्की मशीन कहा जाता है।
+== रजिस्टर मशीन मॉडल ==
+{{details|रजिस्टर मशीन}}
+[[पीटर वैन एम्डे बोस]] इस प्रकार की सभी मशीनों को वर्ग, रजिस्टर मशीन में सम्मिलित करते हैं।<ref name="Boas" /> चूँकि, ऐतिहासिक रूप से साहित्य ने इस समूह के सबसे मौलिक सदस्य अर्थात काउंटर मशीन को रजिस्टर मशीन भी कहा है। और काउंटर मशीन के सबसे मौलिक आगमन को कभी-कभी मिन्स्की मशीन कहा जाता है।
 === काउंटर मशीन, जिसे रजिस्टर मशीन मॉडल भी कहा जाता है ===
-{{details|Counter machine}}
+{{details|काउंटर मशीन}}
-आदिम मॉडल रजिस्टर मशीन, वास्तव में, मल्टीटेप 2-प्रतीक पोस्ट-ट्यूरिंग मशीन है जिसका व्यवहार प्रतिबंधित है इसलिए इसके टेप साधारण काउंटर की तरह काम करते हैं।
+मौलिक मॉडल रजिस्टर मशीन, वास्तव में, मल्टीटेप 2-प्रतीक पोस्ट-ट्यूरिंग मशीन है जिसका व्यवहार प्रतिबंधित है इसलिए इसके टेप साधारण काउंटर की तरह कार्य करते हैं।
-मेल्ज़ाक, लैम्बेक और मिन्स्की के समय तक कंप्यूटर प्रोग्राम की धारणा ने अलग प्रकार की सरल मशीन का निर्माण किया, जिसमें पोस्ट-ट्यूरिंग टेप से कई बाएं छोर वाले टेप काटे गए थे। सभी मामलों में मॉडल केवल दो टेप प्रतीकों {चिह्न, रिक्त} की अनुमति देते हैं।<ref name="Marvin" />
+मेल्ज़ाक, लैम्बेक और मिन्स्की के समय तक कंप्यूटर प्रोग्राम की धारणा ने पृथक प्रकार की सरल मशीन का निर्माण किया था, जिसमें पोस्ट-ट्यूरिंग टेप से विभिन्न बाएं छोर वाले टेप काटे गए थे। सभी स्थितियों में मॉडल केवल दो टेप प्रतीकों {चिह्न, रिक्त} की अनुमति देते हैं।<ref name="Marvin" />
-कुछ संस्करण सकारात्मक पूर्णांकों को केवल रजिस्टर में अनुमत अंकों की स्ट्रिंग/स्टैक के रूप में दर्शाते हैं (अर्थात बाएं सिरे वाला टेप), और गिनती 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=शून्य की सामग्री है तो निर्देश पर जाएं #z}
+::{रजिस्टर #r की कंटेंट में वृद्धि; रजिस्टर #r की कमी कंटेंट; यदि #r=शून्य की कंटेंट है तो निर्देश पर जाएं #z}
-:(2): {सीएलआर (आर); इंक (आर); जेई (आर<sub>i</sub>, आर<sub>j</sub>, z ) }, अर्थात्।
+:(2): { CLR ( r ); INC ( r ); JE ( r<sub>i</sub>, r<sub>j</sub>, z ) }, i.e., अर्थात्।
-::{रजिस्टर आर की स्पष्ट सामग्री; आर की सामग्री में वृद्धि; आर की सामग्री की तुलना करें<sub>i</sub> आर को<sub>j</sub> और यदि समान है तो निर्देश z पर जाएं}
+::{रजिस्टर आर की स्पष्ट कंटेंट; r की कंटेंट में वृद्धि; r<sub>i</sub> को r<sub>j</sub> की कंटेंट की तुलना करें और यदि समान है तो निर्देश z पर जाएं}
-यद्यपि उनका मॉडल इस सरल विवरण से अधिक जटिल है, मेल्ज़ाक कंकड़ मॉडल ने बहु-विषयकता की अनुमति देने के लिए काउंटर की इस धारणा को बढ़ाया।
+यद्यपि उनका मॉडल इस सरल विवरण से अधिक सम्मिश्र है, मेल्ज़ाक पेब्बल मॉडल ने बहु-विषयकता की अनुमति देने के लिए काउंटर की इस धारणा को बढ़ाया था।पेब्बल जोड़ता और घटाता है।
-कंकड़ जोड़ता और घटाता है।
 === रैंडम-एक्सेस मशीन (रैम) मॉडल ===
-{{details|Random-access machine}}
+{{details|रैंडम-एक्सेस मशीन}}
 मेल्ज़ाक ने अपने रजिस्टर/काउंटर-मशीन मॉडल में कुछ गंभीर दोषों को पहचाना:<ref>{{cite journal
@@ Line 109: / Line 106: @@
 | date=September 1961
 | 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" />
+* एसआरएएम, केवल अंकगणितीय निर्देश के साथ उत्तराधिकारी रैम, उत्तराधिकारी (वृद्धि h) अन्य में क्लियर h और IF समानता-मध्य-रजिस्टर सम्मिलित है, फिर xxx पर जाएं।
-वैन एम्डे बोस विभिन्न रैम मॉडल को कई उप-प्रकारों में विभाजित करता है:<ref name="Boas" />* SRAM, केवल अंकगणितीय निर्देश के साथ उत्तराधिकारी RAM, उत्तराधिकारी (वृद्धि h)। अन्य में CLEAR h और IF समानता-बीच-रजिस्टर शामिल है, फिर xxx पर जाएं।
 * रैम: जोड़ और घटाव के साथ मानक मॉडल
 * एमआरएएम: रैम गुणा और भाग के साथ संवर्धित होती है
-* ब्रैम, एमबीआरएएम: रैम और एमआरएएम के बिटवाइज़ बूलियन संस्करण
+* ब्रैम, एमबीआरएएम: रैम और एमआरएएम के बिटवाइज़ बूलियन वर्जन
-* एन****: नाम से पहले एन के साथ उपरोक्त में से किसी का गैर-नियतात्मक संस्करण
+* एन****: नाम से पहले एन के साथ उपरोक्त में से किसी का गैर-नियतात्मक वर्जन
 === रैंडम-एक्सेस संग्रहीत प्रोग्राम (आरएएसपी) मशीन मॉडल ===
 {{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 भी उपयोगी है।)
-: { INC ( r ), कॉपी ( r )<sub>i</sub>, आर<sub>j</sub> ), जेई (आर<sub>i</sub>, आर<sub>i</sub>, z ) }
+एल्गॉट और रॉबिन्सन के मूल आरएएसपी मॉडल में रजिस्टर-मशीन मॉडल के फैशन में केवल तीन निर्देश थे,<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 क्लियर का स्थान लेता है जब कोई रजिस्टर जैसे 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 ) }
-आरएएसपी मॉडल अप्रत्यक्ष के साथ-साथ प्रत्यक्ष-संबोधन की भी अनुमति देते हैं; कुछ लोग तत्काल निर्देशों की भी अनुमति देते हैं, उदा. संचायक को स्थिरांक 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 >, जोड़ें << 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 >, रुकें }
+:{ 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 }
 === पॉइंटर मशीन मॉडल ===
-{{details|Pointer machine}}
+{{details|पॉइंटर मशीन}}
-एक अपेक्षाकृत देर से आने वाली मशीन शॉनहेज की स्टोरेज मॉडिफिकेशन मशीन या [[ सूचक मशीन |सूचक मशीन]] है। अन्य संस्करण कोलमोगोरोव-उसपेन्स्की मशीन और नथ लिंकिंग ऑटोमेटन प्रस्ताव है। (संदर्भ के लिए पॉइंटर मशीन देखें)। राज्य-मशीन आरेख की तरह, नोड कम से कम दो लेबल वाले किनारों (तीर) का उत्सर्जन करता है जो दूसरे नोड या नोड्स को इंगित करता है जो बदले में अन्य नोड्स आदि को इंगित करता है। बाहरी दुनिया केंद्र नोड पर इंगित करती है।
+एक अपेक्षाकृत देर से आने वाली मशीन शॉनहेज की स्टोरेज मॉडिफिकेशन मशीन या [[ सूचक मशीन |सूचक मशीन]] है। अन्य वर्जन कोलमोगोरोव-उसपेन्स्की मशीन और नथ लिंकिंग ऑटोमेटन प्रस्ताव है। (संदर्भ के लिए पॉइंटर मशीन देखें)। स्टेट-मशीन आरेख की तरह, नोड कम से कम दो लेबल वाले किनारों (तीर) का उत्सर्जन करता है जो दूसरे नोड या नोड्स को संकेत करता है जो परिवर्तित करने में अन्य नोड्स आदि को संकेत करता है। बाहरी संसार केंद्र नोड पर संकेत करती है।
-==इनपुट और आउटपुट वाली मशीनें==
+==इनपुट और आउटपुट वाली मशीन==
-उपरोक्त टेप-आधारित मशीनों में से कोई भी इनपुट और आउटपुट टेप से सुसज्जित हो सकती है; उपरोक्त रजिस्टर-आधारित मशीनों में से कोई भी समर्पित इनपुट और आउटपुट रजिस्टरों से सुसज्जित हो सकती है। उदाहरण के लिए, शॉनहेज पॉइंटर-मशीन मॉडल में दो निर्देश हैं जिन्हें इनपुट λ कहा जाता है<sub>0</sub>,एल<sub>1</sub>और आउटपुट β।
+उपरोक्त टेप-आधारित मशीनों में से कोई भी इनपुट और आउटपुट टेप से सुसज्जित हो सकती है; उपरोक्त रजिस्टर-आधारित मशीनों में से कोई भी समर्पित इनपुट और आउटपुट रजिस्टरों से सुसज्जित हो सकती है। उदाहरण के लिए, शॉनहेज पॉइंटर-मशीन मॉडल में दो निर्देश हैं जिन्हें इनपुट λ<sub>0</sub>,L<sub>1</sub>और आउटपुट β कहा जाता है
-पारंपरिक मॉडल के साथ मल्टी-टेप मशीनों पर [[अधरेखीय]] स्पेस जटिलता का अध्ययन करना मुश्किल है, क्योंकि आकार n का इनपुट पहले से ही स्पेस n लेता है। इस प्रकार, छोटी [[DSPACE]] कक्षाओं का अध्ययन करने के लिए, हमें अलग मॉडल का उपयोग करना चाहिए। कुछ अर्थों में, यदि हम इनपुट टेप पर कभी नहीं लिखते हैं, तो हम इस स्थान के लिए स्वयं को चार्ज नहीं करना चाहते हैं। और यदि हम अपने आउटपुट टेप से कभी नहीं पढ़ते हैं, तो हम इस स्थान के लिए स्वयं को चार्ज नहीं करना चाहते हैं।
+पारंपरिक मॉडल के साथ मल्टी-टेप मशीनों पर सबलीनियर स्पेस सम्मिश्रता का अध्ययन करना कठिन है, क्योंकि आकार n का इनपुट पहले से ही स्पेस n लेता है। इस प्रकार, छोटी [[DSPACE|डीएसपीएसीई]] कक्षाओं का अध्ययन करने के लिए, हमें पृथक मॉडल का उपयोग करना चाहिए। कुछ अर्थों में, यदि हम इनपुट टेप पर कभी नहीं लिखते हैं, तो हम इस स्थान के लिए स्वयं को चार्ज नहीं करना चाहते हैं। और यदि हम अपने आउटपुट टेप से कभी नहीं पढ़ते हैं, तो हम इस स्थान के लिए स्वयं को चार्ज नहीं करना चाहते हैं।
-हम इनपुट और आउटपुट के साथ के-स्ट्रिंग ट्यूरिंग मशीन पेश करके इस समस्या का समाधान करते हैं। यह साधारण के-स्ट्रिंग ट्यूरिंग मशीन के समान है, सिवाय ट्रांज़िशन फ़ंक्शन के {{mvar|δ}} प्रतिबंधित है ताकि इनपुट टेप को कभी भी बदला न जा सके, और ताकि आउटपुट हेड कभी भी बाईं ओर न घूम सके। यह मॉडल हमें रैखिक से छोटे नियतात्मक अंतरिक्ष वर्गों को परिभाषित करने की अनुमति देता है। इनपुट-और-आउटपुट वाली ट्यूरिंग मशीनों में भी अन्य ट्यूरिंग मशीनों की तरह ही समय जटिलता होती है; पापादिमित्रिउ 1994 प्रस्ताव 2.2 के शब्दों में:
+हम इनपुट और आउटपुट के साथ K-स्ट्रिंग ट्यूरिंग मशीन प्रस्तुत करके इस समस्या का समाधान करते हैं। यह साधारण K-स्ट्रिंग ट्यूरिंग मशीन के समान है, अतिरिक्त ट्रांज़िशन फ़ंक्शन के {{mvar|δ}} प्रतिबंधित है जिससे इनपुट टेप को कभी भी परिवर्तित नही किया जा सकता है, और जिससे आउटपुट हेड कभी भी बाईं ओर न घूम सके। यह मॉडल हमें रैखिक से छोटे नियतात्मक अंतरिक्ष वर्गों को परिभाषित करने की अनुमति देता है। इनपुट-और-आउटपुट वाली ट्यूरिंग मशीनों में भी अन्य ट्यूरिंग मशीनों की तरह ही समय सम्मिश्रता होती है; पापादिमित्रिउ 1994 प्रस्ताव 2.2 के शब्दों में:
-:किसी भी के-स्ट्रिंग ट्यूरिंग मशीन एम के लिए समय सीमा के भीतर काम करना {{tmath|f(n)}} वहां है {{tmath|(k+2)}}-स्ट्रिंग ट्यूरिंग मशीन एम' इनपुट और आउटपुट के साथ, जो समय सीमा के भीतर संचालित होती है {{tmath|O(f(n))}}.
+:किसी भी k-स्ट्रिंग ट्यूरिंग मशीन M के लिए जो समयबद्ध {{tmath|f(n)}} के अन्दर कार्य करती है, इनपुट और आउटपुट के साथ एक {{tmath|(k+2)}}-स्ट्रिंग ट्यूरिंग मशीन M' है जो समयबद्ध {{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>
+इनपुट और आउटपुट के साथ 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.&nbsp;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>

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 12:25, 9 August 2023

Contents

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

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

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

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

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

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

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

वांग मशीन

बोहम की सैद्धांतिक मशीनी लैंग्वेज पी

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

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

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

रजिस्टर मशीन मॉडल

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

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

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

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

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

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

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 12:25, 9 August 2023

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

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

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

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

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

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

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

वांग मशीन

बोहम की सैद्धांतिक मशीनी लैंग्वेज पी

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

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

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

रजिस्टर मशीन मॉडल

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

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

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

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

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

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

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories