ماشین برنامه ذخیره‌شده با دسترسی تصادفی کیست؟ توضیح بده.
در علوم نظری کامپیوتر، مدل ماشین برنامهٔ ذخیره شده با دسترسی تصادفی (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، مجموعه‌ای ساده جهت خلاصه‌سازی این مثال خواهند بود:برای سهولت مثال، ماشینِ حالت «RAM به عنوان RASP» را به فرمان‌های اولیهٔ طراحی شده برای همان مجموعه، اما تکمیل شده با دو فرمان کپی غیرمستقیم، تجهیز خواهیم نمود:فرمان‌های ماشین حالتِ RAM:همچنانکه ماشین حالتِ ماشین RASP، برنامه را درون رجیسترها تفسیر می‌کند، ماشینِ حالت دقیقاً در حال انجام چه کاری خواهد بود؟ ستون حاوی علامت تعجب !، اعمال ماشین حالت را در توالی زمانی فهرست خواهد نمود، چنان‌که برنامه را "تفسیر می‌کند" (به عمل تبدیل می‌کند):به‌طور مرسوم، اعمال ماشینِ حالت به دو "مرحله"ی اصلی به نام‌های واکشی و اجرا تقسیم می‌کند. در زیر آن مشاهده خواهیم نمود که "زیرفاز"هایی درون این مراحل اصلی وجود دارند. هیچ توافق قراردادی وجود ندارد؛ هر مدل نیازمند تعریف دقیق خودش خواهد بود.مرحلهٔ واکشی.ماشین حالت، هم مستقیم و هم غیرمستقیم، به تمام رجیسترها دسترسی دارد؛ بنابراین #۱ را به عنوان "شمارشگر برنامه" (PC) اتخاذ می‌کند. نقش شمارشگر برنامه "حفظ موقعیت" در فهرست برنامه خواهد بود؛ ماشین حالت، برای کاربرد اختصاصی‌اش، دارای رجیستر حالتِ منحصربفرد خود است.به محض شروع، ماشین حالت منتظر یافتن یک شماره درون PC می‌ماند، یعنی اولین "فرمان برنامه‌ای" درون برنامه (مثلاً در #۵).هدف از نکتهٔ انحرافی بالا این است که نشان دهیم، زمانی‌که ماشین حالت به دو نوع کپی غیرمستقیم دسترسی دارد، کارها آسان‌تر خواهند بود:مثال بعدی نشان می‌دهد که در طی مرحلهٔ "واکشی" ماشینِ حالت، چه اتفاقی رخ می‌دهد. عملیات‌های ماشینِ حالت در زیر ستونی با عنوان "فرمان‌های ماشینِ حالت ↓ " فهرست شده‌اند. مشاهده کنید که در انتهای واکشی، رجیستر #۲ حاوی مقدار عددی ۳ از "کد عملیاتی" ("opcode") فرمان اول JZ است.مرحلهٔ تجزیه: اکنون که شمارهٔ فرمان برنامه‌ای (مثلاً ۳=”JZ”) درون رجیستر #۲ –رجیستر فرمان برنامه‌ای– قرار دارد، ماشینِ حالت به کاهش شماره تا زمانی‌که رجیستر فرمان (IR) خالی شود، ادامه می‌دهد:اگر IR پیش از کاهش خالی بود، پس فرمان برنامه‌ای ۰=HALT خواهد بود، و ماشین به روال "HALT" خود جهش خواهد نمود. پس از اولین کاهش، در صورتی که حفره خالی بود، فرمان INC خواهد بود، و ماشین به فرمان "inc_routine" جهش خواهد نمود. پس از دومین کاهش، IR خالی DEC را نمایش داده و ماشین به فرمان "dec_routine" جهش خواهد کرد. پس از سومین کاهش، IR واقعاً خالی می‌شود و این امر منجر به جهش به روال "JZ_routine" خواهد شد. در صورتی‌که یک عدد غیرمنتظره همچنان درون IR وجود داشته باشد، (برای مثال) ماشین یک خطا را شناسایی نموده و HALT خواهد نمود."مرحلهٔ اجرا، JZ_routine.اکنون ماشینِ حالت می‌داند که کدام دستورالعمل برنامه‌ای را اجرا نماید؛ در واقع به ردیف فرمان‌های "JZ_routine" جهش یافته‌است. فرمان JZ دارای دو عملوند است، (i) رقم رجیستر جهت آزمون، و (ii) آدرسی که در صورت موفقیت‌آمیز بودن آزمون (خالی بودن حفره) باید به آن مراجعه نمود.واکشی عملوند - کدام رجیستر را جهت خالی بودن آزمایش کنیم؟ : مشابه مرحلهٔ واکشی، ماشینِ حالت محدود، مقادیر رجیستری را که توسط PC به آن اشاره شده، مثلاً حفرهٔ #۶، را به درون رجیستر فرمان برنامه‌ایِ #۲ منتقل می‌کند. سپس از مقادیر رجیستر #۲ برای اشاره به رجیستر جهت آزمایش شدن برای صفر، مثلاً رجیستر #۱۸، استفاده می‌کند. حفرهٔ #۱۸ محتوی عدد "n" است. اکنون برای انجام آزمایش، ماشینِ حالت از مقادیر PIR جهت کپی غیرمستقیم رجیستر #۱۸ درون یک رجیستر یدکی، #۳، استفاده می‌کند؛ بنابراین دو احتمال وجود دارد، (ia) رجیستر #۱۸ خالی است، (ib) رجیستر #۱۸ خالی نیست.(ia) در صورتی‌که رجیستر #۳ خالی باشد، ماشینِ حالت به (ii) دومین واکشی عملوند، جهش می‌یابد (واکشی آدرس جهش به).(ib) در صورتی‌که رجیستر #۳ خالی نباشد، ماشین حالت می‌تواند (ii) دومین واکشی عملوند را نادیده بگیرد. این کار به سادگی PC را دو بار کاهش می‌دهد و سپس بدون قید و شرط به مرحلهٔ واکشیِ فرمان، یعنی جاییکه فرمان برنامه‌ای #۸ را واکشی می‌کند (DEC)، بازمی‌گردد.(ii) واکشی عملوند – آدرس جهش به. اگر رجیستر #۳ خالی باشد، ماشینِ حالت اقدام به استفاده از PC جهت کپی غیرمستقیم مقادیر رجیستری که به آن اشاره دارد (#۸) به درون خود، می‌کند. اکنون PC آدرس "جهش به" ۱۵ را نگه می‌دارد. سپس ماشینِ حالت بدون قید و شرط به مرحلهٔ واکشی فرمان بازمی‌گردد، یعنی جاییکه فرمان برنامه‌ای #۱۵ را واکشی می‌نماید (HALT).مرحلهٔ اجرایی INC، DEC.شرح زیر، تفسیر ماشینِ حالت RAM از فرمان‌های برنامه‌ای، یعنی INC h، DEC h، را کامل می‌کند و بدین ترتیب نمایش چگونگی "جعل هویت" RASP توسط RAM را تمکیل می‌نماید.بدون فرمان‌های غیرمستقیم ماشینِ حالت، INCi و DECi، جهت اجرای فرمان‌های برنامه‌ایِ INC و DEC، ماشینِ حالت باید از کپی غیرمستقیم جهت گرفتن مقادیر رجیستر مورد اشاره به درون رجیستر یدکی #۳ استفاده نماید، آن را DEC یا INC کرده، و سپس برای بازفرستادن آن به رجیستر مورد اشاره، از کپی غیرمستقیم استفاده کند.فرمان‌های جایگزین: اگرچه این نمایش به یک RASP اولیه از تنها چهار فرمان منجر شد، خواننده باید حدس بزند که یک فرمان اضافی مانند "ADD &lt;h&gt;" یا "MULT &lt;ha&gt;,«hb&gt;"، چگونه ممکن است انجام شود.برنامه‌های RASP خود اصلاحزمانیکه یک RAM به عنوان یک RASP عمل می‌کند، مورد جدیدی به دست می‌آید: RASP، بر خلاف RAM، ظرفیت خود اصلاحی فرمان‌های برنامه‌ای خود را دارد (فرمان‌های ماشینِ حالت ثابت بوده و غیرقابل تعدیل توسط ماشین هستند). کوک-رکهو (Cook-Reckhow) (1971) (صفحه ۷۵)، مانند هارتمانیس (Hartmanis) (1971) (صفحات ff239)، در توصیفشان از مدل RASP خود، دربارهٔ این موضوع اظهارنظر کرده‌اند.تعریفی اولیه از این مفهوم را می‌توان در گلدشتین-فون نویمان (Goldstine-von Neumann) (1946) یافت:"ما به دستوری (فرمانی) نیاز داریم که بتواند یک عدد را درون یک ردیف مشخص جایگزین نماید… با استفاده از چنین دستوری، نتایج یک محاسبه را می‌توان به صورت فرمان‌هایی نشان داد که این محاسبه یا یک محاسبهٔ دیگر را کنترل می‌کنند" (صفحه ۹۳).چنین قابلیتی، موارد زیر را ممکن می‌سازد:مجموعهٔ فرمان برنامه‌ای RASP از طرف کوک و رکهو (۱۹۷۳).استفان ای. کوک و رابرت ای. رکهو، تفسیر خود از یک RASP را در یک مقالهٔ مؤثر، چنین شرح می‌دهند:"ماشین برنامهٔ ذخیره شده با دسترسی تصادفی (RASP) شرح داده شده در اینجا، مشابه RASPهای شرح داده شده توسط هارتمانیس می‌باشد" (صفحه ۷۴).هدف آن‌ها، مقایسهٔ زمان‌های اجرایی مدل‌های مختلف از جمله RAM، RASP و ماشین تورینگ چند نواری، جهت استفاده در نظریهٔ تحلیل پیچیدگی بود.ویژگی چشمگیر مدل RASP آن‌ها، بی‌قیدی برای فرمان‌های برنامه‌ای غیرمستقیم است (به بحث آن-ها در صفحه ۷۵ رجوع شود). آن‌ها با ملزم نمودن یک برنامه جهت اصلاح خود، به این نتیجه رسیدند: در صورت لزوم، یک فرمان می‌تواند "مولفه"ی (به قول آن‌ها، مثلاً "عملوند") یک فرمان خاص را اصلاح نماید. آن‌ها مدل خود را به گونه‌ای طراحی کردند که هر "فرمان" از دو رجیستر متوالی استفاده نماید، یکی برای "کد عملیاتی" (به قول آن‌ها) و مؤلفهٔ "یک آدرس یا یک ثابت اینتجر".رجیسترهای RASP آن‌ها از لحاظ ظرفیت و از لحاظ تعداد، نامحدود هستند؛ به همین ترتیب، انباشتگر آن-ها یعنی AC، و شمارندهٔ فرمان، IC، نیز نامحدود هستند. مجموعهٔ فرمان‌ها به شرح زیر هستند:منابع.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.