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

Not to be confused with Random-access memory.

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

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

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

मॉडल का परिचय

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

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

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

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

• [आर] का मतलब पता आर के साथ रजिस्टर की सामग्री है। यहाँ लेबल 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 के रूप में संक्षिप्त किया गया है:

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

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

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

परिभाषा: पॉइंटर रजिस्टर की सामग्री लक्ष्य रजिस्टर की ओर इशारा करती है – लक्ष्य या तो स्रोत या गंतव्य रजिस्टर हो सकता है।

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

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

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

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

निम्नलिखित निर्देश mnemonics उदा। सीएलआर (आर) मनमानी हैं; कोई मानक मौजूद नहीं है।

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

'बेस मॉडल 1': मिन्स्की (1961) विज़ुअलाइज़ेशन और लैम्बेक (1961) के निकटतम मॉडल:

• {रजिस्टर आर की वृद्धि सामग्री, रजिस्टर आर की गिरावट सामग्री, यदि रजिस्टर आर की सामग्री शून्य है तो निर्देश I पर जाएं_z ELSE अगले निर्देश पर जारी रखें}:

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 ELSE [IR] + 1 → IR
Halt	H	none	[IR] → IR

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

• {रजिस्टर आर की सामग्री में वृद्धि, रजिस्टर आर की सामग्री को साफ करें, रजिस्टर आर की सामग्री आईएफ_j रजिस्टर आर की सामग्री के बराबर है_k फिर निर्देश I पर जाएं_z ELSE गोटो अगले निर्देश के लिए }

Instruction	Mnemonic	Action on register(s) "r"	Action on finite state machine's Instruction Register, IR
CLeaR	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 ELSE [IR] + 1 → IR
Halt	H	none	[IR] → IR

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

• {रजिस्टर आर की सामग्री में वृद्धि, रजिस्टर आर की सामग्री की प्रतिलिपि बनाएँ_j आर दर्ज करने के लिए_k, अगर रजिस्टर आर की सामग्री_j रजिस्टर आर की सामग्री के बराबर है_k फिर निर्देश I पर जाएं_z ELSE गोटो अगले निर्देश के लिए }

Instruction	Mnemonic	Action on register(s) "r"	Action on finite state machine's Instruction Register, IR
COPY	COPY (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 ELSE [IR] + 1 → IR
Halt	H	none	[IR] → IR

बेस सेट से सुविधा निर्देश बनाना

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

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

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

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

• सीएलआर (आर) =_equiv
• पाश: JZ (आर, बाहर निकलें)

• दिसंबर (आर)
• JZ (0, लूप)

• बाहर निकलें: आदि।

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

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

• { सीएलआर (आर), डीईसी (आर), आईएनसी (आर), सीपीवाई (आर_s, आर_d ), जेजेड (आर, जेड), जेई (आर_j, आर_k, जेड), जे (जेड)}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

कभी-कभी सीएलआर (आर) के उपयोग के बाद आईएनसी (आर) बार-बार के बार के बाद निरंतर के बनाया जाएगा – उदा. स्थिर 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वें स्थान पर कैसे पहुंच सकता है?

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

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

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

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

वह हमें एक बाउंडेड आरपीटी प्रदान करता है जो सीएलआर (आर) और आईएनसी (आर) के साथ मिलकर किसी भी आदिम पुनरावर्ती फ़ंक्शन की गणना कर सकता है, और वह ऊपर उद्धृत अनबाउंड आरपीटी प्रदान करता है जो μ ऑपरेटर की भूमिका निभा रहा है; यह 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 निर्दिष्ट करने की आवश्यकता होगी – अप्रत्यक्ष/प्रत्यक्ष। एक मायने में यह नया आई/डी पैरामीटर एक स्विच है जो निर्देश में निर्दिष्ट प्रत्यक्ष पता प्राप्त करने के लिए एक तरफ फ़्लिप करता है या पॉइंटर रजिस्टर से अप्रत्यक्ष पता प्राप्त करने का दूसरा तरीका है (जो पॉइंटर रजिस्टर{{spaced ndash}कुछ मॉडलों में प्रत्येक रजिस्टर एक सूचक रजिस्टर हो सकता है – निर्देश द्वारा निर्दिष्ट किया गया है)। यह पारस्परिक रूप से अनन्य लेकिन संपूर्ण विकल्प मामलों द्वारा परिभाषा का एक और उदाहरण है, और नीचे दिए गए उदाहरण में दिखाया गया अंकगणितीय समकक्ष क्लेन (1952) पी में परिभाषा से लिया गया है। 229.

उदाहरण: सीपीवाई (अप्रत्यक्ष_source, आर_source, प्रत्यक्ष_destination, आर_destination )

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

मैं * [आर_s] + (1-आई)*आर_s

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

उदाहरण: CPY (1, 3, 0, 4) = CPY (अप्रत्यक्ष, reg 3, प्रत्यक्ष, 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) ने अपने मॉडल पी₀ और पी'₀ COPY निर्देशों के साथ, और Cook-Reckhow (1973) केवल दो अप्रत्यक्ष निर्देशों के साथ अपना संचायक-आधारित मॉडल प्रदान करते हैं{{spaced ndash}अप्रत्यक्ष रूप से संचायक को कॉपी करें, संचायक से अप्रत्यक्ष रूप से कॉपी करें।

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

सीपीवाई (डी, आर_s, डॉ_d ) = स्रोत-रजिस्टर से सीधे गंतव्य-रजिस्टर पर कॉपी करें

सीपीवाई (आई, आर_sp, डॉ_d ) = स्रोत-सूचक रजिस्टर आर में पाए जाने वाले स्रोत पते का उपयोग करके अप्रत्यक्ष रूप से गंतव्य-रजिस्टर पर कॉपी करें_sp.

सीपीवाई (डी, आर_s, मैं, आर_dp ) = गंतव्य-सूचक रजिस्टर आर में पाए जाने वाले गंतव्य पते का उपयोग करके अप्रत्यक्ष रूप से स्रोत-रजिस्टर की सामग्री को रजिस्टर में कॉपी करें_dp.

सीपीवाई (आई, आर_sp, मैं, आर_dp ) = स्रोत-सूचक रजिस्टर r में पाए जाने वाले पते के साथ अप्रत्यक्ष रूप से स्रोत रजिस्टर की सामग्री को कॉपी करें_sp, गंतव्य रजिस्टर में पते के साथ गंतव्य-सूचक रजिस्टर r में पाया जाना है_dp)

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

[आर_s1] + [आर_s2] → आर_d

निकलेगा:

• जोड़ें (डी, आर_s1, डॉ_s2, डॉ_d )
• जोड़ें (मैं, आर_sp1, डॉ_s2, डॉ_d )
• जोड़ें (डी, आर_s1, मैं, आर_sp2, डॉ_d )
• जोड़ें (मैं, आर_sp1, मैं, आर_sp2, डॉ_d )
• जोड़ें (डी, आर_s1, डॉ_s2, मैं, आर_dp )
• जोड़ें (मैं, आर_sp1, डॉ_s2, मैं, आर_dp )
• जोड़ें (डी, आर_s1, मैं, आर_sp2, मैं, आर_dp )
• जोड़ें (मैं, आर_sp1, मैं, आर_sp2, मैं, आर_dp )

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

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

हमारे अंकगणितीय अंग का पहला भाग ... एक समानांतर भंडारण अंग होना चाहिए जो एक संख्या प्राप्त कर सकता है और इसे पहले से ही इसमें जोड़ सकता है, जो इसकी सामग्री को भी साफ़ करने में सक्षम है और जो इसमें शामिल है उसे संग्रहीत कर सकता है। ऐसे अंग को हम Accumulator कहेंगे। यह अतीत और वर्तमान में सबसे विविध प्रकार की कंप्यूटिंग मशीनों में सैद्धांतिक रूप से काफी पारंपरिक है, उदा। डेस्क गुणक, मानक आईबीएम काउंटर, अधिक आधुनिक रिले मशीनें, ENIAC (मूल में बोल्डफेस: गोल्डस्टाइन और वॉन न्यूमैन, 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": copy 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: copy contents of A into r378,426

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

आईएनसी (ए) = आईएनसीए

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

सीपीवाई (डी, आर2, डी, ए) = सीपीवाई (डी, आर2, , )

सीपीवाई (डी, ए, डी, आर2) = सीपीवाई (,, डी, आर2)

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

एलडीए (डी/आई, आर_s ) =_def सीपीवाई (डी/आई, आर_s, डी, ए)

एसटीए (डी/आई, आर_d ) =_def सीपीवाई (डी, ए, डी/आई, आर_d )

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

उदाहरण: आईएनसीए = [ए] +1 → ए

उदाहरण: एडीडीए (आर_s) = [ए] + [आर_s] → ए

उदाहरण: मुला (आर_s) = [ए] * [आर_s] → ए

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

{ एलडीए (आई/डी, आर_s), एसटीए (आई / डी, आर_d), सीएलआरए, आईएनसीए, डीईसीए, एडीडीए (आर_s), सुबा (आर_s), से (आर_s), दिवा (आर_s), वगैरह।)

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

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

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

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

एलडीएएन (आई/डी) = सीपीवाई (आई/डी, एन, डी, ए); लोड संचायक indirection रजिस्टर के माध्यम से

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

यह इतना दिलचस्प तरीका क्यों है? कम से कम दो कारण:

(1) बिना मापदंडों के एक निर्देश सेट:

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

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

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

{एलडीए (आई, एन), एसटीए (आई, एन), सीएलआर (ए/एन), आईएनसी (ए/एन), डीईसी(एन), जेडजेड (ए/एन, आई_z), जेडजेड (आई_z), एच }

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

{सीपीवाई (डी, ईआरएएसई, आई, एन), सीपीवाई (डी, प्रिंट, आई, एन), सीएलआर (एन), आईएनसी (एन), डीईसी (एन), जेजेड (आई, एन, आई_z), जेडजेड (आई_z), एच }

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

{ मिटाएं, प्रिंट करें, सीएलआरएन, दाएं, बाएं, जेजेड (आई, एन, आई_z), जेडजेड (आई_z), एच }

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

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

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

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

निर्देश सेट 1 (संवर्धित): { आईएनसी (एन), डीईसी (एन), सीएलआर (एन), सीपीवाई (डी, आर_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 else [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 else [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 else [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 का उपयोग करने वाला एक RASP केवल आदिम पुनरावर्ती कार्यों की गणना कर सकता है, mu पुनरावर्ती कार्यों के पूर्ण सूट की नहीं।

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

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

मामलों द्वारा परिभाषा φ ('x', y):

• case_0: IF Q₀(x, y) तब φ सत्य है₀(एक्स, वाई) अन्य
• case_1: IF Q₁(x, y) तब φ सत्य है₁(एक्स, वाई) अन्य
• Case_2 से case_next_to_last: आदि। . . . . . . . अन्य
• case_last: IF Q_last(x, y) तब φ सत्य है_last(एक्स, वाई) अन्य
• डिफ़ॉल्ट: φ करें_default(एक्स, वाई)

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

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

मामलों द्वारा परिभाषा CPY (i, q, d, φ) =_def φ (q, r0, ..., अंतिम, y) =

• case_0: अगर सीएलआर (y), [q] - [y]=0 तब CPY ( r0, φ ), J (निकास) ELSE
• case_1: IF INC (y), [q] = [y]=1 फिर CPY (r1, φ ), J (निकास) ELSE
• case_2 केस n के माध्यम से: IF । . . तब । . . अन्य
• case_n: IF INC (y), [q] = [y]=n फिर CPY ( rn, φ ), J (निकास) ELSE
• case_n+1 से case_last: IF । . . तब । . . अन्य
• case_last: IF INC (y), [q] = [y]= last THEN CPY ( rlast, φ ), J (exit) ELSE
• डिफ़ॉल्ट: वूप्स

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

* केस_0:

• सीएलआर (वाई); रजिस्टर वाई = 0 सेट करें
• जेई (क्यू, वाई, _φ0)
• जे (केस_1)

• _φ0: सीपीवाई (आर0, φ)
• जे (बाहर निकलें)

• case_1: आदि।

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

* केस_एन:

• कांग्रेस (वाई)
• जेई (क्यू, वाई, _φn)
• जे (केस_एन+1)

• _φn: सीपीवाई (आरएन, φ)
• जे (बाहर निकलें)

• केस__एन+1: आदि।

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

• मामला_अंतिम:

• कांग्रेस (वाई)
• जेई ( क्यू, वाई, _φlast )
• जे (उफ़)

• _φlast: CPY ( rlast, φ )
• जे (बाहर निकलें)

• वूप्स: हम एक सीमा से बाहर के प्रयास को कैसे हैंडल करते हैं?

* बाहर निकलें: आदि।

यदि 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 ) रजिस्टर ए की सामग्री को दोगुना कर देगा।

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

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

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

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

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

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

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

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

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

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

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

फुटनोट्स

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

निश्चित तथ्य यह है कि किसी भी प्रकार की काउंटर मशीन बिना असीमित रजिस्टर-एड्रेस रजिस्टर को नाम से एक रजिस्टर आर निर्दिष्ट करना चाहिए, यह इंगित करता है कि मॉडल को परिमित होने के लिए आर की आवश्यकता है, हालांकि यह इस अर्थ में असीमित है कि मॉडल संख्या के लिए कोई ऊपरी सीमा नहीं दर्शाता है अपना कार्य करने के लिए आवश्यक रजिस्टरों की संख्या। उदाहरण के लिए, हमें 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 Schönhage (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 RAM" (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.