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

From Vigyanwiki
No edit summary
No edit summary
 
(6 intermediate revisions by 3 users not shown)
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 27: Line 27:
काउंटर मशीन मॉडल अनेक भिन्न-भिन्न नामों से जाने जाते हैं जो उनकी विशिष्टताओं के आधार पर उन्हें भिन्न करने में सहायता कर सकते हैं। निम्नलिखित निर्देश में JZDEC (r) मिश्रित निर्देश है जो यह देखने के लिए परीक्षण करता है कि कोई रजिस्टर r रिक्त है या नहीं; यदि ऐसा है तो निर्देश I<sub>z</sub> पर जाएँ, अन्यथा यदि नहीं तो r की कंटेंट को घटाएँ जाते है:
काउंटर मशीन मॉडल अनेक भिन्न-भिन्न नामों से जाने जाते हैं जो उनकी विशिष्टताओं के आधार पर उन्हें भिन्न करने में सहायता कर सकते हैं। निम्नलिखित निर्देश में JZDEC (r) मिश्रित निर्देश है जो यह देखने के लिए परीक्षण करता है कि कोई रजिस्टर r रिक्त है या नहीं; यदि ऐसा है तो निर्देश I<sub>z</sub> पर जाएँ, अन्यथा यदि नहीं तो r की कंटेंट को घटाएँ जाते है:


* शेफर्डसन-स्टर्गिस मशीन, क्योंकि इन लेखकों ने औपचारिक रूप से अपने मॉडल को सरलता से सुलभ प्रदर्शनी (1963) में बताया था। इस प्रकार अतिरिक्त सुविधा निर्देशों के साथ संवर्धित अनुदेश सेट (1) का उपयोग करता है (JNZ शून्य नहीं होने पर जंप है, JZ के स्थान पर उपयोग किया जाता है):
* शेफर्डसन-स्टर्गिस मशीन, क्योंकि इन लेखकों ने फार्मल रूप से अपने मॉडल को सरलता से सुलभ प्रदर्शनी (1963) में बताया था। इस प्रकार अतिरिक्त सुविधा निर्देशों के साथ संवर्धित अनुदेश सेट (1) का उपयोग करता है (JNZ शून्य नहीं होने पर जंप है, JZ के स्थान पर उपयोग किया जाता है):
*: {INC (r), DEC (r), CLR (r), CPY (r)।<sub>j</sub>, r<sub>k</sub> ), JNZ (r, Z), J (Z)}
*: {INC (r), DEC (r), CLR (r), CPY (r)।<sub>j</sub>, r<sub>k</sub> ), JNZ (r, Z), J (Z)}
* मिन्स्की मशीन, क्योंकि [[मार्विन मिंस्की]] (1961) ने मॉडल को औपचारिक रूप दिया। सामान्यतः निर्देश सेट (1) का उपयोग करता है, किन्तु निर्देश-निष्पादन डिफ़ॉल्ट-अनुक्रमिक नहीं है, इसलिए अतिरिक्त मापदंड 'z' INC के पश्चात् अगले निर्देश को निर्दिष्ट करता है और JZDEC में विकल्प के रूप में दिखाई देता है:
* मिन्स्की मशीन, क्योंकि [[मार्विन मिंस्की]] (1961) ने मॉडल को फार्मल रूप दिया। सामान्यतः निर्देश सेट (1) का उपयोग करता है, किन्तु निर्देश-निष्पादन डिफ़ॉल्ट-अनुक्रमिक नहीं है, इसलिए अतिरिक्त मापदंड 'z' INC के पश्चात् अगले निर्देश को निर्दिष्ट करता है और JZDEC में विकल्प के रूप में दिखाई देता है:
*: { INC ( r, z ), JZDEC ( r, z<sub>true</sub>, z<sub>false</sub>) }
*: { INC ( r, z ), JZDEC ( r, z<sub>true</sub>, z<sub>false</sub>) }
* प्रोग्राम मशीन, प्रोग्राम [[कंप्यूटर]], नाम मिन्स्की (1967) ने मॉडल को दिया क्योंकि, कंप्यूटर की तरह इसके निर्देश क्रमिक रूप से आगे बढ़ते हैं इस प्रकार जब तक कि नियमबद्ध जम्प सफल नहीं होती है। (सामान्यतः) निर्देश सेट (1) का उपयोग करता है किन्तु इसे शेफर्सन-स्टर्गिस मॉडल के समान संवर्धित किया जा सकता है। JZDEC को अधिकांशतः भिन्न कर दिया जाता है:
* प्रोग्राम मशीन, प्रोग्राम [[कंप्यूटर]], नाम मिन्स्की (1967) ने मॉडल को दिया क्योंकि, कंप्यूटर की तरह इसके निर्देश क्रमिक रूप से आगे बढ़ते हैं इस प्रकार जब तक कि नियमबद्ध जम्प सफल नहीं होती है। (सामान्यतः) निर्देश सेट (1) का उपयोग करता है किन्तु इसे शेफर्सन-स्टर्गिस मॉडल के समान संवर्धित किया जा सकता है। JZDEC को अधिकांशतः भिन्न कर दिया जाता है:
Line 43: Line 43:
* अन्य काउंटर मशीनें: मिन्स्की (1967) दर्शाता है कि इस आलेख के मुख्य पैराग्राफ में वर्णित उपलब्ध निर्देशों के सुपरसेट से तीन बेस मॉडल (प्रोग्राम/मिन्स्की/लैम्बेक-अबेकस, उत्तराधिकारी, और एल्गॉट-रॉबिन्सन) कैसे बनाया जाए। मेल्ज़ाक (1961) मॉडल उपरोक्त से अधिक भिन्न है क्योंकि इसमें 'वृद्धि' और 'घटाना' के अतिरिक्त 'जोड़' और 'घटाना' सम्मिलित है। मिन्स्की (1961, 1967) के प्रमाण कि ट्यूरिंग समतुल्यता के लिए एकल रजिस्टर पर्याप्त होगा, गणना का प्रतिनिधित्व करने वाले रजिस्टर में गोडेल संख्या को एन्कोड और डीकोड करने के लिए दो निर्देशों {मल्टीप्लाई K, और डीआईवी K} की आवश्यकता होती है। इस प्रकार मिन्स्की दर्शाता है कि यदि दो या दो से अधिक रजिस्टर उपलब्ध हैं तो सरल INC, DEC आदि पर्याप्त हैं (किन्तु [[ट्यूरिंग पूर्णता]] प्रदर्शित करने के लिए गोडेल संख्या अभी भी आवश्यक है; एल्गॉट-रॉबिन्सन 1964 में भी प्रदर्शित किया गया है)।
* अन्य काउंटर मशीनें: मिन्स्की (1967) दर्शाता है कि इस आलेख के मुख्य पैराग्राफ में वर्णित उपलब्ध निर्देशों के सुपरसेट से तीन बेस मॉडल (प्रोग्राम/मिन्स्की/लैम्बेक-अबेकस, उत्तराधिकारी, और एल्गॉट-रॉबिन्सन) कैसे बनाया जाए। मेल्ज़ाक (1961) मॉडल उपरोक्त से अधिक भिन्न है क्योंकि इसमें 'वृद्धि' और 'घटाना' के अतिरिक्त 'जोड़' और 'घटाना' सम्मिलित है। मिन्स्की (1961, 1967) के प्रमाण कि ट्यूरिंग समतुल्यता के लिए एकल रजिस्टर पर्याप्त होगा, गणना का प्रतिनिधित्व करने वाले रजिस्टर में गोडेल संख्या को एन्कोड और डीकोड करने के लिए दो निर्देशों {मल्टीप्लाई K, और डीआईवी K} की आवश्यकता होती है। इस प्रकार मिन्स्की दर्शाता है कि यदि दो या दो से अधिक रजिस्टर उपलब्ध हैं तो सरल INC, DEC आदि पर्याप्त हैं (किन्तु [[ट्यूरिंग पूर्णता]] प्रदर्शित करने के लिए गोडेल संख्या अभी भी आवश्यक है; एल्गॉट-रॉबिन्सन 1964 में भी प्रदर्शित किया गया है)।


== औपचारिक परिभाषा ==
== फार्मल परिभाषा ==
एक काउंटर मशीन में निम्न सम्मिलित होते हैं:
एक काउंटर मशीन में निम्न सम्मिलित होते हैं:
# लेबल रहित पूर्णांक-मूल्यवान रजिस्टर: रजिस्टरों का सीमित (या कुछ मॉडलों में अनंत) सेट ''r''<sub>0</sub>... r<sub>''n''</sub> जिनमें से प्रत्येक किसी ऋणात्मक पूर्णांक (0, 1, 2, ... - अर्थात असीमित) को धारण कर सकता है। रजिस्टर अपना अंकगणित स्वयं करते हैं; या अधिक विशेष रजिस्टर हो भी सकते हैं और नहीं भी, जैसे संचायक (इस पर अधिक जानकारी के लिए [[रैंडम-एक्सेस मशीन]] देखें)।
# लेबल रहित पूर्णांक-मूल्यवान रजिस्टर: रजिस्टरों का सीमित (या कुछ मॉडलों में अनंत) सेट ''r''<sub>0</sub>... r<sub>''n''</sub> जिनमें से प्रत्येक किसी ऋणात्मक पूर्णांक (0, 1, 2, ... - अर्थात असीमित) को धारण कर सकता है। इस प्रकार रजिस्टर अपना अंकगणित स्वयं करते हैं; या अधिक विशेष रजिस्टर हो भी सकते हैं और नहीं भी, जैसे संचायक (इस पर अधिक जानकारी के लिए [[रैंडम-एक्सेस मशीन]] देखें)।
# एक स्तर रजिस्टर जो निष्पादित किए जाने वाले वर्तमान निर्देश को संग्रहीत/पहचानता है। यह रजिस्टर परिमित है और उपरोक्त रजिस्टरों से भिन्न है; इस प्रकार काउंटर मशीन मॉडल [[हार्वर्ड वास्तुकला|हार्वर्ड आर्किटेक्चर]] का उदाहरण है
# एक स्तर रजिस्टर जो निष्पादित किए जाने वाले वर्तमान निर्देश को संग्रहीत/पहचानता है। यह रजिस्टर परिमित है और उपरोक्त रजिस्टरों से भिन्न है; इस प्रकार काउंटर मशीन मॉडल [[हार्वर्ड वास्तुकला|हार्वर्ड आर्किटेक्चर]] का उदाहरण है
# लेबल किए गए, अनुक्रमिक निर्देशों की सूची: निर्देशों की सीमित सूची ''I''<sub>0</sub>... ''I''<sub>''m''</sub>. प्रोग्राम स्टोर (परिमित स्तर मशीन के निर्देश) रजिस्टरों के समान भौतिक स्थान पर नहीं है। सामान्यतः, किन्तु सदैव नहीं, [[कंप्यूटर प्रोग्राम]] की तरह निर्देश अनुक्रमिक क्रम में सूचीबद्ध होते हैं; जब तक कोई जम्प सफल नहीं होती है, डिफ़ॉल्ट अनुक्रम संख्यात्मक क्रम में जारी रहता है। इस प्रकार सूची में प्रत्येक निर्देश (बहुत) छोटे सेट से है, किन्तु इस सेट में अप्रत्यक्ष सम्मिलित नहीं है। ऐतिहासिक रूप से अधिकांश मॉडलों ने इस सेट से अपने निर्देश प्राप्त किए:
# लेबल किए गए, अनुक्रमिक निर्देशों की सूची: निर्देशों की सीमित सूची ''I''<sub>0</sub>... ''I''<sub>''m''</sub>. प्रोग्राम स्टोर (परिमित स्तर मशीन के निर्देश) रजिस्टरों के समान भौतिक स्थान पर नहीं है। सामान्यतः, किन्तु सदैव नहीं, [[कंप्यूटर प्रोग्राम]] की तरह निर्देश अनुक्रमिक क्रम में सूचीबद्ध होते हैं; जब तक कोई जम्प सफल नहीं होती है, डिफ़ॉल्ट अनुक्रम संख्यात्मक क्रम में जारी रहता है। इस प्रकार सूची में प्रत्येक निर्देश (बहुत) छोटे सेट से है, किन्तु इस सेट में अप्रत्यक्ष सम्मिलित नहीं है। ऐतिहासिक रूप से अधिकांश मॉडलों ने इस सेट से अपने निर्देश प्राप्त किए:
Line 55: Line 55:
:: पूरक [[रजिस्टर-मशीन मॉडल]] में वैकल्पिक निर्देश-सेट पर चर्चा की गई है।
:: पूरक [[रजिस्टर-मशीन मॉडल]] में वैकल्पिक निर्देश-सेट पर चर्चा की गई है।


उदाहरण: रजिस्टर #2 से #3 तक गिनती कॉपी करें
उदाहरण: रजिस्टर #2 से #3 तक गणना कॉपी करें


यह उदाहरण दिखाता है कि तीन और उपयोगी निर्देश कैसे बनाएं: स्पष्ट, नियमबद्ध जंप और कॉपी।
यह उदाहरण दिखाता है कि तीन और उपयोगी निर्देश कैसे बनाएं: स्पष्ट, नियमबद्ध जंप और कॉपी।
Line 91: Line 91:
| align="center" valign="bottom" |  
| align="center" valign="bottom" |  
|}
|}
=== प्रारंभिक नियम ===
=== प्रारंभिक नियम ===


Line 99: Line 97:
===अंतिम नियम ===
===अंतिम नियम ===


प्रोग्राम रजिस्टर #2 की कंटेंट को उसकी मूल गिनती पर और रजिस्टर #3 की कंटेंट को रजिस्टर #2 की मूल कंटेंट के समान रोक देता है, अर्थात,
प्रोग्राम रजिस्टर #2 की कंटेंट को उसकी मूल गणना पर और रजिस्टर #3 की कंटेंट को रजिस्टर #2 की मूल कंटेंट के समान रोक देता है, अर्थात,
: [2] = [3]।
: [2] = [3]।


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


चूँकि, हम देखते हैं कि ADD सरलता से संभव होता। और वास्तव में निम्नलिखित इस बात का सारांश है कि ADD, MULtiply और EXPonent जैसे [[आदिम पुनरावर्ती कार्य|मौलिक पुनरावर्ती कार्य]] कैसे हो सकते हैं (बूलोस-बर्गेस-जेफरी (2002) पृष्ठ 45-51 देखें)।
चूँकि, हम देखते हैं कि ADD सरलता से संभव होता। और वास्तव में निम्नलिखित इस बात का सारांश है कि ADD, MULtiply और EXPonent जैसे [[आदिम पुनरावर्ती कार्य|मौलिक पुनरावर्ती कार्य]] कैसे हो सकते हैं (बूलोस-बर्गेस-जेफरी (2002) पृष्ठ 45-51 देखें)।
Line 907: Line 903:
लेखक बताते हैं कि यह किसी भी उपलब्ध आधार सेट (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 916: Line 912:
(2) 'रजिस्टरों की असीमित संख्या बनाम स्तर-मशीन निर्देशों की बंधी हुई संख्या:' मशीन अपनी सीमित स्तर मशीन की पहुंच/क्षमता से परे पता-संख्या वाले रजिस्टरों तक कैसे पहुंच पाएगी?
(2) 'रजिस्टरों की असीमित संख्या बनाम स्तर-मशीन निर्देशों की बंधी हुई संख्या:' मशीन अपनी सीमित स्तर मशीन की पहुंच/क्षमता से परे पता-संख्या वाले रजिस्टरों तक कैसे पहुंच पाएगी?


(3) पूरी तरह से कम किए गए मॉडल कष्टकर हैं:
(3) पुर्णतः कम किए गए मॉडल कष्टकर हैं:


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


शेफर्डसन और स्टर्गिस के निर्देश ([r] रजिस्टर r की कंटेंट को इंगित करता है):
शेफर्डसन और स्टर्गिस के निर्देश ([r] रजिस्टर r की कंटेंट को संकेत करता है):
** वृद्धि (r); [r] +1 → r
** वृद्धि (r); [r] +1 → r
** कमी (r) ; [r] -1 → r
** कमी (r) ; [r] -1 → r
Line 935: Line 931:
दो काउंटर मशीनें निर्देश के सेट { INC ( r, z ), JZDEC ( r, z<sub>true</sub>, z<sub>false</sub>) }. का उपयोग करती हैं  
दो काउंटर मशीनें निर्देश के सेट { INC ( r, z ), JZDEC ( r, z<sub>true</sub>, z<sub>false</sub>) }. का उपयोग करती हैं  


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


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


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


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


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


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


जोड़ना अप-काउंटर द्वारा किया गया था, जबकि घटाव डाउन-काउंटर द्वारा उधार से निपटने के लिए समान योजना के साथ किया गया था।
जोड़ना अप-काउंटर द्वारा किया गया था, जबकि घटाव डाउन-काउंटर द्वारा उधार से निपटने के लिए समान योजना के साथ किया गया था।
Line 970: Line 966:
टाइम स्लॉट योजना ने 13 दशमलव अंकों के छह रजिस्टरों को परिभाषित किया था, जिनमें से प्रत्येक में साइन बिट था।
टाइम स्लॉट योजना ने 13 दशमलव अंकों के छह रजिस्टरों को परिभाषित किया था, जिनमें से प्रत्येक में साइन बिट था।


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


==यह भी देखें==
==यह भी देखें==
Line 1,023: Line 1,019:
* [[Hao Wang (academic)|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.
* [[Hao Wang (academic)|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.
*<ref>{{cite web |url=http://stedolan.net/research/mov.pdf |title=Archived copy |website=stedolan.net |archive-url=https://web.archive.org/web/20210214020524/https://stedolan.net/research/mov.pdf |archive-date=2021-02-14 |url-status=}}</ref>
*<ref>{{cite web |url=http://stedolan.net/research/mov.pdf |title=Archived copy |website=stedolan.net |archive-url=https://web.archive.org/web/20210214020524/https://stedolan.net/research/mov.pdf |archive-date=2021-02-14 |url-status=}}</ref>
                                                                                                                                                                                                                                                                                                                                                                     
                                                                                                                                                                                                                                                                                                                                                                                                                               
==बाहरी संबंध                                                                                                                                                                                                                                                                                                                                                                                                                                                                                ==
==बाहरी संबंध                                                                                                                                                                                                                                                                                                                                                                                                                                                                                ==
* {{MathWorld|title=Register machine|urlname=RegisterMachine}}
* {{MathWorld|title=Register machine|urlname=RegisterMachine}}
* [http://www.igblan.free-online.co.uk/igblan/ca/minsky.html Igblan - Minsky Register Machines]
* [http://www.igblan.free-online.co.uk/igblan/ca/minsky.html Igblan - Minsky Register Machines]
[[Category: मशीनें पंजीकृत करें]]


[[Category: Machine Translated Page]]
[[Category:Articles with hatnote templates targeting a nonexistent page]]
[[Category:CS1 maint]]
[[Category:Created On 25/07/2023]]
[[Category:Created On 25/07/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Short description with empty Wikidata description]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:मशीनें पंजीकृत करें]]

Latest revision as of 11:22, 12 August 2023

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