काउंटर मशीन: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| (7 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 19: | Line 19: | ||
* सेट 3: {INC (r), CPY (r)।<sub>j</sub>, आर<sub>k</sub>), JE (r<sub>j</sub>, r<sub>k</sub>, z) }, (एल्गॉट-रॉबिन्सन (1964), मिन्स्की (1967)) | * सेट 3: {INC (r), CPY (r)।<sub>j</sub>, आर<sub>k</sub>), JE (r<sub>j</sub>, r<sub>k</sub>, z) }, (एल्गॉट-रॉबिन्सन (1964), मिन्स्की (1967)) | ||
तीन काउंटर मशीन बेस मॉडल में समान कम्प्यूटेशनल पावर होती है क्योंकि मॉडल के निर्देश दूसरे मॉडल से प्राप्त किए जा सकते हैं। सभी [[ट्यूरिंग मशीन]] की कम्प्यूटेशनल पावर के समान हैं। उनकी एकात्मक प्रसंस्करण शैली के कारण, काउंटर मशीनें सामान्यतः तुलनीय ट्यूरिंग मशीनों की तुलना में तेजी से धीमी होती हैं। | तीन काउंटर मशीन बेस मॉडल में समान कम्प्यूटेशनल पावर होती है क्योंकि मॉडल के निर्देश दूसरे मॉडल से प्राप्त किए जा सकते हैं। इस प्रकार सभी [[ट्यूरिंग मशीन]] की कम्प्यूटेशनल पावर के समान हैं। उनकी एकात्मक प्रसंस्करण शैली के कारण, काउंटर मशीनें सामान्यतः तुलनीय ट्यूरिंग मशीनों की तुलना में तेजी से धीमी होती हैं। | ||
== वैकल्पिक नाम, वैकल्पिक मॉडल == | == वैकल्पिक नाम, वैकल्पिक मॉडल == | ||
| Line 27: | Line 27: | ||
काउंटर मशीन मॉडल अनेक भिन्न-भिन्न नामों से जाने जाते हैं जो उनकी विशिष्टताओं के आधार पर उन्हें भिन्न करने में सहायता कर सकते हैं। निम्नलिखित निर्देश में JZDEC (r) मिश्रित निर्देश है जो यह देखने के लिए परीक्षण करता है कि कोई रजिस्टर r रिक्त है या नहीं; यदि ऐसा है तो निर्देश I<sub>z</sub> पर जाएँ, अन्यथा यदि नहीं तो r की कंटेंट को घटाएँ जाते है: | काउंटर मशीन मॉडल अनेक भिन्न-भिन्न नामों से जाने जाते हैं जो उनकी विशिष्टताओं के आधार पर उन्हें भिन्न करने में सहायता कर सकते हैं। निम्नलिखित निर्देश में JZDEC (r) मिश्रित निर्देश है जो यह देखने के लिए परीक्षण करता है कि कोई रजिस्टर r रिक्त है या नहीं; यदि ऐसा है तो निर्देश I<sub>z</sub> पर जाएँ, अन्यथा यदि नहीं तो r की कंटेंट को घटाएँ जाते है: | ||
* शेफर्डसन-स्टर्गिस मशीन, क्योंकि इन लेखकों ने | * शेफर्डसन-स्टर्गिस मशीन, क्योंकि इन लेखकों ने फार्मल रूप से अपने मॉडल को सरलता से सुलभ प्रदर्शनी (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) ने मॉडल को | * मिन्स्की मशीन, क्योंकि [[मार्विन मिंस्की]] (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) ने मॉडल को दिया क्योंकि, कंप्यूटर की तरह इसके निर्देश क्रमिक रूप से आगे बढ़ते हैं जब तक कि नियमबद्ध जम्प सफल नहीं | * प्रोग्राम मशीन, प्रोग्राम [[कंप्यूटर]], नाम मिन्स्की (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>, | *: { INC ( r, z ), JZDEC (r, z<sub>true</sub>, z<sub>false</sub> ) } | ||
* लैम्बेक मशीन, वैकल्पिक नाम बूलोस-बर्गेस-जेफरी (2002) ने अबेकस मशीन को दिया था। अगले निर्देश को निर्दिष्ट करने के लिए अतिरिक्त मापदंड के साथ निर्देश सेट (1-कम) का उपयोग करता है: | * लैम्बेक मशीन, वैकल्पिक नाम बूलोस-बर्गेस-जेफरी (2002) ने अबेकस मशीन को दिया था। अगले निर्देश को निर्दिष्ट करने के लिए अतिरिक्त मापदंड के साथ निर्देश सेट (1-कम) का उपयोग करता है: | ||
*: { INC ( r, z ), JZDEC ( r, z<sub>true</sub>, | *: { INC ( r, z ), JZDEC ( r, z<sub>true</sub>, z<sub>false</sub> ) } | ||
* उत्तराधिकारी मशीन, क्योंकि यह 'उत्तराधिकारी ऑपरेशन' का उपयोग करती है, और पीनो स्वयंसिद्धों से अधिक मिलती-जुलती है। उत्तराधिकारी रैम मॉडल के लिए आधार के रूप में उपयोग किया जाता है। उदाहरण के लिए निर्देश सेट (2) का उपयोग करता है। शॉनहेज को उनके RAM0 और RAM1 मॉडल के आधार के रूप में, जो उनके [[ सूचक मशीन |सूचक मशीन]] SMM मॉडल की ओर ले जाता है, वैन एम्डे बोस (1990) में भी संक्षेप में चर्चा की गई है: | * उत्तराधिकारी मशीन, क्योंकि यह 'उत्तराधिकारी ऑपरेशन' का उपयोग करती है, और पीनो स्वयंसिद्धों से अधिक मिलती-जुलती है। उत्तराधिकारी रैम मॉडल के लिए आधार के रूप में उपयोग किया जाता है। उदाहरण के लिए निर्देश सेट (2) का उपयोग करता है। शॉनहेज को उनके RAM0 और RAM1 मॉडल के आधार के रूप में, जो उनके [[ सूचक मशीन |सूचक मशीन]] SMM मॉडल की ओर ले जाता है, वैन एम्डे बोस (1990) में भी संक्षेप में चर्चा की गई है: | ||
*: {CLR (r), INC (r), JE (r)।<sub>j</sub>, r<sub>k</sub>, z ) } | *: {CLR (r), INC (r), JE (r)।<sub>j</sub>, r<sub>k</sub>, z ) } | ||
* एल्गॉट-रॉबिन्सन मॉडल, उनके आरएएसपी मॉडल (1964) को परिभाषित करने के लिए उपयोग किया जाता है। इस मॉडल को प्रारंभ में रिक्त रजिस्टर की आवश्यकता होती है (उदाहरण के लिए [r0] =0)। (उन्होंने इंडेक्स रजिस्टर के रूप में उपयोग करने के लिए अतिरिक्त रजिस्टर का उपयोग करके अप्रत्यक्ष संबोधन के साथ उसी मॉडल को संवर्धित किया।) | * एल्गॉट-रॉबिन्सन मॉडल, उनके आरएएसपी मॉडल (1964) को परिभाषित करने के लिए उपयोग किया जाता है। इस मॉडल को प्रारंभ में रिक्त रजिस्टर की आवश्यकता होती है (उदाहरण के लिए [r0] =0)। (उन्होंने इंडेक्स रजिस्टर के रूप में उपयोग करने के लिए अतिरिक्त रजिस्टर का उपयोग करके अप्रत्यक्ष संबोधन के साथ उसी मॉडल को संवर्धित किया।) | ||
*: { INC (r), CPY (r<sub>s</sub>, r<sub>d</sub> ), JE (r<sub>j</sub>, r<sub>k</sub>, z ) } | *: { INC (r), CPY (r<sub>s</sub>, r<sub>d</sub> ), JE (r<sub>j</sub>, r<sub>k</sub>, z ) } | ||
* अन्य काउंटर मशीनें: मिन्स्की (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>. प्रोग्राम स्टोर (परिमित स्तर मशीन के निर्देश) रजिस्टरों के समान भौतिक स्थान पर नहीं है। सामान्यतः, किन्तु सदैव नहीं, [[कंप्यूटर प्रोग्राम]] की तरह निर्देश अनुक्रमिक क्रम में सूचीबद्ध होते हैं; जब तक कोई जम्प सफल नहीं होती है, डिफ़ॉल्ट अनुक्रम संख्यात्मक क्रम में जारी रहता है। इस प्रकार सूची में प्रत्येक निर्देश (बहुत) छोटे सेट से है, किन्तु इस सेट में अप्रत्यक्ष सम्मिलित नहीं है। ऐतिहासिक रूप से अधिकांश मॉडलों ने इस सेट से अपने निर्देश प्राप्त किए: | ||
:: {वृद्धि (r), कमी (r), स्पष्ट (r); कॉपी (r<sub>j</sub>,r<sub>k</sub>), यदि r=0 की कंटेंट है तो नियमबद्ध जम्प, यदि r की कंटेंट है तो नियमबद्ध r<sub>j</sub>=r<sub>k</sub>, नियमबद्ध जम्प, हॉल्ट } | :: {वृद्धि (r), कमी (r), स्पष्ट (r); कॉपी (r<sub>j</sub>,r<sub>k</sub>), यदि r=0 की कंटेंट है तो नियमबद्ध जम्प, यदि r की कंटेंट है तो नियमबद्ध r<sub>j</sub>=r<sub>k</sub>, नियमबद्ध जम्प, हॉल्ट } | ||
:: | :: | ||
| Line 55: | Line 55: | ||
:: पूरक [[रजिस्टर-मशीन मॉडल]] में वैकल्पिक निर्देश-सेट पर चर्चा की गई है। | :: पूरक [[रजिस्टर-मशीन मॉडल]] में वैकल्पिक निर्देश-सेट पर चर्चा की गई है। | ||
उदाहरण: रजिस्टर #2 से #3 तक | उदाहरण: रजिस्टर #2 से #3 तक गणना कॉपी करें | ||
यह उदाहरण दिखाता है कि तीन और उपयोगी निर्देश कैसे बनाएं: स्पष्ट, नियमबद्ध जंप और कॉपी। | यह उदाहरण दिखाता है कि तीन और उपयोगी निर्देश कैसे बनाएं: स्पष्ट, नियमबद्ध जंप और कॉपी। | ||
* CLR (J): रजिस्टर r<sub>j</sub> की कंटेंट स्पष्ट करें शून्य करने के लिए. | * CLR (J): रजिस्टर r<sub>j</sub> की कंटेंट स्पष्ट करें शून्य करने के लिए. | ||
* J (Z): अप्रतिबंध निर्देश I<sub>z</sub> पर जाएं. | * J (Z): अप्रतिबंध निर्देश I<sub>z</sub> पर जाएं. | ||
* CPY (S, d): स्रोत रजिस्टर r<sub>s</sub> की कंटेंट की प्रतिलिपि बनाएँ गंतव्य रजिस्टर r<sub>d</sub> के लिए. (वन-इंस्ट्रक्शन सेट कंप्यूटर | * CPY (S, d): स्रोत रजिस्टर r<sub>s</sub> की कंटेंट की प्रतिलिपि बनाएँ गंतव्य रजिस्टर r<sub>d</sub> के लिए. (वन-इंस्ट्रक्शन सेट कंप्यूटर या ट्रांसपोर्ट ट्रिगर आर्किटेक्चर देखें) | ||
पश्चात् में r<sub>s</sub> इसमें इसकी मूल गणना सम्मिलित होगी (MOVE के विपरीत जो स्रोत रजिस्टर को रिक्त कर देता है, अर्थात इसे शून्य पर स्पष्ट कर देता है)। | पश्चात् में r<sub>s</sub> इसमें इसकी मूल गणना सम्मिलित होगी (MOVE के विपरीत जो स्रोत रजिस्टर को रिक्त कर देता है, अर्थात इसे शून्य पर स्पष्ट कर देता है)। | ||
| Line 92: | Line 91: | ||
| align="center" valign="bottom" | | | align="center" valign="bottom" | | ||
|} | |} | ||
=== प्रारंभिक नियम === | === प्रारंभिक नियम === | ||
| Line 100: | Line 97: | ||
===अंतिम नियम === | ===अंतिम नियम === | ||
प्रोग्राम रजिस्टर #2 की कंटेंट को उसकी मूल | प्रोग्राम रजिस्टर #2 की कंटेंट को उसकी मूल गणना पर और रजिस्टर #3 की कंटेंट को रजिस्टर #2 की मूल कंटेंट के समान रोक देता है, अर्थात, | ||
: [2] = [3]। | : [2] = [3]। | ||
| Line 873: | Line 870: | ||
| हाल्ट | | हाल्ट | ||
|} | |} | ||
==आंशिक पुनरावर्ती कार्य: पुनरावर्तन का उपयोग करके सुविधा निर्देश बनाना== | ==आंशिक पुनरावर्ती कार्य: पुनरावर्तन का उपयोग करके सुविधा निर्देश बनाना== | ||
उपरोक्त उदाहरण दर्शाता है कि कैसे पहले मूलभूत निर्देश { INC, DEC, JZ } तीन और निर्देश बना सकते हैं अप्रतिबंध जंप J, CLR, CPY। अर्थ में CPY ने CLR और j प्लस बेस सेट दोनों का उपयोग किया था। यदि रजिस्टर #3 में प्रारंभ में कंटेंट होती, तो #2 और #3 की कंटेंट का योग #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 889: | Line 884: | ||
:: उपरोक्त शेफर्डसन-स्टर्गिस (1963) का निर्देश सेट है। | :: उपरोक्त शेफर्डसन-स्टर्गिस (1963) का निर्देश सेट है। | ||
* ADD | * ADD (r<sub>j</sub>, r<sub>k</sub>, r<sub>i</sub> ) को परिभाषित करें , (संभवतः r<sub>j</sub>, और r<sub>k</sub> की कंटेंट को संरक्षित करना), उपरोक्त के उपयोग से: | ||
: {ADD, CPY, CLR, J, DEC, INC, JZ, H } | : {ADD, CPY, CLR, J, DEC, INC, JZ, H } | ||
* मल्टीप्लाई (r<sub>j</sub>, r<sub>k</sub>, r<sub>i</sub>) (एमयूएल) को परिभाषित करें | * मल्टीप्लाई (r<sub>j</sub>, r<sub>k</sub>, r<sub>i</sub>) (एमयूएल) को परिभाषित करें (संभवतः r<sub>j</sub>, r<sub>k</sub> की कंटेंट को संरक्षित करना), उपरोक्त के संदर्भ में: | ||
: {MUL, ADD, CPY, CLR, J, DEC, INC, JZ, H } | : {MUL, ADD, CPY, CLR, J, DEC, INC, JZ, H } | ||
* घातांक (r<sub>j</sub>, r<sub>k</sub>, r<sub>i</sub> ) | * घातांक (r<sub>j</sub>, r<sub>k</sub>, r<sub>i</sub> ) को परिभाषित करें (EXP) (संभवतः r<sub>j</sub>, r<sub>k</sub> की कंटेंट को संरक्षित करना ) उपरोक्त के संदर्भ में, | ||
: { EXP, MUL, ADD, CPY, CLR, J, DEC, INC, JZ, H } | : { EXP, MUL, ADD, CPY, CLR, J, DEC, INC, JZ, H } | ||
सामान्यतः, हम समान विधियों का उपयोग करके, अपनी इच्छानुसार कोई भी आंशिक- या कुल-मौलिक पुनरावर्ती | सामान्यतः, हम समान विधियों का उपयोग करके, अपनी इच्छानुसार कोई भी आंशिक- या कुल-मौलिक पुनरावर्ती फ़ंक्शन बना सकते हैं। सामान्यतः, मिन्स्की (1967), शेफर्डसन-स्टर्गिस (1963) और बूलोस-बर्गेस-जेफरी (2002) बेस सेट (1) से पांच मौलिक पुनरावर्ती फ़ंक्शन ऑपरेटरों (नीचे 1-5) को बनाने का प्रदर्शन देते हैं। | ||
किन्तु पूर्ण [[ट्यूरिंग मशीन समकक्ष]] के बारे में क्या? हमें पूर्ण तुल्यता प्राप्त करने के लिए छठे ऑपरेटर- μ ऑपरेटर को जोड़ने की आवश्यकता है, जो कुल- और आंशिक- [[रिकर्सन (कंप्यूटर विज्ञान)]] बनाने में सक्षम है: | किन्तु पूर्ण [[ट्यूरिंग मशीन समकक्ष]] के बारे में क्या? हमें पूर्ण तुल्यता प्राप्त करने के लिए छठे ऑपरेटर- μ ऑपरेटर को जोड़ने की आवश्यकता है, जो कुल- और आंशिक- [[रिकर्सन (कंप्यूटर विज्ञान)|रिकर्सन (कंप्यूटर साइंस)]] बनाने में सक्षम है: | ||
# शून्य | # शून्य फ़ंक्शन (या स्थिर फ़ंक्शन) | ||
#उत्तराधिकारी कार्य | #उत्तराधिकारी कार्य | ||
# पहचान | # पहचान फ़ंक्शन | ||
# रचना | # रचना फ़ंक्शन | ||
# [[आदिम पुनरावर्तन|मौलिक पुनरावर्तन]] (प्रेरण) | # [[आदिम पुनरावर्तन|मौलिक पुनरावर्तन]] (प्रेरण) | ||
# μ ऑपरेटर (अनबाउंड सर्च ऑपरेटर) | # μ ऑपरेटर (अनबाउंड सर्च ऑपरेटर) | ||
लेखक बताते हैं कि यह किसी भी उपलब्ध आधार सेट (1, 2, या 3) के अन्दर सरलता से किया जाता है (एक उदाहरण μ ऑपरेटर पर पाया जा सकता है)। इसका कारण यह है कि किसी भी म्यू रिकर्सिव | लेखक बताते हैं कि यह किसी भी उपलब्ध आधार सेट (1, 2, या 3) के अन्दर सरलता से किया जाता है (एक उदाहरण μ ऑपरेटर पर पाया जा सकता है)। इसका कारण यह है कि किसी भी म्यू रिकर्सिव फ़ंक्शन को काउंटर मशीन के रूप में कार्यान्वित किया जा सकता है,<ref>Boolos-Burgess-Jeffrey (2002)</ref> काउंटर मशीन डिज़ाइन के सीमित निर्देश सेट और प्रोग्राम आकार के अतिरिक्त चूँकि, आवश्यक निर्माण प्रति-सहज ज्ञान युक्त हो सकता है, यहां तक कि उन कार्यों के लिए भी जिन्हें रैंडम-एक्सेस मशीन जैसी अधिक सम्मिश्र रजिस्टर मशीनों में परिभाषित करना अपेक्षाकृत आसान है। ऐसा इसलिए है क्योंकि μ ऑपरेटर असीमित संख्या में पुनरावृति कर सकता है, किन्तु कोई भी काउंटर मशीन अपनी निर्देश सूची के सीमित आकार के कारण असीमित संख्या में भिन्न-भिन्न रजिस्टरों को संबोधित नहीं कर सकती है। | ||
उदाहरण के लिए, मौलिक पुनरावर्ती ऑपरेटरों के उपरोक्त पदानुक्रम को नुथ के अप-एरो नोटेशन में उच्च-क्रम वाले तीर संचालन में घातांक से आगे बढ़ाया जा सकता है। किसी भी निश्चित <math>k</math> के लिए , प्रोग्राम <math>Q(x, y) = x \uparrow^k y</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 917: | 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 936: | 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: ट्यूरिंग मशीन को दो स्टैक द्वारा अनुकरण किया जा सकता है।=== | ||
ट्यूरिंग मशीन में एफएसएम और अनंत टेप होता है, जो प्रारंभ में शून्य से भरा होता है, जिस पर मशीन और शून्य लिख सकती है। किसी भी समय, मशीन का रीड/राइट हेड टेप पर सेल की ओर संकेत करता है। उस बिंदु पर इस टेप को संकल्पनात्मक रूप से आधा काटा जा सकता है। टेप के प्रत्येक आधे भाग को [[स्टैक (डेटा संरचना)]] के रूप में माना जा सकता है, जहां शीर्ष रीड/राइट हेड के निकटतम सेल है, और निचला भाग हेड से कुछ दूरी पर है, नीचे से परे टेप पर सभी शून्य हैं। तदनुसार, ट्यूरिंग मशीन को एफएसएम प्लस दो स्टैक द्वारा अनुकरण किया जा सकता है। सिर को बाएँ या दाएँ करके संग्रह से थोड़ा सा उठाकर दूसरे संग्रह पर पुश के समान है। लिखना किसी चीज़ को आगे बढ़ाने से पहले उसे परिवर्तन के समान है। | ट्यूरिंग मशीन में एफएसएम और अनंत टेप होता है, जो प्रारंभ में शून्य से भरा होता है, जिस पर मशीन और शून्य लिख सकती है। किसी भी समय, मशीन का रीड/राइट हेड टेप पर सेल की ओर संकेत करता है। उस बिंदु पर इस टेप को संकल्पनात्मक रूप से आधा काटा जा सकता है। टेप के प्रत्येक आधे भाग को [[स्टैक (डेटा संरचना)]] के रूप में माना जा सकता है, इस प्रकार जहां शीर्ष रीड/राइट हेड के निकटतम सेल है, और निचला भाग हेड से कुछ दूरी पर है, नीचे से परे टेप पर सभी शून्य हैं। तदनुसार, ट्यूरिंग मशीन को एफएसएम प्लस दो स्टैक द्वारा अनुकरण किया जा सकता है। सिर को बाएँ या दाएँ करके संग्रह से थोड़ा सा उठाकर दूसरे संग्रह पर पुश के समान है। लिखना किसी चीज़ को आगे बढ़ाने से पहले उसे परिवर्तन के समान है। | ||
=== | ===फेज 2: स्टैक को दो काउंटरों द्वारा अनुकरण किया जा सकता है।=== | ||
शून्य और वाले स्टैक को दो काउंटरों द्वारा अनुकरण किया जा सकता है जब स्टैक पर बिट्स को बाइनरी संख्या का प्रतिनिधित्व करने के रूप में माना जाता है (स्टैक पर सबसे ऊपरी बिट सबसे कम महत्वपूर्ण बिट होता है)। स्टैक पर शून्य लगाना संख्या को दोगुना करने के समान है। जिसको पुश करके दोगुना करने और 1 जोड़ने के समान है। पॉपिंग 2 से विभाजित करने के समान है, जहां [[शेष]] वह बिट है जिसे पॉप किया गया था। दो काउंटर इस स्टैक का अनुकरण कर सकते हैं, जिसमें से काउंटर में संख्या होती है जिसका बाइनरी प्रतिनिधित्व स्टैक पर बिट्स का प्रतिनिधित्व करता है, और दूसरे काउंटर का उपयोग स्क्रैचपैड के रूप में किया जाता है। पहले काउंटर में संख्या को दोगुना करने के लिए, एफएसएम दूसरे काउंटर को शून्य से प्रारंभ कर सकता है, फिर पहले काउंटर को पुनरावृति बार घटा सकता है और दूसरे काउंटर को दो बार बढ़ा सकता है। यह तब तक जारी रहता है जब तक पहला काउंटर शून्य तक नहीं पहुंच जाता है। उस समय, दूसरा काउंटर दोगुनी संख्या रहता है। काउंटर को दो बार घटाकर और दूसरे को बार बढ़ाकर, और तब तक दोहराते हुए जब तक कि पहला काउंटर शून्य तक न पहुंच जाए, हॉल्टिंग की जाती है। शेष को इस बात से निर्धारित किया जा सकता है कि क्या यह सम या [[विषम संख्या]] में चरणों के पश्चात् शून्य पर पहुंच गया है, जहां चरणों की संख्या की समता एफएसएम की स्थिति में एन्कोड की गई है। | शून्य और वाले स्टैक को दो काउंटरों द्वारा अनुकरण किया जा सकता है जब स्टैक पर बिट्स को बाइनरी संख्या का प्रतिनिधित्व करने के रूप में माना जाता है (स्टैक पर सबसे ऊपरी बिट सबसे कम महत्वपूर्ण बिट होता है)। स्टैक पर शून्य लगाना संख्या को दोगुना करने के समान है। जिसको पुश करके दोगुना करने और 1 जोड़ने के समान है। इस प्रकार पॉपिंग 2 से विभाजित करने के समान है, जहां [[शेष]] वह बिट है जिसे पॉप किया गया था। दो काउंटर इस स्टैक का अनुकरण कर सकते हैं, जिसमें से काउंटर में संख्या होती है जिसका बाइनरी प्रतिनिधित्व स्टैक पर बिट्स का प्रतिनिधित्व करता है, और दूसरे काउंटर का उपयोग स्क्रैचपैड के रूप में किया जाता है। पहले काउंटर में संख्या को दोगुना करने के लिए, एफएसएम दूसरे काउंटर को शून्य से प्रारंभ कर सकता है, फिर पहले काउंटर को पुनरावृति बार घटा सकता है और दूसरे काउंटर को दो बार बढ़ा सकता है। यह तब तक जारी रहता है जब तक पहला काउंटर शून्य तक नहीं पहुंच जाता है। उस समय, दूसरा काउंटर दोगुनी संख्या रहता है। इस प्रकार काउंटर को दो बार घटाकर और दूसरे को बार बढ़ाकर, और तब तक दोहराते हुए जब तक कि पहला काउंटर शून्य तक न पहुंच जाए, हॉल्टिंग की जाती है। शेष को इस बात से निर्धारित किया जा सकता है कि क्या यह सम या [[विषम संख्या]] में चरणों के पश्चात् शून्य पर पहुंच गया है, जहां चरणों की संख्या की समता एफएसएम की स्थिति में एन्कोड की गई है। | ||
=== | ===फेज 3: चार काउंटरों को दो काउंटरों द्वारा अनुकरण किया जा सकता है।=== | ||
पहले की तरह, काउंटरों में से का उपयोग स्क्रैचपैड के रूप में किया जाता है। दूसरे में [[पूर्णांक]] है जिसका [[अभाज्य संख्या]] [[गुणन]]खंड 2<sup>''a''</sup>3<sup>''b''</sup>5<sup>''c''</sup>7<sup>''d''</sup> है. घातांक a, b, c और d को चार आभासी काउंटरों के रूप में माना जा सकता है जिन्हें (गोडेल नंबरिंग के माध्यम से) ही वास्तविक काउंटर में पैक किया जा रहा है। यदि वास्तविक काउंटर को शून्य पर सेट किया जाता है और फिर बार बढ़ाया जाता है, तो यह सभी वर्चुअल काउंटरों को शून्य पर सेट करने के समान है। यदि वास्तविक काउंटर को दोगुना कर दिया जाता है, तो यह a को बढ़ाने के समान है, और यदि इसे आधा कर दिया जाता है, तो यह a को घटाने के समान है। समान प्रक्रिया द्वारा, इसे 3 से गुणा या विभाजित किया जा सकता | |||