ماشین برنامه ذخیره‌شده با دسترسی تصادفی
 | این مقاله نیازمند ویکیسازی است. لطفاً با توجه به راهنمای ویرایش و شیوهنامه، محتوای آن را بهبود بخشید. (دسامبر ۲۰۱۸) |
در علوم نظری کامپیوتر، مدل ماشین برنامهٔ ذخیره شده با دسترسی تصادفی (RASP) یک ماشین انتزاعی است که برای اهداف توسعهٔ الگوریتم و نظریهٔ پیچیدگی الگوریتم مورد استفاده قرار می‌گیرد. RASP یک مدل ماشین دسترسی تصادفی (RAM) است که بر خلاف RAM، برنامه‌اش به همراه ورودی، درون "رجیستر"های آن قرار دارد. رجیسترها نامحدود (دارای ظرفیت بینهایت) هستند؛ محدود بودن تعداد رجیسترها، به مدل بستگی دارد؛ بنابراین نسبت RASP به RAM، مانند ماشین تورینگ جهانی به ماشین تورینگ است. RASP نمونه‌ای از معماری فون نویمان است، درحالیکه RAM نمونه‌ای از معماری هاروارد می‌باشد. از میان تمام مدل‌های انتزاعی، RASP نزدیک‌ترین مدل به مفهوم متداول کامپیوتر است. اما برخلاف کامپیوترهای واقعی، مدل RASP معمولاً دارای مجموعهٔ ساختاری بسیار ساده‌ای است که تا حد زیادی از CISC و حتی پردازشگرهای RISC به صورت ساده‌ترین "حرکات" حسابی و رجیستر به رجیستر، و همچنین فرمان‌های "آزمون/جهش" ساده شده‌اند. برخی مدل‌ها، مانند یک انباشتگر، دارای رجیسترهای کمی بیشتر هستند.RASP به همراه ماشین رجیستر، RAM و ماشین اشاره‌گر، چهار مدل ماشین متوالی رایج را ایجاد می‌کند، که جهت تمایز آن‌ها از مدل‌های "موازی" (مثلاً، ماشین دسترسی تصادفی موازی) به این نام خوانده می‌شوند (van Emde Boas (1990)).
تعریف غیررسمی: مدل برنامه ذخیره شده با دسترسی تصادفی (RASP)[ویرایش]
RASP یک ماشین تورینگ جهانی (UTM) است که بر کالبد یک RAM ماشین دسترسی تصادفی ساخته شده‌است. خواننده به یاد خواهد آورد که UTM یک ماشینگ تورینگ با یک فهرست فرمان‌های "جهانی" حالت محدود است که می‌تواند هرگونه "برنامه"ی به خوبی شکل‌گرفته و نوشته شده بر روی یک نوار ضبط به عنوان یک رشته تورینگ ۵تایی، و از اینرو عمومیت آن، را تفسیر نماید. در حالیکه انتظار می‌رود تا مدل UTM، تورینگ ۵تایی را بر روی نوار خود بیابد، هر مجموعه برنامهٔ قابل تصور را، با توجه به اینکه ماشین تورینگ انتظار دارد که آن‌هارا بیابد، می‌توان در آنجا قرار داد، با توجه به اینکه فهرست حالت محدود آن می‌تواند آن مجموعه برنامه را تفسیر نموده و آن‌ها را به عمل دلخواه تبدیل نماید. در کنار برنامه، سایر موارد چاپ شده بر روی نوار، داده-ها/مولفه‌ها/اعداد ورودی (معمولاً در سمت راست برنامه)، و در نهایت داده‌ها/اعداد خروجی (معمولاً در سمت راست هر دوی آن‌ها، یا آمیخته با ورودی‌ها، یا جایگزین آن‌ها) خواهند بود. "کاربر" باید ابتدای ماشین تورینگ را بالاتر از اولین فرمان قرار دهد، و ورودی‌ها باید در یک محل خاص و قالبی مناسب هم برای برنامهٔ روی نوار و هم برای فهرست فرمان‌های ماشین حالت محدود جای دهد. RASP از این فرمان تقلید می‌کند: "برنامه" و "داده‌هاً را درون حفره‌ها (رجیسترها) جای می‌دهد. اما برخلاف UTM، RSAP اقدام به "واکشی" فرمان‌هایش به صورت ترتیبی می‌کند، مگر اینکه آزمون شرطی آن‌ها را به جای دیگری ارسال نماید. نکتهٔ تردید دو مجموعه فرمان: مدل RASP، بر خلاف UTM، دارای دو مجموعه فرمان است؛ فهرست فرمان‌های حالت ماشین ("مفسر") و "برنامه" درون حفره‌ها.
مثالی از یک RAM به عنوان یک RASP[ویرایش]
نمونه برنامهٔ زیر مقادیر رجیستر (حفره) #۱۸ را به رجیستر (حفره) #۱۹ انتقال داده و مقادیر #۱۸ را در این فرایند پاک خواهد نمود.
5: 03 18 15 JZ 18,15 ; if [18] is zero, jump to 15 to end the program 02 18 DEC 18 ; Decrement [۱۸] 01 19 INC 19 ; Increment [۱۹] 03 19 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
فرمان‌های برنامه‌ای موجود در این ماشین RASP، مجموعه‌ای ساده جهت خلاصه‌سازی این مثال خواهند بود:
| 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 به عنوان RASP» را به فرمان‌های اولیهٔ طراحی شده برای همان مجموعه، اما تکمیل شده با دو فرمان کپی غیرمستقیم، تجهیز خواهیم نمود: فرمان‌های ماشین حالتِ RAM: { INC h; DEC h; JZ h,xxx; CPY <<ha>>,<ha>; CPY <ha>,<<ha>> } همچنانکه ماشین حالتِ ماشین RASP، برنامه را درون رجیسترها تفسیر می‌کند، ماشینِ حالت دقیقاً در حال انجام چه کاری خواهد بود؟ ستون حاوی علامت تعجب !، اعمال ماشین حالت را در توالی زمانی فهرست خواهد نمود، چنان‌که برنامه را "تفسیر می‌کند" (به عمل تبدیل می‌کند):
| PC | IR | ||||||||||||||||||
| hole # → | ۱ | ۲ | ۳ | ۴ | ۵ | ۶ | ۷ | ۸ | ۹ | ۱۰ | ۱۱ | ۱۲ | ۱۳ | ۱۴ | ۱۵ | ۱۶ | ۱۷ | ۱۸ | ۱۹ |
| program, parameters → | ۵ | JZ | ۱۸ | ۱۵ | DEC | ۱۸ | INC | ۱۹ | JZ | ۱۵ | ۵ | H | n | ||||||
| encoded program → | ۵ | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | ||||||
| state machine instructions ↓ | |||||||||||||||||||
| ! |
به‌طور مرسوم، اعمال ماشینِ حالت به دو "مرحله"ی اصلی به نام‌های واکشی و اجرا تقسیم می‌کند. در زیر آن مشاهده خواهیم نمود که "زیرفاز"هایی درون این مراحل اصلی وجود دارند. هیچ توافق قراردادی وجود ندارد؛ هر مدل نیازمند تعریف دقیق خودش خواهد بود.
مرحلهٔ واکشی[ویرایش]
ماشین حالت، هم مستقیم و هم غیرمستقیم، به تمام رجیسترها دسترسی دارد؛ بنابراین #۱ را به عنوان "شمارشگر برنامه" (PC) اتخاذ می‌کند. نقش شمارشگر برنامه "حفظ موقعیت" در فهرست برنامه خواهد بود؛ ماشین حالت، برای کاربرد اختصاصی‌اش، دارای رجیستر حالتِ منحصربفرد خود است. به محض شروع، ماشین حالت منتظر یافتن یک شماره درون PC می‌ماند، یعنی اولین "فرمان برنامه‌ای" درون برنامه (مثلاً در #۵). (بدون استفاده از کپی‌های غیرمستقیم، وظیفهٔ رساندن فرمان برنامه‌ایِ مورد اشاره به #۲ کمی دشوار است. ماشینِ حالت، رجیستر مورد اشاره را به‌طور غیرمستقیم کاهش خواهد داد، درحالیکه رجیستر (خالیِ) #۲ را افزایش می‌دهد. در طول مرحلهٔ "تجزیه"، مقادیر ارائه شدهٔ #۵ را بوسیلهٔ قربانی کردن شمارهٔ درون #۲، ترمیم خواهد نمود) هدف از نکتهٔ انحرافی بالا این است که نشان دهیم، زمانیکه ماشین حالت به دو نوع کپی غیرمستقیم دسترسی دارد، کارها آسان‌تر خواهند بود:
- کپی غیرمستقیم از i و مستقیم به j: CPY <<hi>>,<hj>
- کپی مستقیم از i و غیرمستقیم به j: CPY <hi>,<<hj>>
مثال بعدی نشان می‌دهد که در طی مرحلهٔ "واکشی" ماشینِ حالت، چه اتفاقی رخ می‌دهد. عملیات‌های ماشینِ حالت در زیر ستونی با عنوان "فرمان‌های ماشینِ حالت ↓ " فهرست شده‌اند. مشاهده کنید که در انتهای واکشی، رجیستر #۲ حاوی مقدار عددی ۳ از "کد عملیاتی" ("opcode") فرمان اول JZ است.
| PC | PIR | ||||||||||||||||||||
| hole # → | ۱ | ۲ | ۳ | ۴ | ۵ | ۶ | ۷ | ۸ | ۹ | ۱۰ | ۱۱ | ۱۲ | ۱۳ | ۱۴ | ۱۵ | ۱۶ | ۱۷ | ۱۸ | ۱۹ | ||
| program, parameters → | ۵ | JZ | ۱۸ | ۱۵ | DEC | ۱۸ | INC | ۱۹ | JZ | ۱۵ | ۵ | H | n | ||||||||
| encoded program → | ۵ | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | ||||||||
| step | state machine instructions ↓ | ||||||||||||||||||||
| ۱ | fetch_instr: | CPY <<1>>,<2> | 5 i | [۳] | [۳] | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n |
مرحلهٔ تجزیه: اکنون که شمارهٔ فرمان برنامه‌ای (مثلاً ۳=”JZ”) درون رجیستر #۲ –رجیستر فرمان برنامه‌ای– قرار دارد، ماشینِ حالت به کاهش شماره تا زمانیکه رجیستر فرمان (IR) خالی شود، ادامه می‌دهد: اگر IR پیش از کاهش خالی بود، پس فرمان برنامه‌ای ۰=HALT خواهد بود، و ماشین به روال "HALT" خود جهش خواهد نمود. پس از اولین کاهش، در صورتی که حفره خالی بود، فرمان INC خواهد بود، و ماشین به فرمان "inc_routine" جهش خواهد نمود. پس از دومین کاهش، IR خالی DEC را نمایش داده و ماشین به فرمان "dec_routine" جهش خواهد کرد. پس از سومین کاهش، IR واقعاً خالی می‌شود و این امر منجر به جهش به روال "JZ_routine" خواهد شد. در صورتی‌که یک عدد غیرمنتظره همچنان درون IR وجود داشته باشد، (برای مثال) ماشین یک خطا را شناسایی نموده و HALT خواهد نمود."
| PC | IR | ||||||||||||||||||||
| hole # → | ۱ | ۲ | ۳ | ۴ | ۵ | ۶ | ۷ | ۸ | ۹ | ۱۰ | ۱۱ | ۱۲ | ۱۳ | ۱۴ | ۱۵ | ۱۶ | ۱۷ | ۱۸ | ۱۹ | ||
| program, parameters → | ۵ | JZ | ۱۸ | ۱۵ | DEC | ۱۸ | INC | ۱۹ | JZ | ۱۵ | ۵ | H | n | ||||||||
| encoded program → | ۵ | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | ||||||||
| step | state machine instructions ↓ | ||||||||||||||||||||
| ۱ | fetch_instr: | CPY <<1>>,<2> | 5 i | [۳] | [۳] | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | |||||
| ۲ | parse_instr: | JZ 2,halt | ۵ | ۳ | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۹ | ۵ | ۰ | n | |||||
| ۳ | 2-Dec | ۵ | ۲ | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | ||||||
| ۴ | JZ 2,dec_routine: | ۵ | ۲ | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | ||||||
| ۵ | 2-Dec | ۵ | ۱ | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | ||||||
| ۶ | JZ 2,inc_routine | ۵ | ۱ | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | ||||||
| ۷ | 2-Dec | ۵ | ۰ | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | ||||||
| ۸ | JZ 2, JZ_routine | ۵ | ۰ ! | ||||||||||||||||||
| -- | halt: | HALT | ۵ | ۳ | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | |||||
| -- | inc_routine: | etc. | ۵ | ۳ | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | |||||
| -- | dec_routine: | etc. | ۵ | ۳ | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | |||||
| ۹ | JZ_routine: | etc. | ۵ | ۳ | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n |
مرحلهٔ اجرا، JZ_routine[ویرایش]
اکنون ماشینِ حالت می‌داند که کدام دستورالعمل برنامه‌ای را اجرا نماید؛ در واقع به ردیف فرمان‌های "JZ_routine" جهش یافته‌است. فرمان JZ دارای دو عملوند است، (i) رقم رجیستر جهت آزمون، و (ii) آدرسی که در صورت موفقیت‌آمیز بودن آزمون (خالی بودن حفره) باید به آن مراجعه نمود. واکشی عملوند - کدام رجیستر را جهت خالی بودن آزمایش کنیم؟ : مشابه مرحلهٔ واکشی، ماشینِ حالت محدود، مقادیر رجیستری را که توسط PC به آن اشاره شده، مثلاً حفرهٔ #۶، را به درون رجیستر فرمان برنامه‌ایِ #۲ منتقل می‌کند. سپس از مقادیر رجیستر #۲ برای اشاره به رجیستر جهت آزمایش شدن برای صفر، مثلاً رجیستر #۱۸، استفاده می‌کند. حفرهٔ #۱۸ محتوی عدد "n" است. اکنون برای انجام آزمایش، ماشینِ حالت از مقادیر PIR جهت کپی غیرمستقیم رجیستر #۱۸ درون یک رجیستر یدکی، #۳، استفاده می‌کند؛ بنابراین دو احتمال وجود دارد، (ia) رجیستر #۱۸ خالی است، (ib) رجیستر #۱۸ خالی نیست. (ia) در صورتی‌که رجیستر #۳ خالی باشد، ماشینِ حالت به (ii) دومین واکشی عملوند، جهش می‌یابد (واکشی آدرس جهش به). (ib) در صورتی‌که رجیستر #۳ خالی نباشد، ماشین حالت می‌تواند (ii) دومین واکشی عملوند را نادیده بگیرد. این کار به سادگی PC را دو بار کاهش می‌دهد و سپس بدون قید و شرط به مرحلهٔ واکشیِ فرمان، یعنی جاییکه فرمان برنامه‌ای #۸ را واکشی می‌کند (DEC)، بازمی‌گردد. (ii) واکشی عملوند – آدرس جهش به. اگر رجیستر #۳ خالی باشد، ماشینِ حالت اقدام به استفاده از PC جهت کپی غیرمستقیم مقادیر رجیستری که به آن اشاره دارد (#۸) به درون خود، می‌کند. اکنون PC آدرس "جهش به" ۱۵ را نگه می‌دارد. سپس ماشینِ حالت بدون قید و شرط به مرحلهٔ واکشی فرمان بازمی‌گردد، یعنی جاییکه فرمان برنامه‌ای #۱۵ را واکشی می‌نماید (HALT).
| PC | IR | ||||||||||||||||||||
| hole # → | ۱ | ۲ | ۳ | ۴ | ۵ | ۶ | ۷ | ۸ | ۹ | ۱۰ | ۱۱ | ۱۲ | ۱۳ | ۱۴ | ۱۵ | ۱۶ | ۱۷ | ۱۸ | ۱۹ | ||
| program, parameters → | ۵ | JZ | ۱۸ | ۱۵ | DEC | ۱۸ | INC | ۱۹ | JZ | ۱۵ | ۵ | H | n | ||||||||
| encoded program → | ۵ | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | ||||||||
| step | state machine instructions ↓ | ||||||||||||||||||||
| ۹ | JZ_routine | INC 1 | [۶] | ۳ | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | |||||
| ۱۰ | CPY <<1>>,<2> | 6 i | [۱۸] | ۳ | [۱۸] | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | ||||||
| ۱۱ | test hole: | CPY <<2>>,<3> | ۶ | 18 i | [n] | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | [n] | ||||
| ۱۲ | test hole: | JZ 3, jump | ۶ | 18 i | [n] | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | ||||
| n | n | ||||||||||||||||||||
| ۱۳ | no_jump: | INC 1 | [۷] | ۱۸ | n | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | ||||
| ۱۴ | INC 1 | [۸] | ۱۸ | n | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | |||||
| ۱۵ | J fetch_instr | ۸ | ۱۸ | n | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | |||||
| ۱ | fetch_instr: | CPY <<1>>,<2> | 8 i | [۲] | n | ۳ | ۱۸ | ۱۵ | [۲] | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | ||||
| ۲ | parse: | etc. | |||||||||||||||||||
| ۱۳ | jump: | INC 1 | [۷] | ۱۸ | n | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | ||||
| ۱۴ | CPY <<1>>,<1> | [۱۵] | ۱۸ | n | ۳ | ۱۸ | [۱۵] | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | |||||
| 15 | J fetch_instr | ۱۵ | ۱۸ | n | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | |||||
| ۱ | fetch_instr: | CPY <<1>>,<2> | 15 i | [۰] | n | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | [۰] | n | ||||
| ۲ | parse: | etc. |
| PC | IR | ||||||||||||||||||||
| hole # → | ۱ | ۲ | ۳ | ۴ | ۵ | ۶ | ۷ | ۸ | ۹ | ۱۰ | ۱۱ | ۱۲ | ۱۳ | ۱۴ | ۱۵ | ۱۶ | ۱۷ | ۱۸ | ۱۹ | ||
| program, parameters → | ۵ | JZ | ۱۸ | ۱۵ | DEC | ۱۸ | INC | ۱۹ | JZ | ۱۵ | ۵ | H | n | ||||||||
| encoded program → | ۵ | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | ||||||||
| step | state machine instructions ↓ | ||||||||||||||||||||
| ۱۵ | J fetch_instr | ۸ | ۱۸ | n | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | |||||
| ۱۶ | fetch_instr: | CPY <<1>>,<2> | 8 i | [۲] | n | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | ||||
| ۱۷ | parse: | JZ 2,halt | ۸ | ۲ | n | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | ||||
| ۱۸ | 2-Dec | ۸ | [۱] | n | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | |||||
| ۱۹ | JZ 2, inc_routine: | ۸ | ۱ | n | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | |||||
| ۲۰ | 2-Dec | ۸ | [۰] | n | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | |||||
| 21 | JZ 2, dec_routine: | ۸ | ۰! | n | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | |||||
| ۲۲ | dec_routine: | INC 1 | ۹ | ۰ | n | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | ||||
| 23 | CPY <<1>>,<2> | 9 i | ۱۸ | n | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | |||||
| 24 | CPY <<2>>,<3> | ۹ | 18 i | n | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | |||||
| ۲۵ | JZ 3,*+۲ | ۹ | ۱۸ | n | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | |||||
| 26 | .DEC 3 | ۹ | ۱۸ | n-1 | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | |||||
| 27 | CPY <3>,<<2>> | ۹ | 18 i | n-1 | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n-1 | |||||
| 28 | INC 1 | ۱۰ | ۱۸ | n-1 | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n-1 | |||||
| ۲۹ | J fetch_instr | ۱۰ | ۱۸ | n-1 | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n-1 | |||||
| ۳۰ | fetch_instr: | CPY <<1>>,<2> | 10 i | ۱ | n-1 | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n-1 | ||||
| ۳۱ | parse: | JZ 2,halt | ۱۰ | ۱ | n-1 | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n-1 | ||||
| ۳۲ | 2-Dec | ۱۰ | ۰ | n-1 | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n-1 | |||||
| ۳۳ | JZ 2,inc_routine: | ۱۰ | ۰! | n-1 | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n-1 | |||||
| 34 | inc_routine: | INC 1 | ۱۱ | ۰ | n-1 | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n-1 | ||||
| 35 | CPY <<1>>,<2> | 11 i | ۱۹ | n-1 | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n-1 | |||||
| 36 | CPY <<2>>,<3> | ۱۱ | 19 i | ۰ | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n-1 | ۰ | ||||
| 37 | INC 3 | ۱۱ | ۱۹ | ۱ | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n-1 | ۰ | ||||
| 38 | CPY <3>,<<2>> | ۱۱ | 19 i | ۱ | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n-1 | ۱ | ||||
| 39 | INC 1 | ۱۲ | ۱۹ | ۱ | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n-1 | ۰ | ||||
| 40 | J fetch_instr | ۱۲ | ۱۹ | ۱ | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n-1 | ۰ | ||||
| ۴۱ | fetch_instr: | etc. | ۱۲ | ۱۹ | ۱ | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n-1 | ۰ |
مرحلهٔ اجرایی INC، DEC[ویرایش]
شرح زیر، تفسیر ماشینِ حالت RAM از فرمان‌های برنامه‌ای، یعنی INC h، DEC h، را کامل می‌کند و بدین ترتیب نمایش چگونگی "جعل هویت" RASP توسط RAM را تمکیل می‌نماید. مجموعه فرمان برنامه‌ای هدف: { INC h; DEC h; JZ h,xxx, HALT } بدون فرمان‌های غیرمستقیم ماشینِ حالت، INCi و DECi، جهت اجرای فرمان‌های برنامه‌ایِ INC و DEC، ماشینِ حالت باید از کپی غیرمستقیم جهت گرفتن مقادیر رجیستر مورد اشاره به درون رجیستر یدکی #۳ استفاده نماید، آن را DEC یا INC کرده، و سپس برای بازفرستادن آن به رجیستر مورد اشاره، از کپی غیرمستقیم استفاده کند.
| PC | IR | ||||||||||||||||||||
| hole # → | ۱ | ۲ | ۳ | ۴ | ۵ | ۶ | ۷ | ۸ | ۹ | ۱۰ | ۱۱ | ۱۲ | ۱۳ | ۱۴ | ۱۵ | ۱۶ | ۱۷ | ۱۸ | ۱۹ | ||
| program, parameters → | ۵ | JZ | ۱۸ | ۱۵ | DEC | ۱۸ | INC | ۱۹ | JZ | ۱۵ | ۵ | H | n | ||||||||
| encoded program → | ۵ | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | ||||||||
| step | state machine instructions ↓ | ||||||||||||||||||||
| ۱۵ | J fetch_instr | ۸ | ۱۸ | n | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | |||||
| ۱۶ | fetch_instr: | CPY <<1>>,<2> | 8 i | [۲] | n | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | ||||
| ۱۷ | parse: | JZ 2,halt | ۸ | ۲ | n | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | ||||
| ۱۸ | 2-Dec | ۸ | [۱] | n | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | |||||
| ۱۹ | JZ 2, inc_routine: | ۸ | ۱ | n | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | |||||
| ۲۰ | 2-Dec | ۸ | [۰] | n | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | |||||
| 21 | JZ 2, dec_routine: | ۸ | ۰! | n | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | |||||
| ۲۲ | dec_routine: | INC 1 | ۹ | ۰ | n | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | ||||
| 23 | CPY <<1>>,<2> | 9 i | ۱۸ | n | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | |||||
| 24 | CPY <<2>>,<3> | ۹ | 18 i | n | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | |||||
| ۲۵ | JZ 3,*+۲ | ۹ | ۱۸ | n | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | |||||
| 26 | .DEC 3 | ۹ | ۱۸ | n-1 | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n | |||||
| 27 | CPY <3>,<<2>> | ۹ | 18 i | n-1 | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n-1 | |||||
| 28 | INC 1 | ۱۰ | ۱۸ | n-1 | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n-1 | |||||
| ۲۹ | J fetch_instr | ۱۰ | ۱۸ | n-1 | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n-1 | |||||
| ۳۰ | fetch_instr: | CPY <<1>>,<2> | 10 i | ۱ | n-1 | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n-1 | ||||
| ۳۱ | parse: | JZ 2,halt | ۱۰ | ۱ | n-1 | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n-1 | ||||
| ۳۲ | 2-Dec | ۱۰ | ۰ | n-1 | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n-1 | |||||
| ۳۳ | JZ 2,inc_routine: | ۱۰ | ۰! | n-1 | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n-1 | |||||
| 34 | inc_routine: | INC 1 | ۱۱ | ۰ | n-1 | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n-1 | ||||
| 35 | CPY <<1>>,<2> | 11 i | ۱۹ | n-1 | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n-1 | |||||
| 36 | CPY <<2>>,<3> | ۱۱ | 19 i | ۰ | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n-1 | ۰ | ||||
| 37 | INC 3 | ۱۱ | ۱۹ | ۱ | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n-1 | ۰ | ||||
| 38 | CPY <3>,<<2>> | ۱۱ | 19 i | ۱ | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n-1 | ۱ | ||||
| 39 | INC 1 | ۱۲ | ۱۹ | ۱ | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n-1 | ۰ | ||||
| 40 | J fetch_instr | ۱۲ | ۱۹ | ۱ | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n-1 | ۰ | ||||
| ۴۱ | fetch_instr: | etc. | ۱۲ | ۱۹ | ۱ | ۳ | ۱۸ | ۱۵ | ۲ | ۱۸ | ۱ | ۱۹ | ۳ | ۱۵ | ۵ | ۰ | n-1 | ۰ |
فرمان‌های جایگزین: اگرچه این نمایش به یک RASP اولیه از تنها چهار فرمان منجر شد، خواننده باید حدس بزند که یک فرمان اضافی مانند "ADD <h>" یا "MULT <ha>,<<hb>"، چگونه ممکن است انجام شود. برنامه‌های RASP خود اصلاح زمانیکه یک RAM به عنوان یک RASP عمل می‌کند، مورد جدیدی به دست می‌آید: RASP، بر خلاف RAM، ظرفیت خود اصلاحی فرمان‌های برنامه‌ای خود را دارد (فرمان‌های ماشینِ حالت ثابت بوده و غیرقابل تعدیل توسط ماشین هستند). کوک-رکهو (Cook-Reckhow) (1971) (صفحه ۷۵)، مانند هارتمانیس (Hartmanis) (1971) (صفحات ff239)، در توصیفشان از مدل RASP خود، دربارهٔ این موضوع اظهارنظر کرده‌اند. تعریفی اولیه از این مفهوم را می‌توان در گلدشتین-فون نویمان (Goldstine-von Neumann) (1946) یافت: "ما به دستوری (فرمانی) نیاز داریم که بتواند یک عدد را درون یک ردیف مشخص جایگزین نماید… با استفاده از چنین دستوری، نتایج یک محاسبه را می‌توان به صورت فرمان‌هایی نشان داد که این محاسبه یا یک محاسبهٔ دیگر را کنترل می‌کنند" (صفحه ۹۳). چنین قابلیتی، موارد زیر را ممکن می‌سازد:
- زیر روال‌ها: روال (یا شاید زیر روال) فراخوانده شده، آدرس بازگشت "return_address" را در آخرین فرمان زیر روال ذخیره می‌کند، به‌طور مثال "JMP return_address"
- به اصطلاح JUMP-tables (فهرست‌های JUMP)
- کد خود اصلاح
مجموعهٔ فرمان برنامه‌ای RASP از طرف کوک و رکهو (۱۹۷۳)[ویرایش]
استفان ای. کوک و رابرت ای. رکهو، تفسیر خود از یک RASP را در یک مقالهٔ مؤثر، چنین شرح می‌دهند: "ماشین برنامهٔ ذخیره شده با دسترسی تصادفی (RASP) شرح داده شده در اینجا، مشابه RASPهای شرح داده شده توسط هارتمانیس می‌باشد" (صفحه ۷۴). هدف آن‌ها، مقایسهٔ زمان‌های اجرایی مدل‌های مختلف از جمله RAM، RASP و ماشین تورینگ چند نواری، جهت استفاده در نظریهٔ تحلیل پیچیدگی بود. ویژگی چشمگیر مدل RASP آن‌ها، بی‌قیدی برای فرمان‌های برنامه‌ای غیرمستقیم است (به بحث آن-ها در صفحه ۷۵ رجوع شود). آن‌ها با ملزم نمودن یک برنامه جهت اصلاح خود، به این نتیجه رسیدند: در صورت لزوم، یک فرمان می‌تواند "مولفه"ی (به قول آن‌ها، مثلاً "عملوند") یک فرمان خاص را اصلاح نماید. آن‌ها مدل خود را به گونه‌ای طراحی کردند که هر "فرمان" از دو رجیستر متوالی استفاده نماید، یکی برای "کد عملیاتی" (به قول آن‌ها) و مؤلفهٔ "یک آدرس یا یک ثابت اینتجر". رجیسترهای RASP آن‌ها از لحاظ ظرفیت و از لحاظ تعداد، نامحدود هستند؛ به همین ترتیب، انباشتگر آن-ها یعنی AC، و شمارندهٔ فرمان، IC، نیز نامحدود هستند. مجموعهٔ فرمان‌ها به شرح زیر هستند:
| 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 |
| 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 recursion the other two.
- Arthur Burks, Herman Goldstine, جان فون نویمان (1946), Preliminary discussion of the logical design of an electronic computing instrument, reprinted pp. 92ff in گوردون بل and آلن نیوول (1971), Computer Structures: Readings and Examples, mcGraw-Hill Book Company, New York. ISBN 0-07-004357-4.
- استیون کوک and Robert A. Reckhow (1972), Time-bounded random access machines, Journal of Computer Systems Science 7 (1973), 354-375.
- مارتین دیویس (1958), Computability & Unsolvability, McGraw-Hill Book Company, Inc. New York.
- Calvin Elgot and آبراهام رابینسون (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.
- جان هاپکرافت, جفری اولمن (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.
- استیون کول کلینی (1952), Introduction to Metamathematics, North-Holland Publishing Company, Amsterdam, Netherlands. ISBN 0-7204-2103-9.
- دانلد کنوت (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 1۵ ژوئن ۱۹۶۱), 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 1۵ مه ۱۹۶۱), 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."
- ماروین مینسکی (1961, received August 15, 1960). "Recursive Unsolvability of Post's Problem of 'Tag' and Other Topics in Theory of Turing Machines". Annals of Math. Annals of Mathematics. 74 (3): 437–455. doi:10.2307/1970290. JSTOR 1970290.
{{cite journal}}: Check date values in:|year=(help) - ماروین مینسکی (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 of 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.
مشارکت‌کنندگان ویکی‌پدیا. «ماشین برنامه ذخیره شده با دسترسی تصادفی 1». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲۶ آذر ۱۳۹۵.