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

From Vigyanwiki
No edit summary
No edit summary
 
(7 intermediate revisions by 3 users not shown)
Line 3: Line 3:


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


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


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


व्यावहारिक कंप्यूटर विज्ञान में, समान अवधारणा जिसे [[आभासी मशीन|वर्चुअल मशीन]] के रूप में जाना जाता है, जिसका उपयोग कभी-कभी अंतर्निहित मशीन की संरचना पर निर्भरता को कम करने के लिए किया जाता है। ऐसी मशीनों का उपयोग शिक्षण के लिए भी किया जाता है। रजिस्टर मशीन शब्द का प्रयोग कभी-कभी पाठ्यपुस्तकों में वर्चुअल मशीन को संदर्भित करने के लिए किया जाता है।<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 (बहुत) निर्देशों का सीमित सेट: निर्देश दो वर्गों अंकगणित और नियंत्रण में विभाजित होते हैं। निर्देश-सेट बनाने के लिए निर्देश दो वर्गों से तैयार किए जाते हैं, जैसे कि निर्देश सेट को मॉडल को ट्यूरिंग समतुल्य होने की अनुमति देनी चाहिए (यह किसी भी आंशिक पुनरावर्ती फ़ंक्शन की गणना करने में सक्षम होना चाहिए)।
##अंकगणित: अंकगणितीय निर्देश सभी रजिस्टरों पर या सिर्फ विशेष रजिस्टर (जैसे संचायक) पर कार्य कर सकते हैं। वे ''सामान्यतः'' निम्नलिखित सेटों में से चुने जाते हैं (किन्तु अपवाद सामान्य हैं):
##अंकगणित: अंकगणितीय निर्देश सभी रजिस्टरों पर या सिर्फ विशेष रजिस्टर (जैसे संचायक) पर कार्य कर सकते हैं। वे ''सामान्यतः'' निम्नलिखित सेटों में से चुने जाते हैं (किन्तु अपवाद सामान्य हैं):
##*काउंटर मशीन: { इंक्रीमेंट (आर), डिक्रीमेंट (आर), क्लियर-टू-जीरो (आर)}
##*काउंटर मशीन: { Increment (r), Decrement (r), Clear-to-zero (r) }
##*कम रैम, रैस्प: { इंक्रीमेंट (r), डिक्रीमेंट (r), क्लियर-टू-जीरो (r), लोड-तत्काल-स्थिर k, जोड़ें (r)<sub>1</sub>,आर<sub>2</sub>), उचित-घटाना (आर<sub>1</sub>,आर<sub>2</sub>), इंक्रीमेंट एक्युमुलेटर, डिक्रीमेंट एक्युमुलेटर, क्लीयर एक्युमुलेटर, रजिस्टर आर के एक्युमुलेटर कंटेंट में जोड़ें, रजिस्टर आर के एक्युमुलेटर कंटेंट से प्रॉपर-घटाना, }
##*RAM, RASP: { Increment (r), Decrement (r), Clear-to-zero (r), Load-immediate-constant k, Add (r<sub>1</sub>,r<sub>2</sub>), proper-Subtract (r<sub>1</sub>,r<sub>2</sub>), Increment accumulator, Decrement accumulator, Clear accumulator, Add to accumulator contents of register r, proper-Subtract from accumulator contents of register r, }
##*संवर्धित रैम, रैस्प: सभी कम किए गए निर्देश प्लस: {गुणा करें, विभाजित करें, विभिन्न बूलियन बिट-वाइज़ (लेफ्ट-शिफ्ट, बिट टेस्ट, आदि)}
##*संवर्धित रैम, रैस्प: सभी कम किए गए निर्देश प्लस: { Multiply, Divide, various Boolean bit-wise (left-shift, bit test, etc.)}
##नियंत्रण:
##नियंत्रण:
##*काउंटर मशीन मॉडल: वैकल्पिक {कॉपी (R<sub>1</sub>,R<sub>2</sub>)}
##*काउंटर मशीन मॉडल: वैकल्पिक { Copy (r<sub>1</sub>,r<sub>2</sub>) }
##*रैम और रैस्प मॉडल: अधिकांश में {प्रतिलिपि (R<sub>1</sub>,R<sub>2</sub>) }, या {आर से लोड संचायक, आर में स्टोर संचायक, तत्काल स्थिरांक के साथ लोड संचयकर्ता}
##*रैम और रैस्प मॉडल: अधिकांश में { Copy (r<sub>1</sub>,r<sub>2</sub>) }, or { Load Accumulator from r, Store accumulator into r, Load Accumulator with immediate constant }
##*सभी मॉडल: रजिस्टर के परीक्षण के बाद कम से कम सशर्त छलांग (शाखा, गोटो)। { जंप-इफ-जीरो, जंप-इफ-नॉट-जीरो (अर्ताथ जंप-इफ-पॉजिटिव), जंप-इफ-इक्वल, जंप-इफ-नॉट इक्वल}
##*सभी मॉडल: रजिस्टर के परीक्षण के बाद कम से कम सशर्त छलांग (शाखा, गोटो)। { Jump-if-zero, Jump-if-not-zero (i.e. Jump-if-positive), Jump-if-equal, Jump-if-not equal }
##*सभी मॉडल वैकल्पिक: {बिना शर्त प्रोग्राम जंप (गोटो)}
##*सभी प्रारूप वैकल्पिक हैं: { unconditional program jump (goto) }
## 'रजिस्टर-एड्रेसिंग विधि':
## 'रजिस्टर-एड्रेसिंग विधि':
##*काउंटर मशीन: कोई अप्रत्यक्ष संबोधन नहीं, अत्यधिक एटमाइज्ड मॉडल में तत्काल ऑपरेंड संभव है
##*काउंटर मशीन: कोई अप्रत्यक्ष संबोधन नहीं, अत्यधिक एटमाइज्ड मॉडल में तत्काल ऑपरेंड संभव है
##*रैम और रैस्प: इनडायरेक्ट एड्रेसिंग उपलब्ध, तत्काल ऑपरेंड विशिष्ट
##*रैम और रैस्प: इनडायरेक्ट एड्रेसिंग उपलब्ध, तत्काल ऑपरेंड विशिष्ट
##'इनपुट-आउटपुट': सभी मॉडलों में वैकल्पिक
##'इनपुट-आउटपुट': सभी मॉडलों में वैकल्पिक
#'स्थिति रजिस्टर': विशेष निर्देश रजिस्टर आईआर, परिमित और उपरोक्त रजिस्टरों से अलग, वर्तमान निर्देश को निष्पादित करने के लिए संग्रहीत करता है और इसका पता निर्देशों की तालिका में होता है; यह रजिस्टर और इसकी तालिका परिमित अवस्था मशीन में स्थित है।
#'स्थिति रजिस्टर': विशेष निर्देश रजिस्टर आईआर, परिमित और उपरोक्त रजिस्टरों से अलग, वर्तमान निर्देश को निष्पादित करने के लिए संग्रहीत करता है और इसका पता निर्देशों की तालिका में होता है; यह रजिस्टर और इसकी तालिका परिमित अवस्था की मशीन में स्थित है।
#*आईआर सभी मॉडलों के लिए ऑफ-लिमिट है। रैम और आरएएसपी की स्थिति में, रजिस्टर के पते का निर्धारण करने के प्रयोजनों के लिए, मॉडल या तो (i) सीधे संबोधित करने की स्थिति में - तालिका द्वारा निर्दिष्ट पता और आईआर में अस्थायी रूप से स्थित या (ii) का चयन कर सकता है। अप्रत्यक्ष पते की स्थिति में - आईआर के निर्देश द्वारा निर्दिष्ट रजिस्टर की सामग्री उपलब्ध हैं।
#*आईआर सभी मॉडलों के लिए ऑफ-लिमिट है। रैम और आरएएसपी की स्थिति में, रजिस्टर के पते का निर्धारण करने के प्रयोजनों के लिए, मॉडल या तो (i) सीधे संबोधित करने की स्थिति में उक्त तालिका द्वारा निर्दिष्ट पते और आईआर में अस्थायी रूप से स्थित (ii) का चयन कर सकता है। इस प्रकार अप्रत्यक्ष पते की स्थिति में आईआर के निर्देश द्वारा निर्दिष्ट रजिस्टर की सामग्री उपलब्ध हैं।
#*आईआर रैस्प (या पारंपरिक कंप्यूटर) का प्रोग्राम काउंटर (PC) नहीं है। पीसी संचायक के समान और रजिस्टर है, किन्तु आरएएसपी के वर्तमान रजिस्टर-आधारित निर्देश की संख्या को धारण करने के लिए समर्पित है। इस प्रकार रैस्प के पास दो निर्देश/कार्यक्रम रजिस्टर होते हैं- (i) IR (परिमित स्थिति मशीन का निर्देश रजिस्टर), और (ii) रजिस्टरों में स्थित कार्यक्रम के लिए पीसी (प्रोग्राम काउंटर)। (साथ ही साथ पीसी को समर्पित रजिस्टर, आरएएसपी प्रोग्राम-इंस्ट्रक्शन रजिस्टर (पीआईआर, आईआर, पीआर, आदि जैसे किसी भी नाम से जाने वाले) के लिए और रजिस्टर समर्पित कर सकता है।
#*आईआर रैस्प (या पारंपरिक कंप्यूटर) का प्रोग्राम काउंटर (PC) नहीं है। पीसी संचायक के समान और रजिस्टर है, किन्तु आरएएसपी के वर्तमान रजिस्टर-आधारित निर्देश की संख्या को धारण करने के लिए समर्पित है। इस प्रकार रैस्प के पास दो निर्देश/फंक्शन रजिस्टर होते हैं- (i) आईआर (परिमित स्थिति मशीन का निर्देश रजिस्टर), और (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: उदा. { INC ( r, z ), JZDEC ( r, z<sub>true</sub>, z<sub>false</sub> ) }.<br>सशर्त व्यंजक के बारे में अधिक जानकारी के लिए [[मैककार्थी औपचारिकता]] "IF r=0 THEN z<sub>true</sub> ELSE z<sub>false</sub>" (cf McCarthy (1960))


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


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


पहली प्रवृत्ति-कंप्यूटर के लक्षण वर्णन की ओर-लगती है<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) के साथ दूसरी प्रवृत्ति और, जैसा कि ऊपर उल्लेख किया गया है।


पिछले पांच नामों को स्पष्ट रूप से [[यूरी मटियासेविच]] द्वारा उसी क्रम में सूचीबद्ध किया गया है। वह इसके साथ चलता है:
पिछले पांच नामों को स्पष्ट रूप से [[यूरी मटियासेविच]] द्वारा उसी क्रम में सूचीबद्ध किया गया है। वह इसके साथ चलता है:
: रजिस्टर मशीनें [कुछ लेखक काउंटर-मशीन के पर्यायवाची रजिस्टर मशीन का उपयोग करते हैं] डायोफैंटाइन समीकरणों के निर्माण के लिए विशेष रूप से उपयुक्त हैं। ट्यूरिंग मशीनों की तरह, उनके पास बहुत ही विशेष निर्देश हैं और, इसके अलावा, वे संख्याओं से निपटते हैं (यूरी मटियासेविच (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}
: { LEFT, RIGHT, PRINT, 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] }
:{ LEFT, RIGHT, PRINT, ERASE, JUMP_if_marked, [maybe JUMP or JUMP_IF_blank] }


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


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


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


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


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


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


दरअसल, [[ट्यूरिंग मशीन के उदाहरण]], पोस्ट-ट्यूरिंग मशीन और आंशिक फ़ंक्शन शो के उदाहरण के रूप में, कार्य जटिल हो सकता है।
=== मिन्स्की, मेल्ज़ाक-लैम्बेक और शेफर्डसन-स्टर्गिस मॉडल ने टेप को कई प्रकार से काटा था ===
इस प्रकार क्यों न 'टेप को काटें' जिससे कि प्रत्येक असीम रूप से लंबा हो (किसी भी आकार के पूर्णांक को समायोजित करने के लिए) किन्तु बाएँ सिरे पर, और इन तीन टेपों को पोस्ट-ट्यूरिंग (अर्ताथ वैंग-जैसे) टेप कहें? व्यक्तिगत शीर्ष बाएं (घटाने के लिए) और दाएं (वेतन वृद्धि के लिए) चलेंगे। इस प्रकार से शीर्ष, जुड़े हुए चिह्नों के ढेर के शीर्ष को इंगित करते हैं या मिन्स्की (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) साबित करते हैं कि केवल कुछ टेप- जितने कम एक-अभी भी मशीन को ट्यूरिंग समतुल्य होने की अनुमति देते हैं यदि टेप पर डेटा को गोडेल नंबर (य