ماكينة تسجيل

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

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

يوجد على الأقل أربع فئات فرعية موجودة في الأدبيات . بترتيب تصاعدي للتعقيد:

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

أي نموذج آلي مسجل محدد بشكل صحيح هو نموذج تورينج كامل . تعتمد سرعة الحوسبة بشكل كبير على تفاصيل النموذج.

في علوم الكمبيوتر العملية، يتم استخدام مفهوم مرتبط يُعرف باسم الآلة الافتراضية أحيانًا لتقليل الاعتماد على بنيات الآلة الأساسية. تُستخدم هذه الآلات الافتراضية أيضًا في البيئات التعليمية. في الكتب المدرسية، يُستخدم مصطلح "آلة التسجيل" أحيانًا بالتبادل لوصف الآلة الافتراضية. ^[1]

تتكون آلة التسجيل من:

1. عدد غير محدود من السجلات المميزة المنفصلة غير المحدودة غير المحدودة في المدى (السعة) : مجموعة محدودة (أو غير محدودة في بعض النماذج) من السجلات، كل منها يعتبر ذا مدى غير محدود وكل منها يحمل عددًا صحيحًا واحدًا غير سلبي (0، 1، 2، ...). ^{[nb 1]} قد تقوم السجلات بعملياتها الحسابية الخاصة، أو قد يكون هناك سجل أو أكثر خاص يقوم بالعمليات الحسابية (على سبيل المثال "مجمع" و/أو "سجل عناوين"). انظر أيضًا آلة الوصول العشوائي .${\displaystyle r_{0}\ldots r_{n}}$
2. عدادات أو علامات العد : ^{[nb 2]} أشياء منفصلة لا يمكن تمييزها أو علامات من نوع واحد فقط مناسبة للنموذج. في نموذج آلة العد الأكثر اختزالًا ، لكل عملية حسابية، تتم إضافة أو إزالة كائن/علامة واحدة فقط من موقعها/شريطها. في بعض نماذج آلة العد (على سبيل المثال Melzak، ^[2] Minsky ^[3] ) ومعظم نماذج RAM وRASP، يمكن إضافة أو إزالة أكثر من كائن/علامة في عملية واحدة باستخدام "الجمع" وعادةً "الطرح"؛ وأحيانًا باستخدام "الضرب" و/أو "القسمة". تحتوي بعض النماذج على عمليات تحكم مثل "النسخ" (أو بدلاً من ذلك: "النقل"، "التحميل"، "التخزين") التي تنقل "مجموعات" من الأشياء/العلامات من سجل إلى سجل في إجراء واحد.
3. مجموعة محدودة من التعليمات : تميل التعليمات إلى الانقسام إلى فئتين: الحساب والتحكم. يتم استخلاص التعليمات من الفئتين لتشكيل "مجموعات تعليمات"، بحيث يجب أن تسمح مجموعة التعليمات للنموذج بأن يكون مكافئًا لـ Turing (يجب أن يكون قادرًا على حساب أي دالة تكرارية جزئية ).
   1. الحساب : يمكن أن تعمل التعليمات الحسابية على جميع السجلات أو على سجل محدد، مثل المُراكم. وعادةً ما يتم اختيارها من المجموعات التالية، على الرغم من وجود استثناءات: آلة العداد: {زيادة (r)، نقصان (r)، مسح إلى الصفر (r)} ذاكرة الوصول العشوائي المخفضة، RASP: {زيادة (r)، نقصان (r)، مسح إلى الصفر (r)، تحميل ثابت فوري k، إضافة ( )، طرح صحيح ( )، زيادة المُراكم، نقصان المُراكم، مسح المُراكم، إضافة محتويات السجل إلى المُراكم، طرح صحيح لمحتويات السجل من المُراكم} ذاكرة الوصول العشوائي المُعززة، RASP: تتضمن جميع التعليمات المخفضة بالإضافة إلى: {ضرب، قسمة، عمليات مختلفة على مستوى البتات المنطقية (تحويل إلى اليسار، اختبار البت، إلخ.)}.${\displaystyle r_{1},r_{2}}$${\displaystyle r_{1},r_{2}}$${\displaystyle r}$${\displaystyle r}$
   2. التحكم : نماذج آلات العداد: تتضمن اختياريًا {نسخ ( )}. نماذج RAM وRASP: تتضمن معظمها {نسخ ( )}، أو {تحميل المُجمع من ، تخزين المُجمع في ، تحميل المُجمع بثابت فوري}. جميع النماذج: تتضمن على الأقل "قفزة" شرطية واحدة (فرع، انتقال إلى) بعد اختبار السجل، مثل {قفزة إذا كانت صفرًا، قفزة إذا لم تكن صفرًا (أي، قفزة إذا كانت موجبة)، قفزة إذا كانت مساوية، قفزة إذا لم تكن مساوية}. تتضمن جميع النماذج اختياريًا: {قفزة برنامج غير مشروطة (انتقال إلى)}.${\displaystyle r_{1},r_{2}}$${\displaystyle r_{1},r_{2}}$${\displaystyle r}$${\displaystyle r}$
   3. طريقة معالجة السجل :
      • آلة العداد: لا توجد معالجة غير مباشرة، والمتعاملات الفورية ممكنة في النماذج شديدة الذرات
      • RAM وRASP: معالجة غير مباشرة متاحة، والمتعاملات الفورية نموذجية
   4. الإدخال والإخراج : اختياري في جميع الموديلات
4. سجل الحالة : يخزن سجل التعليمات (IR) الخاص، والذي يختلف عن السجلات المذكورة سابقًا، التعليمات الحالية التي سيتم تنفيذها مع عنوانها في جدول التعليمات. يقع هذا السجل، مع الجدول المرتبط به، داخل آلة الحالة المحدودة. لا يمكن الوصول إلى سجل التعليمات (IR) في جميع النماذج. في حالة RAM وRASP، لتحديد "عنوان" السجل، يمكن للنموذج اختيار إما (i) العنوان المحدد بواسطة الجدول والمخزن مؤقتًا في سجل التعليمات (IR) للتوجيه المباشر، أو (ii) محتويات السجل المحدد بواسطة التعليمات في سجل التعليمات (IR) للتوجيه غير المباشر. من المهم ملاحظة أن سجل التعليمات (IR) ليس "عداد البرنامج" (PC) لـ RASP (أو الكمبيوتر التقليدي). يعد سجل التعليمات (PC) مجرد سجل آخر يشبه المجمع ولكنه مخصص خصيصًا لحمل عدد التعليمات الحالية المستندة إلى السجل في RASP. وبالتالي، يمتلك RASP سجلين "تعليمات/برامج": (i) سجل تعليمات IR (آلة الحالة المحدودة)، و(ii) PC ​​(عداد البرامج) للبرنامج المخزن في السجلات. بالإضافة إلى ذلك، وبصرف النظر عن PC، قد يخصص RASP أيضًا سجلًا آخر لـ "سجل تعليمات البرنامج" (يشار إليه بأسماء مختلفة مثل "PIR" و"IR" و"PR" وما إلى ذلك).
5. قائمة التعليمات المُسمَّاة، عادةً بالترتيب المتسلسل : قائمة محدودة من التعليمات . في حالة آلة العداد وآلة الوصول العشوائي (RAM) وآلة المؤشر، يكون مخزن التعليمات في "الجدول" الخاص بآلة الحالة المحدودة، وبالتالي فإن هذه النماذج هي أمثلة على بنية هارفارد. في حالة RASP، يكون مخزن البرامج في السجلات، وبالتالي فإن هذا مثال على بنية فون نيومان. انظر أيضًا آلة الوصول العشوائي وآلة البرامج المخزنة ذات الوصول العشوائي . عادةً ما يتم سرد التعليمات بالترتيب المتسلسل، مثل برامج الكمبيوتر ، ما لم تنجح القفزة. في هذه الحالة، يستمر التسلسل الافتراضي بالترتيب العددي. الاستثناء من ذلك هو نماذج آلة العداد ^{[4] [3]} - كل تعليمة لها معرف تعليمة "تالية" واحد على الأقل "z"، والفرع الشرطي له معرفان. ${\displaystyle I_{1}\ldots I_{m}}$
   
   • لاحظ أيضًا أن نموذج العداد يجمع بين تعليماتين، JZ ثم DEC: على سبيل المثال { INC ( r, z )، JZDEC ( r, z _true ، z _false ) }.

راجع صيغة مكارثي لمزيد من المعلومات حول التعبير الشرطي "IF r=0 THEN z _true ELSE z _false " ^[5]

ظهرت في أوائل الخمسينيات من القرن العشرين اتجاهان. الأول هو وصف الكمبيوتر بأنه آلة تورينج. والثاني هو تعريف نماذج شبيهة بالكمبيوتر - نماذج ذات تسلسلات تعليمات متسلسلة وقفزات شرطية - بقوة آلة تورينج، وهو ما يسمى بمعادلة تورينج. تم تنفيذ الحاجة إلى هذا العمل في سياق مشكلتين "صعبتين": مشكلة الكلمات غير القابلة للحل التي طرحها إميل بوست ^[6] - مشكلة "العلامة" الخاصة به - والمشكلة "الصعبة" للغاية لمشكلات هيلبرت - السؤال العاشر حول معادلات ديوفانتين . كان الباحثون يبحثون عن نماذج مكافئة لتورينج أقل "منطقية" في طبيعتها وأكثر "حسابية". ^{[2] : 281  [7] : 218}

نشأت الخطوة الأولى نحو توصيف أجهزة الكمبيوتر ^{[nb 3]} مع هانز هيرميس (1954)، ^[8] روزا بيتر (1958)، ^[9] وهينز كافينجست (1959)، ^[10] والخطوة الثانية مع هاو وانج (1954، ^[11] 1957 ^[12] )، وكما هو مذكور أعلاه، تقدم على يد زدزسلاف ألكسندر ميلزاك (1961)، ^[2] يواكيم لامبيك (1961) ^[4] ومارفين مينسكي (1961، ^[3] 1967 ^[13] ).

وقد أدرج يوري ماتياسيفيتش الأسماء الخمسة الأخيرة صراحة بهذا الترتيب . ثم تابع:

" تعتبر آلات التسجيل [يستخدم بعض المؤلفين "آلة التسجيل" مرادفة لـ "آلة مضادة"] مناسبة بشكل خاص لبناء معادلات ديوفانتين. مثل آلات تورينج، تحتوي على تعليمات بدائية للغاية، بالإضافة إلى أنها تتعامل مع الأرقام ". ^[14]

وقد اكتشف لامبيك وميلزاك ومينسكي وشيبردسون وستورجيس بشكل مستقل نفس الفكرة في نفس الوقت. انظر الملاحظة الخاصة بالأولوية أدناه.

يبدأ التاريخ مع نموذج وانج.

كان عمل وانج مستمدًا من ورقة إميل بوست (1936) ^[6] ، وقاد وانج إلى تعريفه لآلة وانج B الخاصة به - وهي نموذج حسابي لآلة ما بعد تورينج مكون من رمزين مع أربع تعليمات ذرية فقط:

{ يسار، يمين، طباعة، القفز إذا تم وضع علامة على التعليمات }

إلى هذه الأربعة أضاف كل من وانج (1954، ^[11] 1957 ^[12] ) ثم سي واي لي (1961) ^[15] تعليمة أخرى من مجموعة Post {ERASE}، ثم القفزة غير المشروطة لمجموعة Post {JUMP_to_ instruction_z} (أو لتسهيل الأمور، القفزة الشرطية JUMP_IF_blank_to_instruction_z، أو كليهما. أطلق لي على هذا نموذج "آلة W":

{ يسار، يمين، طباعة، مسح، JUMP_if_marked، [ربما JUMP أو JUMP_IF_blank] }

وأعرب وانج عن أمله في أن يكون نموذجه بمثابة "تقارب" ^بين نظرية آلات تورينج والعالم العملي للكمبيوتر.

كان عمل وانج مؤثرًا للغاية. نجده مذكورًا في أعمال مينسكي (1961) ^[3] و (1967)، ^[13] وميلزاك (1961)، ^[2] وشيبردسون وستورجيس (1963). ^[7] في الواقع، لاحظ شيبردسون وستورجيس (1963) أن:

" لقد حاولنا أن نخطو خطوة أبعد نحو "التقارب" بين الجوانب العملية والنظرية للحوسبة التي اقترحها وانج، " ^{[7] : 218}

وفي نهاية المطاف، قام مارتن ديفيس بتطوير هذا النموذج إلى آلة ما بعد تورينج (ذات الرمزين).

الصعوبات التي تواجه نموذج وانج/ما بعد تورينج :

ولكن كانت هناك مشكلة: فنموذج وانج (التعليمات الستة لآلة ما بعد تورينج ذات التعليمات السبع) كان لا يزال جهازًا شبيهًا بتورينج ذي الشريط الواحد، مهما كان تدفق التعليمات المتتالية للبرنامج رائعًا. وقد لاحظ كل من ميلزاك (1961) ^[2] وشيبردسون وستورجيس (1963) ^[7] هذا (في سياق بعض الأدلة والتحقيقات):

" ... تتمتع آلة تورينج بقدر معين من التعتيم... آلة تورينج بطيئة في التشغيل (الافتراضي)، وعادة ما تكون معقدة. وهذا يجعل تصميمها صعبًا إلى حد ما، بل ويجعل من الصعب التحقيق في أمور مثل الوقت أو تحسين التخزين أو المقارنة بين كفاءة خوارزميتين. ^{[2] : 281} "... على الرغم من أنها ليست صعبة... فإن البراهين معقدة ومملة لمتابعتها لسببين: (1) آلة تورينج لها رأس فقط، لذا فإن المرء ملزم بتقسيم الحساب إلى خطوات صغيرة جدًا من العمليات على رقم واحد. (2) لديها شريط واحد فقط، لذا يتعين على المرء أن يبذل بعض الجهد للعثور على الرقم الذي يرغب المرء في العمل عليه وإبقائه منفصلاً عن الأرقام الأخرى " ^{[7] : 218}

في الواقع، وكما تظهر الأمثلة في آلة تورينج ، وآلة ما بعد تورينج، والوظائف الجزئية ، فإن العمل يمكن أن يكون "معقدًا".

This section's tone or style may not reflect the encyclopedic tone used on Wikipedia. See Wikipedia's guide to writing better articles for suggestions. (January 2024) (Learn how and when to remove this message)

تؤدي الفكرة الأولية إلى "قص الشريط" بحيث يكون كل شريط طويلًا إلى ما لا نهاية (لاستيعاب أي حجم صحيح) ولكن نهايته يسارية. تسمى هذه الأشرطة الثلاثة "أشرطة ما بعد تورينج (أي مثل وانج)". تتحرك الرؤوس الفردية إلى اليسار (للتناقص) وإلى اليمين (للزيادة). بمعنى ما، تشير الرؤوس إلى "قمة كومة" العلامات المتسلسلة. أو في مينسكي (1961) ^[3] وهوبكروفت وأولمان (1979)، ^{[16] : 171ff} يكون الشريط فارغًا دائمًا باستثناء علامة في الطرف الأيسر - لا يتم طباعة الرأس أو مسحه في أي وقت.

يجب توخي الحذر عند كتابة التعليمات بحيث يحدث اختبار للصفر والقفزة قبل التناقص، وإلا فإن الآلة سوف "تسقط من النهاية" أو "تصطدم بالنهاية" - مما يؤدي إلى إنشاء مثيل لوظيفة جزئية .

أثبت مينسكي (1961) ^[3] وشيبردسون-ستورجيس (1963) ^[7] أن عددًا قليلًا فقط من الأشرطة - شريط واحد فقط - لا يزال يسمح للآلة بأن تكون مكافئة لتورنج إذا تم تمثيل البيانات الموجودة على الشريط كرقم جودل (أو أي رقم آخر فريد قابل للترميز والفك)؛ سيتطور هذا الرقم مع تقدم الحساب. في إصدار الشريط الواحد مع ترميز رقم جودل ، يجب أن تكون آلة العداد قادرة على (أ) ضرب رقم جودل بثابت (الأرقام "2" أو "3")، و (ب) القسمة على ثابت (الأرقام "2" أو "3") والقفز إذا كان الباقي صفرًا. يوضح مينسكي (1967) ^[13] أنه يمكن تخفيف الحاجة إلى مجموعة التعليمات الغريبة هذه إلى { INC (r)، JZDEC (r، z) } وتعليمات الراحة { CLR (r)، J (r) } إذا كان هناك شريطان متاحان. ومع ذلك، لا تزال هناك حاجة إلى عملية غودلية بسيطة. تظهر نتيجة مماثلة في Elgot–Robinson (1964) ^[17] فيما يتعلق بنموذج RASP الخاص بهم.

يختلف نموذج ميلزاك (1961) ^[2] بشكل كبير. فقد استخدم نموذجه الخاص، وقلب الأشرطة رأسياً، وأطلق عليها "ثقوباً في الأرض" ليتم ملؤها بـ "عدادات الحصى". وعلى عكس "الزيادة" و"النقصان" اللذين اقترحهما مينسكي، سمح ميلزاك بالطرح الصحيح لأي عدد من الحصى و"إضافة" أي عدد من الحصى.

لقد قام بتعريف التوجيه غير المباشر لنموذجه ^{[2] : 288} وقدم مثالين لاستخدامه؛ ^{[2] : 89} إن "دليله" ^{[2] : 290-292} على أن نموذجه معادل لتورينج غير دقيق لدرجة أن القارئ لا يستطيع أن يحدد ما إذا كان يقصد أن يكون التوجيه غير المباشر شرطًا للإثبات أم لا.

إن إرث نموذج ميلزاك هو تبسيط لامبيك وإعادة ظهور اتفاقياته التذكيرية في كوك وريكو 1973. ^[18]

قام لامبيك (1961) ^[4] بأخذ نموذج ميلزاك الثلاثي وتقليصه إلى التعليمات الأحادية - X+، X− إذا كان ذلك ممكنًا وإلا فاقفز - نفس التعليمات التي توصل إليها مينسكي (1961) ^{[3] .}

ومع ذلك، مثل نموذج مينسكي (1961) ^[3] ، فإن نموذج لامبيك ينفذ تعليماته بطريقة متسلسلة افتراضية - يحمل كل من X+ وX− معرف التعليمات التالية، كما يحمل X− أيضًا تعليمات الانتقال إلى إذا كان الاختبار الصفري ناجحًا.

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

ما لم تكن هناك مشكلة: إذا كانت هذه الآلة الشبيهة بالحاسوب فون نيومان مبنية على هيكل آلة العداد ، فلن تكون مكافئة لتورنج. لا يمكنها حساب كل ما يمكن حسابه. بطبيعته، يكون النموذج محدودًا بحجم تعليمات آلة الحالة المحدودة (جدًا) . ​​يمكن لآلة العداد القائمة على RASP حساب أي دالة تكرارية بدائية (مثل الضرب) ولكن ليس كل الدوال التكرارية المتعددة (مثل دالة أكرمان ).

قام إلجوت-روبنسون بدراسة إمكانية السماح لنموذج RASP الخاص بهم بـ"تعديل تعليمات برنامجه ذاتيًا". ^[17] كانت الفكرة قديمة، اقترحها بوركس-جولدستين-فون نيومان (1946-1947)، ^[19] وتُسمى أحيانًا "الانتقال المحسوب". يذكر ميلزاك (1961) ^[2] على وجه التحديد "الانتقال المحسوب" بالاسم ولكنه بدلاً من ذلك يوفر نموذجه مع عنونة غير مباشرة.

الانتقال المحسوب: برنامج RASP من التعليمات التي تعدل "عنوان الانتقال" في تعليمات برنامج الانتقال المشروط أو غير المشروط .

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

مثال: يمكن لآلة عداد مزودة بأربعة سجلات غير محدودة فقط أن تضرب أي رقمين (m، n) معًا لإنتاج p - وبالتالي تكون دالة تكرارية بدائية - بغض النظر عن حجم الأرقام m و n ؛ علاوة على ذلك، يلزم أقل من 20 تعليمة للقيام بذلك! على سبيل المثال { 1: CLR (p)، 2: JZ (m، done)، 3 external_loop: JZ (n، done)، 4: CPY (m، temp)، 5: inner_loop: JZ (m، external_loop)، 6: DEC (m)، 7: INC (p)، 8: J (inner_loop)، 9: external_loop: DEC (n)، 10 J (outer_loop)، HALT } ومع ذلك، مع وجود 4 سجلات فقط، فإن هذه الآلة ليست كبيرة بما يكفي لبناء RASP يمكنه تنفيذ خوارزمية الضرب كبرنامج . بغض النظر عن مدى ضخامة آلة الحالة المحدودة التي نبنيها، فسوف يكون هناك دائمًا برنامج (بما في ذلك معلماته) أكبر حجمًا. لذا، وفقًا للتعريف، لا يمكن أن تكون آلة البرنامج المحدودة التي لا تستخدم حيل الترميز غير المحدودة مثل أرقام جودل عالمية .

يشير مينسكي (1967) ^[13] إلى هذه القضية في تحقيقه في آلة عداد (يسميها "نماذج كمبيوتر مبرمجة") مزودة بالتعليمات {CLR (r)، وINC (r)، وRPT ("a" مضروبة في التعليمات m إلى n)}. إنه لا يخبرنا بكيفية إصلاح المشكلة، لكنه يلاحظ أن:

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

ولكن إلجوت وروبنسون حلا المشكلة: ^[17] حيث قاما بتوسيع نطاق P ₀ RASP الخاص بهما بمجموعة مفهرسة من التعليمات - وهو شكل أكثر تعقيدًا إلى حد ما (ولكن أكثر مرونة) من العنونة غير المباشرة. يقوم نموذج P' ₀ الخاص بهما بعنونة السجلات عن طريق إضافة محتويات السجل "الأساسي" (المحدد في التعليمات) إلى "الفهرس" المحدد صراحةً في التعليمات (أو العكس، عن طريق تبديل "الأساسي" و"الفهرس"). وبالتالي فإن تعليمات الفهرسة P' _{0 تحتوي على معلمة واحدة أكثر من تعليمات P 0} غير المفهرسة :

مثال: INC ( r _base , index )؛ سيكون العنوان الفعال هو [r _base ] + index، حيث يتم اشتقاق "index" العدد الطبيعي من تعليمات الآلة ذات الحالة المحدودة نفسها.

بحلول عام 1971، قام هارتمانيس بتبسيط الفهرسة إلى غير المباشرة لاستخدامها في نموذج RASP الخاص به. ^[20]

التوجيه غير المباشر: يزود سجل المؤشر آلة الحالة المحدودة بعنوان سجل الهدف المطلوب للتعليمات. وبعبارة أخرى: محتويات سجل المؤشر هي عنوان سجل "الهدف" الذي ستستخدمه التعليمات. إذا كان سجل المؤشر غير محدود، فإن ذاكرة الوصول العشوائي، وبرنامج RASP المناسب المبني على هيكلها، سيكونان مكافئين لـ Turing. يمكن أن يعمل سجل الهدف إما كسجل مصدر أو سجل وجهة، كما هو محدد في التعليمات.

لاحظ أن آلة الحالة المحدودة لا يتعين عليها تحديد عنوان سجل الهدف هذا صراحةً. فهي تقول لبقية الآلة: أحضر لي محتويات السجل الذي يشير إليه سجل المؤشر الخاص بي ثم قم بتنفيذ الأمر xyz معه. يجب أن تحدد صراحةً بالاسم، عبر تعليماتها، سجل المؤشر هذا (على سبيل المثال "N"، أو "72" أو "PC"، وما إلى ذلك) ولكن ليس من الضروري أن تعرف الرقم الذي يحتويه سجل المؤشر بالفعل (ربما 279,431).

يستشهد كوك وريكهو (1973) ^[18] بهارتمانيس (1971) ^[20] ويبسطان نموذجه إلى ما يسميانه آلة الوصول العشوائي (RAM - أي آلة ذات توجيه غير مباشر وهندسة هارفارد). بمعنى ما، نعود إلى ميلزاك (1961) ^[2] ولكن بنموذج أبسط كثيرًا من نموذج ميلزاك.

كان مينسكي يعمل في مختبر لينكولن التابع لمعهد ماساتشوستس للتكنولوجيا ونشر عمله هناك؛ وقد تم استلام ورقته للنشر في حوليات الرياضيات في 15 أغسطس 1960، ولكن لم يتم نشرها حتى نوفمبر 1961. ^[3] في حين حدث الاستلام قبل عام كامل من استلام ونشر عمل ميلزاك ^[2] ولامبيك ^[4] (تم استلامهما على التوالي في مايو و15 يونيو 1961، ونشرهما جنبًا إلى جنب في سبتمبر 1961). أن (أ) كلاهما كنديان ونُشرا في النشرة الرياضية الكندية ، (ب) لم يكن لدى أي منهما إشارة إلى عمل مينسكي لأنه لم يُنشر بعد في مجلة تمت مراجعتها من قبل الأقران، ولكن (ج) يشير ميلزاك إلى وانج، ويشير لامبيك إلى ميلزاك، مما يقود المرء إلى افتراض أن عملهما حدث في وقت واحد وبشكل مستقل.

حدث نفس الشيء تقريبًا لشيبردسون وستورجيس. ^[21] تم استلام ورقتهم في ديسمبر 1961 - بعد بضعة أشهر فقط من استلام عمل ميلزاك ولامبيك. مرة أخرى، لم يكن لديهم سوى القليل (شهر واحد على الأكثر) أو لم يكن لديهم أي فائدة من مراجعة عمل مينسكي. لقد حرصوا على ملاحظة في الحواشي أن أوراق إيرشوف، ^[22] وكافينجست ^[10] وبيتر ^[9] "ظهرت مؤخرًا" ^{[21] : 219} تم نشرها في وقت أبكر بكثير ولكنها ظهرت باللغة الألمانية في المجلات الألمانية لذا فإن قضايا إمكانية الوصول تطرح نفسها.

لم تظهر الورقة النهائية لشيبردسون وستورجيس في مجلة محكمة حتى عام 1963. ^[7] وكما لاحظوا في الملحق أ، فإن "أنظمة" كافينجست (1959)، ^[10] وإيرشوف (1958)، ^[22] وبيتر (1958) ^[9] كلها متشابهة جدًا مع النتائج التي تم الحصول عليها لاحقًا بحيث لا يمكن تمييزها بمجموعة مما يلي:

إنتاج 0 أي 0 → n

زيادة رقم أي n+1 → n

"أي إجراء العمليات التي تولد الأعداد الطبيعية" ^{[7] : 246}

انسخ رقمًا مثل n → m

"تغيير مسار عملية حسابية"، سواء بمقارنة رقمين أو تقليلهما حتى 0

وفي الواقع، يخلص شيفيرسون وستورجيس إلى ما يلي:

" إن الأنظمة الدنيا المختلفة متشابهة جدًا " ^{[7] : 246}

حسب ترتيب تاريخ النشر ، كانت أعمال كافينجست (1959)، ^[10] إيرشوف (1958)، ^[22] بيتر (1958) هي الأولى. ^[9]

النصوص الأساسية: تتضمن قائمة المراجع التالية للأوراق المصدرية عددًا من النصوص لاستخدامها كخلفية. يمكن العثور على الرياضيات التي أدت إلى موجة الأوراق حول الآلات المجردة في الخمسينيات والستينيات في van Heijenoort (1967) ^[23] - مجموعة من الأوراق الأصلية التي تمتد على مدى 50 عامًا من Frege (1879) ^[24] إلى Gödel (1931). ^[25] Davis (ed.) The Undecidable (1965) ^[26] يحمل الشعلة إلى الأمام بدءًا من Gödel (1931) ^[25] وحتى ملحق Gödel (1964)؛ ^{[27] : 71} تم تضمين الأوراق الأصلية لـ Alan Turing (1936 ^[28] -1937) و Emil Post (1936) ^[6] في The Undecidable . إن الرياضيات التي توصل إليها تشرش وروسر وكلين، والتي تظهر في صورة إعادة طبع للأوراق الأصلية في كتاب "غير القابل للحسم" ، قد تم نقلها إلى كتاب كلين (1952)، ^[29] وهو نص إلزامي لأي شخص يسعى إلى فهم أعمق للرياضيات وراء الآلات. كما تم الإشارة إلى كل من كلين (1952) ^[29] وديفيس (1958) ^[30] في عدد من الأوراق.

للحصول على معالجة جيدة لآلة العداد، انظر الفصل 11 من كتاب مينسكي (1967) "نماذج مشابهة لأجهزة الكمبيوتر الرقمية" - حيث أطلق على آلة العداد اسم "كمبيوتر البرنامج". ^[13] ويمكن العثور على نظرة عامة حديثة في كتاب فان إيمدي بواس (1990). ^[31] ويمكن العثور على معالجة حديثة لنموذج مينسكي (1961) ^[3] /لامبيك (1961) ^{[4] في كتاب بولوس-بورغيس-جيفري (2002)؛ [32]} حيث يعيدون تجسيد "نموذج العداد" الخاص بلامبيك لإثبات تكافؤ آلات تورينج والوظائف التكرارية الجزئية، كما يقدمون مقدمة على مستوى الدراسات العليا لكل من نماذج الآلة المجردة (المضادة وتورينج) ورياضيات نظرية التكرار. بدءًا من الطبعة الأولى لبولوس-بورغيس (1970) ^[33] ظهر هذا النموذج بنفس المعالجة تقريبًا.

الأوراق : تبدأ الأوراق بوانج (1957) ^[12] وتبسيطه الدرامي لآلة تورينج. تم الاستشهاد بتورينج (1936)، ^[28] كليين (1952)، ^[29] ديفيس (1958)، ^[30] وعلى وجه الخصوص بوست (1936) ^[6] في وانج (1957)؛ ^[12] بدوره، تمت الإشارة إلى وانج من قبل ميلزاك (1961)، ^[2] مينسكي (1961)، ^[3] وشيبردسون-ستورجيس (1961-1963) ^{[21] [7]} حيث قاموا بشكل مستقل بتقليص أشرطة تورينج إلى "عدادات". يوفر ميلزاك (1961) ^[2] نموذج آلة العداد ذات الحصى في الثقوب الخاص به بطريقة غير مباشرة ولكنه لا يواصل المعالجة. عمل إلجوت-روبنسون (1964) ^[17] يحدد RASP - آلات البرامج المخزنة ذات الوصول العشوائي الشبيهة بالكمبيوتر - ويبدو أنها أول من حقق في فشل آلة العداد المحدودة في حساب الدوال المتكررة. هذا الفشل - باستثناء الاستخدام الصارم لأرقام جودل على طريقة مينسكي (1961) ^[3] - يؤدي إلى تعريفهم للتعليمات "المفهرسة" (أي العنونة غير المباشرة) لنموذج RASP الخاص بهم. يبحث إلجوت-روبنسون (1964) ^[17] وأكثر من ذلك هارتمانيس (1971) ^[20] في RASPs مع برامج تعديل ذاتية. يحدد هارتمانيس (1971) ^[20] مجموعة تعليمات ذات توجيه غير مباشر، مستشهدًا بملاحظات محاضرات كوك (1970). ^[34] للاستخدام في التحقيقات المتعلقة بالتعقيد الحسابي، قدم كوك وطالبه المتخرج ريكهو (1973) ^[18] تعريفًا لذاكرة الوصول العشوائي (نموذجهما واتفاقية التذكر الخاصة بهما تشبه نموذج ميلزاك، لكنهما لم يقدما له أي مرجع في الورقة). آلات المؤشر هي فرع من كنوث (1968، ^[35] 1973) وشونهاج (1980) بشكل مستقل. ^[36]

تحتوي معظم الأوراق البحثية على رياضيات تتجاوز المستوى الجامعي - وخاصة الدوال التكرارية البدائية والدوال التكرارية المتعددة المقدمة بشكل أنيق في Kleene (1952) ^[29] وأقل عمقًا، ولكنها مفيدة مع ذلك، في Boolos–Burgess–Jeffrey (2002). ^[32]

لقد تم مشاهدة جميع النصوص والأوراق باستثناء النجوم الأربعة. وقد كُتبت هذه النجوم الأربعة باللغة الألمانية وتظهر كمراجع في Shepherdson-Sturgis (1963) ^[7] وElgot-Robinson (1964)؛ ^[17] يقدم Shepherdson-Sturgis (1963) ^[7] مناقشة موجزة لنتائجهم في الملحق A لـ Shepherdson-Sturgis. يبدو أن المصطلحات المستخدمة في ورقة واحدة على الأقل (Kaphengst (1959) ^[10] تعود إلى تحليل Burke-Goldstine-von Neumann (1946-1947) ^[19] لهندسة الكمبيوتر.

مؤلف	سنة	مرجع	آلة تورينج	آلة العداد	كبش	عرموش	آلة المؤشر	التوجيه غير المباشر	برنامج تعديل ذاتي
جولدستاين وفون نيومان	1947 [19]
كليين	1952 [29]
هيرميس	1954–1955 [8]			؟
وانج	1957 [12]			تلميحات				تلميحات
بيتر	1958 [9]			؟
ديفيس	1958 [30]
إرشوف	1959 [22]			؟
كافينجست	1959 [10]			؟
ميلزاك	1961 [2]								تلميحات
لامبيك	1961 [4]
مينسكي	1961 [3]
شيبردسون وستورجيس	1963 [7]							تلميحات
إلجوت وروبنسون	1964 [17]
ديفيس- غير قابل للحسم	1965 [26]
فان هيجنورت	1967 [23]
مينسكي	1967 [13]				تلميحات			تلميحات
كنوث	1968، [35] 1973
هارتمانيس	1971 [20]
كوك آند ريكو	1973 [18]
شونهاج	1980 [36]
فان إيمدي بواس	1990 [31]
بولوس وبورجيس؛ بولوس وبورجيس وجيفري	1970 [33] –2002 [32]

• ولفرام، ستيفن (2002). نوع جديد من العلوم. شركة ولفرام ميديا، ص 97-102. رقم ISBN 1-57955-008-8.

• وايسستين، إريك دبليو. “تسجيل الآلة”. عالم الرياضيات .
• آلات تسجيل مينسكي - إيجبلان