काउंटर मशीन: Difference between revisions

Line 1:

{{Short description|Abstract machine used in a formal logic and theoretical computer science}}

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

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

== बुनियादी सुविधाएँ ==

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

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

* सीएलआर (आर): क्लियर रजिस्टर आर। (आर को शून्य पर सेट करें।)

* आईएनसी (आर): रजिस्टर आर की सामग्री को बढ़ाएं।

Line 12:

* जेई (आरj, आरk, z): यदि रजिस्टर आर की सामग्रीjरजिस्टर आर की सामग्री के बराबर हैkफिर निर्देश पर जाएं अन्यथा क्रम से जारी रखें।

इसके अलावा, मशीन में आमतौर पर एक HALT निर्देश होता है, जो मशीन को रोक देता है (आमतौर पर परिणाम की गणना के बाद)।

इसके अलावा, मशीन में आमतौर पर HALT निर्देश होता है, जो मशीन को रोक देता है (आमतौर पर परिणाम की गणना के बाद)।

ऊपर उल्लिखित निर्देशों का उपयोग करते हुए, विभिन्न लेखकों ने कुछ काउंटर मशीनों पर चर्चा की है:

Line 19:

* सेट 3: {आईएनसी (आर), सीपीवाई (आर)।j, आरk), जेई (आरj, आरk, z) }, (एल्गॉट-रॉबिन्सन (1964), मिन्स्की (1967))

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

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

== वैकल्पिक नाम, वैकल्पिक मॉडल ==

Line 25:

काउंटर मशीन मॉडल कई अलग-अलग नामों से जाने जाते हैं जो उनकी विशिष्टताओं के आधार पर उन्हें अलग करने में मदद कर सकते हैं। निम्नलिखित निर्देश में JZDEC (r) एक मिश्रित निर्देश है जो यह देखने के लिए परीक्षण करता है कि कोई रजिस्टर r खाली है या नहीं; यदि ऐसा है तो निर्देश I पर जाएँz, अन्यथा यदि नहीं तो r की सामग्री को घटाएँ:

काउंटर मशीन मॉडल कई अलग-अलग नामों से जाने जाते हैं जो उनकी विशिष्टताओं के आधार पर उन्हें अलग करने में मदद कर सकते हैं। निम्नलिखित निर्देश में JZDEC (r) मिश्रित निर्देश है जो यह देखने के लिए परीक्षण करता है कि कोई रजिस्टर r खाली है या नहीं; यदि ऐसा है तो निर्देश I पर जाएँz, अन्यथा यदि नहीं तो r की सामग्री को घटाएँ:

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

Line 31:

* मिन्स्की मशीन, क्योंकि [[मार्विन मिंस्की]] (1961) ने मॉडल को औपचारिक रूप दिया। आमतौर पर निर्देश सेट (1) का उपयोग करता है, लेकिन निर्देश-निष्पादन डिफ़ॉल्ट-अनुक्रमिक नहीं है, इसलिए अतिरिक्त पैरामीटर 'z' INC के बाद अगले निर्देश को निर्दिष्ट करता है और JZDEC में विकल्प के रूप में दिखाई देता है:

*: { INC ( r, z ), JZDEC ( r, ztrue, साथfalse) }

* प्रोग्राम मशीन, प्रोग्राम [[कंप्यूटर]], नाम मिन्स्की (1967) ने मॉडल को दिया क्योंकि, एक कंप्यूटर की तरह इसके निर्देश क्रमिक रूप से आगे बढ़ते हैं जब तक कि एक सशर्त छलांग सफल नहीं होती। (आमतौर पर) निर्देश सेट (1) का उपयोग करता है लेकिन इसे शेफर्सन-स्टर्गिस मॉडल के समान संवर्धित किया जा सकता है। JZDEC को अक्सर अलग कर दिया जाता है:

* प्रोग्राम मशीन, प्रोग्राम [[कंप्यूटर]], नाम मिन्स्की (1967) ने मॉडल को दिया क्योंकि, कंप्यूटर की तरह इसके निर्देश क्रमिक रूप से आगे बढ़ते हैं जब तक कि सशर्त छलांग सफल नहीं होती। (आमतौर पर) निर्देश सेट (1) का उपयोग करता है लेकिन इसे शेफर्सन-स्टर्गिस मॉडल के समान संवर्धित किया जा सकता है। JZDEC को अक्सर अलग कर दिया जाता है:

*: { INC ( r ), DEC ( r ), JZ ( r, ztrue )}

* अबेकस मशीन, नाम लैम्बेक (1961) ने मेल्ज़ाक (1961) मॉडल के सरलीकरण के लिए दिया था, और बूलोस-बर्गेस-जेफरी (2002) इसे क्या कहते हैं। मिन्स्की (1961) मॉडल के तरीके से अगले निर्देश को निर्दिष्ट करने के लिए निर्देश सेट (1) का उपयोग करता है लेकिन एक अतिरिक्त पैरामीटर z के साथ;

* अबेकस मशीन, नाम लैम्बेक (1961) ने मेल्ज़ाक (1961) मॉडल के सरलीकरण के लिए दिया था, और बूलोस-बर्गेस-जेफरी (2002) इसे क्या कहते हैं। मिन्स्की (1961) मॉडल के तरीके से अगले निर्देश को निर्दिष्ट करने के लिए निर्देश सेट (1) का उपयोग करता है लेकिन अतिरिक्त पैरामीटर z के साथ;

*: { INC ( r, z ), JZDEC (r, ztrue, साथfalse ) }

* लैम्बेक मशीन, एक वैकल्पिक नाम बूलोस-बर्गेस-जेफरी (2002) ने अबेकस मशीन को दिया। अगले निर्देश को निर्दिष्ट करने के लिए एक अतिरिक्त पैरामीटर के साथ निर्देश सेट (1-कम) का उपयोग करता है:

* लैम्बेक मशीन, वैकल्पिक नाम बूलोस-बर्गेस-जेफरी (2002) ने अबेकस मशीन को दिया। अगले निर्देश को निर्दिष्ट करने के लिए अतिरिक्त पैरामीटर के साथ निर्देश सेट (1-कम) का उपयोग करता है:

*: { INC ( r, z ), JZDEC ( r, ztrue, साथfalse ) }

* उत्तराधिकारी मशीन, क्योंकि यह 'उत्तराधिकारी ऑपरेशन' का उपयोग करती है, और पीनो स्वयंसिद्धों से काफी मिलती-जुलती है। उत्तराधिकारी रैम मॉडल के लिए आधार के रूप में उपयोग किया जाता है। उदाहरण के लिए निर्देश सेट (2) का उपयोग करता है। शॉनहेज को उनके RAM0 और RAM1 मॉडल के आधार के रूप में, जो उनके [[ सूचक मशीन ]] SMM मॉडल की ओर ले जाता है, वैन एम्डे बोस (1990) में भी संक्षेप में चर्चा की गई है:

* उत्तराधिकारी मशीन, क्योंकि यह 'उत्तराधिकारी ऑपरेशन' का उपयोग करती है, और पीनो स्वयंसिद्धों से काफी मिलती-जुलती है। उत्तराधिकारी रैम मॉडल के लिए आधार के रूप में उपयोग किया जाता है। उदाहरण के लिए निर्देश सेट (2) का उपयोग करता है। शॉनहेज को उनके RAM0 और RAM1 मॉडल के आधार के रूप में, जो उनके [[ सूचक मशीन |सूचक मशीन]] SMM मॉडल की ओर ले जाता है, वैन एम्डे बोस (1990) में भी संक्षेप में चर्चा की गई है:

*: {सीएलआर (आर), आईएनसी (आर), जेई (आर)।j, आरk, z ) }

* एल्गॉट-रॉबिन्सन मॉडल, उनके आरएएसपी मॉडल (1964) को परिभाषित करने के लिए उपयोग किया जाता है। इस मॉडल को प्रारंभ में एक खाली रजिस्टर की आवश्यकता होती है (उदाहरण के लिए [r0] =0)। (उन्होंने इंडेक्स रजिस्टर के रूप में उपयोग करने के लिए एक अतिरिक्त रजिस्टर का उपयोग करके अप्रत्यक्ष संबोधन के साथ उसी मॉडल को संवर्धित किया।)

* एल्गॉट-रॉबिन्सन मॉडल, उनके आरएएसपी मॉडल (1964) को परिभाषित करने के लिए उपयोग किया जाता है। इस मॉडल को प्रारंभ में खाली रजिस्टर की आवश्यकता होती है (उदाहरण के लिए [r0] =0)। (उन्होंने इंडेक्स रजिस्टर के रूप में उपयोग करने के लिए अतिरिक्त रजिस्टर का उपयोग करके अप्रत्यक्ष संबोधन के साथ उसी मॉडल को संवर्धित किया।)

*: { आईएनसी (आर), सीपीवाई (आरs, आरd ), जेई (आरj, आरk, z ) }

* अन्य काउंटर मशीनें: मिन्स्की (1967) दर्शाता है कि इस आलेख के मुख्य पैराग्राफ में वर्णित उपलब्ध निर्देशों के सुपरसेट से तीन बेस मॉडल (प्रोग्राम/मिन्स्की/लैम्बेक-अबेकस, उत्तराधिकारी, और एल्गॉट-रॉबिन्सन) कैसे बनाया जाए। मेल्ज़ाक (1961) मॉडल उपरोक्त से काफी अलग है क्योंकि इसमें 'वृद्धि' और 'घटाना' के बजाय 'जोड़' और 'घटाना' शामिल है। मिन्स्की (1961, 1967) के प्रमाण कि ट्यूरिंग समतुल्यता के लिए एक एकल रजिस्टर पर्याप्त होगा, गणना का प्रतिनिधित्व करने वाले रजिस्टर में गोडेल संख्या को एन्कोड और डीकोड करने के लिए दो निर्देशों {मल्टीप्लाई के, और डीआईवी के} की आवश्यकता होती है। मिन्स्की दर्शाता है कि यदि दो या दो से अधिक रजिस्टर उपलब्ध हैं तो सरल INC, DEC आदि पर्याप्त हैं (लेकिन [[ट्यूरिंग पूर्णता]] प्रदर्शित करने के लिए गोडेल संख्या अभी भी आवश्यक है; एल्गॉट-रॉबिन्सन 1964 में भी प्रदर्शित किया गया है)।

* अन्य काउंटर मशीनें: मिन्स्की (1967) दर्शाता है कि इस आलेख के मुख्य पैराग्राफ में वर्णित उपलब्ध निर्देशों के सुपरसेट से तीन बेस मॉडल (प्रोग्राम/मिन्स्की/लैम्बेक-अबेकस, उत्तराधिकारी, और एल्गॉट-रॉबिन्सन) कैसे बनाया जाए। मेल्ज़ाक (1961) मॉडल उपरोक्त से काफी अलग है क्योंकि इसमें 'वृद्धि' और 'घटाना' के बजाय 'जोड़' और 'घटाना' शामिल है। मिन्स्की (1961, 1967) के प्रमाण कि ट्यूरिंग समतुल्यता के लिए एकल रजिस्टर पर्याप्त होगा, गणना का प्रतिनिधित्व करने वाले रजिस्टर में गोडेल संख्या को एन्कोड और डीकोड करने के लिए दो निर्देशों {मल्टीप्लाई के, और डीआईवी के} की आवश्यकता होती है। मिन्स्की दर्शाता है कि यदि दो या दो से अधिक रजिस्टर उपलब्ध हैं तो सरल INC, DEC आदि पर्याप्त हैं (लेकिन [[ट्यूरिंग पूर्णता]] प्रदर्शित करने के लिए गोडेल संख्या अभी भी आवश्यक है; एल्गॉट-रॉबिन्सन 1964 में भी प्रदर्शित किया गया है)।

== औपचारिक परिभाषा ==

एक काउंटर मशीन में निम्न शामिल होते हैं:

# लेबल रहित पूर्णांक-मूल्यवान रजिस्टर: रजिस्टरों का एक सीमित (या कुछ मॉडलों में अनंत) सेट ''आर''0... आर''n'' जिनमें से प्रत्येक किसी एक गैर-नकारात्मक पूर्णांक (0, 1, 2, ... - यानी असीमित) को धारण कर सकता है। रजिस्टर अपना अंकगणित स्वयं करते हैं; एक या अधिक विशेष रजिस्टर हो भी सकते हैं और नहीं भी, जैसे संचायक (इस पर अधिक जानकारी के लिए [[रैंडम-एक्सेस मशीन]] देखें)।

# लेबल रहित पूर्णांक-मूल्यवान रजिस्टर: रजिस्टरों का सीमित (या कुछ मॉडलों में अनंत) सेट ''आर''0... आर''n'' जिनमें से प्रत्येक किसी गैर-नकारात्मक पूर्णांक (0, 1, 2, ... - यानी असीमित) को धारण कर सकता है। रजिस्टर अपना अंकगणित स्वयं करते हैं; या अधिक विशेष रजिस्टर हो भी सकते हैं और नहीं भी, जैसे संचायक (इस पर अधिक जानकारी के लिए [[रैंडम-एक्सेस मशीन]] देखें)।

# एक राज्य रजिस्टर जो निष्पादित किए जाने वाले वर्तमान निर्देश को संग्रहीत/पहचानता है। यह रजिस्टर परिमित है और उपरोक्त रजिस्टरों से अलग है; इस प्रकार काउंटर मशीन मॉडल [[हार्वर्ड वास्तुकला]] का एक उदाहरण है

# एक राज्य रजिस्टर जो निष्पादित किए जाने वाले वर्तमान निर्देश को संग्रहीत/पहचानता है। यह रजिस्टर परिमित है और उपरोक्त रजिस्टरों से अलग है; इस प्रकार काउंटर मशीन मॉडल [[हार्वर्ड वास्तुकला]] का उदाहरण है

# लेबल किए गए, अनुक्रमिक निर्देशों की सूची: निर्देशों की एक सीमित सूची ''I''0... मैं''m''. प्रोग्राम स्टोर (परिमित राज्य मशीन के निर्देश) रजिस्टरों के समान भौतिक स्थान पर नहीं है। आमतौर पर, लेकिन हमेशा नहीं, [[कंप्यूटर प्रोग्राम]] की तरह निर्देश अनुक्रमिक क्रम में सूचीबद्ध होते हैं; जब तक कोई छलांग सफल नहीं होती, डिफ़ॉल्ट अनुक्रम संख्यात्मक क्रम में जारी रहता है। सूची में प्रत्येक निर्देश एक (बहुत) छोटे सेट से है, लेकिन इस सेट में अप्रत्यक्ष शामिल नहीं है। ऐतिहासिक रूप से अधिकांश मॉडलों ने इस सेट से अपने निर्देश प्राप्त किए:

# लेबल किए गए, अनुक्रमिक निर्देशों की सूची: निर्देशों की सीमित सूची ''I''0... मैं''m''. प्रोग्राम स्टोर (परिमित राज्य मशीन के निर्देश) रजिस्टरों के समान भौतिक स्थान पर नहीं है। आमतौर पर, लेकिन हमेशा नहीं, [[कंप्यूटर प्रोग्राम]] की तरह निर्देश अनुक्रमिक क्रम में सूचीबद्ध होते हैं; जब तक कोई छलांग सफल नहीं होती, डिफ़ॉल्ट अनुक्रम संख्यात्मक क्रम में जारी रहता है। सूची में प्रत्येक निर्देश (बहुत) छोटे सेट से है, लेकिन इस सेट में अप्रत्यक्ष शामिल नहीं है। ऐतिहासिक रूप से अधिकांश मॉडलों ने इस सेट से अपने निर्देश प्राप्त किए:

:: {वृद्धि (आर), कमी (आर), स्पष्ट (आर); कॉपी (आरj,आरk), यदि r=0 की सामग्री है तो सशर्त छलांग, यदि r की सामग्री है तो सशर्त छलांगj=आरk, बिना शर्त कूदो, रुको }

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

: कुछ मॉडलों ने या तो उपरोक्त में से कुछ को बिना-पैरामीटर निर्देशों में परमाणुकृत कर दिया है, या उन्हें ही निर्देश में जोड़ दिया है जैसे कि सशर्त कूद-अगर-शून्य जेजेड (आर, जेड) से पहले डिक्रीमेंट। निर्देशों के परमाणुकरण या सुविधाजनक निर्देशों को शामिल करने से वैचारिक शक्ति में कोई बदलाव नहीं होता है, क्योंकि संस्करण में किसी भी कार्यक्रम को सीधे दूसरे में अनुवादित किया जा सकता है।

:: पूरक [[रजिस्टर-मशीन मॉडल]] में वैकल्पिक निर्देश-सेट पर चर्चा की गई है।

Line 66:

! width="54.6" Height="12" | Instruction

! width="163.2" | Effect on register "j"

! width="240.6" | Effect on Instruction Counter Register ICR

! width="248.4" | Summary

|- style="font-size:9pt"

Line 75:

|- style="font-size:9pt"

| Height="11.4" valign="bottom" | DEC ( j )

| align="center" valign="bottom" | [j] -1 → j

| align="center" valign="bottom" | [IC] +1 → IC

| align="center" valign="bottom" | Decrement contents of register j; next instruction

Line 93:

=== प्रारंभिक शर्तें ===

प्रारंभ में, रजिस्टर #2 में 2 शामिल है। रजिस्टर #0, #1 और #3 खाली हैं (जिनमें 0 है)। रजिस्टर #0 पूरी गणना के दौरान अपरिवर्तित रहता है क्योंकि इसका उपयोग बिना शर्त छलांग के लिए किया जाता है। रजिस्टर #1 एक स्क्रैच पैड है। कार्यक्रम निर्देश 1 से शुरू होता है।

प्रारंभ में, रजिस्टर #2 में 2 शामिल है। रजिस्टर #0, #1 और #3 खाली हैं (जिनमें 0 है)। रजिस्टर #0 पूरी गणना के दौरान अपरिवर्तित रहता है क्योंकि इसका उपयोग बिना शर्त छलांग के लिए किया जाता है। रजिस्टर #1 स्क्रैच पैड है। कार्यक्रम निर्देश 1 से शुरू होता है।

===अंतिम शर्तें ===

Line 102:

=== कार्यक्रम का उच्च स्तरीय विवरण ===

प्रोग्राम COPY (#2, #3) के दो भाग हैं। पहले भाग में प्रोग्राम स्रोत रजिस्टर #2 की सामग्री को स्क्रैच-पैड #1 और गंतव्य रजिस्टर #3 दोनों में ले जाता है; इस प्रकार #1 और #3 एक दूसरे की और #2 में मूल गणना की प्रतियां होंगी, लेकिन #2 को शून्य तक घटाने की प्रक्रिया में साफ़ कर दिया गया है। बिना शर्त छलांग J (z) रजिस्टर #0 के परीक्षणों द्वारा की जाती है, जिसमें हमेशा संख्या 0 होती है:

प्रोग्राम COPY (#2, #3) के दो भाग हैं। पहले भाग में प्रोग्राम स्रोत रजिस्टर #2 की सामग्री को स्क्रैच-पैड #1 और गंतव्य रजिस्टर #3 दोनों में ले जाता है; इस प्रकार #1 और #3 दूसरे की और #2 में मूल गणना की प्रतियां होंगी, लेकिन #2 को शून्य तक घटाने की प्रक्रिया में साफ़ कर दिया गया है। बिना शर्त छलांग J (z) रजिस्टर #0 के परीक्षणों द्वारा की जाती है, जिसमें हमेशा संख्या 0 होती है:

: [#2] →#3; [#2] →#1; 0 →#2

Line 111:

पीले रंग में हाइलाइट किया गया प्रोग्राम ऊपरी दाएँ भाग में बाएँ से दाएँ लिखा हुआ दिखाया गया है।

प्रोग्राम का एक रन नीचे दिखाया गया है। समय पृष्ठ के नीचे चला जाता है। निर्देश पीले रंग में हैं, रजिस्टर नीले रंग में हैं। प्रोग्राम को 90 डिग्री पर फ़्लिप किया गया है, शीर्ष पर निर्देश संख्या (पते), पतों के नीचे निर्देश निमोनिक्स, और निमोनिक्स के तहत निर्देश पैरामीटर (प्रति सेल एक):

प्रोग्राम का रन नीचे दिखाया गया है। समय पृष्ठ के नीचे चला जाता है। निर्देश पीले रंग में हैं, रजिस्टर नीले रंग में हैं। प्रोग्राम को 90 डिग्री पर फ़्लिप किया गया है, शीर्ष पर निर्देश संख्या (पते), पतों के नीचे निर्देश निमोनिक्स, और निमोनिक्स के तहत निर्देश पैरामीटर (प्रति सेल एक):

{|class="toccolours" style="font-size:88%;width:100%;text-align:center;"

|- style="font-size:8pt"

Line 873:

==आंशिक पुनरावर्ती कार्य: पुनरावर्तन का उपयोग करके सुविधा निर्देश बनाना==

उपरोक्त उदाहरण दर्शाता है कि कैसे पहले बुनियादी निर्देश { INC, DEC, JZ } तीन और निर्देश बना सकते हैं - बिना शर्त जंप J, CLR, CPY। एक अर्थ में सीपीवाई ने सीएलआर और जे प्लस बेस सेट दोनों का उपयोग किया। यदि रजिस्टर #3 में प्रारंभ में सामग्री होती, तो #2 और #3 की सामग्री का योग #3 में समाप्त होता। इसलिए पूरी तरह से सटीक होने के लिए सीपीवाई कार्यक्रम को सीएलआर (1) और सीएलआर (3) के साथ आगे बढ़ना चाहिए था।

उपरोक्त उदाहरण दर्शाता है कि कैसे पहले बुनियादी निर्देश { INC, DEC, JZ } तीन और निर्देश बना सकते हैं - बिना शर्त जंप J, CLR, CPY। अर्थ में सीपीवाई ने सीएलआर और जे प्लस बेस सेट दोनों का उपयोग किया। यदि रजिस्टर #3 में प्रारंभ में सामग्री होती, तो #2 और #3 की सामग्री का योग #3 में समाप्त होता। इसलिए पूरी तरह से सटीक होने के लिए सीपीवाई कार्यक्रम को सीएलआर (1) और सीएलआर (3) के साथ आगे बढ़ना चाहिए था।

हालाँकि, हम देखते हैं कि ADD आसानी से संभव होता। और वास्तव में निम्नलिखित इस बात का सारांश है कि ADD, MULtiply और EXPonent जैसे [[आदिम पुनरावर्ती कार्य]] कैसे हो सकते हैं (बूलोस-बर्गेस-जेफरी (2002) पृष्ठ 45-51 देखें)।

Line 905:

लेखक बताते हैं कि यह किसी भी उपलब्ध आधार सेट (1, 2, या 3) के भीतर आसानी से किया जाता है (एक उदाहरण μ ऑपरेटर पर पाया जा सकता है)। इसका मतलब यह है कि किसी भी म्यू रिकर्सिव फ़ंक्शन को काउंटर मशीन के रूप में कार्यान्वित किया जा सकता है,<ref>Boolos-Burgess-Jeffrey (2002)</ref> काउंटर मशीन डिज़ाइन के सीमित निर्देश सेट और प्रोग्राम आकार के बावजूद। हालाँकि, आवश्यक निर्माण प्रति-सहज ज्ञान युक्त हो सकता है, यहां तक कि उन कार्यों के लिए भी जिन्हें रैंडम-एक्सेस मशीन जैसी अधिक जटिल रजिस्टर मशीनों में परिभाषित करना अपेक्षाकृत आसान है। ऐसा इसलिए है क्योंकि μ ऑपरेटर असीमित संख्या में बार-बार पुनरावृति कर सकता है, लेकिन कोई भी काउंटर मशीन अपनी निर्देश सूची के सीमित आकार के कारण असीमित संख्या में अलग-अलग रजिस्टरों को संबोधित नहीं कर सकती है।

उदाहरण के लिए, आदिम पुनरावर्ती ऑपरेटरों के उपरोक्त पदानुक्रम को नुथ के अप-एरो नोटेशन में उच्च-क्रम वाले तीर संचालन में घातांक से आगे बढ़ाया जा सकता है। किसी भी निश्चित के लिए <math>k</math>, कार्यक्रम <math>Q(x, y) = x \uparrow^k y</math> आदिम पुनरावर्ती है, और इसे सीधे तरीके से काउंटर मशीन के रूप में कार्यान्वित किया जा सकता है। लेकिन समारोह <math>R(n, x, y) = x \uparrow^n y</math> आदिम पुनरावर्ती नहीं है. किसी को अप-एरो ऑपरेटर को लागू करने का लालच हो सकता है <math>R</math> [[कॉल स्टैक]] को कार्यान्वित करके, उपरोक्त उत्तराधिकारी, जोड़, गुणन और घातांक निर्देशों के समान निर्माण का उपयोग करके, ताकि फ़ंक्शन को छोटे मानों पर पुनरावर्ती रूप से लागू किया जा सके <math>n</math>. यह विचार इस बात के समान है कि कोई व्यक्ति कई प्रोग्रामिंग भाषाओं में फ़ंक्शन को व्यवहार में कैसे लागू कर सकता है। हालाँकि, काउंटर मशीन अपनी गणना में असीमित संख्या में रजिस्टरों का उपयोग नहीं कर सकती है, जो कॉल स्टैक को लागू करने के लिए आवश्यक होगा जो मनमाने ढंग से बड़ा हो सकता है। अप-एरो ऑपरेशन को अभी भी एक काउंटर मशीन के रूप में कार्यान्वित किया जा सकता है क्योंकि यह पुनरावर्ती है, हालांकि फ़ंक्शन को सीमित संख्या में रजिस्टरों के अंदर असीमित मात्रा में जानकारी को एन्कोड करके कार्यान्वित किया जाएगा, जैसे गोडेल नंबरिंग का उपयोग करके।

उदाहरण के लिए, आदिम पुनरावर्ती ऑपरेटरों के उपरोक्त पदानुक्रम को नुथ के अप-एरो नोटेशन में उच्च-क्रम वाले तीर संचालन में घातांक से आगे बढ़ाया जा सकता है। किसी भी निश्चित के लिए <math>k</math>, कार्यक्रम <math>Q(x, y) = x \uparrow^k y</math> आदिम पुनरावर्ती है, और इसे सीधे तरीके से काउंटर मशीन के रूप में कार्यान्वित किया जा सकता है। लेकिन समारोह <math>R(n, x, y) = x \uparrow^n y</math> आदिम पुनरावर्ती नहीं है. किसी को अप-एरो ऑपरेटर को लागू करने का लालच हो सकता है <math>R</math> [[कॉल स्टैक]] को कार्यान्वित करके, उपरोक्त उत्तराधिकारी, जोड़, गुणन और घातांक निर्देशों के समान निर्माण का उपयोग करके, ताकि फ़ंक्शन को छोटे मानों पर पुनरावर्ती रूप से लागू किया जा सके <math>n</math>. यह विचार इस बात के समान है कि कोई व्यक्ति कई प्रोग्रामिंग भाषाओं में फ़ंक्शन को व्यवहार में कैसे लागू कर सकता है। हालाँकि, काउंटर मशीन अपनी गणना में असीमित संख्या में रजिस्टरों का उपयोग नहीं कर सकती है, जो कॉल स्टैक को लागू करने के लिए आवश्यक होगा जो मनमाने ढंग से बड़ा हो सकता है। अप-एरो ऑपरेशन को अभी भी काउंटर मशीन के रूप में कार्यान्वित किया जा सकता है क्योंकि यह पुनरावर्ती है, हालांकि फ़ंक्शन को सीमित संख्या में रजिस्टरों के अंदर असीमित मात्रा में जानकारी को एन्कोड करके कार्यान्वित किया जाएगा, जैसे गोडेल नंबरिंग का उपयोग करके।

== काउंटर मशीन मॉडल के साथ समस्याएं ==

Line 913:

(2) 'रजिस्टरों की असीमित संख्या बनाम राज्य-मशीन निर्देशों की बंधी हुई संख्या:' मशीन अपनी सीमित राज्य मशीन की पहुंच/क्षमता से परे पता-संख्या वाले रजिस्टरों तक कैसे पहुंच पाएगी?

<!-- (1) '''No easy way to arrange for a stored program''': A stored program is required for a "Universal Register Machine" (URM) -- the counterpart of the [[Universal Turing Machine]]. The URM's program would reside in some registers while its input parameters and output parameters would reside in other registers.

~~Melzak observes that, with regards to what he called his "Q-machine":~~

:"there appears to be no easy way to arrange for a stored program. Further, although this is not necessarily bad, there is no separation between the storage and the arithmetic parts of the machine" (Melzak (1961) p. 293)

An approach taken by Minsky (1961, 1967) was to put the program into a single register, the instructions and data encoded by [[Gödel numbering]] (see '''Two-counter machines are Turing powerful''', below). The resultant number (e.g. a huge unary string) would represent the product of all the instructions and data. To "fetch" an instruction, and then to "parse/decode" it into action, this one-tape machine needs the built-in ability to divide the monster number by primes and to test it for "no-remainder", then multiply it by the instruction's action code-number to cause the required action. When more tapes are available Minsky demonstrates that "INCREMENT" and "DECREMENT-with-test/jump" suffice. But all this occurs only at the expense of arcane coding that represents nothing similar to a "programmed computer".

~~What Melzak proposed and is available in RAM and RASP models was the "indirect address"-- but at the expense of more "machine structure".~~

~~:'''The CASE instruction: a primitive way to 'parse'. First parse: the instruction address:'''~~

If indirect addressing were not available, how does a counter machine program "fetch" an instruction from the registers in order to "execute" it? First, the program sets aside a special register that it calls "the program counter" (PC). Suppose after a few instructions that hole #PC contains the number '''3'''. Although our machine knows it has ''an'' instruction's address/number in the PC, our machine does not know ''which'' address/number it is -- is it "7", "15", or "422"?. It must "parse" this number to find out. How? By decrementing PC's count until zero, then jumping to a tiny routine that copies the contents of hole #3 into the PC. This is called the CASE instruction and is shown to be [[primitive recursive]] by a proof of Kleene (1952) p.229.

~~If the machine has a possible #47543 holes, then it must start counting down from #47543. This could take a while.~~

~~:'''Second parse: the instruction''':~~

After the first parse of the number of the next instruction's ''address'', the machine jumps to an instruction to "copy contents of hole #3 to register 'PR'". Since the contents of hole #3 is the instruction (its number, actually) the machine must now parse this ''instruction''.

~~:'''Parsing issues''':~~

We have seen how to solve the "fetch problem" by "parsing" twice to get a number from a register that represents an instruction. But note there is a bit of an issue. Because this is a ''Universal'' Counter Machine there is no "largest" program. For example, suppose the hole-contents-to-be-moved isn't found in hole #47543 but rather hole #218832673911. The machine must parse its way down from some ultimate "end" to the program, or by starting from instruction #1 and working its way up to this #218832673911st hole. But in general it doesn't know where this end is unless there's a special "mark" there telling the machine not to go any further. It is quite possible that the finite state machine will not be large enough to hold this really big number. Every program will be required to contain a number that defines its ultimate length, including all of its input and output and "scratch registers".

~~(2) '''No indirect addressing:'''~~

Thus we have arrived at the crucial deficiency. Nothing like this exists with, for example, the various tape- based [[Turing machine]] models; the position of the head is relative to the head, not absolute.

How much easier it would be if our Universal Counter Machine were equipped with the following ability -- if it could tell the register it calls "the Program Counter" (PC) to use its contents to "point to" the register that at long last delivers up the instruction (i.e. ''contents'' of #1 points to #3 which contains "5", and this "five" represents the instruction "JE"):

~~: [[1] ] → [3] =5 ="JE"~~

Melzak used this modification to prove that his "Q-machine" is [[Turing equivalent]]. Melzak's attempted remedy results in the so-called RAM/RASP ( [[random-access machine]], [[Random-access stored program machine]] ) models, but his comment on page 293 seems to indicate that he was not totally happy with the result.-->

(3) पूरी तरह से कम किए गए मॉडल बोझिल हैं:

Line 955:

Line 925:

** निर्देश I पर बिना शर्त कूदेंz

** यदि [r] =0 हो तो निर्देश I पर कूदेंz

मिन्स्की (1967) ने अपने 2-निर्देश सेट { INC (z), JZDEC (r, I) का विस्तार कियाz) } से { CLR (r), INC (r), JZDEC (r, Iz), जे (आईz) } उनके इस प्रमाण से पहले कि एक यूनिवर्सल प्रोग्राम मशीन केवल दो रजिस्टरों के साथ बनाई जा सकती है (पृष्ठ 255एफएफ)।

मिन्स्की (1967) ने अपने 2-निर्देश सेट { INC (z), JZDEC (r, I) का विस्तार कियाz) } से { CLR (r), INC (r), JZDEC (r, Iz), जे (आईz) } उनके इस प्रमाण से पहले कि यूनिवर्सल प्रोग्राम मशीन केवल दो रजिस्टरों के साथ बनाई जा सकती है (पृष्ठ 255एफएफ)।

==दो-काउंटर मशीनें ट्यूरिंग समकक्ष हैं (चेतावनी के साथ)==

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

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

दो काउंटर मशीनें निर्देश के सेट का उपयोग करती हैं { INC ( r, z ), JZDEC ( r, ztrue, साथfalse) }.

Anonymous

Search

काउंटर मशीन: Difference between revisions

Namespaces

More

Page actions

@@ Line 1: / Line 1: @@
 {{Short description|Abstract machine used in a formal logic and theoretical computer science}}
-काउंटर मशीन एक [[अमूर्त मशीन]] है जिसका उपयोग [[औपचारिक तर्क]] और [[सैद्धांतिक कंप्यूटर विज्ञान]] में गणना के मॉडल के लिए किया जाता है। यह चार प्रकार की [[रजिस्टर मशीन]]ों में से सबसे आदिम है। एक काउंटर मशीन में एक या अधिक अनबाउंडेड ''रजिस्टरों'' का एक सेट शामिल होता है, जिनमें से प्रत्येक एक गैर-नकारात्मक पूर्णांक, और मशीन के पालन के लिए (आमतौर पर अनुक्रमिक) अंकगणित और नियंत्रण निर्देशों की एक सूची रख सकता है। काउंटर मशीन का उपयोग आमतौर पर पारस्परिक बहिष्करण सिद्धांत के संबंध में समानांतर एल्गोरिदम को डिजाइन करने की प्रक्रिया में किया जाता है। जब इस तरीके से उपयोग किया जाता है, तो काउंटर मशीन का उपयोग मेमोरी एक्सेस के संबंध में कम्प्यूटेशनल सिस्टम के अलग-अलग समय-चरणों को मॉडल करने के लिए किया जाता है। प्रत्येक संबंधित कम्प्यूटेशनल चरण के लिए मेमोरी एक्सेस के संबंध में गणनाओं को मॉडलिंग करके, समान मेमोरी पते पर दो (या अधिक) थ्रेड्स द्वारा एक साथ लेखन ऑपरेशन, इंटरलॉकिंग से बचने के लिए ऐसे मामले में समानांतर एल्गोरिदम डिज़ाइन किया जा सकता है।
+काउंटर मशीन [[अमूर्त मशीन]] है जिसका उपयोग [[औपचारिक तर्क]] और [[सैद्धांतिक कंप्यूटर विज्ञान]] में गणना के मॉडल के लिए किया जाता है। यह चार प्रकार की [[रजिस्टर मशीन]]ों में से सबसे आदिम है। काउंटर मशीन में या अधिक अनबाउंडेड ''रजिस्टरों'' का सेट शामिल होता है, जिनमें से प्रत्येक गैर-नकारात्मक पूर्णांक, और मशीन के पालन के लिए (आमतौर पर अनुक्रमिक) अंकगणित और नियंत्रण निर्देशों की सूची रख सकता है। काउंटर मशीन का उपयोग आमतौर पर पारस्परिक बहिष्करण सिद्धांत के संबंध में समानांतर एल्गोरिदम को डिजाइन करने की प्रक्रिया में किया जाता है। जब इस तरीके से उपयोग किया जाता है, तो काउंटर मशीन का उपयोग मेमोरी एक्सेस के संबंध में कम्प्यूटेशनल सिस्टम के अलग-अलग समय-चरणों को मॉडल करने के लिए किया जाता है। प्रत्येक संबंधित कम्प्यूटेशनल चरण के लिए मेमोरी एक्सेस के संबंध में गणनाओं को मॉडलिंग करके, समान मेमोरी पते पर दो (या अधिक) थ्रेड्स द्वारा साथ लेखन ऑपरेशन, इंटरलॉकिंग से बचने के लिए ऐसे मामले में समानांतर एल्गोरिदम डिज़ाइन किया जा सकता है।
 == बुनियादी सुविधाएँ ==
-किसी दिए गए काउंटर मशीन मॉडल के लिए निर्देश सेट छोटा है - केवल एक से छह या सात निर्देशों तक। अधिकांश मॉडलों में कुछ अंकगणितीय ऑपरेशन और कम से कम एक सशर्त ऑपरेशन होता है (यदि स्थिति सत्य है, तो कूदें)। तीन आधार मॉडल, प्रत्येक तीन निर्देशों का उपयोग करते हुए, निम्नलिखित संग्रह से तैयार किए गए हैं। (संक्षिप्ताक्षर मनमाने हैं।)
+किसी दिए गए काउंटर मशीन मॉडल के लिए निर्देश सेट छोटा है - केवल से छह या सात निर्देशों तक। अधिकांश मॉडलों में कुछ अंकगणितीय ऑपरेशन और कम से कम सशर्त ऑपरेशन होता है (यदि स्थिति सत्य है, तो कूदें)। तीन आधार मॉडल, प्रत्येक तीन निर्देशों का उपयोग करते हुए, निम्नलिखित संग्रह से तैयार किए गए हैं। (संक्षिप्ताक्षर मनमाने हैं।)
 * सीएलआर (आर): क्लियर रजिस्टर आर। (आर को शून्य पर सेट करें।)
 * आईएनसी (आर): रजिस्टर आर की सामग्री को बढ़ाएं।
@@ Line 12: / Line 12: @@
 * जेई (आर<sub>j</sub>, आर<sub>k</sub>, z): यदि रजिस्टर आर की सामग्री<sub>j</sub>रजिस्टर आर की सामग्री के बराबर है<sub>k</sub>फिर निर्देश पर जाएं अन्यथा क्रम से जारी रखें।
-इसके अलावा, मशीन में आमतौर पर एक HALT निर्देश होता है, जो मशीन को रोक देता है (आमतौर पर परिणाम की गणना के बाद)।
+इसके अलावा, मशीन में आमतौर पर HALT निर्देश होता है, जो मशीन को रोक देता है (आमतौर पर परिणाम की गणना के बाद)।
 ऊपर उल्लिखित निर्देशों का उपयोग करते हुए, विभिन्न लेखकों ने कुछ काउंटर मशीनों पर चर्चा की है:
@@ Line 19: / Line 19: @@
 * सेट 3: {आईएनसी (आर), सीपीवाई (आर)।<sub>j</sub>, आर<sub>k</sub>), जेई (आर<sub>j</sub>, आर<sub>k</sub>, z) }, (एल्गॉट-रॉबिन्सन (1964), मिन्स्की (1967))
-तीन काउंटर मशीन बेस मॉडल में समान कम्प्यूटेशनल शक्ति होती है क्योंकि एक मॉडल के निर्देश दूसरे मॉडल से प्राप्त किए जा सकते हैं। सभी [[ट्यूरिंग मशीन]]ों की कम्प्यूटेशनल शक्ति के बराबर हैं। उनकी एकात्मक प्रसंस्करण शैली के कारण, काउंटर मशीनें आमतौर पर तुलनीय ट्यूरिंग मशीनों की तुलना में तेजी से धीमी होती हैं।
+तीन काउंटर मशीन बेस मॉडल में समान कम्प्यूटेशनल शक्ति होती है क्योंकि मॉडल के निर्देश दूसरे मॉडल से प्राप्त किए जा सकते हैं। सभी [[ट्यूरिंग मशीन]]ों की कम्प्यूटेशनल शक्ति के बराबर हैं। उनकी एकात्मक प्रसंस्करण शैली के कारण, काउंटर मशीनें आमतौर पर तुलनीय ट्यूरिंग मशीनों की तुलना में तेजी से धीमी होती हैं।
 == वैकल्पिक नाम, वैकल्पिक मॉडल ==
@@ Line 25: / Line 25: @@
 {{main|Counter-machine model}}
-काउंटर मशीन मॉडल कई अलग-अलग नामों से जाने जाते हैं जो उनकी विशिष्टताओं के आधार पर उन्हें अलग करने में मदद कर सकते हैं। निम्नलिखित निर्देश में JZDEC (r) एक मिश्रित निर्देश है जो यह देखने के लिए परीक्षण करता है कि कोई रजिस्टर r खाली है या नहीं; यदि ऐसा है तो निर्देश I पर जाएँ<sub>z</sub>, अन्यथा यदि नहीं तो r की सामग्री को घटाएँ:
+काउंटर मशीन मॉडल कई अलग-अलग नामों से जाने जाते हैं जो उनकी विशिष्टताओं के आधार पर उन्हें अलग करने में मदद कर सकते हैं। निम्नलिखित निर्देश में JZDEC (r) मिश्रित निर्देश है जो यह देखने के लिए परीक्षण करता है कि कोई रजिस्टर r खाली है या नहीं; यदि ऐसा है तो निर्देश I पर जाएँ<sub>z</sub>, अन्यथा यदि नहीं तो r की सामग्री को घटाएँ:
 * शेफर्डसन-स्टर्गिस मशीन, क्योंकि इन लेखकों ने औपचारिक रूप से अपने मॉडल को आसानी से सुलभ प्रदर्शनी (1963) में बताया था। अतिरिक्त सुविधा निर्देशों के साथ संवर्धित अनुदेश सेट (1) का उपयोग करता है (जेएनजेड शून्य नहीं होने पर जंप है, जेजेड के स्थान पर उपयोग किया जाता है):
@@ Line 31: / Line 31: @@
 * मिन्स्की मशीन, क्योंकि [[मार्विन मिंस्की]] (1961) ने मॉडल को औपचारिक रूप दिया। आमतौर पर निर्देश सेट (1) का उपयोग करता है, लेकिन निर्देश-निष्पादन डिफ़ॉल्ट-अनुक्रमिक नहीं है, इसलिए अतिरिक्त पैरामीटर 'z' INC के बाद अगले निर्देश को निर्दिष्ट करता है और JZDEC में विकल्प के रूप में दिखाई देता है:
 *: { INC ( r, z ), JZDEC ( r, z<sub>true</sub>, साथ<sub>false</sub>) }
-* प्रोग्राम मशीन, प्रोग्राम [[कंप्यूटर]], नाम मिन्स्की (1967) ने मॉडल को दिया क्योंकि, एक कंप्यूटर की तरह इसके निर्देश क्रमिक रूप से आगे बढ़ते हैं जब तक कि एक सशर्त छलांग सफल नहीं होती। (आमतौर पर) निर्देश सेट (1) का उपयोग करता है लेकिन इसे शेफर्सन-स्टर्गिस मॉडल के समान संवर्धित किया जा सकता है। JZDEC को अक्सर अलग कर दिया जाता है:
+* प्रोग्राम मशीन, प्रोग्राम [[कंप्यूटर]], नाम मिन्स्की (1967) ने मॉडल को दिया क्योंकि, कंप्यूटर की तरह इसके निर्देश क्रमिक रूप से आगे बढ़ते हैं जब तक कि सशर्त छलांग सफल नहीं होती। (आमतौर पर) निर्देश सेट (1) का उपयोग करता है लेकिन इसे शेफर्सन-स्टर्गिस मॉडल के समान संवर्धित किया जा सकता है। JZDEC को अक्सर अलग कर दिया जाता है:
 *: { INC ( r ), DEC ( r ), JZ ( r, z<sub>true</sub> )}
-* अबेकस मशीन, नाम लैम्बेक (1961) ने मेल्ज़ाक (1961) मॉडल के सरलीकरण के लिए दिया था, और बूलोस-बर्गेस-जेफरी (2002) इसे क्या कहते हैं। मिन्स्की (1961) मॉडल के तरीके से अगले निर्देश को निर्दिष्ट करने के लिए निर्देश सेट (1) का उपयोग करता है लेकिन एक अतिरिक्त पैरामीटर z के साथ;
+* अबेकस मशीन, नाम लैम्बेक (1961) ने मेल्ज़ाक (1961) मॉडल के सरलीकरण के लिए दिया था, और बूलोस-बर्गेस-जेफरी (2002) इसे क्या कहते हैं। मिन्स्की (1961) मॉडल के तरीके से अगले निर्देश को निर्दिष्ट करने के लिए निर्देश सेट (1) का उपयोग करता है लेकिन अतिरिक्त पैरामीटर z के साथ;
 *: { INC ( r, z ), JZDEC (r, z<sub>true</sub>, साथ<sub>false</sub> ) }
-* लैम्बेक मशीन, एक वैकल्पिक नाम बूलोस-बर्गेस-जेफरी (2002) ने अबेकस मशीन को दिया। अगले निर्देश को निर्दिष्ट करने के लिए एक अतिरिक्त पैरामीटर के साथ निर्देश सेट (1-कम) का उपयोग करता है:
+* लैम्बेक मशीन, वैकल्पिक नाम बूलोस-बर्गेस-जेफरी (2002) ने अबेकस मशीन को दिया। अगले निर्देश को निर्दिष्ट करने के लिए अतिरिक्त पैरामीटर के साथ निर्देश सेट (1-कम) का उपयोग करता है:
 *: { INC ( r, z ), JZDEC ( r, z<sub>true</sub>, साथ<sub>false</sub> ) }
-* उत्तराधिकारी मशीन, क्योंकि यह 'उत्तराधिकारी ऑपरेशन' का उपयोग करती है, और पीनो स्वयंसिद्धों से काफी मिलती-जुलती है। उत्तराधिकारी रैम मॉडल के लिए आधार के रूप में उपयोग किया जाता है। उदाहरण के लिए निर्देश सेट (2) का उपयोग करता है। शॉनहेज को उनके RAM0 और RAM1 मॉडल के आधार के रूप में, जो उनके [[ सूचक मशीन ]] SMM मॉडल की ओर ले जाता है, वैन एम्डे बोस (1990) में भी संक्षेप में चर्चा की गई है:
+* उत्तराधिकारी मशीन, क्योंकि यह 'उत्तराधिकारी ऑपरेशन' का उपयोग करती है, और पीनो स्वयंसिद्धों से काफी मिलती-जुलती है। उत्तराधिकारी रैम मॉडल के लिए आधार के रूप में उपयोग किया जाता है। उदाहरण के लिए निर्देश सेट (2) का उपयोग करता है। शॉनहेज को उनके RAM0 और RAM1 मॉडल के आधार के रूप में, जो उनके [[ सूचक मशीन |सूचक मशीन]] SMM मॉडल की ओर ले जाता है, वैन एम्डे बोस (1990) में भी संक्षेप में चर्चा की गई है:
 *: {सीएलआर (आर), आईएनसी (आर), जेई (आर)।<sub>j</sub>, आर<sub>k</sub>, z ) }
-* एल्गॉट-रॉबिन्सन मॉडल, उनके आरएएसपी मॉडल (1964) को परिभाषित करने के लिए उपयोग किया जाता है। इस मॉडल को प्रारंभ में एक खाली रजिस्टर की आवश्यकता होती है (उदाहरण के लिए [r0] =0)। (उन्होंने इंडेक्स रजिस्टर के रूप में उपयोग करने के लिए एक अतिरिक्त रजिस्टर का उपयोग करके अप्रत्यक्ष संबोधन के साथ उसी मॉडल को संवर्धित किया।)
+* एल्गॉट-रॉबिन्सन मॉडल, उनके आरएएसपी मॉडल (1964) को परिभाषित करने के लिए उपयोग किया जाता है। इस मॉडल को प्रारंभ में खाली रजिस्टर की आवश्यकता होती है (उदाहरण के लिए [r0] =0)। (उन्होंने इंडेक्स रजिस्टर के रूप में उपयोग करने के लिए अतिरिक्त रजिस्टर का उपयोग करके अप्रत्यक्ष संबोधन के साथ उसी मॉडल को संवर्धित किया।)
 *: { आईएनसी (आर), सीपीवाई (आर<sub>s</sub>, आर<sub>d</sub> ), जेई (आर<sub>j</sub>, आर<sub>k</sub>, z ) }
-* अन्य काउंटर मशीनें: मिन्स्की (1967) दर्शाता है कि इस आलेख के मुख्य पैराग्राफ में वर्णित उपलब्ध निर्देशों के सुपरसेट से तीन बेस मॉडल (प्रोग्राम/मिन्स्की/लैम्बेक-अबेकस, उत्तराधिकारी, और एल्गॉट-रॉबिन्सन) कैसे बनाया जाए। मेल्ज़ाक (1961) मॉडल उपरोक्त से काफी अलग है क्योंकि इसमें 'वृद्धि' और 'घटाना' के बजाय 'जोड़' और 'घटाना' शामिल है। मिन्स्की (1961, 1967) के प्रमाण कि ट्यूरिंग समतुल्यता के लिए एक एकल रजिस्टर पर्याप्त होगा, गणना का प्रतिनिधित्व करने वाले रजिस्टर में गोडेल संख्या को एन्कोड और डीकोड करने के लिए दो निर्देशों {मल्टीप्लाई के, और डीआईवी के} की आवश्यकता होती है। मिन्स्की दर्शाता है कि यदि दो या दो से अधिक रजिस्टर उपलब्ध हैं तो सरल INC, DEC आदि पर्याप्त हैं (लेकिन [[ट्यूरिंग पूर्णता]] प्रदर्शित करने के लिए गोडेल संख्या अभी भी आवश्यक है; एल्गॉट-रॉबिन्सन 1964 में भी प्रदर्शित किया गया है)।
+* अन्य काउंटर मशीनें: मिन्स्की (1967) दर्शाता है कि इस आलेख के मुख्य पैराग्राफ में वर्णित उपलब्ध निर्देशों के सुपरसेट से तीन बेस मॉडल (प्रोग्राम/मिन्स्की/लैम्बेक-अबेकस, उत्तराधिकारी, और एल्गॉट-रॉबिन्सन) कैसे बनाया जाए। मेल्ज़ाक (1961) मॉडल उपरोक्त से काफी अलग है क्योंकि इसमें 'वृद्धि' और 'घटाना' के बजाय 'जोड़' और 'घटाना' शामिल है। मिन्स्की (1961, 1967) के प्रमाण कि ट्यूरिंग समतुल्यता के लिए एकल रजिस्टर पर्याप्त होगा, गणना का प्रतिनिधित्व करने वाले रजिस्टर में गोडेल संख्या को एन्कोड और डीकोड करने के लिए दो निर्देशों {मल्टीप्लाई के, और डीआईवी के} की आवश्यकता होती है। मिन्स्की दर्शाता है कि यदि दो या दो से अधिक रजिस्टर उपलब्ध हैं तो सरल INC, DEC आदि पर्याप्त हैं (लेकिन [[ट्यूरिंग पूर्णता]] प्रदर्शित करने के लिए गोडेल संख्या अभी भी आवश्यक है; एल्गॉट-रॉबिन्सन 1964 में भी प्रदर्शित किया गया है)।
 == औपचारिक परिभाषा ==
 एक काउंटर मशीन में निम्न शामिल होते हैं:
-# लेबल रहित पूर्णांक-मूल्यवान रजिस्टर: रजिस्टरों का एक सीमित (या कुछ मॉडलों में अनंत) सेट ''आर''<sub>0</sub>... आर<sub>''n''</sub> जिनमें से प्रत्येक किसी एक गैर-नकारात्मक पूर्णांक (0, 1, 2, ... - यानी असीमित) को धारण कर सकता है। रजिस्टर अपना अंकगणित स्वयं करते हैं; एक या अधिक विशेष रजिस्टर हो भी सकते हैं और नहीं भी, जैसे संचायक (इस पर अधिक जानकारी के लिए [[रैंडम-एक्सेस मशीन]] देखें)।
+# लेबल रहित पूर्णांक-मूल्यवान रजिस्टर: रजिस्टरों का सीमित (या कुछ मॉडलों में अनंत) सेट ''आर''<sub>0</sub>... आर<sub>''n''</sub> जिनमें से प्रत्येक किसी गैर-नकारात्मक पूर्णांक (0, 1, 2, ... - यानी असीमित) को धारण कर सकता है। रजिस्टर अपना अंकगणित स्वयं करते हैं; या अधिक विशेष रजिस्टर हो भी सकते हैं और नहीं भी, जैसे संचायक (इस पर अधिक जानकारी के लिए [[रैंडम-एक्सेस मशीन]] देखें)।
-# एक राज्य रजिस्टर जो निष्पादित किए जाने वाले वर्तमान निर्देश को संग्रहीत/पहचानता है। यह रजिस्टर परिमित है और उपरोक्त रजिस्टरों से अलग है; इस प्रकार काउंटर मशीन मॉडल [[हार्वर्ड वास्तुकला]] का एक उदाहरण है
+# एक राज्य रजिस्टर जो निष्पादित किए जाने वाले वर्तमान निर्देश को संग्रहीत/पहचानता है। यह रजिस्टर परिमित है और उपरोक्त रजिस्टरों से अलग है; इस प्रकार काउंटर मशीन मॉडल [[हार्वर्ड वास्तुकला]] का उदाहरण है
-# लेबल किए गए, अनुक्रमिक निर्देशों की सूची: निर्देशों की एक सीमित सूची ''I''<sub>0</sub>... मैं<sub>''m''</sub>. प्रोग्राम स्टोर (परिमित राज्य मशीन के निर्देश) रजिस्टरों के समान भौतिक स्थान पर नहीं है। आमतौर पर, लेकिन हमेशा नहीं, [[कंप्यूटर प्रोग्राम]] की तरह निर्देश अनुक्रमिक क्रम में सूचीबद्ध होते हैं; जब तक कोई छलांग सफल नहीं होती, डिफ़ॉल्ट अनुक्रम संख्यात्मक क्रम में जारी रहता है। सूची में प्रत्येक निर्देश एक (बहुत) छोटे सेट से है, लेकिन इस सेट में अप्रत्यक्ष शामिल नहीं है। ऐतिहासिक रूप से अधिकांश मॉडलों ने इस सेट से अपने निर्देश प्राप्त किए:
+# लेबल किए गए, अनुक्रमिक निर्देशों की सूची: निर्देशों की सीमित सूची ''I''<sub>0</sub>... मैं<sub>''m''</sub>. प्रोग्राम स्टोर (परिमित राज्य मशीन के निर्देश) रजिस्टरों के समान भौतिक स्थान पर नहीं है। आमतौर पर, लेकिन हमेशा नहीं, [[कंप्यूटर प्रोग्राम]] की तरह निर्देश अनुक्रमिक क्रम में सूचीबद्ध होते हैं; जब तक कोई छलांग सफल नहीं होती, डिफ़ॉल्ट अनुक्रम संख्यात्मक क्रम में जारी रहता है। सूची में प्रत्येक निर्देश (बहुत) छोटे सेट से है, लेकिन इस सेट में अप्रत्यक्ष शामिल नहीं है। ऐतिहासिक रूप से अधिकांश मॉडलों ने इस सेट से अपने निर्देश प्राप्त किए:
 :: {वृद्धि (आर), कमी (आर), स्पष्ट (आर); कॉपी (आर<sub>j</sub>,आर<sub>k</sub>), यदि r=0 की सामग्री है तो सशर्त छलांग, यदि r की सामग्री है तो सशर्त छलांग<sub>j</sub>=आर<sub>k</sub>, बिना शर्त कूदो, रुको }
-: कुछ मॉडलों ने या तो उपरोक्त में से कुछ को बिना-पैरामीटर निर्देशों में परमाणुकृत कर दिया है, या उन्हें एक ही निर्देश में जोड़ दिया है जैसे कि सशर्त कूद-अगर-शून्य जेजेड (आर, जेड) से पहले डिक्रीमेंट। निर्देशों के परमाणुकरण या सुविधाजनक निर्देशों को शामिल करने से वैचारिक शक्ति में कोई बदलाव नहीं होता है, क्योंकि एक संस्करण में किसी भी कार्यक्रम को सीधे दूसरे में अनुवादित किया जा सकता है।
+: कुछ मॉडलों ने या तो उपरोक्त में से कुछ को बिना-पैरामीटर निर्देशों में परमाणुकृत कर दिया है, या उन्हें ही निर्देश में जोड़ दिया है जैसे कि सशर्त कूद-अगर-शून्य जेजेड (आर, जेड) से पहले डिक्रीमेंट। निर्देशों के परमाणुकरण या सुविधाजनक निर्देशों को शामिल करने से वैचारिक शक्ति में कोई बदलाव नहीं होता है, क्योंकि संस्करण में किसी भी कार्यक्रम को सीधे दूसरे में अनुवादित किया जा सकता है।
 :: पूरक [[रजिस्टर-मशीन मॉडल]] में वैकल्पिक निर्देश-सेट पर चर्चा की गई है।
@@ Line 66: / Line 66: @@
 ! width="54.6" Height="12" | Instruction
 ! width="163.2" | Effect on register "j"
-! width="240.6" | Effect on  Instruction Counter Register ICR
+! width="240.6" | Effect on Instruction Counter Register ICR
 ! width="248.4" | Summary
 |- style="font-size:9pt"
@@ Line 75: / Line 75: @@
 |- style="font-size:9pt"
 | Height="11.4" valign="bottom" | DEC ( j )
-| align="center" valign="bottom" | [j]  -1 → j
+| align="center" valign="bottom" | [j] -1 → j
 | align="center" valign="bottom" | [IC] +1 → IC
 | align="center" valign="bottom" | Decrement contents of register j; next instruction
@@ Line 93: / Line 93: @@
 === प्रारंभिक शर्तें ===
-प्रारंभ में, रजिस्टर #2 में 2 शामिल है। रजिस्टर #0, #1 और #3 खाली हैं (जिनमें 0 है)। रजिस्टर #0 पूरी गणना के दौरान अपरिवर्तित रहता है क्योंकि इसका उपयोग बिना शर्त छलांग के लिए किया जाता है। रजिस्टर #1 एक स्क्रैच पैड है। कार्यक्रम निर्देश 1 से शुरू होता है।
+प्रारंभ में, रजिस्टर #2 में 2 शामिल है। रजिस्टर #0, #1 और #3 खाली हैं (जिनमें 0 है)। रजिस्टर #0 पूरी गणना के दौरान अपरिवर्तित रहता है क्योंकि इसका उपयोग बिना शर्त छलांग के लिए किया जाता है। रजिस्टर #1 स्क्रैच पैड है। कार्यक्रम निर्देश 1 से शुरू होता है।
 ===अंतिम शर्तें ===
@@ Line 102: / Line 102: @@
 === कार्यक्रम का उच्च स्तरीय विवरण ===
-प्रोग्राम COPY (#2, #3) के दो भाग हैं। पहले भाग में प्रोग्राम स्रोत रजिस्टर #2 की सामग्री को स्क्रैच-पैड #1 और गंतव्य रजिस्टर #3 दोनों में ले जाता है; इस प्रकार #1 और #3 एक दूसरे की और #2 में मूल गणना की प्रतियां होंगी, लेकिन #2 को शून्य तक घटाने की प्रक्रिया में साफ़ कर दिया गया है। बिना शर्त छलांग J (z) रजिस्टर #0 के परीक्षणों द्वारा की जाती है, जिसमें हमेशा संख्या 0 होती है:
+प्रोग्राम COPY (#2, #3) के दो भाग हैं। पहले भाग में प्रोग्राम स्रोत रजिस्टर #2 की सामग्री को स्क्रैच-पैड #1 और गंतव्य रजिस्टर #3 दोनों में ले जाता है; इस प्रकार #1 और #3 दूसरे की और #2 में मूल गणना की प्रतियां होंगी, लेकिन #2 को शून्य तक घटाने की प्रक्रिया में साफ़ कर दिया गया है। बिना शर्त छलांग J (z) रजिस्टर #0 के परीक्षणों द्वारा की जाती है, जिसमें हमेशा संख्या 0 होती है:
 : [#2] →#3; [#2] →#1; 0 →#2
@@ Line 111: / Line 111: @@
 पीले रंग में हाइलाइट किया गया प्रोग्राम ऊपरी दाएँ भाग में बाएँ से दाएँ लिखा हुआ दिखाया गया है।
-प्रोग्राम का एक रन नीचे दिखाया गया है। समय पृष्ठ के नीचे चला जाता है। निर्देश पीले रंग में हैं, रजिस्टर नीले रंग में हैं। प्रोग्राम को 90 डिग्री पर फ़्लिप किया गया है, शीर्ष पर निर्देश संख्या (पते), पतों के नीचे निर्देश निमोनिक्स, और निमोनिक्स के तहत निर्देश पैरामीटर (प्रति सेल एक):
+प्रोग्राम का रन नीचे दिखाया गया है। समय पृष्ठ के नीचे चला जाता है। निर्देश पीले रंग में हैं, रजिस्टर नीले रंग में हैं। प्रोग्राम को 90 डिग्री पर फ़्लिप किया गया है, शीर्ष पर निर्देश संख्या (पते), पतों के नीचे निर्देश निमोनिक्स, और निमोनिक्स के तहत निर्देश पैरामीटर (प्रति सेल एक):
 {|class="toccolours" style="font-size:88%;width:100%;text-align:center;"
 |- style="font-size:8pt"
@@ Line 873: / Line 873: @@
 ==आंशिक पुनरावर्ती कार्य: पुनरावर्तन का उपयोग करके सुविधा निर्देश बनाना==
-उपरोक्त उदाहरण दर्शाता है कि कैसे पहले बुनियादी निर्देश { INC, DEC, JZ } तीन और निर्देश बना सकते हैं - बिना शर्त जंप J, CLR, CPY। एक अर्थ में सीपीवाई ने सीएलआर और जे प्लस बेस सेट दोनों का उपयोग किया। यदि रजिस्टर #3 में प्रारंभ में सामग्री होती, तो #2 और #3 की सामग्री का योग #3 में समाप्त होता। इसलिए पूरी तरह से सटीक होने के लिए सीपीवाई कार्यक्रम को सीएलआर (1) और सीएलआर (3) के साथ आगे बढ़ना चाहिए था।
+उपरोक्त उदाहरण दर्शाता है कि कैसे पहले बुनियादी निर्देश { INC, DEC, JZ } तीन और निर्देश बना सकते हैं - बिना शर्त जंप J, CLR, CPY। अर्थ में सीपीवाई ने सीएलआर और जे प्लस बेस सेट दोनों का उपयोग किया। यदि रजिस्टर #3 में प्रारंभ में सामग्री होती, तो #2 और #3 की सामग्री का योग #3 में समाप्त होता। इसलिए पूरी तरह से सटीक होने के लिए सीपीवाई कार्यक्रम को सीएलआर (1) और सीएलआर (3) के साथ आगे बढ़ना चाहिए था।
 हालाँकि, हम देखते हैं कि ADD आसानी से संभव होता। और वास्तव में निम्नलिखित इस बात का सारांश है कि ADD, MULtiply और EXPonent जैसे [[आदिम पुनरावर्ती कार्य]] कैसे हो सकते हैं (बूलोस-बर्गेस-जेफरी (2002) पृष्ठ 45-51 देखें)।
@@ Line 905: / Line 905: @@
 लेखक बताते हैं कि यह किसी भी उपलब्ध आधार सेट (1, 2, या 3) के भीतर आसानी से किया जाता है (एक उदाहरण μ ऑपरेटर पर पाया जा सकता है)। इसका मतलब यह है कि किसी भी म्यू रिकर्सिव फ़ंक्शन को काउंटर मशीन के रूप में कार्यान्वित किया जा सकता है,<ref>Boolos-Burgess-Jeffrey (2002)</ref> काउंटर मशीन डिज़ाइन के सीमित निर्देश सेट और प्रोग्राम आकार के बावजूद। हालाँकि, आवश्यक निर्माण प्रति-सहज ज्ञान युक्त हो सकता है, यहां तक कि उन कार्यों के लिए भी जिन्हें रैंडम-एक्सेस मशीन जैसी अधिक जटिल रजिस्टर मशीनों में परिभाषित करना अपेक्षाकृत आसान है। ऐसा इसलिए है क्योंकि μ ऑपरेटर असीमित संख्या में बार-बार पुनरावृति कर सकता है, लेकिन कोई भी काउंटर मशीन अपनी निर्देश सूची के सीमित आकार के कारण असीमित संख्या में अलग-अलग रजिस्टरों को संबोधित नहीं कर सकती है।
-उदाहरण के लिए, आदिम पुनरावर्ती ऑपरेटरों के उपरोक्त पदानुक्रम को नुथ के अप-एरो नोटेशन में उच्च-क्रम वाले तीर संचालन में घातांक से आगे बढ़ाया जा सकता है। किसी भी निश्चित के लिए <math>k</math>, कार्यक्रम <math>Q(x, y) = x \uparrow^k y</math> आदिम पुनरावर्ती है, और इसे सीधे तरीके से काउंटर मशीन के रूप में कार्यान्वित किया जा सकता है। लेकिन समारोह <math>R(n, x, y) = x \uparrow^n y</math> आदिम पुनरावर्ती नहीं है. किसी को अप-एरो ऑपरेटर को लागू करने का लालच हो सकता है <math>R</math> [[कॉल स्टैक]] को कार्यान्वित करके, उपरोक्त उत्तराधिकारी, जोड़, गुणन और घातांक निर्देशों के समान निर्माण का उपयोग करके, ताकि फ़ंक्शन को छोटे मानों पर पुनरावर्ती रूप से लागू किया जा सके <math>n</math>. यह विचार इस बात के समान है कि कोई व्यक्ति कई प्रोग्रामिंग भाषाओं में फ़ंक्शन को व्यवहार में कैसे लागू कर सकता है। हालाँकि, काउंटर मशीन अपनी गणना में असीमित संख्या में रजिस्टरों का उपयोग नहीं कर सकती है, जो कॉल स्टैक को लागू करने के लिए आवश्यक होगा जो मनमाने ढंग से बड़ा हो सकता है। अप-एरो ऑपरेशन को अभी भी एक काउंटर मशीन के रूप में कार्यान्वित किया जा सकता है क्योंकि यह पुनरावर्ती है, हालांकि फ़ंक्शन को सीमित संख्या में रजिस्टरों के अंदर असीमित मात्रा में जानकारी को एन्कोड करके कार्यान्वित किया जाएगा, जैसे गोडेल नंबरिंग का उपयोग करके।
+उदाहरण के लिए, आदिम पुनरावर्ती ऑपरेटरों के उपरोक्त पदानुक्रम को नुथ के अप-एरो नोटेशन में उच्च-क्रम वाले तीर संचालन में घातांक से आगे बढ़ाया जा सकता है। किसी भी निश्चित के लिए <math>k</math>, कार्यक्रम <math>Q(x, y) = x \uparrow^k y</math> आदिम पुनरावर्ती है, और इसे सीधे तरीके से काउंटर मशीन के रूप में कार्यान्वित किया जा सकता है। लेकिन समारोह <math>R(n, x, y) = x \uparrow^n y</math> आदिम पुनरावर्ती नहीं है. किसी को अप-एरो ऑपरेटर को लागू करने का लालच हो सकता है <math>R</math> [[कॉल स्टैक]] को कार्यान्वित करके, उपरोक्त उत्तराधिकारी, जोड़, गुणन और घातांक निर्देशों के समान निर्माण का उपयोग करके, ताकि फ़ंक्शन को छोटे मानों पर पुनरावर्ती रूप से लागू किया जा सके <math>n</math>. यह विचार इस बात के समान है कि कोई व्यक्ति कई प्रोग्रामिंग भाषाओं में फ़ंक्शन को व्यवहार में कैसे लागू कर सकता है। हालाँकि, काउंटर मशीन अपनी गणना में असीमित संख्या में रजिस्टरों का उपयोग नहीं कर सकती है, जो कॉल स्टैक को लागू करने के लिए आवश्यक होगा जो मनमाने ढंग से बड़ा हो सकता है। अप-एरो ऑपरेशन को अभी भी काउंटर मशीन के रूप में कार्यान्वित किया जा सकता है क्योंकि यह पुनरावर्ती है, हालांकि फ़ंक्शन को सीमित संख्या में रजिस्टरों के अंदर असीमित मात्रा में जानकारी को एन्कोड करके कार्यान्वित किया जाएगा, जैसे गोडेल नंबरिंग का उपयोग करके।
 == काउंटर मशीन मॉडल के साथ समस्याएं ==
@@ Line 913: / Line 913: @@
 (2) 'रजिस्टरों की असीमित संख्या बनाम राज्य-मशीन निर्देशों की बंधी हुई संख्या:' मशीन अपनी सीमित राज्य मशीन की पहुंच/क्षमता से परे पता-संख्या वाले रजिस्टरों तक कैसे पहुंच पाएगी?
-<!-- (1) '''No easy way to arrange for a stored program''': A stored program is required for a "Universal Register Machine" (URM) -- the counterpart of the [[Universal Turing Machine]]. The URM's program would reside in some registers while its input parameters and output parameters would reside in other registers.
-Melzak observes that, with regards to what he called his "Q-machine":
-:"there appears to be no easy way to arrange for a stored program. Further, although this is not necessarily bad, there is no separation between the storage and the arithmetic parts of the machine" (Melzak (1961) p. 293)
-An approach taken by Minsky (1961, 1967) was to put the program into a single register, the instructions and data encoded by [[Gödel numbering]] (see '''Two-counter machines are Turing powerful''', below). The resultant number (e.g. a huge unary string) would represent the product of all the instructions and data. To "fetch" an instruction, and then to "parse/decode" it into action, this one-tape machine needs the built-in ability to divide the monster number by primes and to test it for "no-remainder", then multiply it by the instruction's action code-number to cause the required action. When more tapes are available Minsky demonstrates that "INCREMENT" and "DECREMENT-with-test/jump" suffice. But all this occurs only at the expense of arcane coding that represents nothing similar to a "programmed computer".
-What Melzak proposed and is available in RAM and RASP models was the "indirect address"-- but at the expense of more "machine structure".
-:'''The CASE instruction: a primitive way to 'parse'. First parse: the instruction address:'''
-If indirect addressing were not available, how does a counter machine program "fetch" an instruction from the registers in order to "execute" it? First, the program sets aside a special register that it calls "the program counter" (PC). Suppose after a few instructions that hole #PC contains the number '''3'''. Although our machine knows it has ''an'' instruction's address/number in the PC, our machine does not know ''which'' address/number it is -- is it "7", "15", or "422"?. It must "parse" this number to find out. How? By decrementing PC's count until zero, then jumping to a tiny routine that copies the contents of hole #3 into the PC. This is called the CASE instruction and is shown to be [[primitive recursive]] by a proof of Kleene (1952) p.229.
-If the machine has a possible #47543 holes, then it must start counting down from #47543. This could take a while.
-:'''Second parse: the instruction''':
-After the first parse of the number of the next instruction's ''address'', the machine jumps to an instruction to "copy contents of hole #3 to register 'PR'". Since the contents of hole #3 is the instruction (its number, actually) the machine must now parse this ''instruction''.
-:'''Parsing issues''':
-We have seen how to solve the "fetch problem" by "parsing" twice to get a number from a register that represents an instruction. But note there is a bit of an issue. Because this is a ''Universal'' Counter Machine there is no "largest" program. For example, suppose the hole-contents-to-be-moved isn't found in hole #47543 but rather hole #218832673911. The machine must parse its way down from some ultimate "end" to the program, or by starting from instruction #1 and working its way up to this #218832673911st hole. But in general it doesn't know where this end is unless there's a special "mark" there telling the machine not to go any further. It is quite possible that the finite state machine will not be large enough to hold this really big number. Every program will be required to contain a number that defines its ultimate length, including all of its input and output and "scratch registers".
-(2) '''No indirect addressing:'''
-Thus we have arrived at the crucial deficiency. Nothing like this exists with, for example, the various tape- based [[Turing machine]] models; the position of the head is relative to the head, not absolute.
-How much easier it would be if our Universal Counter Machine were equipped with the following ability -- if it could tell the register it calls "the Program Counter" (PC) to use its contents to "point to" the register that at long last delivers up the instruction (i.e. ''contents'' of #1 points to #3 which contains "5", and this "five" represents the instruction "JE"):
-: [[1] ] → [3] =5 ="JE"
-Melzak used this modification to prove that his "Q-machine" is [[Turing equivalent]]. Melzak's attempted remedy results in the so-called RAM/RASP ( [[random-access machine]], [[Random-access stored program machine]] ) models, but his comment on page 293 seems to indicate that he was not totally happy with the result.-->
 (3) पूरी तरह से कम किए गए मॉडल बोझिल हैं:
@@ Line 955: / Line 925: @@
 ** निर्देश I पर बिना शर्त कूदें<sub>z</sub>
 ** यदि [r] =0 हो तो निर्देश I पर कूदें<sub>z</sub>
-मिन्स्की (1967) ने अपने 2-निर्देश सेट { INC (z), JZDEC (r, I) का विस्तार किया<sub>z</sub>) } से { CLR (r), INC (r), JZDEC (r, I<sub>z</sub>), जे (आई<sub>z</sub>) } उनके इस प्रमाण से पहले कि एक यूनिवर्सल प्रोग्राम मशीन केवल दो रजिस्टरों के साथ बनाई जा सकती है (पृष्ठ 255एफएफ)।
+मिन्स्की (1967) ने अपने 2-निर्देश सेट { INC (z), JZDEC (r, I) का विस्तार किया<sub>z</sub>) } से { CLR (r), INC (r), JZDEC (r, I<sub>z</sub>), जे (आई<sub>z</sub>) } उनके इस प्रमाण से पहले कि यूनिवर्सल प्रोग्राम मशीन केवल दो रजिस्टरों के साथ बनाई जा सकती है (पृष्ठ 255एफएफ)।
 ==दो-काउंटर मशीनें ट्यूरिंग समकक्ष हैं (चेतावनी के साथ)==
-प्रत्येक ट्यूरिंग मशीन के लिए, एक 2CM होता है जो इसे अनुकरण करता है, यह देखते हुए कि 2CM का इनपुट और आउटपुट ठीक से एन्कोड किया गया है। यह मिन्स्की की पुस्तक (कंप्यूटेशन, 1967, पृष्ठ 255-258) में साबित हुआ है, और एक वैकल्पिक प्रमाण नीचे तीन चरणों में दिया गया है। सबसे पहले, एक ट्यूरिंग मशीन को दो स्टैक से सुसज्जित एक परिमित-राज्य मशीन (एफएसएम) द्वारा अनुकरण किया जा सकता है। फिर, दो स्टैक को चार काउंटरों द्वारा अनुकरण किया जा सकता है। अंत में, चार काउंटरों को दो काउंटरों द्वारा अनुकरण किया जा सकता है।
+प्रत्येक ट्यूरिंग मशीन के लिए, 2CM होता है जो इसे अनुकरण करता है, यह देखते हुए कि 2CM का इनपुट और आउटपुट ठीक से एन्कोड किया गया है। यह मिन्स्की की पुस्तक (कंप्यूटेशन, 1967, पृष्ठ 255-258) में साबित हुआ है, और वैकल्पिक प्रमाण नीचे तीन चरणों में दिया गया है। सबसे पहले, ट्यूरिंग मशीन को दो स्टैक से सुसज्जित परिमित-राज्य मशीन (एफएसएम) द्वारा अनुकरण किया जा सकता है। फिर, दो स्टैक को चार काउंटरों द्वारा अनुकरण किया जा सकता है। अंत में, चार काउंटरों को दो काउंटरों द्वारा अनुकरण किया जा सकता है।
 दो काउंटर मशीनें निर्देश के सेट का उपयोग करती हैं { INC ( r, z ), JZDEC ( r, z<sub>true</sub>, साथ<sub>false</sub>) }.