रैंडम-एक्सेस संग्रहित-प्रोग्राम मशीन

From Vigyanwiki
Revision as of 13:40, 25 July 2023 by alpha>Indicwiki (Created page with "{{more footnotes needed|date=November 2018}} [[सैद्धांतिक कंप्यूटर विज्ञान]] में रैंडम-एक्सेस...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

[[सैद्धांतिक कंप्यूटर विज्ञान]] में रैंडम-एक्सेस स्टोर्ड-प्रोग्राम (आरएएसपी) मशीन मॉडल एक अमूर्त मशीन है जिसका उपयोग कलन विधि विकास और एल्गोरिदमिक जटिलता सिद्धांत के प्रयोजनों के लिए किया जाता है।

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

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

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

अनौपचारिक परिभाषा: रैंडम-एक्सेस संग्रहीत-प्रोग्राम मॉडल (आरएएसपी)

RASP का संक्षेप विवरण:

आरएएसपी एक यूनिवर्सल ट्यूरिंग मशीन (यूटीएम) है जो रैंडम-एक्सेस मशीन रैम चेसिस पर बनाई गई है।

पाठक को याद होगा कि यूटीएम एक ट्यूरिंग मशीन है जिसमें निर्देशों की एक सार्वभौमिक परिमित-राज्य तालिका है जो टेप पर लिखे गए किसी भी अच्छी तरह से गठित प्रोग्राम को ट्यूरिंग 5-टुपल्स की एक स्ट्रिंग के रूप में व्याख्या कर सकती है, इसलिए इसकी सार्वभौमिकता है। जबकि शास्त्रीय यूटीएम मॉडल अपने टेप पर ट्यूरिंग 5-ट्यूपल्स को खोजने की उम्मीद करता है, किसी भी कल्पनाशील प्रोग्राम-सेट को वहां रखा जा सकता है, यह देखते हुए कि ट्यूरिंग मशीन उन्हें ढूंढने की उम्मीद करती है - बशर्ते कि इसकी परिमित-राज्य तालिका उनकी व्याख्या कर सकती है और उन्हें वांछित कार्रवाई में परिवर्तित कर सकती है। प्रोग्राम के साथ, टेप पर इनपुट डेटा/पैरामीटर/नंबर (आमतौर पर प्रोग्राम के दाईं ओर), और अंततः आउटपुट डेटा/नंबर (आमतौर पर दोनों के दाईं ओर, या इनपुट के साथ मिश्रित, या इसे प्रतिस्थापित करते हुए) मुद्रित होंगे। उपयोगकर्ता को ट्यूरिंग मशीन के सिर को पहले निर्देश के ऊपर रखना चाहिए, और इनपुट को एक निर्दिष्ट स्थान पर रखा जाना चाहिए और प्रोग्राम-ऑन-टेप और परिमित-राज्य मशीन के निर्देश-तालिका दोनों के लिए उपयुक्त प्रारूप होना चाहिए।

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

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

आरएएसपी के रूप में काम करने वाली रैम का एक उदाहरण

प्रोग्राम का निम्नलिखित उदाहरण रजिस्टर (छेद) #18 की सामग्री को रजिस्टर (छेद) #19 में ले जाएगा, इस प्रक्रिया में #18 की सामग्री मिटा देगा। 

    5: 03 18 15    JZ 18,15       ; if [18] is zero, jump to 15 to end the program
       02 18       DEC 18         ; Decrement [18]
       01 19       INC 19         ; Increment [19]
       03 15 05    JZ 15, 5       ; If [15] is zero, jump to 5 to repeat the loop (use Halt to simulate unconditional jump)
   15: 00          H              ; Halt

   18:  n                         ; Source value to copy
   19:                            ; Destination for copy

इस आरएएसपी मशीन में उपलब्ध प्रोग्राम-निर्देश उदाहरण को संक्षिप्त रखने के लिए एक सरल सेट होंगे:

Instruction Mnemonic Action on register "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

उदाहरण को आसान बनाने के लिए हम RAM-as-RASP की स्टेट मशीन को एक ही सेट से तैयार किए गए आदिम निर्देशों से लैस करेंगे, लेकिन दो अप्रत्यक्ष प्रतिलिपि निर्देशों के साथ संवर्धित करेंगे:

RAM स्टेट मशीन निर्देश:
{ इंच; डीईसी एच; जेजेड एच,xxx; सीपीवाई ⟪एचa⟫,⟨ha⟩; CPY ⟨ha⟩,⟪ha⟫ }

चूंकि आरएएसपी मशीन की राज्य मशीन रजिस्टरों में प्रोग्राम की व्याख्या करती है, तो राज्य मशीन वास्तव में क्या कर रही होगी? विस्मयादिबोधक चिह्न युक्त स्तम्भ ! राज्य मशीन के कार्यों को समय क्रम में सूचीबद्ध करेगा जैसा वह व्याख्या करता है — क्रिया में परिवर्तित हो जाता है — कार्यक्रम:

PC IR
hole # → 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
program, parameters → 5 JZ 18 15 DEC 18 INC 19 JZ 15 5 H n
encoded program → 5 3 18 15 2 18 1 19 3 15 5 0 n
state machine instructions ↓
!

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

फ़ेच चरण

राज्य मशीन के पास प्रत्यक्ष और अप्रत्यक्ष रूप से सभी रजिस्टरों तक पहुंच है। इसलिए यह #1 को प्रोग्राम काउंटर पीसी के रूप में अपनाता है। प्रोग्राम काउंटर की भूमिका प्रोग्राम की सूची में स्थान बनाए रखने की होगी; राज्य मशीन के पास अपने निजी उपयोग के लिए अपना स्वयं का राज्य रजिस्टर होता है।

प्रारंभ होने पर, राज्य मशीन पीसी में एक नंबर ढूंढने की उम्मीद करती है - प्रोग्राम में पहला प्रोग्राम-निर्देश (यानी #5 पर)।

(अप्रत्यक्ष COPY के उपयोग के बिना, पॉइंट-टू प्रोग्राम-निर्देश को #2 में प्राप्त करने का कार्य थोड़ा कठिन है। राज्य मशीन अप्रत्यक्ष रूप से पॉइंट-टू रजिस्टर को कम कर देगी जबकि सीधे रजिस्टर #2 को बढ़ा (खाली) कर देगी। पार्स चरण के दौरान यह #2 में गिनती का त्याग करके #5 की त्याग की गई सामग्री को पुनर्स्थापित करेगा।)

उपरोक्त चक्कर का उद्देश्य यह दिखाना है कि जब राज्य मशीन के पास दो प्रकार की अप्रत्यक्ष प्रतिलिपि तक पहुंच हो तो जीवन बहुत आसान हो जाता है:

  • i से अप्रत्यक्ष कॉपी करें और j: CPY ⟪h पर सीधे कॉपी करेंi⟫,⟨hj⟩
  • i से सीधे और j: CPY से अप्रत्यक्ष रूप से कॉपी करें ⟨hi⟩,"एचj⟫

निम्नलिखित उदाहरण दिखाता है कि राज्य-मशीन के फ़ेच चरण के दौरान क्या होता है। राज्य-मशीन के संचालन को राज्य मशीन निर्देश ↓ लेबल वाले कॉलम पर सूचीबद्ध किया गया है। ध्यान दें कि फ़ेच के अंत में, रजिस्टर #2 में पहले निर्देश JZ के ऑपरेशन कोड (ऑपकोड) का संख्यात्मक मान 3 शामिल है:

PC PIR
hole # → 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
program, parameters → 5 JZ 18 15 DEC 18 INC 19 JZ 15 5 H n
encoded program → 5 3 18 15 2 18 1 19 3 15 5 0 n
step state machine instructions ↓
1 fetch_instr: CPY ⟪1⟫,⟨2⟩ 5 i [3] [3] 18 15 2 18 1 19 3 15 5 0 n


पार्स चरण

अब जब प्रोग्राम-निर्देश की संख्या (उदाहरण के लिए 3 = JZ) रजिस्टर #2 - प्रोग्राम-निर्देश रजिस्टर पीआईआर में है - राज्य मशीन आईआर खाली होने तक संख्या को कम करने के लिए आगे बढ़ती है:

यदि वेतन वृद्धि से पहले आईआर खाली था तो प्रोग्राम-निर्देश 0 = एचएएलटी होगा, और मशीन अपने एचएएलटी रूटीन पर पहुंच जाएगी। पहले वेतन वृद्धि के बाद, यदि छेद खाली था तो निर्देश INC होगा, और मशीन निर्देश inc_routine पर पहुंच जाएगी। दूसरे वेतन वृद्धि के बाद, खाली आईआर DEC का प्रतिनिधित्व करेगा, और मशीन dec_routine पर पहुंच जाएगी। तीसरे वेतन वृद्धि के बाद, आईआर वास्तव में खाली है, और यह JZ_routine रूटीन में उछाल का कारण बनता है। यदि कोई अप्रत्याशित संख्या अभी भी आईआर में होती, तो मशीन को एक त्रुटि का पता चल जाता और उसे रोक दिया जाता (उदाहरण के लिए)।

PC IR
hole # → 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
program, parameters → 5 JZ 18 15 DEC 18 INC 19 JZ 15 5 H n
encoded program → 5 3 18 15 2 18 1 19 3 15 5 0 n
state machine instructions ↓
CPY ⟪1⟫,⟨2⟩ 5 i [3] [3] 18 15 2 18 1 19 3 15 5 0 n
JZ 2,halt 5 3 3 18 15 2 18 1 19 3 19 5 0 n
3 DEC 2 5 2 3 18 15 2 18 1 19 3 15 5 0 n
4 JZ 2,inc_routine: 5 2 3 18 15 2 18 1 19 3 15 5 0 n
5 DEC 2 5 1 3 18 15 2 18 1 19 3 15 5 0 n
6 JZ 2,dec_routine 5 1 3 18 15 2 18 1 19 3 15 5 0 n
7 DEC 2 5 0 3 18 15 2 18 1 19 3 15 5 0 n
8 JZ 2, JZ_routine 5 0 !
— halt: HALT 5 3 3 18 15 2 18 1 19 3 15 5 0 n
— inc_routine: etc. 5 3 3 18 15 2 18 1 19 3 15 5 0 n
— dec_routine: etc. 5 3 3 18 15 2 18 1 19 3 15 5 0 n
9 JZ_routine: etc. 5 3 3 18 15 2 18 1 19 3 15 5 0 n


चरण निष्पादित करें, JZ_routine

अब राज्य मशीन को पता है कि किस प्रोग्राम-निर्देश को निष्पादित करना है; वास्तव में यह निर्देशों के JZ_routine अनुक्रम पर पहुंच गया है। JZ निर्देश में 2 ऑपरेंड हैं — (i) परीक्षण करने के लिए रजिस्टर की संख्या, और (ii) परीक्षण सफल होने पर जाने का पता (छेद खाली है)।

(i) ऑपरेंड फ़ेच — खाली के लिए परीक्षण करने के लिए कौन सा रजिस्टर?: फ़ेच चरण के अनुरूप, परिमित राज्य मशीन पीसी द्वारा इंगित रजिस्टर की सामग्री, यानी छेद # 6, को प्रोग्राम-इंस्ट्रक्शन रजिस्टर पीआईआर # 2 में ले जाती है। इसके बाद यह रजिस्टर #2 की सामग्री का उपयोग रजिस्टर को शून्य के लिए परीक्षण करने के लिए इंगित करने के लिए करता है, यानी रजिस्टर #18। छेद #18 में एक संख्या n है। परीक्षण करने के लिए, अब राज्य मशीन पीआईआर की सामग्री का उपयोग अप्रत्यक्ष रूप से रजिस्टर #18 की सामग्री को एक अतिरिक्त रजिस्टर, #3 में कॉपी करने के लिए करती है। तो दो स्थितियाँ हैं (ia), रजिस्टर #18 खाली है, (ib) रजिस्टर #18 खाली नहीं है।

(आईए): यदि रजिस्टर #3 खाली है तो राज्य मशीन (ii) दूसरा ऑपरेंड लाने पर पहुंच जाती है — जंप-टू पता प्राप्त करें।

(आईबी): यदि रजिस्टर #3 खाली नहीं है तो राज्य मशीन छोड़ सकती है (ii) दूसरा ऑपरेंड फ़ेच। यह बस पीसी को दोगुना कर देता है और फिर बिना शर्त इंस्ट्रक्शन-फ़ेच चरण में वापस चला जाता है, जहां यह प्रोग्राम-इंस्ट्रक्शन #8 (डीईसी) प्राप्त करता है।

(ii) ऑपरेंड फ़ेच — सीधे पते पर जाएं। यदि रजिस्टर #3 खाली है, तो राज्य मशीन अप्रत्यक्ष रूप से उस रजिस्टर की सामग्री को (#8) स्वयं में कॉपी करने के लिए पीसी का उपयोग करती है। अब पीसी जंप-टू एड्रेस 15 रखता है। फिर स्टेट मशीन बिना शर्त इंस्ट्रक्शन फ़ेच चरण में वापस चली जाती है, जहां यह प्रोग्राम-इंस्ट्रक्शन #15 (एचएएलटी) लाती है।

PC IR
hole # → 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
program, parameters → 5 JZ 18 15 DEC 18 INC 19 JZ 15 5 H n
encoded program → 5 3 18 15 2 18 1 19 3 15 5 0 n
step state machine instructions ↓
9 JZ_routine INC 1 [6] 3 3 18 15 2 18 1 19 3 15 5 0 n
10 CPY ⟪1⟫,⟨2⟩ 6 i [18] 3 [18] 15 2 18 1 19 3 15 5 0 n
11 test hole: CPY ⟪2⟫,⟨3⟩ 6 18 i [n] 3 18 15 2 18 1 19 3 15 5 0 [n]
12 test hole: JZ 3, jump 6 18 i [n] 3 18 15 2 18 1 19 3 15 5 0 n
n n
13 no_jump: INC 1 [7] 18 n 3 18 15 2 18 1 19 3 15 5 0 n
14 INC 1 [8] 18 n 3 18 15 2 18 1 19 3 15 5 0 n
15 J fetch_instr 8 18 n 3 18 15 2 18 1 19 3 15 5 0 n
1 fetch_instr: CPY ⟪1⟫,⟨2⟩ 8 i [2] n 3 18 15 [2] 18 1 19 3 15 5 0 n
2 parse: etc.
13 jump: INC 1 [7] 18 n 3 18 15 2 18 1 19 3 15 5 0 n
14 CPY ⟪1⟫,⟨1⟩ [15] 18 n 3 18 [15] 2 18 1 19 3 15 5 0 n
15 J fetch_instr 15 18 n 3 18 15 2 18 1 19 3 15 5 0 n
1 fetch_instr: CPY ⟪1⟫,⟨2⟩ 15 i [0] n 3 18 15 2 18 1 19 3 15 5 [0] n
2 parse: etc.


निष्पादित चरण INC, DEC

निम्नलिखित प्रोग्राम-निर्देशों, INC h, DEC h की RAM की राज्य-मशीन व्याख्या को पूरा करता है और इस प्रकार यह प्रदर्शन पूरा करता है कि RAM एक RASP का प्रतिरूपण कैसे कर सकता है:

लक्ष्य कार्यक्रम निर्देश सेट: { INC h; डीईसी एच; जेजेड एच,xxx, हॉल्ट }

अप्रत्यक्ष राज्य-मशीन निर्देशों INCi और DECi के बिना, INC और DEC प्रोग्राम-निर्देशों को निष्पादित करने के लिए राज्य मशीन को पॉइंट-टू रजिस्टर की सामग्री को अतिरिक्त रजिस्टर # 3, DEC या INC में प्राप्त करने के लिए अप्रत्यक्ष प्रतिलिपि का उपयोग करना चाहिए, और फिर इसे पॉइंट-टू रजिस्टर पर वापस भेजने के लिए अप्रत्यक्ष प्रतिलिपि का उपयोग करना चाहिए।

PC IR
hole # → 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
program, parameters → 5 JZ 18 15 DEC 18 INC 19 JZ 15 5 H n
encoded program → 5 3 18 15 2 18 1 19 3 15 5 0 n
state machine instructions ↓
15 J fetch_instr 8 18 n 3 18 15 2 18 1 19 3 15 5 0 n
16 fetch_instr: CPY ⟪1⟫,⟨2⟩ 8 i [2] n 3 18 15 2 18 1 19 3 15 5 0 n
17 parse: JZ 2,halt 8 2 n 3 18 15 2 18 1 19 3 15 5 0 n
18 DEC 2 8 [1] n 3 18 15 2 18 1 19 3 15 5 0 n
19 JZ 2, inc_routine: 8 1 n 3 18 15 2 18 1 19 3 15 5 0 n
20 DEC 2 8 [0] n 3 18 15 2 18 1 19 3 15 5 0 n
21 JZ 2, dec_routine: 8 0 ! n 3 18 15 2 18 1 19 3 15 5 0 n
22 dec_routine: INC 1 9 0 n 3 18 15 2 18 1 19 3 15 5 0 n
23 CPY ⟪1⟫,⟨2⟩ 9 i 18 n 3 18 15 2 18 1 19 3 15 5 0 n
24 CPY ⟪2⟫,⟨3⟩ 9 18 i n 3 18 15 2 18 1 19 3 15 5 0 n
25 JZ 3,*+2 9 18 n 3 18 15 2 18 1 19 3 15 5 0 n
26 DEC 3 9 18 n-1 3 18 15 2 18 1 19 3 15 5 0 n
27 CPY ⟨3⟩,⟪2⟫ 9 18 i n-1 3 18 15 2 18 1 19 3 15 5 0 n-1
28 INC 1 10 18 n-1 3 18 15 2 18 1 19 3 15 5 0 n-1
29 J fetch_instr 10 18 n-1 3 18 15 2 18 1 19 3 15 5 0 n-1
30 fetch_instr: CPY ⟪1⟫,⟨2⟩ 10 i 1 n-1 3 18 15 2 18 1 19 3 15 5 0 n-1
31 parse: JZ 2,halt 10 1 n-1 3 18 15 2 18 1 19 3 15 5 0 n-1
32 DEC 2 10 0 n-1 3 18 15 2 18 1 19 3 15 5 0 n-1
33 JZ 2,inc_routine: 10 0 ! n-1 3 18 15 2 18 1 19 3 15 5 0 n-1
34 inc_routine: INC 1 11 0 n-1 3 18 15 2 18 1 19 3 15 5 0 n-1
35 CPY ⟪1⟫,⟨2⟩ 11 i 19 n-1 3 18 15 2 18 1 19 3 15 5 0 n-1
36 CPY ⟪2⟫,⟨3⟩ 11 19 i 0 3 18 15 2 18 1 19 3 15 5 0 n-1 0
37 INC 3 11 19 1 3 18 15 2 18 1 19 3 15 5 0 n-1 0
38 CPY ⟨3⟩,⟪2⟫ 11 19 i 1 3 18 15 2 18 1 19 3 15 5 0 n-1 1
39 INC 1 12 19 1 3 18 15 2 18 1 19 3 15 5 0 n-1 0
40 J fetch_instr 12 19 1 3 18 15 2 18 1 19 3 15 5 0 n-1 0
41 fetch_instr: etc. 12 19 1 3 18 15 2 18 1 19 3 15 5 0 n-1 0

वैकल्पिक निर्देश: हालाँकि प्रदर्शन के परिणामस्वरूप केवल चार निर्देशों का एक आदिम आरएएसपी प्राप्त हुआ, पाठक कल्पना कर सकते हैं कि ADD जैसा अतिरिक्त निर्देश कैसे होगा ⟨h⟩ या बहु ⟨ha⟩,"एचb>किया जा सकता है.

स्व-संशोधित आरएएसपी कार्यक्रम

जब एक रैम आरएएसपी के रूप में कार्य कर रहा होता है, तो कुछ नया प्राप्त होता है: रैम के विपरीत, आरएएसपी में अपने प्रोग्राम-निर्देशों के स्व-संशोधन की क्षमता होती है (राज्य-मशीन निर्देश जमे हुए होते हैं, मशीन द्वारा अपरिवर्तित होते हैं)। कुक-रेकहो (1971) (पृ. 75) ने अपने आरएएसपी मॉडल के विवरण में इस पर टिप्पणी की है, जैसा कि हार्टमैनिस (1971) (पृ. 239एफएफ) ने किया है।

इस धारणा का प्रारंभिक विवरण गोल्डस्टाइन-वॉन न्यूमैन (1946) में पाया जा सकता है:

हमें एक आदेश [निर्देश] की आवश्यकता है जो किसी संख्या को किसी दिए गए क्रम में प्रतिस्थापित कर सके... ऐसे आदेश के माध्यम से एक गणना के परिणामों को उस या एक अलग गणना को नियंत्रित करने वाले निर्देशों में पेश किया जा सकता है (पृष्ठ 93)

ऐसी क्षमता निम्नलिखित को संभव बनाती है:

कुक और रेकहो का आरएएसपी कार्यक्रम-निर्देश सेट (1973)

एक प्रभावशाली पेपर में स्टीफ़न कुक|स्टीफ़न ए. कुक और रॉबर्ट ए. रेकहो ने आरएएसपी के अपने संस्करण को परिभाषित किया है:

यहां वर्णित रैंडम एक्सेस स्टोर्ड-प्रोग्राम मशीन (आरएएसपी) हार्टमैनिस [1971] (पृष्ठ 74) द्वारा वर्णित आरएएसपी के समान है।

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

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

उनके आरएएसपी के रजिस्टर क्षमता में असीमित और संख्या में असीमित हैं; इसी तरह उनके संचायक एसी और अनुदेश काउंटर आईसी असीमित हैं। निर्देश सेट निम्नलिखित है:

operation mnemonic operation code description
load constant LOD, k 1 put constant k into accumulator
add ADD, j 2 add contents of register j to accumulator
subtract SUB, j 3 subtract contents of register j from accumulator
store STO, j 4 copy contents of accumulator into register j
branch on positive accumulator BPA, xxx 5 IF contents of accumulator > 0 THEN jump to xxx ELSE next instruction
read RD, j 6 next input into register j
print PRI, j 7 output contents of register j
halt HLT any other - or + integer stop


संदर्भ

Often both the RAM and RASP machines are presented together in the same article. These have been copied over from Random-access machine; with a few exceptions, these references are the same as those at Register machine.

  • 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 two recursion models.
  • 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 (1972), Time-bounded random access machines, Journal of Computer Systems Science 7 (1973), 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. Vyssotsky of the Bell telephone Laboratories 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. 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. ISBN 0-13-165449-7. 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, appearing 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' 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.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=रैंडम-एक्सेस_संग्रहित-प्रोग्राम_मशीन&oldid=239464’