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

From Vigyanwiki
(Created page with "{{Short description|Abstract machine used in a formal logic and theoretical computer science}} काउंटर मशीन एक अमूर्त मशीन ह...")
 
No edit summary
Line 1: Line 1:
{{Short description|Abstract machine used in a formal logic and theoretical computer science}}
{{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>फिर निर्देश पर जाएं अन्यथा क्रम से जारी रखें।
* जेई (आर<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))
* सेट 3: {आईएनसी (आर), सीपीवाई (आर)।<sub>j</sub>, आर<sub>k</sub>), जेई (आर<sub>j</sub>, आर<sub>k</sub>, z) }, (एल्गॉट-रॉबिन्सन (1964), मिन्स्की (1967))


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


== वैकल्पिक नाम, वैकल्पिक मॉडल ==
== वैकल्पिक नाम, वैकल्पिक मॉडल ==
Line 25: Line 25:
{{main|Counter-machine model}}
{{main|Counter-machine model}}


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


* शेफर्डसन-स्टर्गिस मशीन, क्योंकि इन लेखकों ने औपचारिक रूप से अपने मॉडल को आसानी से सुलभ प्रदर्शनी (1963) में बताया था। अतिरिक्त सुविधा निर्देशों के साथ संवर्धित अनुदेश सेट (1) का उपयोग करता है (जेएनजेड शून्य नहीं होने पर जंप है, जेजेड के स्थान पर उपयोग किया जाता है):
* शेफर्डसन-स्टर्गिस मशीन, क्योंकि इन लेखकों ने औपचारिक रूप से अपने मॉडल को आसानी से सुलभ प्रदर्शनी (1963) में बताया था। अतिरिक्त सुविधा निर्देशों के साथ संवर्धित अनुदेश सेट (1) का उपयोग करता है (जेएनजेड शून्य नहीं होने पर जंप है, जेजेड के स्थान पर उपयोग किया जाता है):
Line 31: Line 31:
* मिन्स्की मशीन, क्योंकि [[मार्विन मिंस्की]] (1961) ने मॉडल को औपचारिक रूप दिया। आमतौर पर निर्देश सेट (1) का उपयोग करता है, लेकिन निर्देश-निष्पादन डिफ़ॉल्ट-अनुक्रमिक नहीं है, इसलिए अतिरिक्त पैरामीटर 'z' INC के बाद अगले निर्देश को निर्दिष्ट करता है और JZDEC में विकल्प के रूप में दिखाई देता है:
* मिन्स्की मशीन, क्योंकि [[मार्विन मिंस्की]] (1961) ने मॉडल को औपचारिक रूप दिया। आमतौर पर निर्देश सेट (1) का उपयोग करता है, लेकिन निर्देश-निष्पादन डिफ़ॉल्ट-अनुक्रमिक नहीं है, इसलिए अतिरिक्त पैरामीटर 'z' INC के बाद अगले निर्देश को निर्दिष्ट करता है और JZDEC में विकल्प के रूप में दिखाई देता है:
*: { INC ( r, z ), JZDEC ( r, z<sub>true</sub>, साथ<sub>false</sub>) }
*: { 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> )}
*: { 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> ) }
*: { 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> ) }
*: { 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 ) }
*: {सीएलआर (आर), आईएनसी (आर), जेई (आर)।<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 ) }
*: { आईएनसी (आर), सीपीवाई (आर<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>, बिना शर्त कूदो, रुको }
:: {वृद्धि (आर), कमी (आर), स्पष्ट (आर); कॉपी (आर<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="54.6" Height="12" | Instruction
! width="163.2" | Effect on register "j"
! 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
! width="248.4" | Summary
|- style="font-size:9pt"
|- style="font-size:9pt"
Line 75: Line 75:
|- style="font-size:9pt"
|- style="font-size:9pt"
| Height="11.4" valign="bottom" | DEC ( j )
| 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" | [IC] +1 → IC
| align="center" valign="bottom" | Decrement contents of register j; next instruction
| 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
: [#2] →#3; [#2] →#1; 0 →#2


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


प्रोग्राम का एक रन नीचे दिखाया गया है। समय पृष्ठ के नीचे चला जाता है। निर्देश पीले रंग में हैं, रजिस्टर नीले रंग में हैं। प्रोग्राम को 90 डिग्री पर फ़्लिप किया गया है, शीर्ष पर निर्देश संख्या (पते), पतों के नीचे निर्देश निमोनिक्स, और निमोनिक्स के तहत निर्देश पैरामीटर (प्रति सेल एक):
प्रोग्राम का रन नीचे दिखाया गया है। समय पृष्ठ के नीचे चला जाता है। निर्देश पीले रंग में हैं, रजिस्टर नीले रंग में हैं। प्रोग्राम को 90 डिग्री पर फ़्लिप किया गया है, शीर्ष पर निर्देश संख्या (पते), पतों के नीचे निर्देश निमोनिक्स, और निमोनिक्स के तहत निर्देश पैरामीटर (प्रति सेल एक):
{|class="toccolours" style="font-size:88%;width:100%;text-align:center;"
{|class="toccolours" style="font-size:88%;width:100%;text-align:center;"
|- style="font-size:8pt"
|- 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 देखें)।
हालाँकि, हम देखते हैं कि ADD आसानी से संभव होता। और वास्तव में निम्नलिखित इस बात का सारांश है कि ADD, MULtiply और EXPonent जैसे [[आदिम पुनरावर्ती कार्य]] कैसे हो सकते हैं (बूलोस-बर्गेस-जेफरी (2002) पृष्ठ 45-51 देखें)।
Line 905: Line 905:
लेखक बताते हैं कि यह किसी भी उपलब्ध आधार सेट (1, 2, या 3) के भीतर आसानी से किया जाता है (एक उदाहरण μ ऑपरेटर पर पाया जा सकता है)। इसका मतलब यह है कि किसी भी म्यू रिकर्सिव फ़ंक्शन को काउंटर मशीन के रूप में कार्यान्वित किया जा सकता है,<ref>Boolos-Burgess-Jeffrey (2002)</ref> काउंटर मशीन डिज़ाइन के सीमित निर्देश सेट और प्रोग्राम आकार के बावजूद। हालाँकि, आवश्यक निर्माण प्रति-सहज ज्ञान युक्त हो सकता है, यहां तक ​​कि उन कार्यों के लिए भी जिन्हें रैंडम-एक्सेस मशीन जैसी अधिक जटिल रजिस्टर मशीनों में परिभाषित करना अपेक्षाकृत आसान है। ऐसा इसलिए है क्योंकि μ ऑपरेटर असीमित संख्या में बार-बार पुनरावृति कर सकता है, लेकिन कोई भी काउंटर मशीन अपनी निर्देश सूची के सीमित आकार के कारण असीमित संख्या में अलग-अलग रजिस्टरों को संबोधित नहीं कर सकती है।
लेखक बताते हैं कि यह किसी भी उपलब्ध आधार सेट (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) 'रजिस्टरों की असीमित संख्या बनाम राज्य-मशीन निर्देशों की बंधी हुई संख्या:' मशीन अपनी सीमित राज्य मशीन की पहुंच/क्षमता से परे पता-संख्या वाले रजिस्टरों तक कैसे पहुंच पाएगी?
(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) पूरी तरह से कम किए गए मॉडल बोझिल हैं:
(3) पूरी तरह से कम किए गए मॉडल बोझिल हैं:


Line 955: Line 925:
** निर्देश I पर बिना शर्त कूदें<sub>z</sub>
** निर्देश I पर बिना शर्त कूदें<sub>z</sub>
** यदि [r] =0 हो तो निर्देश 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>) }.
दो काउंटर मशीनें निर्देश के सेट का उपयोग करती हैं { INC ( r, z ), JZDEC ( r, z<sub>true</sub>, साथ<sub>false</sub>) }.


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


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


===चरण 3: चार काउंटरों को दो काउंटरों द्वारा अनुकरण किया जा सकता है।===
===चरण 3: चार काउंटरों को दो काउंटरों द्वारा अनुकरण किया जा सकता है।===
पहले की तरह, काउंटरों में से एक का उपयोग स्क्रैचपैड के रूप में किया जाता है। दूसरे में एक [[पूर्णांक]] है जिसका [[अभाज्य संख्या]] [[गुणन]]खंड 2 है<sup>ए</sup>3<sup>ख</sup>5<sup>सी</sup>7<sup>घ</sup>. घातांक ए, बी, सी और डी को चार आभासी काउंटरों के रूप में माना जा सकता है जिन्हें (गोडेल नंबरिंग के माध्यम से) एक ही वास्तविक काउंटर में पैक किया जा रहा है। यदि वास्तविक काउंटर को शून्य पर सेट किया जाता है और फिर एक बार बढ़ाया जाता है, तो यह सभी वर्चुअल काउंटरों को शून्य पर सेट करने के बराबर है। यदि वास्तविक काउंटर को दोगुना कर दिया जाता है, तो यह a को बढ़ाने के बराबर है, और यदि इसे आधा कर दिया जाता है, तो यह a को घटाने के बराबर है। एक समान प्रक्रिया द्वारा, इसे 3 से गुणा या विभाजित किया जा सकता है, जो बी को बढ़ाने या घटाने के बराबर है। इसी प्रकार, c और d को बढ़ाया या घटाया जा सकता है। यह जांचने के लिए कि क्या c जैसा वर्चुअल काउंटर शून्य के बराबर है, बस वास्तविक काउंटर को 5 से विभाजित करें, देखें कि शेष क्या है, फिर 5 से गुणा करें और शेष को वापस जोड़ें। इससे वास्तविक काउंटर अपरिवर्तित रहता है। यदि और केवल यदि c शून्य होता तो शेषफल शून्य नहीं होता।
पहले की तरह, काउंटरों में से का उपयोग स्क्रैचपैड के रूप में किया जाता है। दूसरे में [[पूर्णांक]] है जिसका [[अभाज्य संख्या]] [[गुणन]]खंड 2 है<sup>ए</sup>3<sup>ख</sup>5<sup>सी</sup>7<sup>घ</sup>. घातांक ए, बी, सी और डी को चार आभासी काउंटरों के रूप में माना जा सकता है जिन्हें (गोडेल नंबरिंग के माध्यम से) ही वास्तविक काउंटर में पैक किया जा रहा है। यदि वास्तविक काउंटर को शून्य पर सेट किया जाता है और फिर बार बढ़ाया जाता है, तो यह सभी वर्चुअल काउंटरों को शून्य पर सेट करने के बराबर है। यदि वास्तविक काउंटर को दोगुना कर दिया जाता है, तो यह a को बढ़ाने के बराबर है, और यदि इसे आधा कर दिया जाता है, तो यह a को घटाने के बराबर है। समान प्रक्रिया द्वारा, इसे 3 से गुणा या विभाजित किया जा सकता है, जो बी को बढ़ाने या घटाने के बराबर है। इसी प्रकार, c और d को बढ़ाया या घटाया जा सकता है। यह जांचने के लिए कि क्या c जैसा वर्चुअल काउंटर शून्य के बराबर है, बस वास्तविक काउंटर को 5 से विभाजित करें, देखें कि शेष क्या है, फिर 5 से गुणा करें और शेष को वापस जोड़ें। इससे वास्तविक काउंटर अपरिवर्तित रहता है। यदि और केवल यदि c शून्य होता तो शेषफल शून्य नहीं होता।


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


=== चेतावनी: *यदि* इसके काउंटरों को एन और 0 से प्रारंभ किया गया है, तो 2सीएम 2 की गणना नहीं कर सकता है<sup>एन</sup>===
=== चेतावनी: *यदि* इसके काउंटरों को एन और 0 से प्रारंभ किया गया है, तो 2सीएम 2 की गणना नहीं कर सकता है<sup>एन</sup>===


यह परिणाम, एन के अन्य कार्यों की एक सूची के साथ है जो दो-काउंटर मशीन द्वारा गणना योग्य नहीं हैं - जब एक काउंटर में एन और दूसरे में 0 के साथ आरंभ किया जाता है - जैसे कि एन<sup>2</sup>, sqrt(N), लॉग<sub>2</sub>(एन), आदि, श्रोएप्पेल (1972) के एक पेपर में दिखाई देते हैं। परिणाम आश्चर्यजनक नहीं है, क्योंकि दो-काउंटर मशीन मॉडल (मिन्स्की द्वारा) केवल तभी सार्वभौमिक साबित हुआ था जब तर्क एन को एक ट्यूरिंग मशीन का अनुकरण करने के लिए उचित रूप से एन्कोड किया गया था (गोडेलाइज़ेशन द्वारा) जिसके प्रारंभिक टेप में एन यूनरी में एनकोडेड था; इसके अलावा, दो-काउंटर मशीन का आउटपुट समान रूप से एन्कोड किया जाएगा। यह घटना गणना के बहुत छोटे आधारों के लिए विशिष्ट है जिनकी सार्वभौमिकता केवल अनुकरण द्वारा सिद्ध होती है (उदाहरण के लिए, कई [[ट्यूरिंग टारपिट]], सबसे छोटी ज्ञात सार्वभौमिक ट्यूरिंग मशीनें, आदि)।
यह परिणाम, एन के अन्य कार्यों की सूची के साथ है जो दो-काउंटर मशीन द्वारा गणना योग्य नहीं हैं - जब काउंटर में एन और दूसरे में 0 के साथ आरंभ किया जाता है - जैसे कि एन<sup>2</sup>, sqrt(N), लॉग<sub>2</sub>(एन), आदि, श्रोएप्पेल (1972) के पेपर में दिखाई देते हैं। परिणाम आश्चर्यजनक नहीं है, क्योंकि दो-काउंटर मशीन मॉडल (मिन्स्की द्वारा) केवल तभी सार्वभौमिक साबित हुआ था जब तर्क एन को ट्यूरिंग मशीन का अनुकरण करने के लिए उचित रूप से एन्कोड किया गया था (गोडेलाइज़ेशन द्वारा) जिसके प्रारंभिक टेप में एन यूनरी में एनकोडेड था; इसके अलावा, दो-काउंटर मशीन का आउटपुट समान रूप से एन्कोड किया जाएगा। यह घटना गणना के बहुत छोटे आधारों के लिए विशिष्ट है जिनकी सार्वभौमिकता केवल अनुकरण द्वारा सिद्ध होती है (उदाहरण के लिए, कई [[ट्यूरिंग टारपिट]], सबसे छोटी ज्ञात सार्वभौमिक ट्यूरिंग मशीनें, आदि)।


प्रमाण से पहले कुछ दिलचस्प प्रमेय दिए गए हैं:
प्रमाण से पहले कुछ दिलचस्प प्रमेय दिए गए हैं:


* प्रमेय: एक तीन-काउंटर मशीन एक ट्यूरिंग मशीन का अनुकरण कर सकती है (पृष्ठ 2, सीएफ मिन्स्की 1967:170-174 भी)
* प्रमेय: तीन-काउंटर मशीन ट्यूरिंग मशीन का अनुकरण कर सकती है (पृष्ठ 2, सीएफ मिन्स्की 1967:170-174 भी)
* प्रमेय: एक 3CM [तीन-काउंटर मशीन] एक चर के किसी भी आंशिक पुनरावर्ती फ़ंक्शन की गणना कर सकती है। यह तर्क से शुरू होता है [अर्थात्। एन] एक काउंटर में, और (यदि यह रुकता है) उत्तर छोड़ देता है [यानी। एफ(एन)] एक काउंटर में। (पृ. 3)
* प्रमेय: 3CM [तीन-काउंटर मशीन] चर के किसी भी आंशिक पुनरावर्ती फ़ंक्शन की गणना कर सकती है। यह तर्क से शुरू होता है [अर्थात्। एन] काउंटर में, और (यदि यह रुकता है) उत्तर छोड़ देता है [यानी। एफ(एन)] काउंटर में। (पृ. 3)
* प्रमेय: एक काउंटर मशीन को 2CM [दो-काउंटर मशीन] द्वारा सिम्युलेटेड किया जा सकता है, बशर्ते इनपुट और आउटपुट के लिए एक अस्पष्ट कोडिंग स्वीकार की जाए [पी। 3; अस्पष्ट कोडिंग है: 2<sup>डब्ल्यू</sup>3<sup>एक्स</sup>5<sup>तथा</sup>7<sup>Z</sup> जहां सिम्युलेटेड काउंटर W, X, Y, Z हैं]
* प्रमेय: काउंटर मशीन को 2CM [दो-काउंटर मशीन] द्वारा सिम्युलेटेड किया जा सकता है, बशर्ते इनपुट और आउटपुट के लिए अस्पष्ट कोडिंग स्वीकार की जाए [पी। 3; अस्पष्ट कोडिंग है: 2<sup>डब्ल्यू</sup>3<sup>एक्स</sup>5<sup>तथा</sup>7<sup>Z</sup> जहां सिम्युलेटेड काउंटर W, X, Y, Z हैं]
* प्रमेय: किसी भी काउंटर मशीन को 2CM द्वारा सिम्युलेटेड किया जा सकता है, बशर्ते इनपुट और आउटपुट के लिए अस्पष्ट कोडिंग स्वीकार की जाए। (पृ. 3)
* प्रमेय: किसी भी काउंटर मशीन को 2CM द्वारा सिम्युलेटेड किया जा सकता है, बशर्ते इनपुट और आउटपुट के लिए अस्पष्ट कोडिंग स्वीकार की जाए। (पृ. 3)
** परिणाम: 2CM के लिए [[रुकने की समस्या]] हल नहीं हो सकी है।
** परिणाम: 2CM के लिए [[रुकने की समस्या]] हल नहीं हो सकी है।
** परिणाम: 2CM एक तर्क के किसी भी आंशिक पुनरावर्ती फ़ंक्शन की गणना कर सकता है, बशर्ते इनपुट को 2 के रूप में कोडित किया गया हो<sup>N</sup> और आउटपुट (यदि मशीन रुकती है) को 2 के रूप में कोडित किया गया है<sup>उत्तर</sup>. (पृ. 3)
** परिणाम: 2CM तर्क के किसी भी आंशिक पुनरावर्ती फ़ंक्शन की गणना कर सकता है, बशर्ते इनपुट को 2 के रूप में कोडित किया गया हो<sup>N</sup> और आउटपुट (यदि मशीन रुकती है) को 2 के रूप में कोडित किया गया है<sup>उत्तर</sup>. (पृ. 3)
* प्रमेय: कोई भी दो काउंटर मशीन नहीं है जो 2 की गणना करती हो<sup>एन</sup> [यदि एक काउंटर को एन से प्रारंभ किया गया है]। (पृ. 11)
* प्रमेय: कोई भी दो काउंटर मशीन नहीं है जो 2 की गणना करती हो<sup>एन</sup> [यदि काउंटर को एन से प्रारंभ किया गया है]। (पृ. 11)


दूसरे प्रमेय के संबंध में कि A 3CM किसी भी आंशिक पुनरावर्ती फ़ंक्शन की गणना कर सकता है, लेखक पाठक को एक कठिन समस्या के साथ चुनौती देता है: केवल तीन काउंटरों का उपयोग करके दो संख्याओं को गुणा करें (पृष्ठ 2)। मुख्य प्रमाण में यह धारणा शामिल है कि दो-काउंटर मशीनें गैर-रेखीय विकास दर (पृष्ठ 15) यानी फ़ंक्शन 2 के साथ अंकगणितीय अनुक्रमों की गणना नहीं कर सकती हैं<sup>X</sup>किसी भी अंकगणितीय प्रगति की तुलना में अधिक तेज़ी से बढ़ता है। (पृ. 11).
दूसरे प्रमेय के संबंध में कि A 3CM किसी भी आंशिक पुनरावर्ती फ़ंक्शन की गणना कर सकता है, लेखक पाठक को कठिन समस्या के साथ चुनौती देता है: केवल तीन काउंटरों का उपयोग करके दो संख्याओं को गुणा करें (पृष्ठ 2)। मुख्य प्रमाण में यह धारणा शामिल है कि दो-काउंटर मशीनें गैर-रेखीय विकास दर (पृष्ठ 15) यानी फ़ंक्शन 2 के साथ अंकगणितीय अनुक्रमों की गणना नहीं कर सकती हैं<sup>X</sup>किसी भी अंकगणितीय प्रगति की तुलना में अधिक तेज़ी से बढ़ता है। (पृ. 11).


==गिनती द्वारा गणना का एक व्यावहारिक उदाहरण==
==गिनती द्वारा गणना का व्यावहारिक उदाहरण==


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


जोड़ना एक अप-काउंटर द्वारा किया गया था, जबकि घटाव एक डाउन-काउंटर द्वारा किया गया था, उधार से निपटने के लिए एक समान योजना के साथ।
जोड़ना अप-काउंटर द्वारा किया गया था, जबकि घटाव डाउन-काउंटर द्वारा किया गया था, उधार से निपटने के लिए समान योजना के साथ।


टाइम स्लॉट योजना ने 13 दशमलव अंकों के छह रजिस्टरों को परिभाषित किया, जिनमें से प्रत्येक में एक साइन बिट था।
टाइम स्लॉट योजना ने 13 दशमलव अंकों के छह रजिस्टरों को परिभाषित किया, जिनमें से प्रत्येक में साइन बिट था।
गुणा और भाग मूल रूप से बार-बार जोड़ और घटाव द्वारा किया जाता था। वर्गमूल संस्करण, EC-132, लगातार विषम पूर्णांकों को प्रभावी ढंग से घटाता है, प्रत्येक वृद्धि के लिए लगातार दो घटाव की आवश्यकता होती है। पहले के बाद, दूसरे घटाव से पहले न्यूनतम में एक की वृद्धि की गई थी।
गुणा और भाग मूल रूप से बार-बार जोड़ और घटाव द्वारा किया जाता था। वर्गमूल संस्करण, EC-132, लगातार विषम पूर्णांकों को प्रभावी ढंग से घटाता है, प्रत्येक वृद्धि के लिए लगातार दो घटाव की आवश्यकता होती है। पहले के बाद, दूसरे घटाव से पहले न्यूनतम में की वृद्धि की गई थी।


==यह भी देखें==
==यह भी देखें==
Line 1,008: Line 978:
{{reflist}}
{{reflist}}
* [[George Boolos]], [[John P. Burgess]], [[Richard Jeffrey]] (2002), ''Computability and Logic: Fourth Edition'', Cambridge University Press, Cambridge, England. The original Boolos-Jeffrey text has been extensively revised by Burgess: more advanced than an introductory textbook. "Abacus machine" model is extensively developed in Chapter 5 ''Abacus Computability''; it is one of three models extensively treated and compared—the Turing machine (still in Boolos' original 4-tuple form) and recursion the other two.
* [[George Boolos]], [[John P. Burgess]], [[Richard Jeffrey]] (2002), ''Computability and Logic: Fourth Edition'', Cambridge University Press, Cambridge, England. The original Boolos-Jeffrey text has been extensively revised by Burgess: more advanced than an introductory textbook. "Abacus machine" model is extensively developed in Chapter 5 ''Abacus Computability''; it is one of three models extensively treated and compared—the Turing machine (still in Boolos' original 4-tuple form) and recursion the other two.
* [[Arthur Burks]], [[Herman Goldstine]], [[John von Neumann]] (1946), ''Preliminary discussion of the logical design of an electronic computing instrument'', reprinted pp.&nbsp;92ff in [[Gordon Bell]] and [[Allen Newell]] (1971), ''Computer Structures: Readings and Examples'', mcGraw-Hill Book Company, New York. {{ISBN|0-07-004357-4}} .
* [[Arthur Burks]], [[Herman Goldstine]], [[John von Neumann]] (1946), ''Preliminary discussion of the logical design of an electronic computing instrument'', reprinted pp.&nbsp;92ff in [[Gordon Bell]] and [[Allen Newell]] (1971), ''Computer Structures: Readings and Examples'', mcGraw-Hill Book Company, New York. {{ISBN|0-07-004357-4}} .
* [[Stephen Cook|Stephen A. Cook]] and Robert A. Reckhow (1972), ''Time-bounded random access machines'', Journal of Computer Systems Science 7 (1973), 354–375.
* [[Stephen Cook|Stephen A. Cook]] and Robert A. Reckhow (1972), ''Time-bounded random access machines'', Journal of Computer Systems Science 7 (1973), 354–375.
* [[Martin Davis (mathematician)|Martin Davis]] (1958), ''Computability & Unsolvability'', McGraw-Hill Book Company, Inc. New York.
* [[Martin Davis (mathematician)|Martin Davis]] (1958), ''Computability & Unsolvability'', McGraw-Hill Book Company, Inc. New York.

Revision as of 12:40, 2 August 2023

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

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

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

  • सीएलआर (आर): क्लियर रजिस्टर आर। (आर को शून्य पर सेट करें।)
  • आईएनसी (आर): रजिस्टर आर की सामग्री को बढ़ाएं।
  • डीईसी (आर): रजिस्टर आर की सामग्री को घटाएं।
  • सीपीवाई (आरj, आरk): रजिस्टर आर की सामग्री को कॉपी करेंjआर पंजीकृत करने के लिएkआर की सामग्री को छोड़करjअखंड।
  • जेजेड (आर, जेड): यदि रजिस्टर आर में शून्य है तो निर्देश जेड पर जाएं अन्यथा क्रम में जारी रखें।
  • जेई (आरj, आरk, z): यदि रजिस्टर आर की सामग्रीjरजिस्टर आर की सामग्री के बराबर हैkफिर निर्देश पर जाएं अन्यथा क्रम से जारी रखें।

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

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

  • सेट 1: { आईएनसी (आर), डीईसी (आर), जेजेड (आर, जेड) }, (मिन्स्की (1961, 1967), लैम्बेक (1961))
  • सेट 2: { सीएलआर (आर), आईएनसी (आर), जेई (आर)।j, आरk, z) }, (एर्शोव (1958), पीटर (1958) जैसा कि शेफर्डसन-स्टर्गिस (1964); मिन्स्की (1967); शॉनहेज (1980) द्वारा व्याख्या की गई है)
  • सेट 3: {आईएनसी (आर), सीपीवाई (आर)।j, आरk), जेई (आरj, आरk, z) }, (एल्गॉट-रॉबिन्सन (1964), मिन्स्की (1967))

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

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

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

  • शेफर्डसन-स्टर्गिस मशीन, क्योंकि इन लेखकों ने औपचारिक रूप से अपने मॉडल को आसानी से सुलभ प्रदर्शनी (1963) में बताया था। अतिरिक्त सुविधा निर्देशों के साथ संवर्धित अनुदेश सेट (1) का उपयोग करता है (जेएनजेड शून्य नहीं होने पर जंप है, जेजेड के स्थान पर उपयोग किया जाता है):
    {आईएनसी (आर), डीईसी (आर), सीएलआर (आर), सीपीवाई (आर)।j, आरk ), जेएनजेड (आर, जेड), जे (जेड)}
  • मिन्स्की मशीन, क्योंकि मार्विन मिंस्की (1961) ने मॉडल को औपचारिक रूप दिया। आमतौर पर निर्देश सेट (1) का उपयोग करता है, लेकिन निर्देश-निष्पादन डिफ़ॉल्ट-अनुक्रमिक नहीं है, इसलिए अतिरिक्त पैरामीटर 'z' INC के बाद अगले निर्देश को निर्दिष्ट करता है और JZDEC में विकल्प के रूप में दिखाई देता है:
    { INC ( r, z ), JZDEC ( r, ztrue, साथfalse) }
  • प्रोग्राम मशीन, प्रोग्राम कंप्यूटर, नाम मिन्स्की (1967) ने मॉडल को दिया क्योंकि, कंप्यूटर की तरह इसके निर्देश क्रमिक रूप से आगे बढ़ते हैं जब तक कि सशर्त छलांग सफल नहीं होती। (आमतौर पर) निर्देश सेट (1) का उपयोग करता है लेकिन इसे शेफर्सन-स्टर्गिस मॉडल के समान संवर्धित किया जा सकता है। JZDEC को अक्सर अलग कर दिया जाता है:
    { INC ( r ), DEC ( r ), JZ ( r, ztrue )}
  • अबेकस मशीन, नाम लैम्बेक (1961) ने मेल्ज़ाक (1961) मॉडल के सरलीकरण के लिए दिया था, और बूलोस-बर्गेस-जेफरी (2002) इसे क्या कहते हैं। मिन्स्की (1961) मॉडल के तरीके से अगले निर्देश को निर्दिष्ट करने के लिए निर्देश सेट (1) का उपयोग करता है लेकिन अतिरिक्त पैरामीटर z के साथ;
    { INC ( r, z ), JZDEC (r, ztrue, साथfalse ) }
  • लैम्बेक मशीन, वैकल्पिक नाम बूलोस-बर्गेस-जेफरी (2002) ने अबेकस मशीन को दिया। अगले निर्देश को निर्दिष्ट करने के लिए अतिरिक्त पैरामीटर के साथ निर्देश सेट (1-कम) का उपयोग करता है:
    { INC ( r, z ), JZDEC ( r, ztrue, साथfalse ) }
  • उत्तराधिकारी मशीन, क्योंकि यह 'उत्तराधिकारी ऑपरेशन' का उपयोग करती है, और पीनो स्वयंसिद्धों से काफी मिलती-जुलती है। उत्तराधिकारी रैम मॉडल के लिए आधार के रूप में उपयोग किया जाता है। उदाहरण के लिए निर्देश सेट (2) का उपयोग करता है। शॉनहेज को उनके RAM0 और RAM1 मॉडल के आधार के रूप में, जो उनके सूचक मशीन SMM मॉडल की ओर ले जाता है, वैन एम्डे बोस (1990) में भी संक्षेप में चर्चा की गई है:
    {सीएलआर (आर), आईएनसी (आर), जेई (आर)।j, आरk, z ) }
  • एल्गॉट-रॉबिन्सन मॉडल, उनके आरएएसपी मॉडल (1964) को परिभाषित करने के लिए उपयोग किया जाता है। इस मॉडल को प्रारंभ में खाली रजिस्टर की आवश्यकता होती है (उदाहरण के लिए [r0] =0)। (उन्होंने इंडेक्स रजिस्टर के रूप में उपयोग करने के लिए अतिरिक्त रजिस्टर का उपयोग करके अप्रत्यक्ष संबोधन के साथ उसी मॉडल को संवर्धित किया।)
    { आईएनसी (आर), सीपीवाई (आरs, आरd ), जेई (आरj, आरk, z ) }
  • अन्य काउंटर मशीनें: मिन्स्की (1967) दर्शाता है कि इस आलेख के मुख्य पैराग्राफ में वर्णित उपलब्ध निर्देशों के सुपरसेट से तीन बेस मॉडल (प्रोग्राम/मिन्स्की/लैम्बेक-अबेकस, उत्तराधिकारी, और एल्गॉट-रॉबिन्सन) कैसे बनाया जाए। मेल्ज़ाक (1961) मॉडल उपरोक्त से काफी अलग है क्योंकि इसमें 'वृद्धि' और 'घटाना' के बजाय 'जोड़' और 'घटाना' शामिल है। मिन्स्की (1961, 1967) के प्रमाण कि ट्यूरिंग समतुल्यता के लिए एकल रजिस्टर पर्याप्त होगा, गणना का प्रतिनिधित्व करने वाले रजिस्टर में गोडेल संख्या को एन्कोड और डीकोड करने के लिए दो निर्देशों {मल्टीप्लाई के, और डीआईवी के} की आवश्यकता होती है। मिन्स्की दर्शाता है कि यदि दो या दो से अधिक रजिस्टर उपलब्ध हैं तो सरल INC, DEC आदि पर्याप्त हैं (लेकिन ट्यूरिंग पूर्णता प्रदर्शित करने के लिए गोडेल संख्या अभी भी आवश्यक है; एल्गॉट-रॉबिन्सन 1964 में भी प्रदर्शित किया गया है)।

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

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

  1. लेबल रहित पूर्णांक-मूल्यवान रजिस्टर: रजिस्टरों का सीमित (या कुछ मॉडलों में अनंत) सेट आर0... आरn जिनमें से प्रत्येक किसी गैर-नकारात्मक पूर्णांक (0, 1, 2, ... - यानी असीमित) को धारण कर सकता है। रजिस्टर अपना अंकगणित स्वयं करते हैं; या अधिक विशेष रजिस्टर हो भी सकते हैं और नहीं भी, जैसे संचायक (इस पर अधिक जानकारी के लिए रैंडम-एक्सेस मशीन देखें)।
  2. एक राज्य रजिस्टर जो निष्पादित किए जाने वाले वर्तमान निर्देश को संग्रहीत/पहचानता है। यह रजिस्टर परिमित है और उपरोक्त रजिस्टरों से अलग है; इस प्रकार काउंटर मशीन मॉडल हार्वर्ड वास्तुकला का उदाहरण है
  3. लेबल किए गए, अनुक्रमिक निर्देशों की सूची: निर्देशों की सीमित सूची I0... मैंm. प्रोग्राम स्टोर (परिमित राज्य मशीन के निर्देश) रजिस्टरों के समान भौतिक स्थान पर नहीं है। आमतौर पर, लेकिन हमेशा नहीं, कंप्यूटर प्रोग्राम की तरह निर्देश अनुक्रमिक क्रम में सूचीबद्ध होते हैं; जब तक कोई छलांग सफल नहीं होती, डिफ़ॉल्ट अनुक्रम संख्यात्मक क्रम में जारी रहता है। सूची में प्रत्येक निर्देश (बहुत) छोटे सेट से है, लेकिन इस सेट में अप्रत्यक्ष शामिल नहीं है। ऐतिहासिक रूप से अधिकांश मॉडलों ने इस सेट से अपने निर्देश प्राप्त किए:
{वृद्धि (आर), कमी (आर), स्पष्ट (आर); कॉपी (आरj,आरk), यदि r=0 की सामग्री है तो सशर्त छलांग, यदि r की सामग्री है तो सशर्त छलांगj=आरk, बिना शर्त कूदो, रुको }
कुछ मॉडलों ने या तो उपरोक्त में से कुछ को बिना-पैरामीटर निर्देशों में परमाणुकृत कर दिया है, या उन्हें ही निर्देश में जोड़ दिया है जैसे कि सशर्त कूद-अगर-शून्य जेजेड (आर, जेड) से पहले डिक्रीमेंट। निर्देशों के परमाणुकरण या सुविधाजनक निर्देशों को शामिल करने से वैचारिक शक्ति में कोई बदलाव नहीं होता है, क्योंकि संस्करण में किसी भी कार्यक्रम को सीधे दूसरे में अनुवादित किया जा सकता है।
पूरक रजिस्टर-मशीन मॉडल में वैकल्पिक निर्देश-सेट पर चर्चा की गई है।

== उदाहरण: रजिस्टर #2 से #3 == तक गिनती कॉपी करें यह उदाहरण दिखाता है कि तीन और उपयोगी निर्देश कैसे बनाएं: स्पष्ट, बिना शर्त जंप और कॉपी।

  • सीएलआर (जे): रजिस्टर आर की सामग्री साफ़ करेंjशून्य करने के लिए.
  • जे (जेड): बिना शर्त निर्देश I पर जाएंz.
  • सीपीवाई (एस, डी): स्रोत रजिस्टर आर की सामग्री की प्रतिलिपि बनाएँsगंतव्य रजिस्टर आर के लिएd. (वन-इंस्ट्रक्शन सेट कंप्यूटर#ट्रांसपोर्ट ट्रिगर आर्किटेक्चर देखें)

बाद में आरsइसमें इसकी मूल गणना शामिल होगी (MOVE के विपरीत जो स्रोत रजिस्टर को खाली कर देता है, यानी इसे शून्य पर साफ़ कर देता है)।

मूल सेट (1) का उपयोग यहां परिभाषित अनुसार किया गया है:

Instruction Effect on register "j" Effect on Instruction Counter Register ICR Summary
INC ( j ) [j] +1 → j [IC] +1 → IC Increment contents of register j; next instruction
DEC ( j ) [j] -1 → j [IC] +1 → IC Decrement contents of register j; next instruction
JZ ( j, z) IF [j] = 0 THEN Iz → IC ELSE [IC] +1 → IC If contents of register j=0 then instruction z else next instruction
HALT


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

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

अंतिम शर्तें

प्रोग्राम रजिस्टर #2 की सामग्री को उसकी मूल गिनती पर और रजिस्टर #3 की सामग्री को रजिस्टर #2 की मूल सामग्री के बराबर रोक देता है, यानी,

[2] = [3]।

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

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

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

दूसरे भाग में प्रोग्राम स्क्रैच-पैड #1 की सामग्री को वापस #2 पर ले जाता है (लौटाता है, पुनर्स्थापित करता है), इस प्रक्रिया में स्क्रैच-पैड #1 को साफ़ करता है:

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

कार्यक्रम

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

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

1 2 3 4 5 6 7 8 9 10 ← Instruction number (address)
JZ DEC INC INC JZ JZ DEC INC JZ H ← Instruction
2 2 3 1 0 1 1 2 0 ← Register number
6 1 10 6 ← Jump-to instruction number
step IC Inst # reg # J-addr reg0 reg1 reg2 reg3 reg4 IC
start 0 0 2 0 0 1 move [#2] to #1 and #3:
1 1 JZ 2 6 0 0 2 0 0 1→2 JZ Jump fails: register #2 contains 2
2 2 DEC 2 0 0 0 2→1 0 0 2→3 DEC Decrement register #2 from 2 to 1
3 3 INC 3 0 0 0 1 0→1 0 3→4 INC Increment register #3 from 0 to 1
4 4 INC 1 0 0 0→1 1 1 0 4→5 INC Increment register #1 from 0 to 1
5 5 JZ 0 1 0 1 1 1 0 5→1 JZ U-Jump: register #0 is empty
6 1 JZ 2 6 0 1 1 1 0 1→2 JZ Jump fails: register #2 contains 1
7 2 DEC 2 0 0 1 1→0 1 0 2→3 DEC Decrement register #2 from 1 to 0
8 3 INC 3 0 0 1 0 1→2 0 3→4 INC Increment register #3 from 1 to 2
9 4 INC 1 0 0 1→2 0 2 0 4→5 INC Increment register #1 from 1 to 2
10 5 JZ 0 1 0 2 0 2 0 5→1 JZ U-Jump: register #0 is empty
11 1 JZ 2 6 0 2 0 2 0 1→6 JZ Jump !: register #2 is empty
move [1] to 2:
12 6 JZ 1 10 0 2 0 2 0 6→7 JZ Jump fails: register #1 contains 2
13 7 DEC 1 0 0 2→1 0 2 0 7→8 DEC Decrement register #1 from 2 to 1
14 8 INC 2 0 0 1 0→1 2 0 8→9 INC Increment register #2 from 0 to 1
15 9 JZ 0 6 0 1 1 2 0 9→6 JZ U-Jump: register #0 is empty
16 6 JZ 1 10 0 1 1 2 0 6→7 JZ Jump fails: register #1 contains 1
17 7 DEC 1 0 0 1→0 1 2 0 7→8 DEC Decrement register #1 from 1 to 0
18 8 INC 2 0 0 0 1→2 2 0 8→9 INC Increment register #2 from 1 to 2
19 9 JZ 0 6 0 0 2 2 0 9→6 JZ U-Jump: register #0 is empty
20 6 JZ 1 10 0 0 2 2 0 6→10 JZ Jump !: register #1 is empty
21 10 H 0 0 0 0 2 2 0 10→10 H HALT


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

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

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

  • आरंभिक निर्देश सेट: {DEC, INC, JZ, H }
  • बिना शर्त जंप J (z) को JZ (r0, z) के संदर्भ में परिभाषित करें, यह देखते हुए कि r0 में 0 है।
{जे, दिसंबर, इंक, जेजेड, एच }
  • उपरोक्त के संदर्भ में CLeaR (r) को परिभाषित करें:
{सीएलआर, जे, डीईसी, आईएनसी, जेजेड, एच }
  • सीओपीवाई को परिभाषित करें (आरj, आरk ) आर की सामग्री को संरक्षित करते समयj उपरोक्त के संदर्भ में:
{ सीपीवाई, सीएलआर, जे, डीईसी, आईएनसी, जेजेड, एच }
उपरोक्त शेफर्डसन-स्टर्गिस (1963) का निर्देश सेट है।
  • ADD को परिभाषित करें (rj, आरk, आरi ) , (शायद आर की सामग्री को संरक्षित करनाj, और आरk ), उपरोक्त के उपयोग से:
{जोड़ें, सीपीवाई, सीएलआर, जे, डीईसी, आईएनसी, जेजेड, एच }
  • मल्टीप्लाई को परिभाषित करें (आरj, आरk, आरi ) (एमयूएल) (शायद आर की सामग्री को संरक्षित करनाj, आरk), उपरोक्त के संदर्भ में:
{एमयूएल, एडीडी, सीपीवाई, सीएलआर, जे, डीईसी, आईएनसी, जेजेड, एच }
  • घातांक को परिभाषित करें (rj, आरk, आरi ) (EXP) (शायद आर की सामग्री को संरक्षित करनाj, आरk ) उपरोक्त के संदर्भ में,
{ EXP, MUL, ADD, CPY, CLR, J, DEC, INC, JZ, H }

सामान्य तौर पर, हम समान विधियों का उपयोग करके, अपनी इच्छानुसार कोई भी आंशिक- या कुल-आदिम पुनरावर्ती फ़ंक्शन बना सकते हैं। दरअसल, मिन्स्की (1967), शेफर्डसन-स्टर्गिस (1963) और बूलोस-बर्गेस-जेफरी (2002) बेस सेट (1) से पांच आदिम पुनरावर्ती फ़ंक्शन ऑपरेटरों (नीचे 1-5) को बनाने का प्रदर्शन देते हैं।

लेकिन पूर्ण ट्यूरिंग मशीन समकक्षों के बारे में क्या? हमें पूर्ण तुल्यता प्राप्त करने के लिए छठे ऑपरेटर- μ ऑपरेटर को जोड़ने की आवश्यकता है, जो कुल- और आंशिक- रिकर्सन (कंप्यूटर विज्ञान) बनाने में सक्षम है:

  1. शून्य फ़ंक्शन (या स्थिर फ़ंक्शन)
  2. उत्तराधिकारी कार्य
  3. पहचान समारोह
  4. रचना समारोह
  5. आदिम पुनरावर्तन (प्रेरण)
  6. μ ऑपरेटर (अनबाउंड सर्च ऑपरेटर)

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

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

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

रैंडम-एक्सेस मशीन लेख में समस्याओं पर विस्तार से चर्चा की गई है। समस्याएँ दो प्रमुख वर्गों और तीसरे असुविधा वर्ग में आती हैं:

(1) 'रजिस्टरों की असीमित क्षमताएं बनाम राज्य-मशीन निर्देशों की बंधी हुई क्षमताएं:' मशीन अपनी परिमित राज्य मशीन की क्षमता से बड़े स्थिरांक कैसे बनाएगी?

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

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

शेफर्डसन और स्टर्गिस (1963) अपने 6-निर्देश सेट के बारे में क्षमाप्रार्थी नहीं हैं। उन्होंने अपनी पसंद प्रोग्रामिंग में आसानी के आधार पर बनाई है... न कि मितव्ययता के आधार पर (पृ. 219 फुटनोट 1)।

शेफर्डसन और स्टर्गिस के निर्देश ([आर] रजिस्टर आर की सामग्री को इंगित करता है):

    • वेतन वृद्धि (आर); [आर] +1 → आर
    • कमी (आर) ; [आर] -1 → आर
    • साफ़ (आर) ; 0 → आर
    • कॉपी (आरs आर कोd ) ; [आरs] → आरd
    • निर्देश I पर बिना शर्त कूदेंz
    • यदि [r] =0 हो तो निर्देश I पर कूदेंz

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

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

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

चरण 1: ट्यूरिंग मशीन को दो स्टैक द्वारा अनुकरण किया जा सकता है।

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

चरण 2: स्टैक को दो काउंटरों द्वारा अनुकरण किया जा सकता है।

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

चरण 3: चार काउंटरों को दो काउंटरों द्वारा अनुकरण किया जा सकता है।

पहले की तरह, काउंटरों में से का उपयोग स्क्रैचपैड के रूप में किया जाता है। दूसरे में पूर्णांक है जिसका अभाज्य संख्या गुणनखंड 2 है35सी7. घातांक ए, बी, सी और डी को चार आभासी काउंटरों के रूप में माना जा सकता है जिन्हें (गोडेल नंबरिंग के माध्यम से) ही वास्तविक काउंटर में पैक किया जा रहा है। यदि वास्तविक काउंटर को शून्य पर सेट किया जाता है और फिर बार बढ़ाया जाता है, तो यह सभी वर्चुअल काउंटरों को शून्य पर सेट करने के बराबर है। यदि वास्तविक काउंटर को दोगुना कर दिया जाता है, तो यह a को बढ़ाने के बराबर है, और यदि इसे आधा कर दिया जाता है, तो यह a को घटाने के बराबर है। समान प्रक्रिया द्वारा, इसे 3 से गुणा या विभाजित किया जा सकता है, जो बी को बढ़ाने या घटाने के बराबर है। इसी प्रकार, c और d को बढ़ाया या घटाया जा सकता है। यह जांचने के लिए कि क्या c जैसा वर्चुअल काउंटर शून्य के बराबर है, बस वास्तविक काउंटर को 5 से विभाजित करें, देखें कि शेष क्या है, फिर 5 से गुणा करें और शेष को वापस जोड़ें। इससे वास्तविक काउंटर अपरिवर्तित रहता है। यदि और केवल यदि c शून्य होता तो शेषफल शून्य नहीं होता।

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

चेतावनी: *यदि* इसके काउंटरों को एन और 0 से प्रारंभ किया गया है, तो 2सीएम 2 की गणना नहीं कर सकता हैएन

यह परिणाम, एन के अन्य कार्यों की सूची के साथ है जो दो-काउंटर मशीन द्वारा गणना योग्य नहीं हैं - जब काउंटर में एन और दूसरे में 0 के साथ आरंभ किया जाता है - जैसे कि एन2, sqrt(N), लॉग2(एन), आदि, श्रोएप्पेल (1972) के पेपर में दिखाई देते हैं। परिणाम आश्चर्यजनक नहीं है, क्योंकि दो-काउंटर मशीन मॉडल (मिन्स्की द्वारा) केवल तभी सार्वभौमिक साबित हुआ था जब तर्क एन को ट्यूरिंग मशीन का अनुकरण करने के लिए उचित रूप से एन्कोड किया गया था (गोडेलाइज़ेशन द्वारा) जिसके प्रारंभिक टेप में एन यूनरी में एनकोडेड था; इसके अलावा, दो-काउंटर मशीन का आउटपुट समान रूप से एन्कोड किया जाएगा। यह घटना गणना के बहुत छोटे आधारों के लिए विशिष्ट है जिनकी सार्वभौमिकता केवल अनुकरण द्वारा सिद्ध होती है (उदाहरण के लिए, कई ट्यूरिंग टारपिट, सबसे छोटी ज्ञात सार्वभौमिक ट्यूरिंग मशीनें, आदि)।

प्रमाण से पहले कुछ दिलचस्प प्रमेय दिए गए हैं:

  • प्रमेय: तीन-काउंटर मशीन ट्यूरिंग मशीन का अनुकरण कर सकती है (पृष्ठ 2, सीएफ मिन्स्की 1967:170-174 भी)
  • प्रमेय: 3CM [तीन-काउंटर मशीन] चर के किसी भी आंशिक पुनरावर्ती फ़ंक्शन की गणना कर सकती है। यह तर्क से शुरू होता है [अर्थात्। एन] काउंटर में, और (यदि यह रुकता है) उत्तर छोड़ देता है [यानी। एफ(एन)] काउंटर में। (पृ. 3)
  • प्रमेय: काउंटर मशीन को 2CM [दो-काउंटर मशीन] द्वारा सिम्युलेटेड किया जा सकता है, बशर्ते इनपुट और आउटपुट के लिए अस्पष्ट कोडिंग स्वीकार की जाए [पी। 3; अस्पष्ट कोडिंग है: 2डब्ल्यू3एक्स5तथा7Z जहां सिम्युलेटेड काउंटर W, X, Y, Z हैं]
  • प्रमेय: किसी भी काउंटर मशीन को 2CM द्वारा सिम्युलेटेड किया जा सकता है, बशर्ते इनपुट और आउटपुट के लिए अस्पष्ट कोडिंग स्वीकार की जाए। (पृ. 3)
    • परिणाम: 2CM के लिए रुकने की समस्या हल नहीं हो सकी है।
    • परिणाम: 2CM तर्क के किसी भी आंशिक पुनरावर्ती फ़ंक्शन की गणना कर सकता है, बशर्ते इनपुट को 2 के रूप में कोडित किया गया होN और आउटपुट (यदि मशीन रुकती है) को 2 के रूप में कोडित किया गया हैउत्तर. (पृ. 3)
  • प्रमेय: कोई भी दो काउंटर मशीन नहीं है जो 2 की गणना करती होएन [यदि काउंटर को एन से प्रारंभ किया गया है]। (पृ. 11)

दूसरे प्रमेय के संबंध में कि A 3CM किसी भी आंशिक पुनरावर्ती फ़ंक्शन की गणना कर सकता है, लेखक पाठक को कठिन समस्या के साथ चुनौती देता है: केवल तीन काउंटरों का उपयोग करके दो संख्याओं को गुणा करें (पृष्ठ 2)। मुख्य प्रमाण में यह धारणा शामिल है कि दो-काउंटर मशीनें गैर-रेखीय विकास दर (पृष्ठ 15) यानी फ़ंक्शन 2 के साथ अंकगणितीय अनुक्रमों की गणना नहीं कर सकती हैंXकिसी भी अंकगणितीय प्रगति की तुलना में अधिक तेज़ी से बढ़ता है। (पृ. 11).

गिनती द्वारा गणना का व्यावहारिक उदाहरण

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

जोड़ना अप-काउंटर द्वारा किया गया था, जबकि घटाव डाउन-काउंटर द्वारा किया गया था, उधार से निपटने के लिए समान योजना के साथ।

टाइम स्लॉट योजना ने 13 दशमलव अंकों के छह रजिस्टरों को परिभाषित किया, जिनमें से प्रत्येक में साइन बिट था। गुणा और भाग मूल रूप से बार-बार जोड़ और घटाव द्वारा किया जाता था। वर्गमूल संस्करण, EC-132, लगातार विषम पूर्णांकों को प्रभावी ढंग से घटाता है, प्रत्येक वृद्धि के लिए लगातार दो घटाव की आवश्यकता होती है। पहले के बाद, दूसरे घटाव से पहले न्यूनतम में की वृद्धि की गई थी।

यह भी देखें

  • पॉइंटर मशीन
  • पोस्ट-ट्यूरिंग मशीन
  • रैंडम-एक्सेस मशीन
  • रजिस्टर मशीन
  • वांग बी-मशीन

संदर्भ

  1. Boolos-Burgess-Jeffrey (2002)
  • George Boolos, John P. Burgess, Richard Jeffrey (2002), Computability and Logic: Fourth Edition, Cambridge University Press, Cambridge, England. The original Boolos-Jeffrey text has been extensively revised by Burgess: more advanced than an introductory textbook. "Abacus machine" model is extensively developed in Chapter 5 Abacus Computability; it is one of three models extensively treated and compared—the Turing machine (still in Boolos' original 4-tuple form) and recursion the other two.
  • Arthur Burks, Herman Goldstine, John von Neumann (1946), Preliminary discussion of the logical design of an electronic computing instrument, reprinted pp. 92ff in Gordon Bell and Allen Newell (1971), Computer Structures: Readings and Examples, mcGraw-Hill Book Company, New York. ISBN 0-07-004357-4 .
  • Stephen A. Cook and Robert A. Reckhow (1972), Time-bounded random access machines, Journal of Computer Systems Science 7 (1973), 354–375.
  • Martin Davis (1958), Computability & Unsolvability, McGraw-Hill Book Company, Inc. New York.
  • 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.
  • Fischer, Patrick C.; Meyer, A. R.; Rosenberg, Arnold L. (1968), "Counter machines and counter languages", Mathematical Systems Theory, 2 (3): 265–283, doi:10.1007/bf01694011, MR 0235932, S2CID 13006433. Develops time hierarchy and space hierarchy theorems for counter machines, analogous to the hierarchies for Turing machines.
  • J. Hartmanis (1971), "Computational Complexity of Random Access Stored Program Machines," Mathematical Systems Theory 5, 3 (1971) pp. 232–245.
  • Hopcroft, John; Jeffrey Ullman (1979). Introduction to Automata Theory, Languages and Computation (1st ed.). Reading Mass: Addison-Wesley. ISBN 0-201-02988-X. A difficult book centered around the issues of machine-interpretation of "languages", NP-Completeness, etc.
  • Stephen Kleene (1952), Introduction to Metamathematics, North-Holland Publishing Company, Amsterdam, Netherlands. ISBN 0-7204-2103-9.
  • Donald Knuth (1968), The Art of Computer Programming, Second Edition 1973, Addison-Wesley, Reading, Massachusetts. Cf pages 462-463 where he defines "a new kind of abstract machine or 'automaton' which deals with linked structures."
  • Joachim Lambek (1961, received 15 June 1961), How to Program an Infinite Abacus, Mathematical Bulletin, vol. 4, no. 3. September 1961 pages 295–302. In his Appendix II, Lambek proposes a "formal definition of 'program'. He references Melzak (1961) and Kleene (1952) Introduction to Metamathematics.
  • Z. A. Melzak (1961, received 15 May 1961), An informal Arithmetical Approach to Computability and Computation, Canadian Mathematical Bulletin, vol. 4, no. 3. September 1961 pages 279-293. Melzak offers no references but acknowledges "the benefit of conversations with Drs. R. Hamming, D. McIlroy and V. Vyssots of the Bell telephone Laborators and with Dr. H. Wang of Oxford University."
  • Marvin Minsky (1961). "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.
  • Marvin Minsky (1967). Computation: Finite and Infinite Machines (1st ed.). Englewood Cliffs, N. J.: Prentice-Hall, Inc. In particular see chapter 11: Models Similar to Digital Computers and chapter 14: Very Simple Bases for Computability. In the former chapter he defines "Program machines" and in the later chapter he discusses "Universal Program machines with Two Registers" and "...with one register", etc.
  • John C. Shepherdson and H. E. Sturgis (1961) received December 1961 Computability of Recursive Functions, Journal of the Association for Computing Machinery (JACM) 10:217-255, 1963. An extremely valuable reference paper. In their Appendix A the authors cite 4 others with reference to "Minimality of Instructions Used in 4.1: Comparison with Similar Systems".
    • Kaphengst, Heinz, Eine Abstrakte programmgesteuerte Rechenmaschine', Zeitschrift fur mathematische Logik und Grundlagen der Mathematik:5 (1959), 366-379.
    • Ershov, A. P. On operator algorithms, (Russian) Dok. Akad. Nauk 122 (1958), 967-970. English translation, Automat. Express 1 (1959), 20-23.
    • Péter, Rózsa Graphschemata und rekursive Funktionen, Dialectica 12 (1958), 373.
    • Hermes, Hans Die Universalität programmgesteuerter Rechenmaschinen. Math.-Phys. Semesterberichte (Göttingen) 4 (1954), 42–53.
  • A. Schönhage (1980), Storage Modification Machines, Society for Industrial and Applied Mathematics, SIAM J. Comput. Vol. 9, No. 3, August 1980. Wherein Schönhage shows the equivalence of his SMM with the "successor RAM" (Random Access Machine), etc.
  • Rich Schroeppel, May 1972, "A Two counter Machine Cannot Calculate 2N", Massachusetts Institute of Technology, A. I. Laboratory, Artificial Intelligence Memo #257. The author references Minsky 1967 and notes that "Frances Yao independently proved the non-computability using a similar method in April 1971."
  • Peter van Emde Boas, Machine Models and Simulations pp. 3–66, appearing in:
Jan van Leeuwen, ed. Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity, The MIT PRESS/Elsevier, 1990. ISBN 0-444-88071-2 (volume A). QA 76.H279 1990.
van Emde Boas' treatment of SMMs appears on pp. 32-35. This treatment clarifies Schōnhage 1980 -- it closely follows but expands slightly the Schōnhage treatment. Both references may be needed for effective understanding.
  • Hao Wang (1957), A Variant to Turing's Theory of Computing Machines, JACM (Journal of the Association for Computing Machinery) 4; 63–92. Presented at the meeting of the Association, June 23–25, 1954.
  • [1]


बाहरी संबंध

  1. "Archived copy" (PDF). stedolan.net. Archived from the original (PDF) on 2021-02-14.{{cite web}}: CS1 maint: archived copy as title (link)