آلة الوصول العشوائي

في علم الحاسوب ، تُعدّ آلة الوصول العشوائي ( RAM أو آلة RA ) نموذجًا للحوسبة يصف آلة مجردة ضمن فئة آلات السجلات . تشبه آلة RA آلة العداد إلى حد كبير ، ولكنها تتميز بقدرة إضافية على "العنونة غير المباشرة" لسجلاتها. تُعادل "السجلات" بديهيًا الذاكرة الرئيسية للحاسوب العادي، باستثناء قدرتها الإضافية على تخزين الأعداد الطبيعية بأي حجم. وكما هو الحال في آلة العداد، تحتوي آلة RA على تعليمات التنفيذ في الجزء ذي الحالات المحدودة من الآلة (ما يُعرف ببنية هارفارد ).

يُطلق على ما يُعادل آلة تورينج العالمية في آلة الوصول العشوائي (RA) - حيث يُخزَّن برنامجها في سجلاتها بالإضافة إلى بياناتها - اسم آلة الوصول العشوائي ذات البرنامج المخزن أو آلة RASP. وهي مثال على ما يُسمى ببنية فون نيومان، وتُعدّ الأقرب إلى المفهوم الشائع للحاسوب .

إلى جانب نموذجي آلة تورينج وآلة العداد ، تُستخدم نماذج آلة الوصول العشوائي (RA) وآلة الوصول العشوائي المتوازي (RASP) في تحليل التعقيد الحسابي . ويُطلق فان إمدي بواس (1990) على هذه النماذج الثلاثة، بالإضافة إلى آلة المؤشر ، اسم "نماذج الآلة التسلسلية"، لتمييزها عن نماذج " آلة الوصول العشوائي المتوازية ".

وصف غير رسمي

يتكون جهاز التصوير بالرنين المغناطيسي من المكونات التالية:

عدد لا نهائي من مواقع الذاكرة تُسمى " المسجلات "؛ لكل مسجل عنوان، وهو إما عدد طبيعي أو صفر؛ يمكن لكل مسجل تخزين عدد طبيعي واحد فقط من أي حجم، أو صفر.
جدول التعليمات ، أو ببساطة "الجدول"، الذي يحتوي على تعليمات التنفيذ؛ تختلف مجموعة التعليمات الدقيقة باختلاف المؤلف؛ تشمل التعليمات الشائعة: الزيادة، والنقصان، والمسح إلى الصفر، والنسخ، والقفز المشروط، والإيقاف؛ أما التعليمات الأخرى فهي غير ضرورية لأنه يمكن إنشاؤها من خلال تركيبات من التعليمات الموجودة في مجموعة التعليمات.
يوجد سجل خاص يُسمى " سجل التعليمات " (IR)؛ يشير هذا السجل إلى التعليمات التي يتم تنفيذها في جدول التعليمات.

للحصول على وصف لمفهوم مشابه، ولكن بأسلوب فكاهي، انظر إلى لغة البرمجة الباطنية Brainfuck . ^{[ 1 ]}

مقدمة عن النموذج

يبدأ مفهوم ذاكرة الوصول العشوائي (RAM) بأبسط نموذج على الإطلاق، وهو ما يُعرف بنموذج آلة العداد . إلا أن إضافتين تُبعدان هذا النموذج عن نموذج آلة العداد. الأولى تُحسّن الآلة من خلال سهولة العنونة غير المباشرة؛ أما الثانية فتُحوّل النموذج نحو الحاسوب التقليدي القائم على المُراكم بإضافة مُسجّل واحد أو أكثر من المُسجّلات المساعدة (المُخصصة)، وأكثرها شيوعًا هو ما يُسمى "المُراكم".

التعريف الرسمي

آلة الوصول العشوائي (RAM) هي نموذج آلة حسابية مجردة، مطابقة لآلة عداد متعددة السجلات، مع إضافة خاصية العنونة غير المباشرة. وبناءً على التعليمات الواردة في جدول آلة الحالة المحدودة ، تستنتج الآلة عنوان سجل "الهدف" إما (أ) مباشرةً من التعليمات نفسها، أو (ب) بشكل غير مباشر من محتويات سجل "المؤشر" المحدد في التعليمات (مثل الرقم، التسمية).

بحسب التعريف: السجل هو موقع له عنوان (معرّف/محدد فريد ومميز يُعادل عددًا طبيعيًا) ومحتوى - عدد طبيعي واحد. وللدقة، سنستخدم الرموز شبه الرسمية من بولوس-بورغيس-جيفري (2002) لتحديد السجل ومحتوياته والعملية التي تُجرى عليه.

[r] تعني "محتويات السجل ذي العنوان r". والرمز "r" هنا هو "متغير" يمكن ملؤه برقم طبيعي أو حرف (مثل "A") أو اسم.
→ تعني "النسخ/الإيداع في"، أو "الاستبدال"، ولكن دون إتلاف المصدر.

مثال: [3] + 1 → 3؛ تعني: "يتم وضع محتويات سجل المصدر ذي العنوان "3"، مضافًا إليها 1، في سجل الوجهة ذي العنوان "3" (هنا المصدر والوجهة هما نفس المكان). إذا كان [3] = 37، أي أن محتويات السجل 3 هي الرقم "37"، فسيتم وضع 37 + 1 = 38 في السجل 3.

مثال: [3] → 5؛ تعني "يتم وضع محتويات سجل المصدر ذي العنوان "3" في سجل الوجهة ذي العنوان "5". إذا كان [3]=38، أي أن محتويات السجل 3 هي الرقم 38، فسيتم وضع هذا الرقم في السجل 5. لا تتأثر محتويات السجل 3 بهذه العملية، لذا يبقى [3] كما هو 38، وهو الآن مطابق لـ [5].

التعريف: التعليمات المباشرة هي التي تحدد في التعليمات نفسها عنوان سجل المصدر أو الوجهة الذي ستكون محتوياته موضوع التعليمات. التعريف: التعليمات غير المباشرة هي التي تحدد "سجل مؤشر"، ومحتوياته هي عنوان سجل "هدف". يمكن أن يكون سجل الهدف إما مصدرًا أو وجهة (تُقدم تعليمات النسخ المختلفة أمثلة على ذلك). يمكن للسجل أن يُعنون نفسه بشكل غير مباشر.

نظراً لعدم وجود معيار/اتفاقية، ستحدد هذه المقالة "مباشر/غير مباشر"، ويرمز له اختصاراً بـ "d/i"، كمعامل (أو معاملات) في التعليمات:

مثال: تعني COPY ( d , A, i , N ) أن d يحصل مباشرة على عنوان سجل المصدر (السجل "A") من التعليمة نفسها، ولكن بشكل غير مباشر يحصل i على عنوان الوجهة من سجل المؤشر N. لنفترض أن [N]=3، فإن السجل 3 هو الوجهة وستقوم التعليمة بما يلي: [A] → 3.

التعريف: تستخدم التعليمات محتويات سجل المصدر . ويمكن تحديد عنوان سجل المصدر إما (أ) مباشرةً بواسطة التعليمات، أو (ب) بشكل غير مباشر بواسطة سجل المؤشر المحدد بواسطة التعليمات.

التعريف: محتويات سجل المؤشر هي عنوان سجل "الهدف".

التعريف: يشير محتوى سجل المؤشر إلى سجل الهدف - قد يكون "الهدف" إما سجل مصدر أو سجل وجهة.

التعريف: سجل الوجهة هو المكان الذي تُودع فيه التعليمة نتيجتها. يمكن تحديد عنوان سجل المصدر إما (أ) مباشرةً بواسطة التعليمة، أو (ب) بشكل غير مباشر بواسطة سجل المؤشر المحدد بواسطة التعليمة. قد يكون سجل المصدر وسجل الوجهة سجلاً واحداً.

تذكير: نموذج آلة البيع

يقدم ميلزاك (1961) تصورًا مبسطًا لآلة عدّ: فجوات في الأرض تُسمى "سجلاتها"، وتحتوي هذه الفجوات على حصى. وبناءً على تعليمات، يقوم "الحاسوب" (شخص أو آلة) بإضافة (زيادة) أو إزالة (إنقاص) حصاة واحدة من هذه الفجوات. وعند الحاجة، تُضاف حصى إضافية، وتُعاد الحصى الزائدة إلى مصدر لا نهائي؛ وإذا كانت الفجوة صغيرة جدًا بحيث لا تتسع للحصى، يقوم "الحاسوب" بتوسيعها.

يقدم مينسكي (1961) وهوبكروفت-أولمان (1979، ص 171) تصورًا لآلة تورينج متعددة الأشرطة ، بعدد من الأشرطة ذات النهاية اليسرى يساوي عدد "السجلات". طول كل شريط غير محدود من اليمين، وكل مربع فارغ باستثناء الطرف الأيسر الذي يحمل علامة. تمثل المسافة بين "رأس" الشريط وطرفه الأيسر، مقاسةً بعدد مربعات الشريط، العدد الطبيعي في "السجل". لإنقاص عدد المربعات، يتحرك رأس الشريط إلى اليسار؛ ولزيادته، يتحرك إلى اليمين. لا حاجة لطباعة أو مسح علامات على الشريط؛ التعليمات الشرطية الوحيدة هي التحقق مما إذا كان الرأس عند الطرف الأيسر، وذلك باختبار علامة الطرف الأيسر باستخدام تعليمة "القفز إذا كانت مُعلَّمة".

إن "الرموز التذكيرية" التالية مثل "CLR (r)" هي رموز اعتباطية؛ لا يوجد معيار محدد.

تحتوي آلة التسجيل ، كذاكرة خارجية لآلة الحالة المحدودة ، على مجموعة غير محدودة (انظر الحاشية | قابلة للعد وغير محدودة) من المواقع المنفصلة والمُصنفة بشكل فريد ذات سعة غير محدودة ، تُسمى "السجلات". تحتوي هذه السجلات على أعداد طبيعية فقط (صفر وأعداد صحيحة موجبة). وفقًا لقائمة التعليمات المتسلسلة في جدول آلة الحالة المحدودة، تُجرى بعض العمليات الأولية (مثلاً 2) على محتويات هذه "السجلات". أخيرًا، يتوفر تعبير شرطي على شكل IF-THEN-ELSE لاختبار محتويات سجل واحد أو سجلين، ولإخراج آلة الحالة المحدودة من تسلسل التعليمات الافتراضي.

النموذج الأساسي 1 : النموذج الأقرب إلى تصور مينسكي (1961) ولامبيك (1961):

{ زيادة محتويات المسجل r، إنقاص محتويات المسجل r، إذا كانت محتويات المسجل r تساوي صفرًا، فانتقل إلى التعليمات 1 _z، وإلا فاستمر إلى التعليمات التالية }:

تعليمات	ذاكري	الإجراء على السجل (السجلات) "r"	الإجراء على سجل التعليمات الخاص بآلة الحالة المحدودة، IR
زيادة	شركة (ر)	[r] + 1 → r	[IR] + 1 → IR
تخفيض	DEC ( r )	[r] - 1 → r	[IR] + 1 → IR
اقفز إذا كان الصفر	JZ ( r, z )	لا أحد	إذا كان [r] = 0 فإن z → IR، وإلا فإن [IR] + 1 → IR
وقف	ح	لا أحد	[IR] → IR

النموذج الأساسي 2 : نموذج "الخلف" (سمي على اسم دالة الخلف لبديهيات بيانو ):

{ قم بزيادة محتويات المسجل r، وامسح محتويات المسجل r، وإذا كانت محتويات المسجل rj _تساوي محتويات المسجل rk _، فانتقل إلى التعليمات 1z _،وإلا فانتقل إلى التعليمات التالية. }

تعليمات	ذاكري	الإجراء على السجل (السجلات) "r"	الإجراء على سجل التعليمات الخاص بآلة الحالة المحدودة، IR
واضح	CLR ( r )	0 → r	[IR] + 1 → IR
زيادة	شركة (ر)	[r] + 1 → r	[IR] + 1 → IR
انتقل إذا كان متساويًا	JE (r1, r2, z)	لا أحد	إذا كان [r1] = [r2] فإن z → IR، وإلا فإن [IR] + 1 → IR
وقف	ح	لا أحد	[IR] → IR

النموذج الأساسي 3 : استخدمه إلجوت-روبنسون (1964) في بحثهما عن RASPs المحدودة وغير المحدودة - النموذج "الخلف" مع COPY في مكان CLEAR:

{ قم بزيادة محتويات المسجل r، وانسخ محتويات المسجل r _j إلى المسجل r _k ، وإذا كانت محتويات المسجل r _j تساوي محتويات المسجل r _k، فانتقل إلى التعليمات I _z،وإلا فانتقل إلى التعليمات التالية }

تعليمات	ذاكري	الإجراء على السجل (السجلات) "r"	الإجراء على سجل التعليمات الخاص بآلة الحالة المحدودة، IR
ينسخ	نسخ (r1، r2)	[r1] → r2	[IR] + 1 → IR
زيادة	شركة (ر)	[r] + 1 → r	[IR] + 1 → IR
انتقل إذا كان متساويًا	JE (r1, r2, z)	لا أحد	إذا كان [r1] = [r2] فإن z → IR، وإلا فإن [IR] + 1 → IR
وقف	ح	لا أحد	[IR] → IR

إنشاء "تعليمات ملائمة" من المجموعات الأساسية

تُعتبر المجموعات الأساسية الثلاث المذكورة أعلاه (1، 2، أو 3) متكافئة، بمعنى أنه يُمكن إنشاء تعليمات إحدى المجموعات باستخدام تعليمات مجموعة أخرى (تمرين مفيد: تلميح من مينسكي (1967) - قم بتعريف سجل محجوز، على سبيل المثال، سمّه "0" (أو Z للدلالة على "صفر" أو E للدلالة على "مسح") ليحتوي على الرقم 0). يعتمد اختيار النموذج على ما يجده المؤلف أسهل استخدامًا في عرض توضيحي أو برهان، وما إلى ذلك.

علاوة على ذلك، يمكننا إنشاء أي من الدوال التكرارية الأولية من المجموعات الأساسية 1 أو 2 أو 3 (انظر مينسكي (1967)، وبولوس-بورغيس-جيفري (2002)). (سيتم مناقشة كيفية توسيع نطاق البحث ليشمل الدوال التكرارية الكلية والجزئية في سياق العنونة غير المباشرة). مع ذلك، يُعدّ بناء الدوال التكرارية الأولية أمرًا صعبًا نظرًا لصغر حجم مجموعات التعليمات. يتمثل أحد الحلول في توسيع مجموعة معينة بإضافة "تعليمات مُيسّرة" من مجموعة أخرى.

لن تكون هذه إجراءات فرعية بالمعنى التقليدي، بل ستكون عبارة عن كتل من التعليمات مُنشأة من المجموعة الأساسية ومُعطاة رمزًا تذكيريًا. من الناحية الرسمية، لاستخدام هذه الكتل، نحتاج إما إلى (أ) "توسيعها" إلى ما يُعادلها من التعليمات الأساسية - سيتطلب ذلك استخدام سجلات مؤقتة أو "مساعدة"، لذا يجب أن يأخذ النموذج ذلك في الاعتبار، أو (ب) تصميم أجهزتنا/نماذجنا مع تضمين هذه التعليمات مُسبقًا.

مثال: المجموعة الأساسية 1. لإنشاء سجل CLR (r)، استخدم مجموعة التعليمات لعدّ السجل r تنازليًا إلى الصفر. لاحظ استخدام التلميح المذكور أعلاه:

CLR (r) = _مكافئ
حلقة : JZ (r, خروج )

DEC (r)
JZ (0، حلقة )

مخرج : إلخ.

مرة أخرى، كل هذا من أجل التسهيل فقط؛ لا شيء من هذا يزيد من القوة الجوهرية للنموذج.

على سبيل المثال: ستتضمن المجموعة الأكثر توسعًا كل تعليمة فريدة من المجموعات الثلاث، بالإضافة إلى القفزة غير المشروطة J (z) أي:

{ CLR (r), DEC (r), INC (r), CPY ( r _s , r _d ), JZ (r, z), JE ( r _j , r _k , z ), J(z) }

يختار معظم المؤلفين أحد القفزات الشرطية، على سبيل المثال يستخدم Shepherdson-Sturgis (1963) المجموعة المذكورة أعلاه ناقص JE (لكي يكونوا دقيقين تمامًا، فإنهم يستخدمون JNZ - القفز إذا لم يكن صفرًا بدلاً من JZ؛ وهي تعليمات ملائمة أخرى محتملة).

العملية "غير المباشرة"

مثال على العنونة غير المباشرة

إن مفهوم "العملية غير المباشرة" ليس بالأمر غير المألوف في حياتنا اليومية.

مثال: البحث عن الكنز.

في الموقع "Tom_&_Becky's_cave_in_pirate_chest" سنجد خريطة ترشدنا إلى "الكنز":

(1) نذهب إلى الموقع "كهف توم وبيكي..." ونحفر حتى نجد صندوقًا خشبيًا

(2) يوجد داخل الصندوق خريطة لموقع الكنز: "تحت الشرفة الأمامية لمنزل تاتشر"

(3) نذهب إلى الموقع "تحت الشرفة الأمامية لتاتشر"، ونقوم بتكسير الخرسانة، ونكتشف "الكنز": كيس من مقابض الأبواب الصدئة.

تحدد التوجيهات غير المباشرة موقعًا يُعرف باسم صندوق القراصنة في "كهف توم وبيكي..." والذي يعمل كمؤشر إلى أي موقع آخر (بما في ذلك نفسه): محتوياته (خريطة الكنز) توفر "عنوان" الموقع المستهدف "تحت الشرفة الأمامية لتاتشر" حيث يحدث الحدث الحقيقي.

لماذا الحاجة إلى عملية غير مباشرة: مشكلتان رئيسيتان في نموذج الآلة المضادة

فيما يلي، يجب التذكير بأن هذه النماذج هي نماذج مجردة تختلف اختلافًا جوهريًا عن أي شيء حقيقي ماديًا في أمرين: عدد غير محدود من المسجلات، لكل منها سعة غير محدودة. تبرز المشكلة بشكل جليّ عند محاولة استخدام نموذج آلة العداد لبناء خوارزمية RASP مكافئة لخوارزمية تورينج ، وبالتالي حساب أي دالة تكرارية جزئية من نوع mu .

أضاف ميلزاك (1961) التوجيه غير المباشر إلى نموذجه "الحفرة والحصاة" ليتمكن من تعديل نفسه باستخدام "انتقال محسوب"، وقدم مثالين على استخدامه ("التمثيل العشري بمقياس d" و"الفرز حسب الحجم"، لكن من غير الواضح ما إذا كان قد استخدمهما في برهانه على أن النموذج مكافئ لتورينغ، إذ "ترك البرنامج نفسه للقارئ كتمرين" (ص 292)). تمكن مينسكي (1961، 1967) من إثبات أنه باستخدام ترميز غودل العددي المناسب (وإن كان صعب الاستخدام) ، لا يحتاج نموذج السجل إلى التوجيه غير المباشر ليكون مكافئًا لتورينغ؛ ولكنه يحتاج إلى سجل واحد على الأقل غير محدود. وكما هو موضح أدناه، ألمح مينسكي (1967) إلى المشكلة في RASP لكنه لم يقدم حلاً. أثبت إلجوت وروبنسون (1964) أن نموذج RASP الخاص بهما P0 _-الذي يفتقر إلى إمكانية التوجيه غير المباشر - لا يستطيع حساب جميع "الدوال التسلسلية المتكررة" (التي لها معلمات ذات طول عشوائي) إذا لم يكن لديه القدرة على تعديل تعليماته الخاصة، ولكنه يستطيع ذلك باستخدام أعداد غودل إذا كان لديه هذه القدرة (ص 395-397؛ وبالتحديد الشكل 2 والحاشية ص 395). من ناحية أخرى، يستطيع نموذج RASP الخاص بهما P'0 _المزود بـ "سجل فهرسة" (عنونة غير مباشرة) حساب جميع "الدوال التسلسلية المتكررة الجزئية" (الدوال المتكررة من نوع mu) (ص 397-398).

يقول كوك وريكهاو (1973) ذلك بأبسط طريقة:

التعليمات غير المباشرة ضرورية لكي يتمكن برنامج ثابت من الوصول إلى عدد غير محدود من السجلات مع تغير المدخلات. (ص 73)

السعات غير المحدودة للسجلات مقابل السعات المحدودة لتعليمات آلة الحالة : يُفترض أن يكون ما يُسمى بجزء الحالة المحدودة من الآلة - وفقًا للتعريف المعتاد للخوارزمية - محدودًا جدًا من حيث عدد "الحالات" (التعليمات) وأحجام التعليمات (قدرتها على استيعاب الرموز/الإشارات). فكيف تنقل آلة الحالة ثابتًا كبيرًا بشكل تعسفي مباشرةً إلى سجل، مثل MOVE (k, r) (نقل الثابت k إلى السجل r)؟ إذا كانت الثوابت الضخمة ضرورية، فيجب أن تبدأ إما في السجلات نفسها أو أن تُنشأ بواسطة آلة الحالة باستخدام عدد محدود من التعليمات، مثل إجراءات الضرب والجمع الفرعية باستخدام INC وDEC (ولكن ليس عددًا شبه لانهائي منها!).

أحيانًا، يُنشأ الثابت k باستخدام الأمر CLR(r) متبوعًا بالأمر INC(r) مكررًا k مرة - على سبيل المثال، لوضع الثابت k=3 في المسجل r، أي 3 → r، لذا في نهاية التعليمة [r]=3: CLR(r)، INC(r)، INC(r)، INC(r). وقد ذكر كلين (1952) هذه الحيلة في الصفحة 223. تكمن المشكلة عندما يتجاوز العدد المطلوب إنشاؤه عدد التعليمات المتاحة لآلة الحالة المحدودة ؛ إذ يوجد دائمًا ثابت أكبر من عدد التعليمات المتاحة لآلة الحالة المحدودة .

عدد غير محدود من المسجلات مقابل تعليمات محدودة لآلة الحالة : هذه المشكلة أشد خطورة من الأولى. وتبرز هذه المشكلة تحديدًا عند محاولة بناء ما يُسمى بـ RASP، وهي "آلة شاملة" (انظر المزيد في آلة تورينج الشاملة ) تستخدم آلة الحالة المحدودة الخاصة بها لتفسير "برنامج تعليمات" موجود في مسجلاتها - أي أننا نبني ما يُسمى اليوم حاسوبًا ببنية فون نيومان .

لاحظ أن آلة الحالة المحدودة في جهاز العداد يجب أن تستدعي السجل صراحةً (مباشرةً) باسمه/رقمه: فمثلاً، تستدعي الدالة INC (65,356) السجل رقم "65,365" صراحةً . إذا تجاوز عدد السجلات قدرة آلة الحالة المحدودة على الوصول إليها، فلن يكون بالإمكان الوصول إلى السجلات الواقعة خارج هذا النطاق. على سبيل المثال، إذا كانت آلة الحالة المحدودة لا تستطيع الوصول إلا إلى 65,536 = 2^ ¹⁶ سجلاً، فكيف يمكنها الوصول إلى السجل رقم 65,537؟

كيف نتعامل مع سجل خارج نطاق آلة الحالة المحدودة؟ يتمثل أحد الحلول في تعديل تعليمات البرنامج (المخزنة في السجلات) بحيث تحتوي على أكثر من أمر. لكن هذا الحل قد ينفد أيضًا ما لم تكن التعليمات ذات حجم غير محدود (محتمل). فلماذا لا نستخدم "تعليمات فائقة" واحدة - رقمًا ضخمًا جدًا - تحتوي على جميع تعليمات البرنامج المشفرة فيه؟ هكذا حل مينسكي المشكلة، لكن ترقيم غودل الذي استخدمه يمثل عائقًا كبيرًا أمام النموذج، والنتيجة لا تشبه مفهومنا البديهي عن "حاسوب البرنامج المخزن".

توصل إلجوت وروبنسون (1964) إلى استنتاج مماثل فيما يتعلق بـ RASP "المحدد بشكل نهائي". في الواقع، يمكنه الوصول إلى عدد غير محدود من السجلات (على سبيل المثال لجلب التعليمات منها) ولكن فقط إذا سمح RASP "بالتعديل الذاتي" لتعليمات برنامجه ، وقام بتشفير "بياناته" في عدد غودل (الشكل 2، صفحة 396).

في سياق نموذج أقرب إلى الحاسوب باستخدام تعليمة التكرار (RPT) الخاصة به، يُشوقنا مينسكي (1967) بحل للمشكلة (انظر الصفحتين 214 و259)، لكنه لا يقدم حلاً قاطعاً. ويؤكد ما يلي:

"بشكل عام، لا يمكن أن تكون عملية RPT تعليمة في الجزء ذي الحالة المحدودة من الجهاز ... فقد يؤدي ذلك إلى استنفاد أي مقدار معين من التخزين المسموح به في الجزء المحدود من الكمبيوتر [هكذا، وهو الاسم الذي أطلقه على نماذج ذاكرة الوصول العشوائي الخاصة به]. تتطلب عمليات RPT سجلات غير محدودة خاصة بها." (ص 214).

يقدم لنا دالة تكرارية محدودة (RPT) يمكنها، بالاشتراك مع CLR(r) وINC(r)، حساب أي دالة تكرارية أولية . كما يقدم دالة تكرارية غير محدودة (RPT) المذكورة أعلاه، والتي تؤدي دور عامل μ؛ ويمكنها، بالاشتراك مع CLR(r) وINC(r)، حساب دوال μ التكرارية. لكنه لا يناقش "التوجيه غير المباشر" أو نموذج RAM بحد ذاته.

من المراجع الواردة في هارتمانيس (1971)، يبدو أن كوك (في ملاحظاته أثناء عمله في جامعة كاليفورنيا، بيركلي، عام 1970) قد رسّخ مفهوم العنونة غير المباشرة. ويتضح هذا جليًا في ورقة كوك وريكهاو (1973) - حيث كان كوك مشرفًا على رسالة الماجستير لريكهاو. يستخدم نموذج هارتمانيس - المشابه إلى حد كبير لنموذج ميلزاك (1961) - عمليات جمع وطرح ثنائية وثلاثية السجلات، ونسختين للمعاملات؛ بينما يقلل نموذج كوك وريكهاو عدد المعاملات (السجلات المُشار إليها في تعليمات البرنامج) إلى استدعاء واحد باستخدام مُراكم "AC".

الحل باختصار: تصميم الآلة/النموذج مع توجيه غير محدود - توفير سجل "عنوان" غير محدود يمكنه تسمية أي سجل مهما كان عدده. لكي يعمل هذا، يتطلب السجل غير المحدود عمومًا إمكانية مسحه ثم زيادته (وربما إنقاصه) عبر حلقة تكرارية لا نهائية. بهذا المعنى، يمثل الحل عامل μ غير المحدود الذي يمكنه، عند الضرورة، البحث بلا نهاية على طول سلسلة السجلات غير المحدودة حتى يعثر على ما يبحث عنه. سجل المؤشر يشبه أي سجل آخر تمامًا باستثناء واحد: في ظل ظروف تُسمى "العنونة غير المباشرة"، يُقدم محتوياته ، بدلًا من مُعامل العنوان في جدول آلة الحالة، ليكون عنوان السجل المستهدف (بما في ذلك نفسه!).

التوجيه المحدود والدوال التكرارية الأولية

إذا تجنبنا نهج مينسكي المتمثل في رقم واحد ضخم في سجل واحد، وحددنا أن نموذج الآلة لدينا سيكون "مثل جهاز كمبيوتر"، فسيتعين علينا مواجهة مشكلة عدم التوجيه هذه إذا أردنا حساب الدوال المتكررة (وتسمى أيضًا الدوال المتكررة μ ) - سواء كانت كلية أو جزئية.

يستطيع نموذجنا الأبسط للآلة المضادة تنفيذ شكل "محدود" من التوجيه غير المباشر ، وبالتالي حساب الفئة الفرعية للدوال التكرارية الأولية ، باستخدام "عامل" تكراري أولي يُسمى "التعريف بالحالات" (كما هو مُعرّف في Kleene (1952) صفحة 229 وBoolos-Burgess-Jeffrey صفحة 74). يُعدّ هذا "التوجيه غير المباشر المحدود" عملية شاقة ومملة. يتطلب "التعريف بالحالات" من الآلة تحديد/تمييز محتويات سجل المؤشر من خلال محاولة مطابقة هذه المحتويات، مرارًا وتكرارًا حتى النجاح، مع رقم/اسم يُعلنه عامل الحالة صراحةً . وهكذا، يبدأ التعريف بالحالات من، على سبيل المثال، عنوان الحد الأدنى، ويستمر بشكل متكرر نحو عنوان الحد الأعلى في محاولة لإيجاد تطابق.

هل الرقم في السجل N يساوي صفرًا؟ إذا لم يكن كذلك، فهل يساوي 1؟ 2؟ 3؟ ... 65364؟ إذا لم يكن كذلك، فنحن عند الرقم الأخير 65365، ويجب أن يكون هو الرقم الصحيح، وإلا فسنواجه مشكلة!

لن يسمح لنا التوجيه "المحدود" بحساب الدوال التكرارية الجزئية - لذلك نحتاج إلى توجيه غير محدود يُعرف أيضًا باسم عامل μ .

لنفترض أننا تمكّنا من الوصول إلى الرقم 65367، وأن هذا السجل يحتوي بالفعل على ما نبحث عنه. حينها كنا سنُكمل حساباتنا بنجاح! لكن لنفترض أن الرقم 65367 لا يحتوي على ما نحتاجه. إلى أي مدى يجب أن نواصل البحث؟

لكي يكون جهاز العد مكافئًا لآلة تورينج، عليه إما استخدام طريقة مينسكي غودل ذات السجل الواحد ، أو أن يُزوّد بقدرة على استكشاف نهايات سلسلة سجلاته، إلى ما لا نهاية إذا لزم الأمر. (يُعرّف عدم العثور على شيء "خارج النطاق" معنى فشل الخوارزمية في الإنهاء؛ انظر كلين (1952)، الصفحات 316 وما بعدها، الفصل الثاني عشر: الدوال التكرارية الجزئية ، وخاصة الصفحات 323-325). للمزيد حول هذا الموضوع، انظر المثال أدناه.

التوجيه غير المحدود والدوال التكرارية الجزئية

للحصول على توجيه غير محدود ، نحتاج إلى تغيير "مادي" في نموذج الآلة. بمجرد إجراء هذا التغيير، لم يعد النموذج آلة عدّاد، بل آلة وصول عشوائي.

عند تحديد تعليمة INC، على سبيل المثال، يجب على تعليمة آلة الحالة المحدودة تحديد مصدر عنوان السجل المطلوب. يمكن أن يكون هذا المصدر إما (أ) تعليمة آلة الحالة التي توفر تسمية صريحة ، أو (ب) سجل المؤشر الذي يحتوي على العنوان المطلوب. عند تحديد عنوان سجل، يجب تحديد مُعامل إضافي "i/d" - "غير مباشر/مباشر". يُعد هذا المُعامل "i/d" بمثابة "مفتاح" يُبدّل بين الحصول على العنوان المباشر كما هو مُحدد في التعليمة، أو الحصول على العنوان غير المباشر من سجل المؤشر (يُحدد المُعامل - في بعض النماذج، يمكن أن يكون أي سجل سجل مؤشر - بواسطة التعليمة). يُعد هذا "الاختيار الحصري والشامل" مثالًا آخر على "التعريف حسب الحالات"، والمكافئ الحسابي الموضح في المثال أدناه مُستمد من التعريف الوارد في Kleene (1952) صفحة 229.

مثال: CPY ( _مصدر غير مباشر ، _مصدر مباشر ، _وجهة مباشرة ، _وجهة مباشرة )

قم بتعيين رمز لتحديد العنونة المباشرة كـ d="0" والعنونة غير المباشرة كـ i="1". عندها يمكن لجهازنا تحديد عنوان المصدر على النحو التالي:

i*[r _s ] + (1-i)*r _s

على سبيل المثال، لنفترض أن محتويات السجل 3 هي "5" (أي [3]=5) ومحتويات السجل 4 هي "2" (أي [4]=2):

مثال: CPY ( 1, 3, 0, 4 ) = CPY ( indirect, reg 3, direct, reg 4 )

1*[3] + 0*3 = [3] = عنوان سجل المصدر 5

0*[4] + 1*4 = 4 = عنوان سجل الوجهة 4

مثال: CPY ( 0, 3, 0, 4 )

0*[3] + 1*3 = 3 = عنوان سجل المصدر 3

0*[4] + 1*4 = 4 = عنوان سجل الوجهة 4

مثال: CPY ( 0, 3, 1, 4 )

0*[3] + 1*3 = 3 = عنوان سجل المصدر 3

1*[4] + 0*4 = [4] = عنوان سجل الوجهة 2

تعليمات النسخ غير المباشرة

لعلّ أكثر التعليمات المضافة فائدة هي COPY. في الواقع، زوّد إلغوت-روبنسون (1964) نموذجيهما P0 _و P'0 بتعليمات COPY، بينما زوّد كوك-ريكهاو (1973) نموذجهما القائم على المُراكم بتعليمات غير مباشرة فقط _–COPY إلى المُراكم بشكل غير مباشر، وCOPY من المُراكم بشكل غير مباشر.

وفرة من التعليمات : نظرًا لإمكانية إضافة نظير غير مباشر لأي تعليمة تعمل على سجل واحد (بما في ذلك القفزات الشرطية وغير الشرطية، انظر نموذج إلغوت-روبنسون)، فإن تضمين التعليمات غير المباشرة سيضاعف عدد التعليمات ذات المعامل/السجل الواحد (مثل INC (d, r)، INC (i, r)). والأسوأ من ذلك، أن كل تعليمة ذات معاملين/سجلين سيكون لها 4 أنواع محتملة، على سبيل المثال:

CPY (d, r _s , d, r _d ) = نسخ البيانات مباشرة من سجل المصدر إلى سجل الوجهة

CPY (i, r _sp , d, r _d ) = نسخ إلى سجل الوجهة بشكل غير مباشر باستخدام عنوان المصدر الموجود في سجل مؤشر المصدر r _sp .

CPY (d, r _s , i, r _dp ) = نسخ محتويات سجل المصدر بشكل غير مباشر إلى السجل باستخدام عنوان الوجهة الموجود في سجل مؤشر الوجهة r _dp .

CPY (i, r _sp , i, r _dp ) = نسخ محتويات سجل المصدر بشكل غير مباشر، حيث يوجد عنوانه في سجل مؤشر المصدر r _sp ، إلى سجل الوجهة، حيث يوجد عنوانه في سجل مؤشر الوجهة r _dp .

وبالمثل، فإن كل تعليمة ثلاثية السجلات تتضمن سجلين مصدر r _s1 r _s2 وسجل وجهة r _d ستنتج 8 أنواع، على سبيل المثال عملية الجمع:

[r _s1 ] + [r _s2 ] → r _d

سينتج عنه:

أضف (d, r _s1 , d, r _s2 , d, r _d )
أضف ( i, r _sp1 , d, r _s2 , d, r _d )
أضف (d, r _s1 , i, r _sp2 , d, r _d )
أضف ( i, r _sp1 , i, r _sp2 , d, r _d )
ADD ( d, r _s1 , d, r _s2 , i, r _dp )
ADD ( i, r _sp1 , d, r _s2 , i, r _dp )
أضف ( d, r _s1 , i, r _sp2 , i, r _dp )
أضف ( i, r _sp1 , i, r _sp2 , i, r _dp )

إذا خصصنا سجلاً واحداً ليكون "المُجمِّع" (انظر أدناه) وفرضنا قيوداً صارمة على التعليمات المسموح بها، فسنتمكن من تقليل عدد العمليات المباشرة وغير المباشرة بشكل كبير. مع ذلك، يجب التأكد من كفاية مجموعة التعليمات المُصغَّرة الناتجة، ويجب أن نُدرك أن هذا التخفيض سيأتي على حساب زيادة عدد التعليمات لكل عملية "مهمة".

مفهوم "المراكم أ"

يخصص العرف التاريخي سجلاً للمراكم، وهو "جهاز حسابي" يقوم حرفياً بتجميع رقمه أثناء سلسلة من العمليات الحسابية:

"يجب أن يكون الجزء الأول من جهازنا الحسابي... جهاز تخزين متوازٍ يمكنه استقبال رقم وإضافته إلى الرقم الموجود فيه، كما أنه قادر على مسح محتوياته وتخزين ما يحتويه. سنطلق على هذا الجهاز اسم " المراكم" . وهو أمر شائع من حيث المبدأ في أجهزة الحوسبة القديمة والحديثة من مختلف الأنواع، مثل مضاعفات المكتب، وعدادات IBM القياسية، وأجهزة الترحيل الحديثة، وجهاز ENIAC " (الخط العريض في الأصل: Goldstine and von Neumann, 1946؛ ص 98 في Bell and Newell 1971).

مع ذلك، يأتي استخدام المُراكم على حساب زيادة عدد التعليمات لكل عملية حسابية، لا سيما فيما يتعلق بتعليمات "القراءة والتعديل والكتابة" مثل "زيادة محتويات السجل المشار إليه بواسطة السجل r2 بشكل غير مباشر". يشير الحرف "A" إلى سجل "المُراكم" A.

ملصق	تعليمات	أ	r2	378,426	وصف
		...	378,426	17
INCi ( r2 ):	CPY ( i, r2, d, A )	17	378,426	17	يشير محتوى r2 إلى r378,426 الذي يحتوي على القيمة "17": انسخ هذا إلى A
	شركة (أ)	18	378,426	17	محتويات الأسمنت من النوع أ
	CPY ( d, A, i, r2 )	18	378,426	18	يشير محتوى r2 إلى r378,426: انسخ محتويات A إلى r378,426

إذا التزمنا باسم محدد للمراكم، مثلاً "A"، فيمكننا تضمين المركم في التعليمات، على سبيل المثال،

INC ( أ ) = INCA

ومع ذلك، عندما نكتب تعليمات CPY بدون استدعاء المُراكم، تكون التعليمات غامضة أو يجب أن تحتوي على معلمات فارغة:

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

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

تاريخيًا، حظيت هاتان التعليمتان CPY بأسماء مميزة، إلا أنه لا يوجد اتفاق رسمي على ذلك. يستخدم التقليد (مثل حاسوب MIX الخيالي لكنوت (1973) ) اسمين هما LOAD وSTORE. هنا نضيف المعامل "i/d".

LDA ( d/i, r _s ) = _def CPY ( d/i, r _s , d, A )

STA ( d/i, r _d ) = _def CPY ( d, A, d/i, r _d )

في النموذج النموذجي القائم على المُراكم، تستخدم جميع عمليات الحساب ذات المتغيرين والعمليات الثابتة (مثل ADD(A, r) و SUB(A, r)) (أ) محتويات المُراكم، بالإضافة إلى (ب) محتويات سجل مُحدد. أما العمليات ذات المتغير الواحد (مثل INC(A) و DEC(A) و CLR(A)) فتتطلب المُراكم فقط. يُودع كلا نوعي التعليمات النتيجة (مثل المجموع، أو الفرق، أو الضرب، أو خارج القسمة، أو الباقي) في المُراكم.

مثال: INCA = [A] + 1 → A

مثال: ADDA (r _s ) = [A] + [r _s ] → A

مثال: MULA (r _s ) = [A] * [r _s ] → A

إذا رغبنا في ذلك، يمكننا اختصار الرموز لأن هناك على الأقل سجل مصدر واحد وسجل وجهة هو دائمًا المُراكم A. وبالتالي لدينا :

{LDA (i/d, r _s )، STA (i/d، r _d )، CLRA، INCA، DECA، ADDA (r _s )، SUBA (r _s )، MULA (r _s )، DIVA (r _s )، إلخ.)

مفهوم سجل العناوين غير المباشر "N"

إذا كان نموذجنا يحتوي على مُجمِّع غير محدود، فهل يمكننا تقييد جميع السجلات الأخرى؟ ليس قبل أن نوفر سجلًا واحدًا على الأقل غير محدود نستمد منه عناويننا غير المباشرة.

يتمثل النهج البسيط في استخدام نفسه (كما تفعل شونهاج).

ثمة نهج آخر (يتبعه شونهاج أيضًا) يتمثل في تعريف سجل معين على أنه "سجل العنوان غير المباشر" وحصر التوجيه غير المباشر بالنسبة لهذا السجل (يستخدم نموذج RAM0 الخاص بشونهاج كلاً من السجلين A وN للتعليمات المباشرة وغير المباشرة). ومرة أخرى، لا يحمل سجلنا الجديد اسمًا تقليديًا - ربما يكون "N" اختصارًا لـ "iNdex"، أو "iNdirect"، أو "رقم العنوان".

لتحقيق أقصى قدر من المرونة، كما فعلنا مع المُراكم A ، سنعتبر N مجرد سجل آخر يخضع للزيادة، والنقصان، والمسح، والاختبار، والنسخ المباشر، وما إلى ذلك. مرة أخرى، يمكننا تقليص التعليمات إلى مُعامل واحد يوفر التوجيه والتوجيه غير المباشر، على سبيل المثال.

LDAN (i/d) = CPY (i/d, N, d, A)؛ مُجمِّع التحميل عبر سجل الاتجاه الداخلي

STAN (i/d) = CPY (d, A, i/d, N). تخزين المُراكم عبر سجل الاتجاه الداخلي

لماذا يُعد هذا النهج مثيرًا للاهتمام؟ لسببين على الأقل:

(1) مجموعة تعليمات بدون معلمات:

يقوم شونهاج بذلك لإنتاج مجموعة تعليمات RAM0 الخاصة به. انظر القسم أدناه.

(2) اختزال ذاكرة الوصول العشوائي إلى آلة ما بعد تورينج:

انطلاقًا من مبدأ التبسيط، نُختزل جميع السجلات باستثناء المُراكم A وسجل التوجيه غير المباشر N، على سبيل المثال r = { r0, r1, r2, ... }، إلى سلسلة غير محدودة من خانات ذات سعة محدودة (جدًا). لن تقوم هذه الخانات بأي وظيفة سوى تخزين أرقام محدودة (جدًا)، مثل بت واحد بقيمة { 0, 1 }. وبالمثل، نُصغّر المُراكم إلى بت واحد. ونُقيّد العمليات الحسابية على السجلين { A, N }، ونستخدم عمليات التوجيه غير المباشر لسحب محتويات السجلات إلى المُراكم، وكتابة 0 أو 1 من المُراكم إلى سجل.

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

نواصل المضي قدماً ونتخلص من A تماماً باستخدام سجلين "ثابتين" يسمى "ERASE" و "PRINT": [ERASE]=0، [PRINT]=1.

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

أعد تسمية تعليمات النسخ واستدعِ INC (N) = RIGHT و DEC (N) = LEFT وستحصل على نفس التعليمات الموجودة في آلة Post-Turing، بالإضافة إلى CLRN إضافي :

{ مسح، طباعة، مسح، يمين، يسار، JZ (i، N، I _z )، JZ (I _z )، H }

تكافؤ تورينج لذاكرة الوصول العشوائي مع التوجيه غير المباشر

في القسم السابق، أوضحنا بشكل غير رسمي أن ذاكرة الوصول العشوائي (RAM) ذات قدرة التوجيه غير المحدودة تُنتج آلة ما بعد تورينج . وبما أن آلة ما بعد تورينج مكافئة لآلة تورينج، فقد أثبتنا أن ذاكرة الوصول العشوائي ذات التوجيه غير المحدود مكافئة لآلة تورينج.

نقدم هنا شرحًا أكثر تفصيلًا. نبدأ بتصميم نموذجنا بثلاثة سجلات محجوزة هي "E" و"P" و"N"، بالإضافة إلى مجموعة غير محدودة من السجلات 1، 2، ...، n إلى اليمين. تُعتبر السجلات 1، 2، ...، n بمثابة "مربعات الشريط". يشير السجل "N" إلى "المربع الممسوح ضوئيًا" الذي يراقبه "الرأس" حاليًا. يمكن اعتبار "الرأس" في وضع القفزة الشرطية - لاحظ أنه يستخدم العنونة غير المباشرة (انظر Elgot-Robinson، صفحة 398). عند إنقاص أو زيادة قيمة "N"، سيتحرك الرأس (الظاهري) "يسارًا" أو "يمينًا" على طول المربعات. سننقل محتويات "E"=0 أو "P"=1 إلى "المربع الممسوح ضوئيًا" الذي يشير إليه N، باستخدام CPY غير المباشر.

إن حقيقة أن شريطنا ينتهي من اليسار تمثل لنا مشكلة بسيطة: كلما حدث LEFT، سيتعين على تعليماتنا اختبار ما إذا كانت محتويات "N" تساوي صفرًا أم لا؛ إذا كان الأمر كذلك، فيجب علينا ترك عددها عند "0" (هذا هو خيارنا كمصممين - على سبيل المثال، قد نجعل الآلة / النموذج "يطلق حدثًا" من اختيارنا).

مجموعة التعليمات 1 (المُعززة): { INC (N), DEC (N), CLR (N), CPY (d, r _s ,i, N), JZ ( i, r, z ), HALT }

يُعرّف الجدول التالي تعليمات ما بعد تورينج بدلالة تعليمات ذاكرة الوصول العشوائي (RAM) المكافئة لها، ويُقدّم مثالاً على كيفية عملها. يُظهر الجدول الموقع (الظاهري) لرأس القراءة/الكتابة على طول شريط المسجلات r0-r5... مُظللاً.

ذاكري	ملصق:		هـ	P	شمال	r0	r1	r2	r3	r4	r5	إلخ.	الإجراءات المتعلقة بالسجلات	إجراء على سجل تعليمات آلة الحالة المحدودة IR

	يبدأ:		0	1	3				1	0

R	يمين:	شركة (N)	0	1	4				1	0			[N] +1 → N	[IR] +1 → IR

P	مطبعة:	CPY ( d, P, i, N )	0	1	4				1	1			[P]=1 → [N]=r4	[IR] +1 → IR

هـ	مسح:	CPY ( d, E, i, N )	0	1	4				1	0			[E]=0 → [N]=r4	[IR] +1 → IR

ل	غادر:	JZ ( i, N, end )	0	1	4				1	0			لا أحد	إذا كان N = r4] = 0، فإن "end" → IR، وإلا فإن [IR] + 1 → IR
		DEC ( N )	0	1	3				1	0			[N] -1 → N

J0 (توقف)	jump_if_blank:	JZ ( i, N, end )	0	1	3				1	0			لا أحد	إذا كان N = r3] = 0، فإن "end" → IR، وإلا فإن [IR] + 1 → IR

J1 (توقف)	jump_if_mark:	JZ ( i, N, halt )	0	1	3				1	0			N =r3] → A	إذا كان N = r3] = 0، فإن "end" → IR، وإلا فإن [IR] + 1 → IR
	نهاية	. . . إلخ.	0	1	3				1	0

	وقف:	ح	0	1	3				1	0			لا أحد	[IR] +1 → IR

مثال: يؤدي التوجيه غير المباشر المحدود إلى آلة لا تُكافئ آلة تورينج.

خلال هذا العرض التوضيحي، يجب أن نضع في اعتبارنا أن التعليمات الموجودة في جدول آلة الحالة المحدودة محدودة ، أي أنها محدودة :

"إلى جانب كونها مجرد مجموعة محدودة من القواعد التي تعطي تسلسلًا من العمليات لحل نوع معين من المشاكل، فإن الخوارزمية لها خمس سمات مهمة [النهائية، والتحديد، والمدخلات، والمخرجات، والفعالية]" (تمت إضافة الخط المائل، كنوت ص 4-7).

تكمن الصعوبة في أن السجلات لها "أسماء" صريحة (أرقام) ويجب على جهازنا استدعاء كل منها بالاسم من أجل "الوصول" إليها.

سنقوم بإنشاء CPY غير المباشر (i, q, d, φ) باستخدام عامل CASE. سيتم تحديد عنوان السجل المستهدف بواسطة محتويات السجل "q"؛ وبمجرد أن يحدد عامل CASE هذا الرقم، سيقوم CPY بإيداع محتويات السجل الذي يحمل هذا الرقم مباشرةً في السجل "φ". سنحتاج إلى سجل إضافي سنسميه "y" - وهو بمثابة عداد تصاعدي.

إذن، ما يلي هو في الواقع برهان عملي على إمكانية محاكاة CPY غير المباشر (i, q, d, φ) دون تغيير في تصميم عدادنا/نموذجنا. مع ذلك، تجدر الإشارة إلى أنه نظرًا لأن CPY غير المباشر هذا "محدود" بحجم/نطاق آلة الحالة المحدودة، فإن RASP الذي يستخدم CPY غير المباشر لا يمكنه حساب سوى الدوال التكرارية الأولية ، وليس المجموعة الكاملة من الدوال التكرارية mu .

تم شرح عامل CASE في كتاب كلين (1952) (ص 229) وفي كتاب بولوس-بورغيس-جيفري (2002) (ص 74)؛ ويؤكد المؤلفان الأخيران على فائدته. التعريف التالي هو تعريف كلين، ولكنه مُعدّل ليعكس بنية "IF-THEN-ELSE" المألوفة.

يقوم عامل CASE بإرجاع عدد طبيعي إلى φ اعتمادًا على الحالة التي يتم استيفاؤها، بدءًا من الحالة 0 وصولًا إلى الحالة الأخيرة؛ إذا لم يتم استيفاء أي حالة، فسيتم إرجاع العدد المسمى "default" (المعروف أيضًا باسم "woops") إلى φ (حيث يشير x إلى مجموعة مختارة من المعلمات، على سبيل المثال السجل q والسلسلة r0، ... rlast)):

التعريف حسب الحالات φ ( x , y ):

الحالة 0: إذا كانت Q ₀ ( x , y) صحيحة، فإن φ ₀ ( x , y) وإلا
الحالة 1: إذا كانت Q1 ₍ x , y) صحيحة، فإن φ1 ₍ x , y) صحيحة أيضًا، وإلا
الحالات من 2 إلى الحالة قبل الأخيرة: إلخ. . . . . . . . . . وإلا
case_last: إذا كانت Q _last ( x , y) صحيحة، فإن φ _last ( x , y) وإلا
الوضع الافتراضي: نفّذ φ _{الوضع الافتراضي} ( س ، ص)

يشترط كلين أن تكون "المسندات" Q _n التي يتم إجراء الاختبار فيها جميعها متنافية بشكل متبادل - "المسندات" هي وظائف تنتج فقط { صحيح، خطأ } للإخراج؛ يضيف Boolos-Burgess-Jeffrey شرط أن تكون الحالات "شاملة".

نبدأ برقم في المسجل q يمثل عنوان المسجل الهدف. ولكن ما هو هذا الرقم؟ ستختبره "الشروط" لمعرفة ذلك، تجربة تلو الأخرى: JE (q, y, z) متبوعة بـ INC (y). بمجرد تحديد الرقم بشكل صريح، يقوم عامل CASE بنسخ محتويات هذا المسجل مباشرةً إلى φ.

التعريف حسب الحالات CPY (i، q، d، φ) = _def φ (q، r0، ...، rlast، y) =

الحالة 0: إذا كان CLR (y)، [q] - [y]=0، فقم بتنفيذ CPY ( r0, φ )، ثم J (خروج) وإلا
الحالة 1: إذا كانت قيمة y تساوي 1، فإن q = y = 1، ثم CPY(r1, φ)، J(خروج)؛ وإلا
من الحالة ٢ إلى الحالة ن: إذا... إذن... وإلا
case_n: IF INC (y), [q] = [y]=n THEN CPY ( rn, φ ), J (exit) ELSE
من الحالة رقم n+1 إلى الحالة الأخيرة: إذا... ثم... وإلا
case_last: إذا كان INC (y)، [q] = [y]="last" ثم CPY ( rlast, φ )، J (خروج) وإلا
الوضع الافتراضي: خطأ

الحالة 0 (الخطوة الأساسية للتكرار على y) تبدو كالتالي:

الحالة_0 :

CLR ( y ) ; ضبط السجل y = 0
JE ( q, y, _φ0 )
J ( الحالة 1 )

_φ0: CPY ( r0, φ )
J ( مخرج )

الحالة 1: إلخ.

تبدو الحالة رقم n (خطوة الاستقراء) على النحو التالي؛ تذكر أن كل حالة من حالات "n" و "n+1" و ... و "last" يجب أن تكون عددًا طبيعيًا صريحًا:

case_n :

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

_φn: CPY ( rn, φ )
J ( مخرج )

الحالة__ن+1: إلخ.

يُوقف Case_last عملية الاستقراء ويُقيّد عامل CASE (وبالتالي يُقيّد عامل "النسخ غير المباشر"):

case_last :

INC ( y )
JE ( q, y, _φlast )
J ( يا إلهي )

_φlast : CPY ( rlast, φ )
J ( مخرج )

عفواً: كيف نتعامل مع محاولة الخروج عن حدود الملعب؟
مخرج: إلخ.

لو كان بإمكان CASE الاستمرار إلى ما لا نهاية، لكان عامل mu . لكنه لا يستطيع ذلك - فقد وصل "سجل الحالة" الخاص بآلة الحالة المحدودة إلى الحد الأقصى لعدده (على سبيل المثال 65365 = 11111111,11111111 ₂ ) أو نفدت تعليمات جدوله؛ فهو آلة محدودة ، في نهاية المطاف.

أمثلة على النماذج

نموذج التسجيل إلى التسجيل ("القراءة والتعديل والكتابة") لكوك وريكهاو (1973)

إن نموذج Cook and Rechkow الشائع يشبه إلى حد ما نموذج Malzek ذو السجل الثلاثي (المكتوب باستخدام رموز Knuth - لم تكن التعليمات الأصلية تحتوي على أي رموز باستثناء TRA، Read، Print).

LOAD ( C, r_d ) ; C → r_d، C هو أي عدد صحيح

مثال: LOAD ( 0, 5 )سيتم مسح السجل 5.

ADD ( r_s1, r_s2, r_d ) ; [r_s1] + [r_s2] → r_d، يمكن أن تكون السجلات متطابقة أو مختلفة؛

مثال: ADD ( A, A, A )سيؤدي ذلك إلى مضاعفة محتويات السجل A.

SUB ( r_s1, r_s2, r_d ) ; [r_s1] - [r_s2] → r_dقد تكون السجلات متطابقة أو مختلفة:

مثال: SUB ( 3, 3, 3 )سيتم مسح السجل رقم 3.

COPY ( i, r_p, d, r_d ) ; [[r_p] ] → r_d، انسخ محتويات سجل المصدر المشار إليه بواسطة سجل المؤشر r _p بشكل غير مباشر إلى سجل الوجهة.
COPY ( d, r_s, i, r_p ) ; [r_s] → [r_p]. انسخ محتويات سجل المصدر r _s إلى سجل الوجهة الذي يشير إليه سجل المؤشر r _p .
JNZ ( r, I_z ) ;قفزة مشروطة إذا كانت قيمة [r] موجبة؛ أي إذا كانت [r] > 0، فانتقل إلى التعليمة z، وإلا فاستمر في التسلسل (يُطلق كوك وريكهاو على هذا اسم: "نقل التحكم إلى السطر m إذا كانت Xj > 0").
READ ( r_d ) ;انسخ "المدخلات" إلى سجل الوجهة r _d
PRINT ( r_s ) ;انسخ محتويات سجل المصدر r _s إلى "المخرجات".

ذاكرة الوصول العشوائي (RAM0) وذاكرة الوصول العشوائي (RAM1) لشونهاج (1980)

يصف شونهاج (1980) نموذجًا بدائيًا للغاية ومجزأً تم اختياره لإثبات تكافؤ نموذج آلة المؤشر SMM الخاص به :

"من أجل تجنب أي عنونة صريحة، يحتوي RAM0 على مُراكم بمحتويات z وسجل عنوان إضافي بمحتويات حالية n (في البداية 0)" (ص 494)

نموذج RAM1 : يوضح شونهاج كيف يمكن استخدام تصميمه لتشكيل الشكل الأكثر شيوعًا وقابلية للاستخدام لذاكرة الوصول العشوائي "الخالدة" (باستخدام الرموز التذكيرية لهذه المقالة):

LDA k ; k --> A ، k ثابت، وهو رقم صريح مثل "47"
LDA ( d, r ) ; [r] → A ;تحميل A مباشرة
LDA ( i, r ) ; [[r]] → A ;تحميل A بشكل غير مباشر
STA ( d, r ) ; [A] → r ;تخزين A مباشرة
STA ( i, r ) ; [A] → [r] ;تخزين A بشكل غير مباشر
JEA ( r, z ) ; IF [A] = [r] then I_z else continue
INCA ; [A] + 1 --> A

نموذج RAM0 : يحتوي جهاز RAM0 الخاص بشونهاج على 6 تعليمات يُشار إليها بحرف واحد (يبدو أن التعليمة السادسة "C xxx" تتضمن "تجاوز المعامل التالي"). وقد خصص شونهاج للمراكم بالحرف "z"، وللمُجمِّع بالحرف "n"، وهكذا. وبدلاً من رموز شونهاج، سنستخدم الرموز المذكورة أعلاه.

(Z), CLRA: 0 → A
(A), INCA: [A] +1 → A
(N), CPYAN: [A] → N
(A), LDAA: [[A]] → A يشير محتوى A إلى عنوان السجل؛ ضع محتويات السجل في A
(S), STAN: [A] → [N] يشير محتوى N إلى عنوان السجل؛ ضع محتوى A في السجل الذي يشير إليه N
(C), JAZ ( z ): [A] = 0 then go to I_z; غامض في معاملته

يأتي التوجيه غير المباشر (1) من CPYAN (نسخ/نقل المحتويات من A إلى N) الذي يعمل مع store_A_via_N STAN، ومن (2) تعليمات التوجيه غير المباشر الخاصة .LDAA ( [[A]] → [A] )

الحواشي

محدود مقابل غير محدود

إنّ حقيقة تعريفية مفادها أن أي نوع من آلات العد التي لا تحتوي على سجل عنوان غير محدود يجب أن يحدد سجلًا باسم "r" تشير إلى أن النموذج يتطلب أن يكون "r" محدودًا ، على الرغم من أنه "غير محدود" بمعنى أن النموذج لا يفرض حدًا أقصى لعدد السجلات اللازمة لأداء وظيفته. على سبيل المثال، لا نشترط أن يكون r < 83,617,563,821,029,283,746 ولا r < 2^1,000,001، وهكذا.

وبالتالي، يمكن لنموذجنا "توسيع" عدد السجلات، إذا لزم الأمر لإجراء عملية حسابية معينة. ومع ذلك، هذا يعني أن أي عدد يتوسع إليه النموذج يجب أن يكون محدودًا - يجب أن يكون قابلاً للفهرسة باستخدام عدد طبيعي: ω ليس خيارًا متاحًا .

يمكننا تجاوز هذا القيد من خلال توفير سجل غير محدود لتوفير عنوان السجل الذي يحدد عنوانًا غير مباشر.

انظر أيضاً

روابط خارجية

مراجع

^ إردي ، جيرجو (6 سبتمبر 2010). "من آلات التسجيل إلى Brainfuck، الجزء الأول" . تم الاسترجاع بتاريخ 2024-02-07 .

باستثناءات قليلة، فإن هذه المراجع هي نفسها الموجودة في آلة التسجيل .

- جولدستين، هيرمان هـ.، وفون نيومان، جون، "تخطيط وتشفير مسائل جهاز حاسوب إلكتروني"، تقرير رقم 1947، معهد الدراسات المتقدمة ، برينستون. أعيد طبعه في الصفحات 92-119 في كتاب بيل، سي. جوردون ونيويل، ألين (1971)، هياكل الحاسوب: قراءات وأمثلة ، شركة ماكجرو هيل للنشر، نيويورك. ISBN 0-07-004357-4}.
جورج بولوس ، جون ب. بورغيس ، ريتشارد جيفري (2002)، الحوسبة والمنطق: الطبعة الرابعة ، مطبعة جامعة كامبريدج، كامبريدج، إنجلترا. خضع نص بولوس-جيفري الأصلي لمراجعة شاملة من قِبل بورغيس، وهو أكثر تقدمًا من مجرد كتاب تمهيدي. تم تطوير نموذج "آلة المعداد" بشكل موسع في الفصل الخامس " حوسبة المعداد " ؛ وهو أحد ثلاثة نماذج تمت معالجتها ومقارنتها بشكل موسع - آلة تورينج (لا تزال في شكل بولوس الأصلي المكون من 4 عناصر) والتكرار هما النموذجان الآخران.
آرثر بيركس ، وهيرمان غولدستاين ، وجون فون نيومان (1946)، مناقشة تمهيدية للتصميم المنطقي لجهاز حاسوب إلكتروني ، أعيد طبعه في الصفحات 92 وما بعدها في كتاب غوردون بيل وآلان نيويل (1971)، هياكل الحاسوب: قراءات وأمثلة ، شركة ماكجرو هيل للنشر، نيويورك. ISBN 0-07-004357-4 .
ستيفن أ. كوك وروبرت أ. ريكهاو (1973)، آلات الوصول العشوائي المحدودة زمنيا ، مجلة علوم أنظمة الحاسوب 7(4):354-375.
مارتن ديفيس (1958)، قابلية الحساب وعدم قابلية الحل ، شركة ماكجرو هيل للنشر، نيويورك.
كالفن إلجوت وأبراهام روبنسون (1964)، آلات البرامج المخزنة ذات الوصول العشوائي، نهج للغات البرمجة ، مجلة رابطة آلات الحوسبة، المجلد 11، العدد 4 (أكتوبر 1964)، ص 365-399.
J. Hartmanis (1971), "التعقيد الحسابي لآلات البرامج المخزنة ذات الوصول العشوائي"، نظرية الأنظمة الرياضية 5، 3 (1971) ص 232-245.
جون هوبكروفت ، جيفري أولمان (1979). مقدمة في نظرية الأوتوماتا واللغات والحوسبة ، الطبعة الأولى، ريدينغ، ماساتشوستس: أديسون-ويسلي. ISBN 0-201-02988-Xكتاب صعب يتمحور حول قضايا التفسير الآلي لـ "اللغات"، واكتمال NP، وما إلى ذلك.
ستيفن كلين (1952)، مقدمة في ما وراء الرياضيات ، دار نشر نورث هولاند، أمستردام، هولندا. رقم ISBN 0-7204-2103-9.
دونالد كنوث (1968)، فن برمجة الحاسوب ، الطبعة الثانية 1973، أديسون-ويسلي، ريدينغ، ماساتشوستس. انظر الصفحات 462-463 حيث يُعرّف "نوعًا جديدًا من الآلات المجردة أو "الأوتوماتون" التي تتعامل مع الهياكل المرتبطة".
يواكيم لامبيك (1961، تاريخ الاستلام 15 يونيو 1961)، كيفية برمجة عداد لانهائي ، النشرة الرياضية، المجلد 4، العدد 3، سبتمبر 1961، الصفحات 295-302. في الملحق الثاني، يقترح لامبيك "تعريفًا رسميًا لـ'البرنامج'". ويشير إلى ميلزاك (1961) وكلين (1952)، مقدمة في ما وراء الرياضيات .
ز. أ. ميلزاك (1961، تاريخ الاستلام 15 مايو 1961)، مدخل حسابي غير رسمي للحوسبة والحساب ، النشرة الرياضية الكندية ، المجلد 4، العدد 3، سبتمبر 1961، الصفحات 279-293. لم يذكر ميلزاك أي مراجع، لكنه أقرّ بـ "فائدة المحادثات مع الدكاترة ر. هامينغ، ود. ماكلروي، وف. فيسوتس من مختبرات بيل للهواتف، ومع الدكتور هـ. وانغ من جامعة أكسفورد".
مارفن مينسكي (1961). "عدم قابلية حل مسألة بوست المتعلقة بـ'الوسم' بشكل متكرر ومواضيع أخرى في نظرية آلات تورينج". حوليات الرياضيات . 74 (3). حوليات الرياضيات، المجلد 74، العدد 3: 437-455 . doi : 10.2307/1970290 . JSTOR 1970290 .
مارفن مينسكي (1967). الحوسبة: الآلات المحدودة واللامحدودة ( الطبعة الأولى). إنجلوود كليفس، نيوجيرسي: برنتيس هول، إنك.انظر تحديدًا الفصل 11: نماذج مشابهة للحواسيب الرقمية ، والفصل 14: أسس بسيطة جدًا للحوسبة . في الفصل الأول، يُعرّف "آلات البرمجة"، وفي الفصل الثاني، يناقش "آلات البرمجة الشاملة ذات سجلين" و"...ذات سجل واحد"، إلخ.
حصل جون سي. شيبردسون وإتش إي ستورجيس (1961) على جائزة في ديسمبر 1961 عن بحثهما المنشور في مجلة جمعية آلات الحوسبة (JACM) 10:217-255، 1963. يُعد هذا البحث مرجعًا قيّمًا للغاية. وفي الملحق (أ)، يستشهد المؤلفان بأربعة مراجع أخرى فيما يتعلق بـ "الحد الأدنى من التعليمات المستخدمة في 4.1: مقارنة مع أنظمة مماثلة".

كافينجست، هاينز، Eine Abstrakte Programmgesteuerte Rechenmaschine' ، Zeitschrift fur mathematische Logik und Grundlagen der Mathematik: 5 (1959)، 366-379.
إرشوف، أ.ب. حول خوارزميات المؤثرات ، (بالروسية) دوك. أكاد. ناوك 122 (1958)، 967-970. الترجمة الإنجليزية، أوتومات. إكسبريس 1 (1959)، 20-23.
بيتر، روزا Graphschemata والوظائف المتكررة ، جدلية 12 (1958)، 373.
هيرميس، هانز Die Universalität Programmgesteuerter Rechenmaschinen. الرياضيات-فيزياء. سيمستربريخت (غوتنغن) 4 (1954)، 42-53.

أرنولد شونهاج (1980)، آلات تعديل التخزين ، جمعية الرياضيات الصناعية والتطبيقية، مجلة SIAM للحوسبة، المجلد 9، العدد 3، أغسطس 1980. حيث يُظهر شونهاج تكافؤ آلة تعديل التخزين الخاصة به مع "آلة الوصول العشوائي" (RAM) اللاحقة، إلخ. آلات تعديل التخزين ، في علوم الحاسوب النظرية (1979)، الصفحات 36-37
بيتر فان إمده بواس ، "نماذج ومحاكاة الآلات"، الصفحات 3-66، في: جان فان ليوين (محرر)، دليل علوم الحاسوب النظرية. المجلد أ: الخوارزميات والتعقيد ، مطبعة معهد ماساتشوستس للتكنولوجيا/إلسيفير، 1990. ISBN 0-444-88071-2(المجلد أ). QA 76.H279 1990. يظهر تناول فان إمده بواس لموضوع SMMs في الصفحات 32-35. يوضح هذا التناول ما ورد في دراسة شونهاج 1980 ، إذ يتبعه عن كثب مع توسيع طفيف. قد يكون كلا المرجعين ضروريًا لفهمٍ فعّال.
هاو وانغ (1957)، صيغة معدلة لنظرية تورينغ لآلات الحوسبة ، مجلة جمعية آلات الحوسبة (JACM) 4؛ 63-92. عُرضت في اجتماع الجمعية، 23-25 يونيو 1954.

[1] إردي ، جيرجو (6 سبتمبر 2010). "من آلات التسجيل إلى Brainfuck، الجزء الأول" . تم الاسترجاع بتاريخ 2024-02-07 .

[ 1 ]