रजिस्टर मशीन: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
{{Short description|Type of abstract machine}}
{{Short description|Type of abstract machine}}
[[गणितीय तर्क]] और [[सैद्धांतिक कंप्यूटर विज्ञान]] में एक रजिस्टर मशीन [[अमूर्त मशीन]]ों का एक सामान्य वर्ग है जिसका उपयोग [[ट्यूरिंग मशीन]] के समान तरीके से किया जाता है। सभी मॉडल [[ट्यूरिंग पूर्णता]] हैं।
[[गणितीय तर्क]] और [[सैद्धांतिक कंप्यूटर विज्ञान]] में '''रजिस्टर मशीन''' [[अमूर्त मशीन|वर्चुअल मशीनों]] का सामान्य वर्ग है जिसका उपयोग [[ट्यूरिंग मशीन]] की सरल विधियो द्वारा किया जाता है। यह सभी प्रारूपों में [[ट्यूरिंग पूर्णता]] पर निर्भर रहती हैं।


== अवलोकन ==
== अवलोकन ==
रजिस्टर मशीन को उसका नाम एक या एक से अधिक [[प्रोसेसर रजिस्टर]] के उपयोग से मिलता है। ट्यूरिंग मशीन द्वारा उपयोग किए जाने वाले टेप और सिर के विपरीत, मॉडल एकाधिक, विशिष्ट रूप से संबोधित रजिस्टरों का उपयोग करता है, जिनमें से प्रत्येक में एक सकारात्मक [[पूर्णांक]] होता है।
रजिस्टर मशीन को उसका नाम [[प्रोसेसर रजिस्टर]] के उपयोग से मिला हैं। ट्यूरिंग मशीन द्वारा उपयोग किए जाने वाले टेप और सिर के विपरीत, मॉडल एकाधिक, विशिष्ट रूप से संबोधित रजिस्टरों का उपयोग करता है, जिनमें से प्रत्येक में सकारात्मक [[पूर्णांक]] होता है।


साहित्य में कम से कम चार उप-वर्ग पाए जाते हैं, यहाँ सबसे आदिम से [[कंप्यूटर]] की तरह सबसे अधिक सूचीबद्ध हैं:
साहित्य रूप से कम से कम चार उप-वर्ग बनाए गए हैं, जिसमे सबसे विशेष रूप से [[कंप्यूटर]] के उपयोग के माध्यम से सबसे अधिक सरलता से सूचीबद्ध हैं:
* [[काउंटर मशीन]] - कंप्यूटर हार्डवेयर का सबसे आदिम और कम सैद्धांतिक मॉडल। अप्रत्यक्ष संबोधन का अभाव है। [[हार्वर्ड वास्तुकला]] के तरीके में निर्देश परिमित राज्य मशीन में हैं।
* [[काउंटर मशीन]] - कंप्यूटर हार्डवेयर का सबसे विशेष और कम सैद्धांतिक मॉडल में किया जाता हैं। इसमें अप्रत्यक्ष संबोधन का अभाव रहता है। [[हार्वर्ड वास्तुकला|हार्वर्ड संरचना]] के तरीके में निर्देश परिमित स्थिति मशीन में हैं।
*[[सूचक मशीन]] - काउंटर मशीन और रैम मॉडल का मिश्रण। किसी भी मॉडल की तुलना में कम सामान्य और अधिक अमूर्त। हार्वर्ड वास्तुकला के तरीके में निर्देश परिमित राज्य मशीन में हैं।
*[[सूचक मशीन]] - काउंटर मशीन और रैम मॉडल का मिश्रण। किसी भी मॉडल की तुलना में कम सामान्य और अधिक वर्चुअल। हार्वर्ड संरचना के तरीके में निर्देश परिमित स्थिति मशीन में हैं।
*[[रैंडम-एक्सेस मशीन]] (रैम) - एक काउंटर मशीन जिसमें इनडायरेक्ट एड्रेसिंग और, आमतौर पर, एक संवर्धित निर्देश सेट होता है। हार्वर्ड वास्तुकला के तरीके में निर्देश परिमित राज्य मशीन में हैं।
*[[रैंडम-एक्सेस मशीन]] (रैम) - काउंटर मशीन जिसमें इनडायरेक्ट एड्रेसिंग और, सामान्यतः, संवर्धित निर्देश सेट होता है। हार्वर्ड संरचना के तरीके में निर्देश परिमित स्थिति मशीन में हैं।
*[[रैंडम-एक्सेस संग्रहीत प्रोग्राम मशीन]] मॉडल (आरएएसपी) - [[यूनिवर्सल ट्यूरिंग मशीन]] के अनुरूप अपने रजिस्टरों में निर्देशों के साथ एक रैम; इस प्रकार यह [[वॉन न्यूमैन वास्तुकला]] का एक उदाहरण है। लेकिन एक कंप्यूटर के विपरीत, मॉडल प्रभावी रूप से अनंत रजिस्टरों के साथ ''आदर्श'' है (और यदि उपयोग किया जाता है, प्रभावी रूप से अनंत विशेष रजिस्टर जैसे एक संचायक)। कंप्यूटर की तुलना में, निर्देश सेट संख्या और जटिलता में बहुत कम होता है।
*[[रैंडम-एक्सेस संग्रहीत प्रोग्राम मशीन]] मॉडल (आरएएसपी) - [[यूनिवर्सल ट्यूरिंग मशीन]] के अनुरूप अपने रजिस्टरों में निर्देशों के साथ रैम को उपयोग किया जाता हैं और इस प्रकार यह [[वॉन न्यूमैन वास्तुकला|वॉन न्यूमैन संरचना]] का उदाहरण है। किन्तु कंप्यूटर के विपरीत, मॉडल प्रभावी रूप से अनंत रजिस्टरों के साथ ''आदर्श'' रूपों में उपयोग में लाया जाता हैं (और यदि उपयोग किया जाता है, तो प्रभावी रूप से अनंत विशेष रजिस्टर जैसे संचायक को संलग्न किया जाता हैं)। इस प्रकार कंप्यूटर की तुलना में, निर्देश सेट संख्या और जटिलता में बहुत कम होता है।
 
कोई भी ठीक से परिभाषित रजिस्टर मशीन मॉडल ट्यूरिंग पूर्णता है। कम्प्यूटेशनल गति मॉडल की बारीकियों पर बहुत निर्भर है।
 
व्यावहारिक कंप्यूटर विज्ञान में, एक समान अवधारणा जिसे [[आभासी मशीन]] के रूप में जाना जाता है, का उपयोग कभी-कभी अंतर्निहित मशीन आर्किटेक्चर पर निर्भरता को कम करने के लिए किया जाता है। ऐसी मशीनों का उपयोग शिक्षण के लिए भी किया जाता है। रजिस्टर मशीन शब्द का प्रयोग कभी-कभी पाठ्यपुस्तकों में वर्चुअल मशीन को संदर्भित करने के लिए किया जाता है।<ref>[[Harold Abelson]] and [[Gerald Jay Sussman]] with Julie Sussman, [[Structure and Interpretation of Computer Programs]], [[MIT Press]], [[Cambridge, Massachusetts]], 2nd Ed, 1996</ref>


कोई भी ठीक से परिभाषित रजिस्टर मशीन मॉडल ट्यूरिंग पूर्णता होती है। कम्प्यूटरीकृत गति प्रारूप की विशेष रूप से बहुत निर्भर है।


व्यावहारिक कंप्यूटर विज्ञान में, समान अवधारणा जिसे [[आभासी मशीन|वर्चुअल मशीन]] के रूप में जाना जाता है, जिसका उपयोग कभी-कभी अंतर्निहित मशीन की संरचना पर निर्भरता को कम करने के लिए किया जाता है। ऐसी मशीनों का उपयोग शिक्षण के लिए भी किया जाता है। रजिस्टर मशीन शब्द का प्रयोग कभी-कभी पाठ्यपुस्तकों में वर्चुअल मशीन को संदर्भित करने के लिए किया जाता है।<ref>[[Harold Abelson]] and [[Gerald Jay Sussman]] with Julie Sussman, [[Structure and Interpretation of Computer Programs]], [[MIT Press]], [[Cambridge, Massachusetts]], 2nd Ed, 1996</ref>
== औपचारिक परिभाषा ==
== औपचारिक परिभाषा ==
एक रजिस्टर मशीन में शामिल हैं:
एक रजिस्टर मशीन में सम्मलित हैं:


# लेबल किए गए, असतत, असीमित रजिस्टरों की असीमित संख्या सीमा (क्षमता) में असीमित: रजिस्टरों का एक परिमित (या कुछ मॉडलों में अनंत) सेट <math>r_0 \ldots r_n</math> प्रत्येक को अनंत सीमा का माना जाता है और जिनमें से प्रत्येक में एक गैर-ऋणात्मक पूर्णांक (0, 1, 2, ...) होता है।<ref>". . . a denumerable sequence of registers numbered 1, 2, 3, ..., each of which can store any natural number 0, 1, 2, .... Each particular program, however, involves only a finite number of these registers, the others remaining empty (i.e. containing 0) throughout the computation." Shepherdson and Sturgis 1961:219. Lambek 1961:295 proposed: "a countably infinite set of ''locations'' (holes, wires, etc).</ref> रजिस्टर अपना अंकगणित कर सकते हैं, या एक या एक से अधिक विशेष रजिस्टर हो सकते हैं जो अंकगणित करते हैं उदा। एक संचायक और/या पता रजिस्टर। रैंडम-एक्सेस मशीन भी देखें।
# लेबल किए गए, असतत, असीमित रजिस्टरों की असीमित संख्या सीमा (क्षमता) में असीमित: रजिस्टरों का परिमित (या कुछ मॉडलों में अनंत) सेट <math>r_0 \ldots r_n</math> प्रत्येक को अनंत सीमा का माना जाता है और जिनमें से प्रत्येक में गैर-ऋणात्मक पूर्णांक (0, 1, 2, ...) होता है।<ref>". . . a denumerable sequence of registers numbered 1, 2, 3, ..., each of which can store any natural number 0, 1, 2, .... Each particular program, however, involves only a finite number of these registers, the others remaining empty (i.e. containing 0) throughout the computation." Shepherdson and Sturgis 1961:219. Lambek 1961:295 proposed: "a countably infinite set of ''locations'' (holes, wires, etc).</ref> रजिस्टर अपना अंकगणित कर सकते हैं, या इससे अधिक विशेष रजिस्टर हो सकते हैं जो अंकगणित करते हैं। उदाहरण के लिए संचायक और/या पता रजिस्टर तथा रैंडम-एक्सेस मशीन इसका मुख्य उदाहरण हैं।
#'टैली काउंटर या निशान':<ref>For example, Lambek 1961:295 proposed the use of pebbles, beads, etc.</ref> असतत, अप्रभेद्य वस्तुएं या मॉडल के लिए उपयुक्त केवल एक प्रकार के निशान। सबसे कम काउंटर मशीन मॉडल में, प्रत्येक अंकगणितीय ऑपरेशन के अनुसार केवल एक वस्तु/चिह्न को उसके स्थान/टेप से जोड़ा या हटाया जाता है। कुछ काउंटर मशीन मॉडल में (जैसे मेल्ज़ाक (1961), मिन्स्की (1961)) और अधिकांश रैम और आरएएसपी मॉडल में एक से अधिक ऑब्जेक्ट/मार्क को एक ऑपरेशन में जोड़ा या हटाया जा सकता है और आमतौर पर घटाव; कभी-कभी गुणा और/या भाग के साथ। कुछ मॉडलों में नियंत्रण संचालन होते हैं जैसे कॉपी (विभिन्न: मूव, लोड, स्टोर) जो एक क्रिया में रजिस्टर से रजिस्टर करने के लिए ऑब्जेक्ट्स/मार्क्स के क्लंप को स्थानांतरित करते हैं।
#'टैली काउंटर या निशान':<ref>For example, Lambek 1961:295 proposed the use of pebbles, beads, etc.</ref> असतत, अप्रभेद्य वस्तुएं या मॉडल के लिए उपयुक्त केवल प्रकार के निशान उपलब्ध रहते हैं। सबसे कम काउंटर मशीन मॉडल में, प्रत्येक अंकगणितीय ऑपरेशन के अनुसार केवल वस्तु/चिह्न को उसके स्थान/टेप से जोड़ा या हटाया जाता है। कुछ काउंटर मशीन मॉडल में (जैसे मेल्ज़ाक (1961), मिन्स्की (1961)) और अधिकांश रैम और आरएएसपी मॉडल में से अधिक ऑब्जेक्ट/मार्क को ऑपरेशन में जोड़ा या हटाया जा सकता है और सामान्यतः घटाव के लिए तथा कभी-कभी गुणा और/या भाग के साथ उपयोग किया जाता हैं। कुछ मॉडलों में नियंत्रण संचालन होते हैं जैसे कॉपी (विभिन्न: मूव, लोड, स्टोर) जो क्रिया में रजिस्टर से रजिस्टर करने के लिए ऑब्जेक्ट्स/मार्क्स के क्लंप को स्थानांतरित करते हैं।
#A (बहुत) निर्देशों का सीमित सेट: निर्देश दो वर्गों में विभाजित होते हैं: अंकगणित और नियंत्रण। निर्देश-सेट बनाने के लिए निर्देश दो वर्गों से तैयार किए जाते हैं, जैसे कि एक निर्देश सेट को मॉडल को ट्यूरिंग समतुल्य होने की अनुमति देनी चाहिए (यह किसी भी आंशिक पुनरावर्ती फ़ंक्शन की गणना करने में सक्षम होना चाहिए)।
#A (बहुत) निर्देशों का सीमित सेट: निर्देश दो वर्गों अंकगणित और नियंत्रण में विभाजित होते हैं। निर्देश-सेट बनाने के लिए निर्देश दो वर्गों से तैयार किए जाते हैं, जैसे कि निर्देश सेट को मॉडल को ट्यूरिंग समतुल्य होने की अनुमति देनी चाहिए (यह किसी भी आंशिक पुनरावर्ती फ़ंक्शन की गणना करने में सक्षम होना चाहिए)।
##अंकगणित: अंकगणितीय निर्देश सभी रजिस्टरों पर या सिर्फ एक विशेष रजिस्टर (जैसे संचायक) पर काम कर सकते हैं। वे ''आमतौर पर'' निम्नलिखित सेटों में से चुने जाते हैं (लेकिन अपवाद लाजिमी हैं):
##अंकगणित: अंकगणितीय निर्देश सभी रजिस्टरों पर या सिर्फ विशेष रजिस्टर (जैसे संचायक) पर कार्य कर सकते हैं। वे ''सामान्यतः'' निम्नलिखित सेटों में से चुने जाते हैं (किन्तु अपवाद सामान्य हैं):
##*काउंटर मशीन: { इंक्रीमेंट (आर), डिक्रीमेंट (आर), क्लियर-टू-जीरो (आर)}
##*काउंटर मशीन: { इंक्रीमेंट (आर), डिक्रीमेंट (आर), क्लियर-टू-जीरो (आर)}
##*कम RAM, RASP: { इंक्रीमेंट (r), डिक्रीमेंट (r), क्लियर-टू-जीरो (r), लोड-तत्काल-स्थिर k, जोड़ें (r)<sub>1</sub>,आर<sub>2</sub>), उचित-घटाना (आर<sub>1</sub>,आर<sub>2</sub>), इंक्रीमेंट एक्युमुलेटर, डिक्रीमेंट एक्युमुलेटर, क्लीयर एक्युमुलेटर, रजिस्टर आर के एक्युमुलेटर कंटेंट में जोड़ें, रजिस्टर आर के एक्युमुलेटर कंटेंट से प्रॉपर-घटाना, }
##*कम रैम, रैस्प: { इंक्रीमेंट (r), डिक्रीमेंट (r), क्लियर-टू-जीरो (r), लोड-तत्काल-स्थिर k, जोड़ें (r)<sub>1</sub>,आर<sub>2</sub>), उचित-घटाना (आर<sub>1</sub>,आर<sub>2</sub>), इंक्रीमेंट एक्युमुलेटर, डिक्रीमेंट एक्युमुलेटर, क्लीयर एक्युमुलेटर, रजिस्टर आर के एक्युमुलेटर कंटेंट में जोड़ें, रजिस्टर आर के एक्युमुलेटर कंटेंट से प्रॉपर-घटाना, }
##*संवर्धित RAM, RASP: सभी कम किए गए निर्देश प्लस: {गुणा करें, विभाजित करें, विभिन्न बूलियन बिट-वाइज़ (लेफ्ट-शिफ्ट, बिट टेस्ट, आदि)}
##*संवर्धित रैम, रैस्प: सभी कम किए गए निर्देश प्लस: {गुणा करें, विभाजित करें, विभिन्न बूलियन बिट-वाइज़ (लेफ्ट-शिफ्ट, बिट टेस्ट, आदि)}
##नियंत्रण:
##नियंत्रण:
##*काउंटर मशीन मॉडल: वैकल्पिक {कॉपी (आर<sub>1</sub>,आर<sub>2</sub>)}
##*काउंटर मशीन मॉडल: वैकल्पिक {कॉपी (R<sub>1</sub>,R<sub>2</sub>)}
##*RAM और RASP मॉडल: अधिकांश में {प्रतिलिपि (r<sub>1</sub>,आर<sub>2</sub>) }, या {आर से लोड संचायक, आर में स्टोर संचायक, तत्काल स्थिरांक के साथ लोड संचयकर्ता}
##*रैम और रैस्प मॉडल: अधिकांश में {प्रतिलिपि (R<sub>1</sub>,R<sub>2</sub>) }, या {आर से लोड संचायक, आर में स्टोर संचायक, तत्काल स्थिरांक के साथ लोड संचयकर्ता}
##*सभी मॉडल: एक रजिस्टर के परीक्षण के बाद कम से कम एक सशर्त छलांग (शाखा, गोटो)। { जंप-इफ-जीरो, जंप-इफ-नॉट-जीरो (यानी जंप-इफ-पॉजिटिव), जंप-इफ-इक्वल, जंप-इफ-नॉट इक्वल}
##*सभी मॉडल: रजिस्टर के परीक्षण के बाद कम से कम सशर्त छलांग (शाखा, गोटो)। { जंप-इफ-जीरो, जंप-इफ-नॉट-जीरो (अर्ताथ जंप-इफ-पॉजिटिव), जंप-इफ-इक्वल, जंप-इफ-नॉट इक्वल}
##*सभी मॉडल वैकल्पिक: {बिना शर्त प्रोग्राम जंप (गोटो)}
##*सभी मॉडल वैकल्पिक: {बिना शर्त प्रोग्राम जंप (गोटो)}
## 'रजिस्टर-एड्रेसिंग विधि':
## 'रजिस्टर-एड्रेसिंग विधि':
##*काउंटर मशीन: कोई अप्रत्यक्ष संबोधन नहीं, अत्यधिक एटमाइज्ड मॉडल में तत्काल ऑपरेंड संभव है
##*काउंटर मशीन: कोई अप्रत्यक्ष संबोधन नहीं, अत्यधिक एटमाइज्ड मॉडल में तत्काल ऑपरेंड संभव है
##*RAM और RASP: इनडायरेक्ट एड्रेसिंग उपलब्ध, तत्काल ऑपरेंड विशिष्ट
##*रैम और रैस्प: इनडायरेक्ट एड्रेसिंग उपलब्ध, तत्काल ऑपरेंड विशिष्ट
##'इनपुट-आउटपुट': सभी मॉडलों में वैकल्पिक
##'इनपुट-आउटपुट': सभी मॉडलों में वैकल्पिक
#'राज्य रजिस्टर': एक विशेष निर्देश रजिस्टर आईआर, परिमित और उपरोक्त रजिस्टरों से अलग, वर्तमान निर्देश को निष्पादित करने के लिए संग्रहीत करता है और इसका पता निर्देशों की तालिका में होता है; यह रजिस्टर और इसकी तालिका परिमित अवस्था मशीन में स्थित है।
#'स्थिति रजिस्टर': विशेष निर्देश रजिस्टर आईआर, परिमित और उपरोक्त रजिस्टरों से अलग, वर्तमान निर्देश को निष्पादित करने के लिए संग्रहीत करता है और इसका पता निर्देशों की तालिका में होता है; यह रजिस्टर और इसकी तालिका परिमित अवस्था मशीन में स्थित है।
#*आईआर सभी मॉडलों के लिए ऑफ-लिमिट है। रैम और आरएएसपी के मामले में, एक रजिस्टर के पते का निर्धारण करने के प्रयोजनों के लिए, मॉडल या तो (i) सीधे संबोधित करने के मामले में - तालिका द्वारा निर्दिष्ट पता और आईआर में अस्थायी रूप से स्थित या (ii) का चयन कर सकता है। अप्रत्यक्ष पते के मामले में - आईआर के निर्देश द्वारा निर्दिष्ट रजिस्टर की सामग्री।
#*आईआर सभी मॉडलों के लिए ऑफ-लिमिट है। रैम और आरएएसपी की स्थिति में, रजिस्टर के पते का निर्धारण करने के प्रयोजनों के लिए, मॉडल या तो (i) सीधे संबोधित करने की स्थिति में - तालिका द्वारा निर्दिष्ट पता और आईआर में अस्थायी रूप से स्थित या (ii) का चयन कर सकता है। अप्रत्यक्ष पते की स्थिति में - आईआर के निर्देश द्वारा निर्दिष्ट रजिस्टर की सामग्री उपलब्ध हैं।
#*IR RASP (या पारंपरिक कंप्यूटर) का प्रोग्राम काउंटर (PC) नहीं है। पीसी एक संचायक के समान एक और रजिस्टर है, लेकिन आरएएसपी के वर्तमान रजिस्टर-आधारित निर्देश की संख्या को धारण करने के लिए समर्पित है। इस प्रकार एक RASP के पास दो निर्देश/कार्यक्रम रजिस्टर होते हैं- (i) IR (परिमित राज्य मशीन का निर्देश रजिस्टर), और (ii) रजिस्टरों में स्थित कार्यक्रम के लिए एक पीसी (प्रोग्राम काउंटर)। (साथ ही साथ पीसी को समर्पित एक रजिस्टर, एक आरएएसपी प्रोग्राम-इंस्ट्रक्शन रजिस्टर (पीआईआर, आईआर, पीआर, आदि जैसे किसी भी नाम से जाने वाले) के लिए एक और रजिस्टर समर्पित कर सकता है।
#*आईआर रैस्प (या पारंपरिक कंप्यूटर) का प्रोग्राम काउंटर (PC) नहीं है। पीसी संचायक के समान और रजिस्टर है, किन्तु आरएएसपी के वर्तमान रजिस्टर-आधारित निर्देश की संख्या को धारण करने के लिए समर्पित है। इस प्रकार रैस्प के पास दो निर्देश/कार्यक्रम रजिस्टर होते हैं- (i) IR (परिमित स्थिति मशीन का निर्देश रजिस्टर), और (ii) रजिस्टरों में स्थित कार्यक्रम के लिए पीसी (प्रोग्राम काउंटर)। (साथ ही साथ पीसी को समर्पित रजिस्टर, आरएएसपी प्रोग्राम-इंस्ट्रक्शन रजिस्टर (पीआईआर, आईआर, पीआर, आदि जैसे किसी भी नाम से जाने वाले) के लिए और रजिस्टर समर्पित कर सकता है।
#'लेबल निर्देशों की सूची, आमतौर पर अनुक्रमिक क्रम में': निर्देशों की एक सीमित सूची <math>I_1 \ldots I_m</math>. काउंटर मशीन, रैंडम-एक्सेस मशीन (रैम) और पॉइंटर मशीन के मामले में निर्देश स्टोर परिमित राज्य मशीन की तालिका में है; इस प्रकार ये मॉडल हार्वर्ड आर्किटेक्चर के उदाहरण हैं। आरएएसपी के मामले में प्रोग्राम स्टोर रजिस्टरों में है; इस प्रकार यह वॉन न्यूमैन वास्तुकला का एक उदाहरण है। रैंडम-एक्सेस मशीन और रैंडम-एक्सेस स्टोर-प्रोग्राम मशीन भी देखें। <br>आमतौर पर, [[कंप्यूटर प्रोग्राम]] की तरह, निर्देश अनुक्रमिक क्रम में सूचीबद्ध होते हैं; जब तक कूदना सफल नहीं होता तब तक डिफ़ॉल्ट अनुक्रम संख्यात्मक क्रम में जारी रहता है। इसका एक अपवाद एबैकस (लैम्बेक (1961), मिन्स्की (1961)) काउंटर मशीन मॉडल है- प्रत्येक निर्देश में कम से कम एक अगला निर्देश पहचानकर्ता z होता है, और सशर्त शाखा में दो होते हैं।
#'लेबल निर्देशों की सूची, सामान्यतः अनुक्रमिक क्रम में': निर्देशों की सीमित सूची <math>I_1 \ldots I_m</math>. काउंटर मशीन, रैंडम-एक्सेस मशीन (रैम) और पॉइंटर मशीन की स्थिति में निर्देश स्टोर परिमित स्थिति मशीन की तालिका में है; इस प्रकार ये मॉडल हार्वर्ड संरचना के उदाहरण हैं। आरएएसपी की स्थिति में प्रोग्राम स्टोर रजिस्टरों में है; इस प्रकार यह वॉन न्यूमैन संरचना का उदाहरण है। रैंडम-एक्सेस मशीन और रैंडम-एक्सेस स्टोर-प्रोग्राम मशीन भी देखें। <br>सामान्यतः, [[कंप्यूटर प्रोग्राम]] की तरह, निर्देश अनुक्रमिक क्रम में सूचीबद्ध होते हैं; जब तक कूदना सफल नहीं होता तब तक डिफ़ॉल्ट अनुक्रम संख्यात्मक क्रम में जारी रहता है। इसका अपवाद एबैकस (लैम्बेक (1961), मिन्स्की (1961)) काउंटर मशीन मॉडल है- प्रत्येक निर्देश में कम से कम अगला निर्देश पहचानकर्ता z होता है, और सशर्त शाखा में दो होते हैं।
#*ध्यान दें कि अबेकस मॉडल दो निर्देशों को जोड़ता है, JZ फिर DEC: उदा. { कांग्रेस (आर, जेड), जेडडीईसी (आर, जेड<sub>true</sub>, साथ<sub>false</sub> ) }.<br>सशर्त व्यंजक IF r=0 THEN z के बारे में अधिक जानकारी के लिए [[मैककार्थी औपचारिकता]] देखें<sub>true</sub> अन्य जेड<sub>false</sub>(सीएफ मैककार्थी (1960))।
#*ध्यान दें कि अबेकस मॉडल दो निर्देशों को जोड़ता है, JZ फिर DEC: उदा. { कांग्रेस (आर, जेड), जेडडीईसी (आर, जेड<sub>true</sub>, साथ<sub>false</sub> ) }.<br>सशर्त व्यंजक IF r=0 THEN z के बारे में अधिक जानकारी के लिए [[मैककार्थी औपचारिकता]] देखें<sub>true</sub> अन्य जेड<sub>false</sub>(सीएफ मैककार्थी (1960))।


== रजिस्टर मशीन मॉडल का ऐतिहासिक विकास ==
== रजिस्टर मशीन मॉडल का ऐतिहासिक विकास ==


1950 के दशक की शुरुआत में दो रुझान दिखाई दिए- पहला कंप्यूटर को ट्यूरिंग मशीन के रूप में चिह्नित करने के लिए, दूसरा कंप्यूटर जैसे मॉडल को परिभाषित करने के लिए-अनुक्रमिक निर्देश अनुक्रम और सशर्त कूद वाले मॉडल-एक ट्यूरिंग मशीन की शक्ति के साथ, यानी एक तथाकथित ट्यूरिंग तुल्यता। इस काम की आवश्यकता दो कठिन समस्याओं के संदर्भ में की गई थी: [[एमिल पोस्ट]] द्वारा प्रस्तुत अघुलनशील शब्द समस्या- टैग की उनकी समस्या- और हिल्बर्ट की समस्याओं की बहुत कठिन समस्या- [[डायोफैंटाइन समीकरण]]ों के आसपास 10वां प्रश्न। शोधकर्ता ट्यूरिंग-समतुल्य मॉडल की खोज कर रहे थे जो प्रकृति में कम तार्किक और अधिक अंकगणितीय थे (cf Melzak (1961) पृष्ठ 281, शेफर्डसन-स्टर्गिस (1963) पृष्ठ 218)।
1950 के दशक की प्रारंभ में दो रुझान दिखाई दिए- पहला कंप्यूटर को ट्यूरिंग मशीन के रूप में चिह्नित करने के लिए, दूसरा कंप्यूटर जैसे मॉडल को परिभाषित करने के लिए-अनुक्रमिक निर्देश अनुक्रम और सशर्त कूद वाले मॉडल-एक ट्यूरिंग मशीन की शक्ति के साथ, अर्ताथ तथाकथित ट्यूरिंग तुल्यता। इस कार्य की आवश्यकता दो कठिन समस्याओं के संदर्भ में की गई थी: [[एमिल पोस्ट]] द्वारा प्रस्तुत अघुलनशील शब्द समस्या- टैग की उनकी समस्या- और हिल्बर्ट की समस्याओं की बहुत कठिन समस्या- [[डायोफैंटाइन समीकरण]] के आसपास 10वां प्रश्न हैं। शोधकर्ता ट्यूरिंग-समतुल्य मॉडल की खोज कर रहे थे जो प्रकृति में कम तार्किक और अधिक अंकगणितीय थे (cf Melzak (1961) पृष्ठ 281, शेफर्डसन-स्टर्गिस (1963) पृष्ठ 218)।


पहली प्रवृत्ति-कंप्यूटर के लक्षण वर्णन की ओर-लगती है<ref>See the "Note" in Shepherdson and Sturgis 1963:219. In their Appendix A the authors follow up with a listing and discussions of Kaphengst's, Ershov's and Péter's instruction sets (cf p. 245ff).</ref> हैंस हेमीज़ (1954), रोज़ा पेटर (1958), और [[हेंज कफेंग्स्ट]] (1959) के साथ, हाओ वांग (अकादमिक) (1954, 1957) के साथ दूसरी प्रवृत्ति और, जैसा कि ऊपर उल्लेख किया गया है, [[Zdzislaw अलेक्जेंडर मेल्ज़ाक]] (1961) द्वारा आगे बढ़ाया गया, [[जोआचिम लैम्बेक]] (1961) और [[मार्विन मिंस्की]] (1961, 1967)।
पहली प्रवृत्ति-कंप्यूटर के लक्षण वर्णन की ओर-लगती है<ref>See the "Note" in Shepherdson and Sturgis 1963:219. In their Appendix A the authors follow up with a listing and discussions of Kaphengst's, Ershov's and Péter's instruction sets (cf p. 245ff).</ref> हैंस हेमीज़ (1954), रोज़ा पेटर (1958), और [[हेंज कफेंग्स्ट]] (1959) के साथ, हाओ वांग (अकादमिक) (1954, 1957) के साथ दूसरी प्रवृत्ति और, जैसा कि ऊपर उल्लेख किया गया है, [[Zdzislaw अलेक्जेंडर मेल्ज़ाक]] (1961) द्वारा आगे बढ़ाया गया, [[जोआचिम लैम्बेक]] (1961) और [[मार्विन मिंस्की]] (1961, 1967)।


पिछले पांच नामों को स्पष्ट रूप से [[यूरी मटियासेविच]] द्वारा उसी क्रम में सूचीबद्ध किया गया है। वह इसके साथ चलता है:
पिछले पांच नामों को स्पष्ट रूप से [[यूरी मटियासेविच]] द्वारा उसी क्रम में सूचीबद्ध किया गया है। वह इसके साथ चलता है:
: रजिस्टर मशीनें [कुछ लेखक काउंटर-मशीन के पर्यायवाची रजिस्टर मशीन का उपयोग करते हैं] डायोफैंटाइन समीकरणों के निर्माण के लिए विशेष रूप से उपयुक्त हैं। ट्यूरिंग मशीनों की तरह, उनके पास बहुत ही आदिम निर्देश हैं और, इसके अलावा, वे संख्याओं से निपटते हैं (यूरी मटियासेविच (1993), हिल्बर्ट की दसवीं समस्या, पुस्तक के अध्याय 5 की टिप्पणी, http://logic.pdmi.ras.ru/ पर युमैट/H10Pbook/commch_5htm. )
: रजिस्टर मशीनें [कुछ लेखक काउंटर-मशीन के पर्यायवाची रजिस्टर मशीन का उपयोग करते हैं] डायोफैंटाइन समीकरणों के निर्माण के लिए विशेष रूप से उपयुक्त हैं। ट्यूरिंग मशीनों की तरह, उनके पास बहुत ही विशेष निर्देश हैं और, इसके अलावा, वे संख्याओं से निपटते हैं (यूरी मटियासेविच (1993), हिल्बर्ट की दसवीं समस्या, पुस्तक के अध्याय 5 की टिप्पणी, http://logic.pdmi.ras.ru/ पर युमैट/H10Pbook/commch_5htm. )


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


इतिहास की शुरुआत वांग के मॉडल से होती है।
इतिहास की प्रारंभ वांग के मॉडल से होती है।


=== वांग का (1954, 1957) मॉडल: पोस्ट-ट्यूरिंग मशीन ===
=== वांग का (1954, 1957) मॉडल: पोस्ट-ट्यूरिंग मशीन ===
वैंग का काम एमिल पोस्ट (1936) के पेपर से हुआ और वैंग को उनकी [[वैंग बी-मशीन]] की परिभाषा तक ले गया- एक दो-प्रतीक पोस्ट-ट्यूरिंग मशीन कम्प्यूटेशन मॉडल जिसमें केवल चार परमाणु निर्देश थे:
वैंग का कार्य एमिल पोस्ट (1936) के पेपर से हुआ और वैंग को उनकी [[वैंग बी-मशीन]] की परिभाषा तक ले गया- दो-प्रतीक पोस्ट-ट्यूरिंग मशीन कम्प्यूटेशन मॉडल जिसमें केवल चार परमाणु निर्देश थे:
: {बाएं, दाएं, प्रिंट, JUMP_if_marked_to_instruction_z}
: {बाएं, दाएं, प्रिंट, JUMP_if_marked_to_instruction_z}


इन चारों को दोनों वांग (1954, 1957) और फिर सी. वाई. ली (1961) ने पोस्ट सेट {ERASE} से एक और निर्देश जोड़ा, और फिर एक पोस्ट की बिना शर्त छलांग {JUMP_to_instruction_z} (या चीजों को आसान बनाने के लिए, सशर्त कूद JUMP_IF_blank_to_instruction_z, या दोनों। ली ने इसे डब्ल्यू-मशीन मॉडल का नाम दिया:
इन चारों को दोनों वांग (1954, 1957) और फिर सी. वाई. ली (1961) ने पोस्ट सेट {ERASE} से और निर्देश जोड़ा, और फिर पोस्ट की बिना शर्त छलांग {JUMP_to_instruction_z} (या चीजों को सरल बनाने के लिए, सशर्त कूद JUMP_IF_blank_to_instruction_z, या दोनों। ली ने इसे डब्ल्यू-मशीन मॉडल का नाम दिया:
:{ बाएँ, दाएँ, प्रिंट करें, मिटाएँ, JUMP_if_marked, [शायद JUMP या JUMP_IF_blank] }
:{ बाएँ, दाएँ, प्रिंट करें, मिटाएँ, JUMP_if_marked, [शायद JUMP या JUMP_IF_blank] }


वांग ने आशा व्यक्त की कि उनका मॉडल ट्यूरिंग मशीनों के सिद्धांत और कंप्यूटर की व्यावहारिक दुनिया के बीच एक तालमेल (पृ. 63) होगा।
वांग ने आशा व्यक्त की कि उनका मॉडल ट्यूरिंग मशीनों के सिद्धांत और कंप्यूटर की व्यावहारिक दुनिया के बीच तालमेल (पृ. 63) होगा।


वांग का काम अत्यधिक प्रभावशाली था। हम उसे मिंस्की (1961) और (1967), मेल्ज़ाक (1961), शेफर्डसन और स्टर्गिस (1963) द्वारा संदर्भित पाते हैं। वास्तव में, शेफर्डसन और स्टर्गिस (1963) टिप्पणी करते हैं कि:
वांग का कार्य अत्यधिक प्रभावशाली था। हम उसे मिंस्की (1961) और (1967), मेल्ज़ाक (1961), शेफर्डसन और स्टर्गिस (1963) द्वारा संदर्भित पाते हैं। वास्तव में, शेफर्डसन और स्टर्गिस (1963) टिप्पणी करते हैं कि:
: ... हमने वैंग द्वारा सुझाई गई संगणना के व्यावहारिक और सैद्धांतिक पहलुओं के बीच एक कदम और आगे बढ़ने की कोशिश की है (पृ. 218)।
: ... हमने वैंग द्वारा सुझाई गई संगणना के व्यावहारिक और सैद्धांतिक पहलुओं के बीच कदम और आगे बढ़ने की कोशिश की है (पृ. 218)।


[[मार्टिन डेविस (गणितज्ञ)]] ने अंततः इस मॉडल को (2-प्रतीक) पोस्ट-ट्यूरिंग मशीन में विकसित किया।
[[मार्टिन डेविस (गणितज्ञ)]] ने अंततः इस मॉडल को (2-प्रतीक) पोस्ट-ट्यूरिंग मशीन में विकसित किया।
Line 70: Line 68:
वैंग/पोस्ट-ट्यूरिंग मॉडल के साथ कठिनाइयाँ:
वैंग/पोस्ट-ट्यूरिंग मॉडल के साथ कठिनाइयाँ:


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


: ... एक ट्यूरिंग मशीन में एक निश्चित अपारदर्शिता होती है... एक ट्यूरिंग मशीन (काल्पनिक) संचालन में धीमी होती है और आमतौर पर जटिल होती है। इससे इसे डिजाइन करना कठिन हो जाता है, और समय या भंडारण अनुकूलन या दो एल्गोरिदम की दक्षता के बीच तुलना जैसे मामलों की जांच करना भी कठिन हो जाता है। (मेल्ज़ाक (1961) पृष्ठ 281)
: ... ट्यूरिंग मशीन में निश्चित अपारदर्शिता होती है... ट्यूरिंग मशीन (काल्पनिक) संचालन में धीमी होती है और सामान्यतः जटिल होती है। इससे इसे डिजाइन करना कठिन हो जाता है, और समय या भंडारण अनुकूलन या दो एल्गोरिदम की दक्षता के बीच तुलना जैसे मामलों की जांच करना भी कठिन हो जाता है। (मेल्ज़ाक (1961) पृष्ठ 281)


: ... हालांकि मुश्किल नहीं है ... प्रमाण दो कारणों से जटिल और थकाऊ हैं: (1) एक ट्यूरिंग मशीन में केवल सिर होता है ताकि एक अंक पर संचालन के बहुत छोटे चरणों में गणना को तोड़ने के लिए बाध्य हो . (2) इसमें केवल एक टेप होता है जिससे किसी को उस नंबर को खोजने के लिए कुछ परेशानी में पड़ना पड़ता है जिस पर वह काम करना चाहता है और उसे अन्य नंबरों से अलग रखता है (शेफर्डसन और स्टर्गिस (1963) पृष्ठ 218)।
: ... चूंकि मुश्किल नहीं है ... प्रमाण दो कारणों से जटिल और थकाऊ हैं: (1) ट्यूरिंग मशीन में केवल सिर होता है जिससे कि अंक पर संचालन के बहुत छोटे चरणों में गणना को तोड़ने के लिए बाध्य हो . (2) इसमें केवल टेप होता है जिससे किसी को उस नंबर को खोजने के लिए कुछ परेशानी में पड़ना पड़ता है जिस पर वह कार्य करना चाहता है और उसे अन्य नंबरों से अलग रखता है (शेफर्डसन और स्टर्गिस (1963) पृष्ठ 218)।


दरअसल, [[ट्यूरिंग मशीन के उदाहरण]], पोस्ट-ट्यूरिंग मशीन और आंशिक फ़ंक्शन शो के उदाहरण के रूप में, काम जटिल हो सकता है।
दरअसल, [[ट्यूरिंग मशीन के उदाहरण]], पोस्ट-ट्यूरिंग मशीन और आंशिक फ़ंक्शन शो के उदाहरण के रूप में, कार्य जटिल हो सकता है।
<!-- Example: Multiply '''a''' x '''b''' = '''c''', for example: 3 x 4 = 12.
<!-- Example: Multiply '''a''' x '''b''' = '''c''', for example: 3 x 4 = 12.


Line 218: Line 216:
  |
  |
|}-->
|}-->




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


हमें केवल अपने निर्देशों को लिखने में सावधानी बरतनी है ताकि शून्य के लिए एक परीक्षण हो और घटने से पहले कूद जाए अन्यथा हमारी मशीन अंत से गिर जाएगी या अंत से टकरा जाएगी - हमारे पास आंशिक कार्य का एक उदाहरण होगा। घटने से पहले हमारी मशीन को हमेशा यह सवाल पूछना चाहिए: क्या टेप/काउंटर खाली है? यदि ऐसा है तो मैं घट नहीं सकता, अन्यथा मैं कर सकता हूँ।
हमें केवल अपने निर्देशों को लिखने में सावधानी बरतनी है जिससे कि शून्य के लिए परीक्षण हो और घटने से पहले कूद जाए अन्यथा हमारी मशीन अंत से गिर जाएगी या अंत से टकरा जाएगी - हमारे पास आंशिक कार्य का उदाहरण होगा। घटने से पहले हमारी मशीन को हमेशा यह सवाल पूछना चाहिए: क्या टेप/काउंटर खाली है? यदि ऐसा है तो मैं घट नहीं सकता, अन्यथा मैं कर सकता हूँ।


मिन्स्की (1961) और शेफर्डसन-स्टर्गिस (1963) साबित करते हैं कि केवल कुछ टेप- जितने कम एक-अभी भी मशीन को ट्यूरिंग समतुल्य होने की अनुमति देते हैं यदि टेप पर डेटा को गोडेल नंबर (या कुछ अन्य विशिष्ट रूप से एनकोडेबल-) के रूप में दर्शाया जाता है। डिकोडेबल नंबर); गणना आगे बढ़ने पर यह संख्या विकसित होगी। गोडेल संख्या एन्कोडिंग वाले एक टेप संस्करण में काउंटर मशीन को (i) गोडेल संख्या को एक स्थिरांक (संख्या 2 या 3) से गुणा करने में सक्षम होना चाहिए, और (ii) एक स्थिरांक (संख्या 2 या 3) से विभाजित करना चाहिए और कूदना चाहिए यदि शेष शून्य है। मिंस्की (1967) ने दिखाया कि इस विचित्र निर्देश सेट की आवश्यकता को {INC (r), JZDEC (r, z)} और सुविधा निर्देश {CLR (r), J (r)} में शिथिल किया जा सकता है यदि दो टेप उपलब्ध हैं . हालाँकि, एक साधारण गोडेलाइज़ेशन अभी भी आवश्यक है। उनके आरएएसपी मॉडल के संबंध में एल्गोट-रॉबिन्सन (1964) में एक समान परिणाम दिखाई देता है।
मिन्स्की (1961) और शेफर्डसन-स्टर्गिस (1963) साबित करते हैं कि केवल कुछ टेप- जितने कम एक-अभी भी मशीन को ट्यूरिंग समतुल्य होने की अनुमति देते हैं यदि टेप पर डेटा को गोडेल नंबर (या कुछ अन्य विशिष्ट रूप से एनकोडेबल-) के रूप में दर्शाया जाता है। डिकोडेबल नंबर); गणना आगे बढ़ने पर यह संख्या विकसित होगी। गोडेल संख्या एन्कोडिंग वाले टेप संस्करण में काउंटर मशीन को (i) गोडेल संख्या को स्थिरांक (संख्या 2 या 3) से गुणा करने में सक्षम होना चाहिए, और (ii) स्थिरांक (संख्या 2 या 3) से विभाजित करना चाहिए और कूदना चाहिए यदि शेष शून्य है। मिंस्की (1967) ने दिखाया कि इस विचित्र निर्देश सेट की आवश्यकता को {INC (r), JZDEC (r, z)} और सुविधा निर्देश {CLR (r), J (r)} में शिथिल किया जा सकता है यदि दो टेप उपलब्ध हैं . चूंकि, साधारण गोडेलाइज़ेशन अभी भी आवश्यक है। उनके आरएएसपी मॉडल के संबंध में एल्