रैंडम-एक्सेस मशीन

Not to be confused with रैंडम एक्सेस मेमोरी.

कंप्यूटर विज्ञान में, रैंडम-एक्सेस मशीन (रैम) रजिस्टर मशीन के सामान्य वर्ग में अमूर्त मशीन है। रैम काउंटर मशीन के समान ही है | किन्तु इसके रजिस्टरों के 'अप्रत्यक्ष पता' की अतिरिक्त क्षमता के साथ काउंटर मशीन की तरह, रैम के पास मशीन के परिमित-स्तर भाग (तथाकथित हार्वर्ड आर्किटेक्चर ) में इसके निर्देश हैं।

रैम यूनिवर्सल ट्यूरिंग मशीन के समान है | रजिस्टरों के साथ-साथ इसके डेटा में इसके कंप्यूटर प्रोग्राम के साथ को रैंडम-एक्सेस संग्रहित प्रोग्राम मशीन या आरएएसपी कहा जाता है। यह तथाकथित वॉन न्यूमैन आर्किटेक्चर का उदाहरण है और कंप्यूटर की सामान्य धारणा के सबसे निकट है।

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

मॉडल का परिचय

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

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

रैंडम-एक्सेस मशीन (रैम) अमूर्त कम्प्यूटेशनल-मशीन मॉडल है | जो अप्रत्यक्ष एड्रेसिंग के साथ मल्टीपल-रजिस्टर काउंटर मशीन के समान है। अपने परिमित स्तर मशीन की टेबल से निर्देश के विवेक पर, मशीन एक लक्ष्य रजिस्टर का पता प्राप्त करती है या तो (i) सीधे निर्देश से, या (ii) अप्रत्यक्ष रूप से पॉइंटर रजिस्टर की पदार्थ (जैसे संख्या, लेबल) से निर्दिष्ट होती है।

परिभाषा के अनुसार: रजिस्टर पता (एक अद्वितीय, विशिष्ट पदनाम/प्राकृतिक संख्या के समान लोकेटर) और पदार्थ दोनों के साथ एक स्थान है। प्राकृतिक संख्या स्पष्टता के लिए हम बूलोस-बर्गेस-जेफरी (2002) से अर्ध-औपचारिक प्रतीकवाद का उपयोग रजिस्टर, इसकी पदार्थ और रजिस्टर पर संचालन निर्दिष्ट करने के लिए करेंगे:

• R का कारण पता R के साथ रजिस्टर की पदार्थ है। यहाँ लेबल r चर है जिसे प्राकृतिक संख्या या अक्षर (जैसे A ) या एक नाम से भरा जा सकता है।
• → का अर्थ है प्रतिलिपि/जमा करना, या प्रतिस्थापित करना, किन्तु स्रोत को नष्ट किए बिना

उदाहरण: [3] +1 → 3 का अर्थ है "स्रोत रजिस्टर की पदार्थ पते के साथ" 3 "प्लस 1 को पते के साथ गंतव्य रजिस्टर में डाल दिया जाता है | " 3 "(यहां स्रोत और गंतव्य एक ही स्थान हैं)। यदि [3] = 37 अर्थात रजिस्टर 3 की पदार्थ संख्या "37" है तो 37+1 = 38 को रजिस्टर 3 में रखा जाएगा।

उदाहरण: [3] → 5; का अर्थ है पते 3 के साथ स्रोत रजिस्टर की पदार्थ को पते 5 के साथ गंतव्य रजिस्टर में रखा गया है। यदि [3] = 38, अर्थात रजिस्टर 3 की पदार्थ संख्या 38 है, तो यह संख्या रजिस्टर 5 में डाल दी जाएगी। रजिस्टर 3 की पदार्थ इस संचालन से परेशान नहीं होती है, इसलिए [3] 38 बनी रहती है , अब [5] के समान है।

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

मानक/सम्मेलन की चाह के लिए यह लेख निर्देश में मापदंड (या मापदंड) के रूप में प्रत्यक्ष/अप्रत्यक्ष निर्दिष्ट करेगा, जिसे d/i के रूप में संक्षिप्त किया गया है |

उदाहरण: प्रतिलिपि ('d, A, i, N) का अर्थ सीधे 'd' स्रोत रजिस्टर का पता प्राप्त करें (पंजीकरण A) निर्देश से ही किन्तु अप्रत्यक्ष रूप से 'i' पॉइंटर-रजिस्टर N से गंतव्य पता प्राप्त करें मान लीजिए [N] = 3, तो रजिस्टर 3 गंतव्य है और निर्देश निम्नलिखित कार्य करेगा: [A] → 3।

परिभाषा: स्रोत रजिस्टर की पदार्थ का उपयोग निर्देश द्वारा किया जाता है। स्रोत रजिस्टर का पता या तो (i) सीधे निर्देश द्वारा निर्दिष्ट किया जा सकता है, या (ii) अप्रत्यक्ष रूप से निर्देश द्वारा निर्दिष्ट सूचक रजिस्टर द्वारा निर्दिष्ट किया जा सकता है।

परिभाषा: सूचक रजिस्टर की पदार्थ लक्ष्य रजिस्टर का पता है।

परिभाषा: पॉइंटर रजिस्टर की पदार्थ लक्ष्य रजिस्टर की ओर संकेत करती है | लक्ष्य या तो स्रोत या गंतव्य रजिस्टर हो सकता है।

परिभाषा: गंतव्य रजिस्टर वह स्थान है | जहाँ निर्देश अपना परिणाम जमा करता है। स्रोत रजिस्टर का पता या तो (i) सीधे निर्देश द्वारा निर्दिष्ट किया जा सकता है, या (ii) अप्रत्यक्ष रूप से निर्देश द्वारा निर्दिष्ट सूचक रजिस्टर द्वारा निर्दिष्ट किया जा सकता है। स्रोत और गंतव्य रजिस्टर एक हो सकते हैं।

रिफ्रेशर: काउंटर-मशीन मॉडल

मेल्ज़क (1961) काउंटर मशीन का सरल दृश्य प्रदान करता है | इसके रजिस्टर जमीन में छेद होते हैं, और इन छेदों में कंकड़ होते हैं। निर्देश के अनुसार, इन छिद्रों में और बाहर कंप्यूटर (व्यक्ति या मशीन) कंकड़ जोड़ता है | (वृद्धि) या हटाता है (डिक्रीमेंट्स)। आवश्यकतानुसार, अतिरिक्त कंकड़ आते हैं, और अतिरिक्त कंकड़ अनंत आपूर्ति में वापस चले जाते हैं | यदि छेद कंकड़ रखने के लिए बहुत छोटा है तो कंप्यूटर छेद को बड़ा खोदता है।

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

निम्नलिखित निर्देश म्नेमोनिच्स उदाहरण सीएलआर (R) इच्छानुसार हैं | कोई मानक उपस्थित नहीं है।

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

'बेस मॉडल 1': मिन्स्की (1961) विज़ुअलाइज़ेशन और लैम्बेक (1961) के निकटतम मॉडल | {रजिस्टर R की वृद्धि पदार्थ, रजिस्टर R की गिरावट पदार्थ, यदि रजिस्टर R की पदार्थ शून्य है तो निर्देश I_z पर जाएं अन्य अगले निर्देश पर जारी रखें}:

Instruction	Mnemonic	Action on register(s) "r"	Action on finite state machine's Instruction Register, IR
INCrement	INC ( r )	[r] + 1 → r	[IR] + 1 → IR
DECrement	DEC ( r )	[r] - 1 → r	[IR] + 1 → IR
Jump if Zero	JZ ( r, z )	none	IF [r] = 0 THEN z → IR अन्य [IR] + 1 → IR
Halt	H	none	[IR] → IR

बेस मॉडल 2: उत्तराधिकारी मॉडल (पियानो सिद्धांत के उत्तराधिकारी कार्य के नाम पर):

• {रजिस्टर R की पदार्थ में वृद्धि, रजिस्टर R की पदार्थ को साफ करें, रजिस्टर R_z की पदार्थ if_j रजिस्टर R_k की पदार्थ के समान है फिर निर्देश पर जाएं अन्य गोटो अगले निर्देश के लिए }

Instruction	Mnemonic	Action on register(s) "r"	Action on finite state machine's Instruction Register, IR
स्पष्ट	CLR ( r )	0 → r	[IR] + 1 → IR
INCrement	INC ( r )	[r] + 1 → r	[IR] + 1 → IR
Jump if Equal	JE (r1, r2, z)	none	IF [r1] = [r2] THEN z → IR अन्य [IR] + 1 → IR
Halt	H	none	[IR] → IR

बेस मॉडल 3: एलगॉट-रॉबिन्सन (1964) द्वारा परिबद्ध और असंबद्ध आरएएसपी की जांच में उपयोग किया गया | स्पष्ट के स्थान पर प्रतिलिपि वाला उत्तराधिकारी मॉडल:

• {रजिस्टर R की पदार्थ में वृद्धि, रजिस्टर R_j की पदार्थ की प्रतिलिपि बनाएँ R_k अंकित करने के लिए, यदि रजिस्टर R_j की सामग्री रजिस्टर R_k की पदार्थ के समान है फिर निर्देश I_z पर जाएं अन्य गोटो अगले निर्देश के लिए }

Instruction	Mnemonic	Action on register(s) "r"	Action on finite state machine's Instruction Register, IR
प्रतिलिपि	प्रतिलिपि (r1, r2)	[r1] → r2	[IR] + 1 → IR
INCrement	INC ( r )	[r] + 1 → r	[IR] + 1 → IR
Jump if Equal	JE (r1, r2, z)	none	IF [r1] = [r2] THEN z → IR अन्य [IR] + 1 → IR
Halt	H	none	[IR] → IR

बेस समुच्चय से सुविधा निर्देश बनाना

उपरोक्त तीन आधार समुच्चय 1, 2, या 3 इसमें समतुल्य हैं कि कोई दूसरे समुच्चय के निर्देशों का उपयोग करके समुच्चय के निर्देश बना सकता है | (एक रोचक अभ्यास: मिन्स्की से संकेत (1967) आरक्षित रजिस्टर घोषित करें उदाहरण. संख्या 0 को सम्मिलित करने के लिए इसे 0 (या शून्य के लिए Z या मिटाने के लिए E) पर कॉल करें)। मॉडल का चुनाव इस बात पर निर्भर करेगा कि लेखक को प्रदर्शन, या प्रमाण आदि में किसका उपयोग करना सबसे सरल लगता है।

इसके अतिरिक्त, आधार समुच्चय 1, 2, या 3 से हम किसी भी पुनरावर्ती कार्य (सीएफ मिंस्की (1967), बूलोस-बर्गेस-जेफरी (2002)) को बना सकते हैं। (कुल और आंशिक mu पुनरावर्ती कार्यों को कैप्चर करने के लिए नेट को व्यापक कैसे बनाया जाए, इस पर अप्रत्यक्ष संबोधन के संदर्भ में चर्चा की जाएगी)। चूँकि, पुनरावर्ती कार्यों का निर्माण करना कठिनाई है | क्योंकि निर्देश समुच्चय इतने (छोटे) हैं। समाधान दूसरे समुच्चय से सुविधा निर्देशों के साथ विशेष समुच्चय का विस्तार करना है |

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

उदाहरण: बेस समुच्चय 1. सीएलआर (R) बनाने के लिए निर्देशों के ब्लॉक का उपयोग करें, रजिस्टर R को शून्य करने के लिए काउंट डाउन करें। ऊपर बताए गए संकेत के उपयोग पर ध्यान दें:

• CLR (R) =_equiv
• loop: JZ (R, बाहर निकलें)

• DEC (R)
• JZ (0, loop)

• exit: etc।

फिर से, यह सब केवल सुविधा के लिए है इसमें से कोई भी मॉडल की आंतरिक शक्ति को नहीं बढ़ाता है।

उदाहरण के लिए: सबसे विस्तारित समुच्चय में तीन सेटों में से प्रत्येक अद्वितीय निर्देश और बिना शर्त जंप J (z) सम्मिलित होगा |

• • { CLR (r), DEC (r), INC (r), CPY ( r_s, r_d ), JZ (r, z), JE ( r_j, r_k, z ), J(z) }

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

अप्रत्यक्ष संचालन

अप्रत्यक्ष संबोधन का उदाहरण

हमारे दैनिक जीवन में अप्रत्यक्ष संचालन की धारणा असामान्य नहीं है।

उदाहरण: खजाने की खोज।

स्थान पर टॉम & बेकी'स केव इन पाइरेट चेस्ट वह स्थान होगा जहां हम खजाने की ओर निर्देशित करने वाला नक्शा ढूंढ सकते हैं |

(1) हम टॉम & बेकी की गुफा के स्थान पर जाते हैं और तब तक खुदाई करते हैं जब तक हमें लकड़ी का बक्सा नहीं मिल जाता है |

(2) बॉक्स के अंदर खजाने के स्थान का नक्शा है | थैचर के सामने पोर्च के नीचे है |

(3) हम थैचर फ्रंट पोर्च के नीचे स्थान पर जाते हैं, जैकहैमर कंक्रीट को दूरस्थ करते हैं, और खजाने की खोज करते हैं: जंग लगी डोर-नॉब्स की एक बोरी है ।

अविवेक टॉम & बैकी'स केव में पाइरेट चेस्ट के रूप में पहचाने जाने वाले स्थान को निर्दिष्ट करता है | जो किसी अन्य स्थान (स्वयं सहित) के लिए संकेतक के रूप में कार्य करता है | इसकी पदार्थ (खजाने का नक्शा) लक्ष्य स्थान का पता प्रदान करता है |

अंडर_थैचर_फ्रंट_पोर्च जहां वास्तविक कार्रवाई हो रही है।

अप्रत्यक्ष संचालन की आवश्यकता क्यों: काउंटर-मशीन मॉडल के साथ दो प्रमुख समस्याएं है |

निम्नलिखित में किसी को यह याद रखना चाहिए कि ये मॉडल भौतिक रूप से वास्तविक किसी भी चीज़ से दो मूलभूत अंतरों के साथ अमूर्त मॉडल हैं | असीम क्षमता वाले प्रत्येक रजिस्टर की असीमित संख्या समस्या सबसे नाटकीय रूप से प्रकट होती है | जब कोई आरएएसपी बनाने के लिए काउंटर-मशीन मॉडल का उपयोग करने की प्रयास करता है | जो ट्यूरिंग पूर्णता है और इस प्रकार किसी आंशिक एमयू रिकर्सिव फलन की गणना करता है |

• मेल्ज़ाक (1961) ने अपने होल-एंड-पेबल मॉडल में अप्रत्यक्ष रूप से जोड़ा जिससे उनका मॉडल संगणित गोटो के साथ खुद को संशोधित कर सके और इसके उपयोग के दो उदाहरण प्रदान करता है |(डी के पैमाने में दशमलव प्रतिनिधित्व और परिमाण द्वारा छंटनी, चाहे इनका उपयोग किया गया हो) उनके प्रमाण में कि मॉडल ट्यूरिंग समतुल्य है, स्पष्ट नहीं है | क्योंकि कार्यक्रम को पाठक के लिए अभ्यास के रूप में छोड़ दिया गया है |(पृष्ठ 292) मिन्स्की (1961, 1967) यह प्रदर्शित करने में सक्षम थे कि, उपयुक्त (किन्तु उपयोग में कठिनाई) गोडेल नंबर एन्कोडिंग के साथ, रजिस्टर मॉडल को ट्यूरिंग समतुल्य होने के लिए संकेत की आवश्यकता नहीं थी | किन्तु इसके लिए कम से कम असीमित रजिस्टर की आवश्यकता थी। जैसा कि नीचे उल्लेख किया गया है, मिंस्की (1967) आरएएसपी के लिए समस्या का संकेत देता है, किन्तु समाधान की प्रस्तुति नहीं करता है। एलगोट और रॉबिन्सन (1964) ने सिद्ध किया कि उनका आरएएसपी मॉडल P₀ – इसकी कोई अप्रत्यक्ष क्षमता नहीं है | सभी पुनरावर्ती अनुक्रमिक कार्यों की गणना नहीं कर सकता है (जिनके इच्छानुसार लंबाई के मापदंड हैं) यदि इसमें अपने स्वयं के निर्देशों को संशोधित करने की क्षमता नहीं है, किन्तु यह गोडेल संख्या के माध्यम से कर सकता है | यदि यह करता है (पृष्ठ 395-397; विशेष रूप से चित्र 2 और फुटनोट पृष्ठ 395)। दूसरी ओर उनका आरएएसपी मॉडल P'₀ इंडेक्स रजिस्टर (इनडायरेक्ट एड्रेसिंग) से लैस सभी आंशिक पुनरावर्ती अनुक्रमिक कार्यों (एमयू पुनरावर्ती कार्यों) की गणना कर सकता है (पृष्ठ 397-398)।

कुक एंड रेक्हो (1973) इसे सबसे संक्षेप में कहते हैं |

निश्चित कार्यक्रम के लिए अप्रत्यक्ष निर्देश आवश्यक हैं | जिससे इनपुट में भिन्नता के रूप में रजिस्टरों की असीमित संख्या तक पहुंच हो सके। (पृष्ठ 73)

• 'रजिस्टरों की असीमित क्षमता बनाम स्तर-मशीन निर्देशों की सीमित क्षमता': मशीन का तथाकथित परिमित स्तर हिस्सा माना जाता है | एल्गोरिदम की सामान्य परिभाषा के अनुसार{{अंतरित एनदैस}राज्यों (निर्देशों) की संख्या और निर्देशों के आकार (प्रतीकों/संकेतों को धारण करने की उनकी क्षमता) दोनों में बहुत सीमित है तो कैसे स्तर मशीन इच्छानुसार से बड़े स्थिरांक को सीधे रजिस्टर में ले जाती है, उदाहरण मूव (के, R) (R रजिस्टर करने के लिए निरंतर के को स्थानांतरित करें) | यदि विशाल स्थिरांक आवश्यक हैं, तो उन्हें या तो स्वयं रजिस्टरों में प्रारंभ करना चाहिए या स्तर मशीन द्वारा निर्देशों की सीमित संख्या का उपयोग करके बनाया जाना चाहिए। आईएनसी और DEC का उपयोग करके गुणा करें और सबरूटीन्स जोड़ें (किन्तु इनमें से अर्ध-अनंत संख्या नहीं!)।

कभी-कभी सीएलआर (R) के उपयोग के बाद आईएनसी (R) बार-बार के बार के बाद निरंतर के बनाया जाएगा – उदा. स्थिर k = 3 को रजिस्टर r में रखने के लिए, अर्थात 3 → r, इसलिए निर्देश के अंत में [r] = 3: CLR (r), INC (r), INC (r), INC (r)। इस ट्रिक का उल्लेख क्लेन (1952) पृष्ठ द्वारा किया गया है। 223. समस्या तब उत्पन्न होती है | जब बनाई जाने वाली संख्या परिमित स्तर मशीन के लिए उपलब्ध निर्देशों की संख्या को समाप्त कर देती है | परिमित स्तर मशीन के लिए उपलब्ध निर्देशों की संख्या की तुलना में सदैव एक बड़ा स्थिरांक होता है।

• 'रजिस्टरों की असीमित संख्या बनाम बाध्य स्तर-मशीन निर्देश' यह पहली समस्या से अधिक गंभीर है। विशेष रूप से, यह समस्या तब उत्पन्न होती है | जब हम तथाकथित आरएएसपी, सार्वभौमिक मशीन (यूनिवर्सल ट्यूरिंग मशीन पर अधिक देखें) बनाने का प्रयास करते हैं | जो अपने परिमित-स्तर मशीन का उपयोग अपने रजिस्टरों में स्थित निर्देशों के कार्यक्रम की व्याख्या करने के लिए करती है। – अर्थात। हम वो बना रहे हैं जिसे आजकल वॉन न्यूमैन आर्किटेक्चर वाला कंप्यूटर कहा जाता है।

ध्यान दें कि काउंटर मशीन की परिमित स्तर मशीन को अपने नाम/संख्या से स्पष्ट रूप से (सीधे) रजिस्टर को कॉल करना चाहिए: INC (65,356) रजिस्टर संख्या 65,365 को स्पष्ट रूप से कॉल करता है। यदि रजिस्टरों की संख्या उन्हें संबोधित करने के लिए परिमित स्तर मशीन की क्षमता से अधिक है, तो सीमा के बाहर के रजिस्टर अगम्य होंगे। उदाहरण के लिए, यदि परिमित अवस्था मशीन केवल 65,536 = 2¹⁶ तक पहुँच सकती है पंजीकृत है तो यह 65,537 वें स्थान पर कैसे पहुंच सकता है |

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

एल्गोट और रॉबिन्सन (1964) आरएएसपी के संबंध में एक समान निष्कर्ष पर आते हैं | जो निश्चित रूप से निर्धारित होता है। वास्तव में यह रजिस्टरों की असीमित संख्या तक पहुंच सकता है (उदाहरण के लिए उनसे निर्देश प्राप्त करने के लिए) किन्तु केवल तभी जब आरएएसपी अपने प्रोग्राम निर्देशों के स्वयं संशोधन की अनुमति देता है, और अपने डेटा को गोडेल नंबर (चित्र 2 पी। 396) में एन्कोड किया है।

अपने आरपीटी (रिपीट) निर्देश का उपयोग करते हुए अधिक कंप्यूटर जैसे मॉडल के संदर्भ में मिन्स्की (1967) हमें समस्या के समाधान के साथ आकर्षित करता है (cf p. 214, p. 259) किन्तु कोई ठोस समाधान प्रदान नहीं करता है। वह प्रमाणित करता है |

सामान्यतः आरपीटी संचालन मशीन के परिमित-स्तर भाग में निर्देश नहीं हो सकता है | यह कंप्यूटर के परिमित भाग में अनुमत भंडारण की किसी विशेष मात्रा को समाप्त कर सकता है | sic, उसके रैम मॉडल के लिए उसका नाम आरपीटी संचालन के लिए स्वयं के अनंत रजिस्टरों की आवश्यकता होती है। (पृष्ठ 214)।

वह हमें बाउंडेड आरपीटी प्रदान करता है | जो सीएलआर (R) और आईएनसी (R) के साथ मिलकर किसी भी पुनरावर्ती फलन की गणना कर सकता है, और वह ऊपर उद्धृत अनबाउंड आरपीटी प्रदान करता है जो μ ऑपरेटर की भूमिका निभा रहा है | यह CLR (r) और INC (r) के साथ मिलकर mu पुनरावर्ती कार्यों की गणना कर सकता है। किन्तु वह परोक्ष या प्रति रैम मॉडल पर चर्चा नहीं करता है।

हार्टमैनिस (1971) के संदर्भों से ऐसा प्रतीत होता है कि कुक (यूसी बर्कले, 1970 में अपने व्याख्यान नोट्स में) ने अप्रत्यक्ष संबोधन की धारणा को शक्तिशाली किया है। यह कुक एंड रेक्हो (1973) के पेपर में स्पष्ट हो जाता है। कुक रेक्हो के मास्टर के थीसिस सलाहकार हैं। हार्टमैनिस का मॉडल मेल्ज़ाक के (1961) मॉडल के समान दो और तीन-रजिस्टर जोड़ और घटाव और दो मापदंड प्रतियों का उपयोग करता है | कुक और रेकहो का मॉडल संचायक एसी के उपयोग से एक कॉल-आउट के लिए मापदंडों की संख्या (प्रोग्राम निर्देशों में बुलाए गए रजिस्टर) को कम करता है।

संक्षेप में समाधान: हमारी मशीन/मॉडल को असीमित संकेत के साथ डिज़ाइन करें | असीमित पता रजिस्टर प्रदान करें जो संभावित रूप से किसी भी रजिस्टर का नाम (कॉल आउट) कर सकता है, चाहे कितने भी हों। इसके लिए काम करने के लिए, सामान्य रूप से, असीमित रजिस्टर को साफ़ करने की क्षमता की आवश्यकता होती है और फिर संभावित अनंत लूप द्वारा वृद्धि (और संभवतः, कमी) की आवश्यकता होती है। इस अर्थ में समाधान असीमित μ ऑपरेटर का प्रतिनिधित्व करता है, जो आवश्यक होने पर, रजिस्टरों की असीमित स्ट्रिंग के साथ अनंत तक शिकार कर सकता है, जब तक कि वह जो ढूंढ रहा है उसे नहीं मिल जाता। पॉइंटर रजिस्टर बिल्कुल अपवाद के साथ किसी भी अन्य रजिस्टर की तरह है: अप्रत्यक्ष एड्रेसिंग कहलाने वाली परिस्थितियों में यह स्टेट मशीन के टेबल में एड्रेस-ऑपरेंड के अतिरिक्त अपनी पदार्थ प्रदान करता है, लक्ष्य रजिस्टर का पता होने के लिए (संभवतः स्वयं सहित!) है | .

परिबद्ध संकेत और पुनरावर्ती कार्य

यदि हम रजिस्टर में राक्षस संख्या के मिन्स्की दृष्टिकोण से बचते हैं, और निर्दिष्ट करते हैं कि हमारा मशीन मॉडल कंप्यूटर की तरह होगा, तो हमें इस अप्रत्यक्ष समस्या का सामना करना होगा यदि हम पुनरावर्ती कार्यों की गणना कर रहे हैं (जिसे μ-पुनरावर्ती कार्य भी कहा जाता है) कुल और आंशिक दोनों किस्में है।

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

क्या रजिस्टर N में संख्या 0 के समान है यदि नहीं तो क्या यह 1 के समान है 2? 3? 65364? यदि नहीं तो हम अंतिम संख्या 65365 पर हैं और यह उत्तम होगा, अन्यथा हमें समस्या है |

बाउंडेड इनडायरेक्शन हमें आंशिक पुनरावर्ती कार्यों की गणना करने की अनुमति नहीं देगा उनके लिए हमें अनबाउंड इंडिकेशन उर्फ ​​​​μ ऑपरेटर की आवश्यकता है।

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

ट्यूरिंग पूर्णता होने के लिए काउंटर मशीन को या तो दुर्भाग्यपूर्ण सिंगल-रजिस्टर मिन्स्की गोडेल नंबर विधि का उपयोग करने की आवश्यकता होती है, या यदि आवश्यक हो तो इसके रजिस्टर स्ट्रिंग के सिरों का पता लगाने की क्षमता के साथ संवर्धित किया जाना चाहिए। (वहाँ कुछ खोजने में विफलता यह परिभाषित करती है कि एल्गोरिथम को समाप्त करने में विफल होने का क्या अर्थ है; सीएफ क्लेन (1952) पीपी। 316ff अध्याय XII आंशिक पुनरावर्ती कार्य, विशेष रूप से पी। 323-325।) उदाहरण में इस पर और देखें। नीचे।

असीम अप्रत्यक्ष और आंशिक पुनरावर्ती कार्य

अनबाउंड इंडिकेशन के लिए हमें अपने मशीन मॉडल में हार्डवेयर परिवर्तन की आवश्यकता होती है। एक बार जब हम यह परिवर्तन कर लेते हैं तो मॉडल काउंटर मशीन नहीं रह जाता है, किन्तु रैंडम-एक्सेस मशीन बन जाता है।

अब जब उदा. आईएनसी निर्दिष्ट है, परिमित स्तर मशीन के निर्देश को यह निर्दिष्ट करना होगा कि ब्याज के रजिस्टर का पता कहां से आएगा। यह या तो हो सकता है (i) स्तर मशीन का निर्देश जो स्पष्ट लेबल प्रदान करता है, या (ii) पॉइंटर-रजिस्टर जिसकी पदार्थ रुचि का पता है। जब भी कोई निर्देश रजिस्टर पता निर्दिष्ट करता है तो उसे अब अतिरिक्त मापदंड i/d निर्दिष्ट करने की आवश्यकता होगी – अप्रत्यक्ष/प्रत्यक्ष। एक मायने में यह नया आई/डी मापदंड स्विच है जो निर्देश में निर्दिष्ट प्रत्यक्ष पता प्राप्त करने के लिए एक तरफ फ़्लिप करता है या पॉइंटर रजिस्टर से अप्रत्यक्ष पता प्राप्त करने का दूसरा विधि है (जो पॉइंटर रजिस्टर{{अंतरित एनदैस}कुछ मॉडलों में प्रत्येक रजिस्टर सूचक रजिस्टर हो सकता है – निर्देश द्वारा निर्दिष्ट किया गया है)। यह पारस्परिक रूप से अनन्य किन्तु संपूर्ण विकल्प स्थितियों द्वारा परिभाषा का एक और उदाहरण है, और नीचे दिए गए उदाहरण में दिखाया गया अंकगणितीय समकक्ष क्लेन (1952) पी में परिभाषा से लिया गया है। 229.

उदाहरण: सीपीवाई ( indirect_source, r_source, direct_destination, r_destination )

डायरेक्ट एड्रेसिंग को d= 0 और इनडायरेक्ट एड्रेसिंग को i= 1 के रूप में निर्दिष्ट करने के लिए कोड असाइन करें। तब हमारी मशीन स्रोत का पता निम्नानुसार निर्धारित कर सकती है |

i*[r_s] + (1-i)*r_s

उदाहरण के लिए, मान लीजिए कि रजिस्टर 3 की पदार्थ 5 है (अर्थात [3]=5 ) और रजिस्टर 4 की पदार्थ 2 है (अर्थात [4]=2 ):

उदाहरण: CPY (1, 3, 0, 4) = CPY (indirect, reg 3, direct, reg 4 )

1*[3] + 0*3 = [3] = स्रोत-पंजीकरण पता 5

0*[4] + 1*4 = 4 = गंतव्य-पंजीकरण पता 4

उदाहरण: CPY ( 0, 3, 0, 4 )

0*[3] + 1*3 = 3 = स्रोत-पंजीकरण पता 3

0*[4] + 1*4 = 4 = गंतव्य-पंजीकरण पता 4

उदाहरण: CPY ( 0, 3, 1, 4 )

0*[3] + 1*3 = 3 = स्रोत-पंजीकरण पता 3

1 * [4] + 0 * 4 = [4] = गंतव्य-पंजीकरण पता 2

अप्रत्यक्ष कॉपी निर्देश

संभवतः जोड़े गए निर्देशों में सबसे उपयोगी है कॉपी। दरअसल, एलगॉट-रॉबिन्सन (1964) ने अपने मॉडल पी₀ और पी'₀ प्रतिलिपि निर्देशों के साथ, और कुक-रेकहो (1973) केवल दो अप्रत्यक्ष निर्देशों के साथ अपना संचायक-आधारित मॉडल प्रदान करते हैं | {{अंतरित एनदैस} अप्रत्यक्ष रूप से संचायक को कॉपी करें, संचायक से अप्रत्यक्ष रूप से कॉपी करें।

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

CPY (d, r_s, d, r_d ) = COPY स्रोत-रजिस्टर से सीधे गंतव्य-रजिस्टर पर कॉपी करें

CPY (i, r_sp, d, r_d ) = COPY स्रोत-सूचक रजिस्टर R_sp में पाए जाने वाले स्रोत पते का उपयोग करके अप्रत्यक्ष रूप से गंतव्य-रजिस्टर पर कॉपी करें.

CPY (d, r_s, i, r_dp ) = COPY गंतव्य-सूचक रजिस्टर R_dp में पाए जाने वाले गंतव्य पते का उपयोग करके अप्रत्यक्ष रूप से स्रोत-रजिस्टर की पदार्थ को रजिस्टर में कॉपी करें.

CPY (i, r_sp, i, r_dp ) = COPY स्रोत-सूचक रजिस्टर r_sp में पाए जाने वाले पते के साथ अप्रत्यक्ष रूप से स्रोत रजिस्टर की पदार्थ को कॉपी करें, गंतव्य रजिस्टर में पते के साथ गंतव्य-सूचक रजिस्टर r_dp में पाया जाना है)

इसी तरह प्रत्येक तीन-रजिस्टर निर्देश जिसमें दो स्रोत रजिस्टर R_s1 r_s2 सम्मिलित हैं और गंतव्य रजिस्टर R_d इसके परिणामस्वरूप 8 किस्में होंगी, उदाहरण के लिए अतिरिक्त होते है |

[r_s1] + [r_s2] → r_d

निकलेगा:

• • ADD ( d, r_s1, d, r_s2, d, r_d )
  • ADD ( i, r_sp1, d, r_s2, d, r_d )
  • ADD ( d, r_s1, i, r_sp2, d, r_d )
  • ADD ( i, r_sp1, i, r_sp2, d, r_d )
  • ADD ( d, r_s1, d, r_s2, i, r_dp )
  • ADD ( i, r_sp1, d, r_s2, i, r_dp )
  • ADD ( d, r_s1, i, r_sp2, i, r_dp )
  • ADD ( i, r_sp1, i, r_sp2, i, r_dp )

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

संचायक A की धारणा ऐतिहासिक सम्मेलन संचायक को रजिस्टर समर्पित करता है | अंकगणितीय अंग जो अंकगणितीय कार्यों के अनुक्रम के समय शाब्दिक रूप से अपनी संख्या जमा करता है |

हमारे अंकगणितीय अंग का पहला भाग समानांतर भंडारण अंग होना चाहिए | जो एक संख्या प्राप्त कर सकता है और इसे पहले से ही इसमें जोड़ सकता है | जो इसकी पदार्थ को भी साफ़ करने में सक्षम है और जो इसमें सम्मिलित है उसे संग्रहीत कर सकता है। ऐसे अंग को हम संचायक कहेंगे। यह अतीत और वर्तमान में सबसे विविध प्रकार की कंप्यूटिंग मशीनों में सैद्धांतिक रूप से अधिक पारंपरिक है, उदाहरण। डेस्क गुणक, मानक आईबीएम काउंटर, अधिक आधुनिक रिले मशीनें, ईएनआईएसी (मूल में बोल्डफेस: गोल्डस्टाइन और वॉन न्यूमैन, 1946; बेल और नेवेल 1971 में पृष्ठ 98)।

चूँकि, संचायक प्रति अंकगणितीय संचालन के अधिक निर्देशों की कीमत पर आता है, विशेष रूप से 'पढ़ें-संशोधित-लिखें' निर्देशों के संबंध में, जैसे कि इंक्रीमेंट अप्रत्यक्ष रूप से रजिस्टर की पदार्थ को रजिस्टर r2 द्वारा इंगित किया जाता है। A संचायक रजिस्टर A को निर्दिष्ट करता है |

Label	Instruction		A	r2	r378,426	Description
			. . .	378,426	17
INCi ( r2 ):	CPY ( i, r2, d, A )		17	378,426	17	Contents of r2 points to r378,426 with contents "17": प्रतिलिपि this to A
	INC ( A )		18	378,426	17	Incement contents of A
	CPY ( d, A, i, r2 )		18	378,426	18	Contents of r2 points to r378,426: प्रतिलिपि contents of A into r378,426

यदि हम संचायक के लिए विशिष्ट नाम से चिपके रहते हैं, उदा. A, हम निर्देशों में संचायक को इंगित कर सकते हैं, उदाहरण के लिए,

INC ( A ) = INCA

चूँकि, जब हम बिना संचायक के CPY निर्देश लिखते हैं तो निर्देश अस्पष्ट होते हैं या उनके पास खाली मापदंड होने चाहिए:

CPY ( d, r2, d, A ) = CPY (d, r2, , )

CPY ( d, A, d, r2 ) = CPY ( , , d, r2)

ऐतिहासिक रूप से क्या हुआ है कि इन दो सीपीवाई निर्देशों को विशिष्ट नाम प्राप्त हुए हैं; चूँकि, कोई सम्मेलन उपस्थित नहीं है। परंपरा (उदाहरण के लिए डोनाल्ड नुथ (1973) काल्पनिक मिक्स कंप्यूटर) लोड और स्टोर नामक दो नामों का उपयोग करती है। यहां हम i/d मापदंड जोड़ रहे हैं:

LDA ( d/i, r_s ) =_def CPY ( d/i, r_s, d, A )

STA ( d/i, r_d ) =_def CPY ( d, A, d/i, r_d )

विशिष्ट संचायक-आधारित मॉडल में इसके सभी दो-चर अंकगणितीय और निरंतर संचालन होंगे (जैसे ADD (A, r), SUB (A, r) ) उपयोग (i) संचायक की पदार्थ, साथ में (ii) निर्दिष्ट रजिस्टर की पदार्थ . वन-वैरिएबल ऑपरेशंस (जैसे INC (A), DEC (A) और CLR (A) ) के लिए केवल संचायक की आवश्यकता होती है। दोनों निर्देश-प्रकार संचायक में परिणाम (जैसे योग, अंतर, उत्पाद, भागफल या शेष) जमा करते हैं।

उदाहरण: INCA = [A] +1 → A

उदाहरण: ADDA (r_s) = [A] + [r_s] → A

उदाहरण: MULA (r_s) = [A] * [r_s] → A

यदि हम ऐसा चुनते हैं, तो हम म्नेमोनिच्स को संक्षिप्त कर सकते हैं क्योंकि कम से कम स्रोत-रजिस्टर और गंतव्य रजिस्टर सदैव संचायक A होता है। इस प्रकार हमारे पास है:

{ LDA (i/d, r_s), STA (i/d, r_d), CLRA, INCA, DECA, ADDA (r_s), SUBA (r_s), MULA (r_s), DIVA (r_s), etc.)

अप्रत्यक्ष पता रजिस्टर N की धारणा

यदि हमारे मॉडल में असीमित संचायक है तो क्या हम अन्य सभी रजिस्टरों को बाध्य कर सकते हैं ? जब तक हम कम से कम असीमित रजिस्टर प्रदान नहीं करते हैं | जिससे हम अपने अप्रत्यक्ष पते प्राप्त करते हैं।

न्यूनतम दृष्टिकोण स्वयं का उपयोग करना है (शॉनहेज ऐसा करता है)।

एक अन्य दृष्टिकोण (शॉनहेज यह भी करता है) विशिष्ट रजिस्टर को अप्रत्यक्ष पता रजिस्टर घोषित करना है और इस रजिस्टर के सापेक्ष अप्रत्यक्षता को सीमित करना है (स्कोनहेज का रैम0 मॉडल अप्रत्यक्ष और साथ ही प्रत्यक्ष निर्देशों के लिए A और N दोनों रजिस्टरों का उपयोग करता है)। फिर से हमारे नए रजिस्टर में कोई पारंपरिक नाम नहीं है | संभवतः N आईएनडीएक्स से, या इनडायरेक्ट या एड्रेस नंबर है।

अधिकतम लचीलेपन के लिए, जैसा कि हमने संचायक A के लिए किया है | हम N को वेतन वृद्धि, कमी, स्पष्ट, परीक्षण, प्रत्यक्ष प्रति, आदि के लिए सिर्फ एक और रजिस्टर विषय मानेंगे। फिर से हम निर्देश को एकल-मापदंड में सिकोड़ सकते हैं जो दिशा और संकेत प्रदान करता है, उदाहरण के लिए।

LDAN (i/d) = CPY (i/d, N, d, A); लोड संचायक इनडायरेक्शन रजिस्टर के माध्यम से |

STAN (i/d) = CPY (d, A, i/d, N) स्टोर एक्यूमुलेटर इनडायरेक्शन रजिस्टर के माध्यम से |

यह इतना रोचक विधि क्यों है ? कम से कम दो कारण है |

(1) बिना मापदंडों के निर्देश समुच्चय है |

स्कोनहागे अपने RAM0 निर्देश समुच्चय को बनाने के लिए ऐसा करता है। नीचे अनुभाग देखें।

(2) रैम को पोस्ट-ट्यूरिंग मशीन में कम करें:

अतिसूक्ष्मवादी के रूप में प्रस्तुत करते हुए, हम संचायक A और अप्रत्यक्ष रजिस्टर N को छोड़कर सभी रजिस्टरों को कम कर देते हैं उदा. r = {r0, r1, r2, ...} (बहुत-) परिबद्ध-क्षमता वाले कबूतर-छिद्रों की असीमित स्ट्रिंग के लिए। ये कुछ भी नहीं करेंगे किन्तु (बहुत-) बंधे हुए नंबरों को पकड़ेंगे। मूल्य {0, 1} के साथ अकेला बिट। इसी तरह हम संचायक को एक बिट तक सिकोड़ते हैं। हम किसी भी अंकगणित को रजिस्टरों {A, N} तक सीमित रखते हैं, रजिस्टरों की पदार्थ को संचायक में खींचने के लिए अप्रत्यक्ष संचालन का उपयोग करते हैं और संचायक से रजिस्टर में 0 या 1 लिखते हैं:

{ LDA (i, N), STA (i, N), CLR (A/N), INC (A/N), DEC(N), JZ (A/N, I_z), JZ (I_z), H }

हम ERASE और PRINT: [ERASE]=0, [PRINT]=1 नामक दो स्थिर रजिस्टरों के उपयोग से A को और आगे बढ़ाते हैं और पूरी तरह से समाप्त कर देते हैं।

{ CPY (d, ERASE, i, N), CPY (d, PRINT, i, N), CLR (N), INC (N), DEC (N), JZ (i, N, I_z), JZ (I_z), H }

प्रतिलिपि निर्देशों का नाम बदलें और INC (N) = राइट, DEC (N) = LEFT पर कॉल करें और हमारे पास पोस्ट-ट्यूरिंग मशीन के समान निर्देश हैं, साथ ही अतिरिक्त CLRN:

{ ERASE, PRINT, CLRN, RIGHT, LEFT, JZ (i, N, I_z), JZ (I_z), H }

संकेत के साथ रैम की ट्यूरिंग समानता

ऊपर दिए गए अनुभाग में हमने अनौपचारिक रूप से दिखाया कि असीमित अप्रत्यक्ष क्षमता वाली रैम पोस्ट-ट्यूरिंग मशीन का उत्पादन करती है। पोस्ट-ट्यूरिंग मशीन ट्यूरिंग समतुल्य है, इसलिए हमने दिखाया है कि अप्रत्यक्ष रैम ट्यूरिंग समतुल्य है।

हम यहां थोड़ा और औपचारिक प्रदर्शन देते हैं। हमारे मॉडल को तीन आरक्षित रजिस्टरों E , P , और N के साथ डिजाइन करके प्रारंभ करें, साथ ही दाईं ओर रजिस्टर 1, 2, ..., n का असीमित समुच्चय। रजिस्टर 1, 2, ..., n को टेप का वर्ग माना जाएगा। सिर वर्तमान में देख रहा है कि स्कैन वर्ग के लिए N अंक अंकित करें। सिर को सशर्त छलांग के रूप में माना जा सकता है – ध्यान दें कि यह अप्रत्यक्ष संबोधन का उपयोग करता है (सीएफ एल्गोट-रॉबिन्सन पी. 398)। जैसा कि हम N को घटाते या बढ़ाते हैं (स्पष्ट) सिर वर्गों के साथ बाएं या दाएं चलेगा। हम अप्रत्यक्ष CPY का उपयोग करते हुए N द्वारा बताए गए अनुसार E = 0 या P = 1 की पदार्थ को स्कैन किए गए वर्ग में ले जाएंगे।

तथ्य यह है कि हमारा टेप बायीं ओर है, हमें सामान्य समस्या के साथ प्रस्तुत करता है: जब भी LEFT होता है तो हमारे निर्देशों को यह निर्धारित करने के लिए परीक्षण करना होगा कि N की पदार्थ शून्य है या नहीं यदि ऐसा है तो हमें इसकी गिनती 0 पर छोड़ देनी चाहिए (यह डिजाइनरों के रूप में हमारी पसंद है उदाहरण के लिए हमारे पास मशीन/मॉडल हमारे द्वारा चुनी गई घटना को ट्रिगर कर सकता है)।

Instruction set 1 (augmented): { INC (N), DEC (N), CLR (N), CPY (d, r_s,i, N), JZ ( i, r, z ), HALT }

निम्न तालिका दोनों पोस्ट-ट्यूरिंग निर्देशों को उनके रैम समकक्ष निर्देशों के संदर्भ में परिभाषित करती है और उनके कामकाज का उदाहरण देती है। रजिस्टर r0-r5 के टेप के साथ सिर का (स्पष्ट) स्थान। छायांकित दिखाया गया है |

Mnemonic	label:			E	P	N		r0	r1	r2	r3	r4	r5	etc.	Action on registers	Action on finite state machine Instruction Register IR
	start:			0	1	3					1	0
R	right:	INC ( N )		0	1	4					1	0			[N] +1 → N	[IR] +1 → IR
P	print:	CPY ( d, P, i, N )		0	1	4					1	1			[P]=1 → [N]=r4	[IR] +1 → IR
E	erase:	CPY ( d, E, i, N )		0	1	4					1	0			[E]=0 → [N]=r4	[IR] +1 → IR
L	left:	JZ ( i, N, end )		0	1	4					1	0			none	IF N =r4] =0 THEN "end" → IR अन्य [IR]+1 → IR
		DEC ( N )		0	1	3					1	0			[N] -1 → N
J0 ( halt )	jump_if_blank:	JZ ( i, N, end )		0	1	3					1	0			none	IF N =r3] =0 THEN "end" → IR अन्य [IR]+1 → IR
J1 ( halt )	jump_if_mark:	JZ ( i, N, halt )		0	1	3					1	0			N =r3] → A	IF N =r3] =0 THEN "end" → IR अन्य [IR]+1 → IR
	end	. . . etc.		0	1	3					1	0
	halt:	H		0	1	3					1	0			none	[IR] +1 → IR

उदाहरण: बंधा हुआ संकेत ऐसी मशीन देता है जो ट्यूरिंग समकक्ष नहीं है |

इस पूरे प्रदर्शन के समय हमें यह ध्यान रखना होगा कि परिमित स्तर मशीन की तालिका में दिए गए निर्देश परिमित हैं, अर्थात परिमित:

केवल नियमों का परिमित समुच्चय होने के अतिरिक्त जो विशिष्ट प्रकार की समस्या को हल करने के लिए संचालन का क्रम देता है, एल्गोरिथ्म में पांच महत्वपूर्ण विशेषताएं हैं [परिमितता, निश्चितता, इनपुट, आउटपुट, प्रभावशीलता] (इटैलिक जोड़ा गया, नुथ पी। 4- 7).

कठिनाई उत्पन्न होती है क्योंकि रजिस्टरों में स्पष्ट नाम (संख्या) होते हैं और इसे एक्सेस करने के लिए हमारी मशीन को प्रत्येक को नाम से पुकारना चाहिए।

हम CASE ऑपरेटर के साथ अप्रत्यक्ष CPY (i, q, d, φ) बनाएंगे। लक्ष्य रजिस्टर का पता रजिस्टर क्यू की पदार्थ द्वारा निर्दिष्ट किया जाएगा; एक बार जब CASE ऑपरेटर यह निर्धारित कर लेता है कि यह संख्या क्या है, तो CPY उस संख्या के साथ रजिस्टर की पदार्थ को सीधे रजिस्टर φ में जमा कर देगा। हमें अतिरिक्त रजिस्टर की आवश्यकता होगी जिसे हम y कहेंगे – यह अप-काउंटर के रूप में कार्य करता है।

तो निम्नलिखित वास्तव में रचनात्मक प्रदर्शन या प्रमाण है कि हम वास्तव में अप्रत्यक्ष सीपीवाई (i, q, d, φ) को हमारे काउंटर मशीन/मॉडल में हार्डवेयर डिज़ाइन परिवर्तन के बिना अनुकरण कर सकते हैं। चूँकि, ध्यान दें कि क्योंकि यह अप्रत्यक्ष CPY परिमित स्तर मशीन के आकार/सीमा से घिरा है, इस अप्रत्यक्ष CPY का उपयोग करने वाला आरएएसपी केवल पुनरावर्ती कार्यों की गणना कर सकता है, mu पुनरावर्ती कार्यों के पूर्ण सूट की नहीं।

क्लेन (1952) (पृष्ठ 229) और बूलोस-बर्गेस-जेफरी (2002) (पृष्ठ 74) में CASE संचालक का वर्णन किया गया है; बाद के लेखक इसकी उपयोगिता पर जोर देते हैं। निम्नलिखित परिभाषा प्रति क्लेन है किन्तु परिचित IF-THEN-अन्य निर्माण को दर्शाने के लिए संशोधित की गई है।

CASE ऑपरेटर प्राकृतिक संख्या को φ में लौटाता है, जो इस बात पर निर्भर करता है कि कौन सा स्थिति संतुष्ट है, case_0 से प्रारंभ होता है और क्रमिक रूप से case_last तक जाता है; यदि कोई स्थिति संतुष्ट नहीं होता है तो डिफ़ॉल्ट (उर्फ वूप्स) नामक संख्या को φ में वापस कर दिया जाता है (यहाँ 'x' मापदंडों के कुछ चयन को निर्दिष्ट करता है, उदाहरण के लिए q रजिस्टर करें और स्ट्रिंग r0, ... rlast )):

स्थितियों द्वारा परिभाषा φ ('x', y):

• • case_0: IF Q₀(x, y) is true THEN φ₀(x, y) ELSE
  • case_1: IF Q₁(x, y) is true THEN φ₁(x, y) ELSE
  • cases_2 through case_next_to_last: etc. . . . . . . . . ELSE
  • case_last: IF Q_last(x, y) is true THEN φ_last(x, y) ELSE
  • default: do φ_default(x, y)

क्लेन की आवश्यकता है कि विधेय Q_n कि परीक्षण करना सभी परस्पर अनन्य हैं विधेय ऐसे कार्य हैं जो आउटपुट के लिए केवल {true, false} उत्पन्न करते हैं | बूलोस-बर्गेस-जेफरी आवश्यकता को जोड़ते हैं कि स्थिति संपूर्ण हैं।

हम रजिस्टर क्यू में एक नंबर से प्रारंभ करते हैं जो लक्ष्य रजिस्टर के पते का प्रतिनिधित्व करता है। किन्तु यह संख्या क्या है? विधेय यह पता लगाने के लिए परीक्षण करेगा, एक के बाद एक परीक्षण: JE (q, y, z) के बाद INC (y)। एक बार संख्या की स्पष्ट रूप से पहचान हो जाने के बाद, CASE ऑपरेटर सीधे/स्पष्ट रूप से इस रजिस्टर की पदार्थ को φ में कॉपी कर लेता है:

स्थितियों द्वारा परिभाषा CPY (i, q, d, φ) =_def φ (q, r0, ..., rlast, y) =

• case_0: IF CLR (y), [q] - [y]=0 THEN CPY ( r0, φ ), J (exit) ELSE
• case_1: IF INC (y), [q] = [y]=1 THEN CPY ( r1, φ ), J (exit) ELSE
• case_2 through case n: IF . . . THEN . . . ELSE
• case_n: IF INC (y), [q] = [y]=n THEN CPY ( rn, φ ), J (exit) ELSE
• case_n+1 to case_last: IF . . . THEN . . . ELSE
• case_last: IF INC (y), [q] = [y]="last" THEN CPY ( rlast, φ ), J (exit) ELSE
• default: woops

Case_0 (y पर पुनरावर्तन का आधार चरण) इस तरह दिखता है:

*

• case_0:

• CLR ( y ) ; set register y = 0
• JE ( q, y, _φ0 )
• J ( case_1 )

• _φ0: CPY ( r0, φ )
• J ( exit )

• case_1: etc.

Case_n (इंडक्शन स्टेप) ऐसा दिखता है; याद रखें, n , n+1 , ..., अंतिम का प्रत्येक उदाहरण स्पष्ट प्राकृतिक संख्या होना चाहिए:

*

• case_n:

• INC ( y )
• JE ( q, y, _φn )
• J ( case_n+1)

• _φn: CPY ( rn, φ )
• J ( exit )

• case__n+1: etc.

Case_last इंडक्शन को रोकता है और CASE ऑपरेटर को बाध्य करता है (और इस तरह अप्रत्यक्ष कॉपी ऑपरेटर को बाध्य करता है):

• • case_last:

  • INC ( y )
  • JE ( q, y, _φlast )
  • J ( woops )

  • _φlast: CPY ( rlast, φ )
  • J ( exit ) वूप्स: हम एक सीमा से बाहर के प्रयास को कैसे हैंडल करते हैं ?

*

• exit: etc.

यदि CASE अनंत तक जारी रह सकता है तो यह ऑपरेटर में होगा। किन्तु यह नहीं हो सकता इसका परिमित स्तर मशीन स्तर रजिस्टर अपनी अधिकतम संख्या तक पहुँच गया है (65365 = 11111111,11111111₂ में)) या इसकी तालिका में निर्देश समाप्त हो गए हैं | आखिर यह परिमित मशीन है।

मॉडल के उदाहरण

रजिस्टर-टू-रजिस्टर (पढ़ें-संशोधित-लिखें) कुक और रेकहो (1973) का मॉडल

सामान्यतः सामने आने वाला कुक और रेचको मॉडल टर्नरी-रजिस्टर माल्ज़ेक मॉडल जैसा है (नूथ मेमोनिक्स के साथ लिखा गया है) मूल निर्देशों में टीआरए, रीड, प्रिंट को छोड़कर कोई स्मृति चिन्ह नहीं था)।

• LOAD ( C, rd ) ; C → rd, C कोई पूर्णांक है

उदाहरण: LOAD ( 0, 5 ) रजिस्टर 5 को साफ़ करेगा।

• ADD ( rs1, rs2, rd ) ; [rs1] + [rs2] → rd, रजिस्टर समान या भिन्न हो सकते हैं;

उदाहरण: ADD ( A, A, A ) रजिस्टर A की पदार्थ को दोगुना कर देगा।

• SUB ( rs1, rs2, rd ) ; [rs1] - [rs2] → rd, रजिस्टर समान या भिन्न हो सकते हैं:

उदाहरण: SUB ( 3, 3, 3 ) रजिस्टर 3 को साफ़ करेगा।

• प्रतिलिपि ( i, rp, d, rd ) ; [[rp] ] → rd, पॉइंटर-रजिस्टर R_p द्वारा इंगित स्रोत-रजिस्टर की पदार्थ को अप्रत्यक्ष रूप से कॉपी करें गंतव्य रजिस्टर में।
• प्रतिलिपि ( d, rs, i, rp ) ; [rs] → [rp]. स्रोत रजिस्टर R की पदार्थ की प्रतिलिपि बनाएँ_s पॉइंटर-रजिस्टर R_p. द्वारा इंगित गंतव्य-रजिस्टर में
• JNZ ( r, Iz ) ; सशर्त कूद यदि [R] सकारात्मक है; अर्थात IF [r]> 0 फिर निर्देश z पर जाएं और अनुक्रम में जारी रखें (कुक और रेकहो इसे कॉल करें: Xj> 0 होने पर लाइन m पर नियंत्रण स्थानांतरित करें)
• READ ( rd ) ; इनपुट को गंतव्य रजिस्टर R_d में कॉपी करें
• PRINT ( rs ) ; स्रोत रजिस्टर R_s की पदार्थ की प्रतिलिपि बनाएँ आउटपुट के लिए।

शॉनहेज का RAM0 और RAM1 (1980)

शॉनहेज (1980) अपने एसएमएम पॉइंटर मशीन मॉडल की समानता के प्रमाण के लिए चुने गए एक बहुत ही , परमाणु मॉडल का वर्णन करता है:

किसी भी स्पष्ट संबोधन से बचने के लिए RAM0 में पदार्थ z के साथ संचायक है और वर्तमान पदार्थ n (प्रारंभ में 0) (पृष्ठ 494) के साथ अतिरिक्त पता रजिस्टर है।

'RAM1 मॉडल': शॉनहेज दर्शाता है कि कैसे उसके निर्माण का उपयोग अधिक सामान्य, प्रयोग करने योग्य उत्तराधिकारी-जैसे रैम बनाने के लिए किया जा सकता है | (इस लेख के निमोनिक्स का उपयोग करके):

• LDA k ; k --> A , k स्थिरांक है, सुस्पष्ट संख्या जैसे कि 47
• LDA ( d, r ) ; [r] → A ; सीधे लोड A
• LDA ( i, r ) ; [[r]] → A ; अप्रत्यक्ष रूप से लोड A
• STA ( d, r ) ; [A] → r ; सीधे स्टोर A
• STA ( i, r ) ; [A] → [r] ; अप्रत्यक्ष रूप से स्टोर A
• JEA ( r, z ) ; IF [A] = [r] then Iz अन्य continue
• INCA ; [A] + 1 --> A

RAM0 मॉडल: स्कोनहागे की RAM0 मशीन में 6 निर्देश हैं जो एक अक्षर से संकेतित हैं (छठे C xxx में 'स्किप ओवर नेक्स्ट मापदंड' सम्मिलित है। स्कोनहागे ने संचायक को z , N के साथ n , आदि के साथ नामित किया है। स्कोनहागे के म्नेमोनिच्स के अतिरिक्त हम इसका उपयोग करेंगे स्मृति चिन्ह ऊपर विकसित हुआ।

• (Z), CLRA: 0 → A
• (A), INCA: [A] +1 → A
• (N), सीपीयान: [A] → N
• (A), LDAA: [[A]] → A ; पता पंजीकृत करने के लिए A अंक की पदार्थ; A में रजिस्टर की पदार्थ डालें
• (S), STAN: [A] → [N] ; पता अंकित करने के लिए N अंक की पदार्थ; A की पदार्थ को N द्वारा इंगित रजिस्टर में रखें
• (C), JAZ ( z ): [A] = 0 then go to Iz ; उसके इलाज में अस्पष्ट

संकेत (i) सीपीयान से आता है (कॉपी / ट्रांसफर पदार्थ A से N) स्टोर ए के माध्यम से एन स्टेन के साथ काम कर रहा है, और (ii) अजीबोगरीब अप्रत्यक्ष निर्देश से LDAA ( [[A]] → [A] ).

फुटनोट्स

परिमित बनाम असीम

निश्चित तथ्य यह है कि किसी भी प्रकार की काउंटर मशीन बिना असीमित रजिस्टर-एड्रेस रजिस्टर को नाम से रजिस्टर R निर्दिष्ट करना चाहिए, यह इंगित करता है |कि मॉडल को परिमित होने के लिए R की आवश्यकता है, चूँकि यह इस अर्थ में असीमित है कि मॉडल संख्या के लिए कोई ऊपरी सीमा नहीं दर्शाता है अपना कार्य करने के लिए आवश्यक रजिस्टरों की संख्या उदाहरण के लिए, हमें r <83,617,563,821,029,283,746 और न ही r <2^1,000,001, आदि की आवश्यकता नहीं है।

इस प्रकार हमारा मॉडल निश्चित गणना करने के लिए आवश्यक होने पर रजिस्टरों की संख्या का विस्तार कर सकता है। चूँकि इसका कारण यह है कि मॉडल जिस भी संख्या तक फैलता है वह परिमित होना चाहिए | यह प्राकृतिक संख्या के साथ अनुक्रमणीय होना चाहिए: ω कोई विकल्प नहीं है।

अप्रत्यक्ष पते को निर्दिष्ट करने वाले रजिस्टर का पता प्रदान करने के लिए हम असीमित रजिस्टर प्रदान करके इस प्रतिबंध से बच सकते हैं।

यह भी देखें

• रियल रैम
• ट्रांसडिकोटोमस मॉडल

बाहरी संबंध

• Random Access Machine Emulator
• Random Access Machine Emulator
• Random Access Machine Emulator

संदर्भ

With a few exceptions, these references are the same as those at Register machine.

• • Goldstine, Herman H., and von Neumann, John, "Planning and Coding of the Problems for an Electronic Computing Instrument", Rep. 1947, Institute for Advanced Study, Princeton. Reprinted on pp. 92–119 in Bell, C. Gordon and Newell, Allen (1971), Computer Structures: Readings and Examples, McGraw-Hill Book Company, New York. ISBN 0-07-004357-4}.
• George Boolos, John P. Burgess, Richard Jeffrey (2002), Computability and Logic: Fourth Edition, Cambridge University Press, Cambridge, England. The original Boolos-Jeffrey text has been extensively revised by Burgess: more advanced than an introductory textbook. "Abacus machine" model is extensively developed in Chapter 5 Abacus Computability; it is one of three models extensively treated and compared – the Turing machine (still in Boolos' original 4-tuple form) and recursion the other two.
• Arthur Burks, Herman Goldstine, John von Neumann (1946), Preliminary discussion of the logical design of an electronic computing instrument, reprinted pp. 92ff in Gordon Bell and Allen Newell (1971), Computer Structures: Readings and Examples, mcGraw-Hill Book Company, New York. ISBN 0-07-004357-4 .
• Stephen A. Cook and Robert A. Reckhow (1973), Time-bounded random access machines, Journal of Computer Systems Science 7(4):354-375.
• Martin Davis (1958), Computability & Unsolvability, McGraw-Hill Book Company, Inc. New York.
• Calvin Elgot and Abraham Robinson (1964), Random-Access Stored-Program Machines, an Approach to Programming Languages, Journal of the Association for Computing Machinery, Vol. 11, No. 4 (October, 1964), pp. 365–399.
• J. Hartmanis (1971), "Computational Complexity of Random Access Stored Program Machines," Mathematical Systems Theory 5, 3 (1971) pp. 232–245.
• John Hopcroft, Jeffrey Ullman (1979). Introduction to Automata Theory, Languages and Computation, 1st ed., Reading Mass: Addison-Wesley. ISBN 0-201-02988-X. A difficult book centered around the issues of machine-interpretation of "languages", NP-Completeness, etc.
• Stephen Kleene (1952), Introduction to Metamathematics, North-Holland Publishing Company, Amsterdam, Netherlands. ISBN 0-7204-2103-9.
• Donald Knuth (1968), The Art of Computer Programming, Second Edition 1973, Addison-Wesley, Reading, Massachusetts. Cf pages 462-463 where he defines "a new kind of abstract machine or 'automaton' which deals with linked structures."
• Joachim Lambek (1961, received 15 June 1961), How to Program an Infinite Abacus, Mathematical Bulletin, vol. 4, no. 3. September 1961 pages 295-302. In his Appendix II, Lambek proposes a "formal definition of 'program'. He references Melzak (1961) and Kleene (1952) Introduction to Metamathematics.
• Z. A. Melzak (1961, received 15 May 1961), An informal Arithmetical Approach to Computability and Computation, Canadian Mathematical Bulletin, vol. 4, no. 3. September 1961 pages 279-293. Melzak offers no references but acknowledges "the benefit of conversations with Drs. R. Hamming, D. McIlroy and V. Vyssots of the Bell telephone Laborators and with Dr. H. Wang of Oxford University."
• Marvin Minsky (1961). "Recursive Unsolvability of Post's Problem of 'Tag' and Other Topics in Theory of Turing Machines". Annals of Mathematics. The Annals of Mathematics, Vol. 74, No. 3. 74 (3): 437–455. doi:10.2307/1970290. JSTOR 1970290.
• Marvin Minsky (1967). Computation: Finite and Infinite Machines (1st ed.). Englewood Cliffs, N. J.: Prentice-Hall, Inc. In particular see chapter 11: Models Similar to Digital Computers and chapter 14: Very Simple Bases for Computability. In the former chapter he defines "Program machines" and in the later chapter he discusses "Universal Program machines with Two Registers" and "...with one register", etc.
• John C. Shepherdson and H. E. Sturgis (1961) received December 1961 Computability of Recursive Functions, Journal of the Association for Computing Machinery (JACM) 10:217-255, 1963. An extremely valuable reference paper. In their Appendix A the authors cite 4 others with reference to "Minimality of Instructions Used in 4.1: Comparison with Similar Systems".

• Kaphengst, Heinz, Eine Abstrakte programmgesteuerte Rechenmaschine', Zeitschrift fur mathematische Logik und Grundlagen der Mathematik:5 (1959), 366-379.
• Ershov, A. P. On operator algorithms, (Russian) Dok. Akad. Nauk 122 (1958), 967-970. English translation, Automat. Express 1 (1959), 20-23.
• Péter, Rózsa Graphschemata und rekursive Funktionen, Dialectica 12 (1958), 373.
• Hermes, Hans Die Universalität programmgesteuerter Rechenmaschinen. Math.-Phys. Semsterberichte (Göttingen) 4 (1954), 42-53.

• Arnold स्कोनहागे (1980), Storage Modification Machines, Society for Industrial and Applied Mathematics, SIAM J. Comput. Vol. 9, No. 3, August 1980. Wherein Schōnhage shows the equivalence of his SMM with the "successor रैम" (Random Access Machine), etc. resp. Storage Modification Machines, in Theoretical Computer Science (1979), pp. 36–37
• Peter van Emde Boas, "Machine Models and Simulations" pp. 3–66, in: Jan van Leeuwen, ed. Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity, The MIT PRESS/Elsevier, 1990. ISBN 0-444-88071-2 (volume A). QA 76.H279 1990. van Emde Boas's treatment of SMMs appears on pp. 32–35. This treatment clarifies Schōnhage 1980 – it closely follows but expands slightly the Schōnhage treatment. Both references may be needed for effective understanding.
• Hao Wang (1957), A Variant to Turing's Theory of Computing Machines, JACM (Journal of the Association for Computing Machinery) 4; 63-92. Presented at the meeting of the Association, June 23–25, 1954.