آلة البيع

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

تستطيع آلات العدّ المزودة بثلاثة عدادات حساب أي دالة تكرارية جزئية لمتغير واحد. أما آلات العدّ المزودة بعدادين فهي كاملة تورينج : إذ يمكنها محاكاة أي آلة تورينج مشفرة بشكل مناسب. بينما تستطيع آلات العدّ المزودة بعداد واحد فقط التعرف على مجموعة شاملة مناسبة من اللغات المنتظمة ومجموعة جزئية من اللغات الحتمية الخالية من السياق . ^{[ 1 ]}

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

• CLR (r): مسح السجل r . (ضبط قيمة r إلى الصفر.)
• INC (r): زيادة محتويات السجل r .
• DEC (r): قم بإنقاص محتويات السجل r .
• CPY (r _j , rk ₎ : نسخ محتويات السجل r _j إلى السجل r _k مع ترك محتويات r _j سليمة.
• JZ (r, z): إذا كان السجل r يحتوي على صفر، فانتقل إلى التعليمات z، وإلا فاستمر في التسلسل.
• JE (r _j , rk _, z): IF the contents of register r _j Equals the contents of register r _k THEN Jump to instruction z ELSE continue in sequence.

بالإضافة إلى ذلك، تحتوي الآلة عادةً على تعليمات HALT، والتي توقف الآلة (عادةً بعد حساب النتيجة).

باستخدام التعليمات المذكورة أعلاه، ناقش العديد من المؤلفين آلات عدّ معينة:

• المجموعة 1: { INC (r), DEC (r), JZ (r, z) }, (Minsky (1961, 1967), Lambek (1961))
• المجموعة 2: { CLR (r), INC (r), JE (r _j , r _k , z) }, (Ershov (1958), Peter (1958) كما فسرها Shepherdson–Sturgis (1964); Minsky (1967); Schönhage (1980))
• المجموعة 3: { INC (r)، CPY (r _j , r _k )، JE (r _j , r _k , z) }، (Elgot–Robinson (1964)، Minsky (1967))

تتمتع النماذج الأساسية الثلاثة لآلات العدّ بنفس القدرة الحسابية، إذ يمكن اشتقاق تعليمات أي نموذج من تعليمات نموذج آخر. جميعها تُعادل القدرة الحسابية لآلات تورينج . ونظرًا لأسلوب معالجتها الأحادي، فإن آلات العدّ عادةً ما تكون أبطأ بشكل كبير من آلات تورينج المماثلة.

تُعرف نماذج آلات العد بأسماء مختلفة قد تساعد في تمييزها بناءً على خصائصها. فيما يلي، تُعدّ التعليمة "JZDEC ( r )" تعليمة مركبة تختبر ما إذا كان المسجل r فارغًا؛ إذا كان كذلك، فانتقل إلى التعليمة I _z ، وإلا فقم بإنقاص محتويات r.

• آلة مينسكي ، نسبةً إلى مارفن مينسكي (1961) الذي وضع النموذج بشكل رسمي. آلة المعداد ، وهو الاسم الذي أطلقه لامبيك (1961) على تبسيطه لنموذج ميلزاك (1961)، وهو الاسم الذي أطلقه عليه بولوس-بورغيس-جيفري (1974). آلة لامبيك ، وهو اسم بديل أطلقه بولوس-بورغيس-جيفري (1974) على آلة المعداد. عادةً ما تستخدم مجموعة التعليمات (1)، ولكن تنفيذ التعليمات ليس تسلسليًا افتراضيًا، لذا يظهر المعامل الإضافي 'z' لتحديد التعليمات التالية بعد INC، وكبديل في JZDEC.

  { INC ( r, z ), JZDEC ( r, z _true , z _false ) }

• آلة البرمجة ، حاسوب البرمجة ، هي الأسماء التي أطلقها مينسكي (1967) على هذا النموذج لأنه، مثل الحاسوب ، تُنفذ تعليماته بالتسلسل ما لم تنجح قفزة شرطية. يستخدم (عادةً) مجموعة التعليمات (1)، ولكن يمكن توسيعه على غرار نموذج شيفيرسون-ستورجيس. غالبًا ما يتم تقسيم JZDEC إلى أجزاء.

  { INC ( r ), CPY ( r _s , r _d ), JZ ( r, z _true )}

• آلة الخلف ، لأنها تستخدم "عملية الخلف" الخاصة ببديهيات بيانو ، وتشبهها إلى حد كبير . تُستخدم كأساس لنموذج ذاكرة الوصول العشوائي للخلف . تستخدم مجموعة التعليمات (2) التي وضعها شونهاج، على سبيل المثال، كأساس لنموذجي RAM0 وRAM1 اللذين يؤديان إلى نموذج آلة المؤشر SMM الخاص به ، ^{[ 2 ] [ 3 ]} والذي ناقشه فان إمده بواس بإيجاز أيضًا: ^{[ 4 ] [ 5 ]}

  { CLR ( r )، INC ( r )، JE ( r _j , r _k , z ) }

• نموذج إلجوت-روبنسون ، المستخدم لتعريف نموذج RASP الخاص بهم (1964). يتطلب هذا النموذج سجلًا فارغًا واحدًا في البداية (مثلًا [r0] = 0). (قاموا بتطوير النموذج نفسه باستخدام العنونة غير المباشرة من خلال استخدام سجل إضافي يُستخدم كسجل "فهرسة").

  { INC (r), CPY ( r _s , r _d ), JE ( r _j , r _k , z ) }

• آلة شيبردسون-ستورجيس ، لأن هؤلاء المؤلفين قد أوضحوا نموذجهم رسميًا في شرح مبسط (1963). تستخدم مجموعة التعليمات (1) معززة بتعليمات إضافية ملائمة (JNZ تعني "القفز إذا لم يكن صفرًا"، وتُستخدم بدلًا من JZ):

  { INC ( r ), DEC ( r ), CLR ( r ), CPY ( r _j , _rk ), JNZ ( r, z ), J ( z ) }

• آلات عدّ أخرى : يُبيّن مينسكي (1967) كيفية بناء النماذج الأساسية الثلاثة (البرنامج/مينسكي/معداد لامبيك، والنموذج اللاحق، وإلغوت-روبنسون) من مجموعة التعليمات المتاحة الموضحة في الفقرة الافتتاحية لهذه المقالة. يختلف نموذج ميلزاك (1961) اختلافًا كبيرًا عن النموذج السابق، إذ يتضمن عمليتي "الجمع" و"الطرح" بدلًا من "الزيادة" و"الإنقاص". تتطلب براهين مينسكي (1961، 1967) التي تُثبت أن سجلًا واحدًا يكفي لإثبات تكافؤ تورينج، استخدام التعليمتين {MULtiply k, وDIV k} لترميز وفك ترميز عدد غودل في السجل الذي يُمثل العملية الحسابية. يُوضح مينسكي أنه في حال توفر سجلين أو أكثر، فإن التعليمات الأبسط مثل INC وDEC كافية (لكن لا يزال عدد غودل مطلوبًا لإثبات تكافؤ تورينج ؛ وقد تم إثبات ذلك أيضًا في إلغوت-روبنسون 1964).

تتكون آلة العد من:

1. سجلات ذات قيم عددية صحيحة غير محدودة ومُصنّفة : هي مجموعة محدودة (أو غير محدودة في بعض النماذج) من السجلات r₀ ... rₙ _{، حيث يمكن لكل سجل} منها أن يحتوي على أي عدد صحيح غير سالب (0، 1، 2، ... - أي غير محدود). تُجري هذه السجلات عملياتها الحسابية الخاصة؛ وقد تحتوي على سجل خاص واحد أو أكثر، مثل "المُجمِّع" (انظر آلة الوصول العشوائي لمزيد من المعلومات حول هذا الموضوع).  
2. سجل حالة يُخزّن/يُحدّد التعليمات الحالية المراد تنفيذها. هذا السجل محدود ومنفصل عن السجلات المذكورة أعلاه؛ لذا يُعدّ نموذج آلة العدّ مثالًا على بنية هارفارد.
3. قائمة التعليمات المتسلسلة والمُعَلَّمة : قائمة محدودة من التعليمات I ₀  ... I _m . لا يقع مخزن البرنامج (تعليمات آلة الحالة المحدودة ) في نفس "الحيز" المادي للمسجلات. عادةً، ولكن ليس دائمًا، كما هو الحال في برامج الحاسوب، تُدرج التعليمات بترتيب تسلسلي؛ ما لم تنجح عملية القفز، يستمر التسلسل الافتراضي بالترتيب العددي. كل تعليمة في القائمة تنتمي إلى مجموعة صغيرة جدًا، ولكن هذه المجموعة لا تشمل التعليمات غير المباشرة. تاريخيًا، استمدت معظم النماذج تعليماتها من هذه المجموعة. 

{ زيادة (r)، إنقاص (r)، مسح (r)؛ نسخ (r _j ، r _k )، قفزة مشروطة إذا كانت محتويات r=0، قفزة مشروطة إذا كانت r _j = r _k ، قفزة غير مشروطة، إيقاف }

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

تتم مناقشة مجموعات التعليمات البديلة في الملحق الخاص بنماذج آلة التسجيل .

يوضح هذا المثال كيفية إنشاء ثلاث تعليمات مفيدة أخرى: clear و unconditional jump و copy .

• CLR ( j ): مسح محتويات السجل r _j إلى الصفر.
• J ( z ): الانتقال غير المشروط إلى التعليمات I _z .
• CPY ( s, d ): انسخ محتويات سجل المصدر r _s إلى سجل الوجهة r _d . (انظر: حاسوب ذو مجموعة تعليمات واحدة# بنية مُشغَّلة بالنقل )

بعد ذلك، سيحتوي r _s على عدده الأصلي (على عكس MOVE الذي يفرغ سجل المصدر، أي يمسحه إلى الصفر).

تُستخدم المجموعة الأساسية (1) كما هو مُعرّف هنا:

يوضح المثال أعلاه كيف يمكن للتعليمات الأساسية الأولى { INC, DEC, JZ } أن تُنشئ ثلاث تعليمات إضافية: القفزة غير المشروطة J، وCLR، وCPY. بمعنى آخر، استخدمت CPY كلاً من CLR وJ بالإضافة إلى مجموعة الأساس. لو كان السجل رقم 3 يحتوي على بيانات في البداية، لكان مجموع بيانات السجلين رقم 2 ورقم 3 قد انتهى به المطاف في السجل رقم 3. لذا، لكي يكون برنامج CPY دقيقًا تمامًا، كان ينبغي أن يسبق حركاته بـ CLR (1) وCLR (3).

مع ذلك، نرى أن عملية الجمع (ADD) كانت ممكنة بسهولة. وفي الواقع، فيما يلي ملخص لكيفية ظهور الدوال التكرارية الأساسية مثل الجمع والضرب والأس. ^{[ 6 ]}

• مجموعة التعليمات الأولية: { DEC, INC, JZ, H }
• عرّف "القفزة J (z)" غير المشروطة بدلالة JZ ( r0, z ) بشرط أن r0 تحتوي على 0.

{ J, DEC, INC, JZ, H }

• عرّف "CLeaR ( r )" من حيث ما سبق:

{ CLR, J, DEC, INC, JZ, H }

• قم بتعريف "CoPY ( r _j , rk ₎ " مع الحفاظ على محتويات r _j وفقًا لما سبق:

{ CPY, CLR, J, DEC, INC, JZ, H }

ما سبق هو مجموعة التعليمات الخاصة بـ Shepherdson–Sturgis (1963).

• قم بتعريف "ADD ( r _j , _rk , r _i )", (ربما مع الحفاظ على محتويات r _j و _rk ), باستخدام ما سبق:

{ ADD, CPY, CLR, J, DEC, INC, JZ, H }

• عرّف "MULtiply ( r _j , _rk , r _i )" (MUL) (ربما مع الحفاظ على محتويات r _j , rk ₎ ، من حيث ما سبق:

{ MUL, ADD, CPY, CLR, J, DEC, INC, JZ, H }

• عرّف "EXPonential ( r _j , _rk , r _i )" (EXP) (ربما مع الحفاظ على محتويات r _j , rk ₎ من حيث ما سبق،

{ EXP, MUL, ADD, CPY, CLR, J, DEC, INC, JZ, H }

بشكل عام، يمكننا بناء أي دالة تكرارية أولية جزئية أو كلية نرغب بها، باستخدام نفس الأساليب. في الواقع، قدم كل من مينسكي (1967)، وشيباردسون-ستورجيس (1963)، وبولوس-بورغيس-جيفري (1974) أمثلة توضيحية لكيفية تكوين "المؤثرات" الخمسة للدوال التكرارية الأولية (1-5 أدناه) من المجموعة الأساسية (1).

لكن ماذا عن التكافؤ الكامل لتورينغ ؟ نحتاج إلى إضافة العامل السادس - العامل μ - للحصول على التكافؤ الكامل، القادر على إنشاء الدوال التكرارية الكلية والجزئية :

1. الدالة الصفرية (أو الدالة الثابتة )
2. دالة الخلف
3. دالة التطابق
4. دالة التركيب
5. الاستقراء البدائي (الاستقراء)
6. عامل μ (عامل البحث غير المحدود)

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

على سبيل المثال، يمكن توسيع التسلسل الهرمي المذكور أعلاه للعوامل التكرارية الأولية ليشمل عمليات الأسهم ذات الرتبة الأعلى في تدوين كنوت للسهم العلوي . لأي قيمة ثابتة${\displaystyle k}$، الوظيفة${\displaystyle Q(x,y)=x\uparrow ^{k}y}$هي دالة تكرارية بدائية، ويمكن تنفيذها كآلة عداد بطريقة مباشرة. لكن الدالة${\displaystyle R(n,x,y)=x\uparrow ^{n}y}$ليست دالة تكرارية بدائية. قد يميل المرء إلى استخدام عامل السهم العلوي.${\displaystyle R}$باستخدام بنية مشابهة لتعليمات اللاحق والجمع والضرب والأس المذكورة أعلاه، من خلال تنفيذ مكدس استدعاء بحيث يمكن تطبيق الدالة بشكل متكرر على قيم أصغر من${\displaystyle n}$هذه الفكرة مشابهة لكيفية تنفيذ الوظيفة عمليًا في العديد من لغات البرمجة. مع ذلك، لا يمكن لآلة العداد استخدام عدد غير محدود من المسجلات في حساباتها، وهو ما يتطلبه تنفيذ مكدس استدعاءات قد ينمو بشكل عشوائي. يمكن تنفيذ عملية السهم لأعلى كآلة عداد لأنها غير تكرارية، ولكن سيتم تنفيذ الوظيفة عن طريق ترميز كمية غير محدودة من المعلومات داخل عدد محدود من المسجلات، كما هو الحال باستخدام ترقيم غودل .

تُناقش هذه المشكلات بالتفصيل في مقال "آلة الوصول العشوائي ". وتنقسم هذه المشكلات إلى فئتين رئيسيتين، بالإضافة إلى فئة ثالثة تُعرف باسم "فئة الإزعاج".

(1) السعات غير المحدودة للسجلات مقابل السعات المحدودة لتعليمات آلة الحالة: كيف ستنشئ الآلة ثوابت أكبر من سعة آلة الحالة المحدودة الخاصة بها؟

(2) عدد غير محدود من السجلات مقابل عدد محدود من تعليمات آلة الحالة: كيف ستتمكن الآلة من الوصول إلى السجلات ذات أرقام العناوين التي تتجاوز نطاق/قدرة آلة الحالة المحدودة الخاصة بها؟

(3) النماذج المختزلة بالكامل معقدة:

لم يبدِ شيبردسون وستورجيس (1963) أي ندم على مجموعة التعليمات الست التي استخدموها. وقد اتخذوا هذا الاختيار بناءً على "سهولة البرمجة... بدلاً من الاقتصاد" (ص  219، الحاشية 1).

تعليمات شيبردسون وستورجيس ( [r] تشير إلى "محتويات السجل r"):

• • زيادة (r)  ؛ [r] +1 → r
  • إنقاص (r)  ؛ [r] -1 → r
  • مسح ( r )  ؛ 0 → r
  • انسخ ( r _s إلى r _d )  ؛ [r _s ] → r _d
  • انتقل إلى التعليمات I _{z بشكل غير مشروط}
  • انتقل إذا كان [r] = 0 إلى التعليمة I _z

قام مينسكي (1967) بتوسيع مجموعة التعليمات المكونة من 2 { INC (z), JZDEC (r, I _z ) } إلى { CLR (r), INC (r), JZDEC (r, I _z ), J (I _z ) } قبل إثباته أنه يمكن بناء "آلة برمجة عالمية" باستخدام سجلين فقط (ص  255 وما بعدها).

لكل آلة تورينج ، توجد آلة 2CM تحاكيها، بشرط أن تكون مدخلات ومخرجات آلة 2CM مشفرة بشكل صحيح. وقد ثبت ذلك في كتاب مينسكي ( الحوسبة ، 1967، ص  255-258)، وفيما يلي برهان بديل مُوجز في ثلاث خطوات. أولًا، يمكن محاكاة آلة تورينج بواسطة آلة حالة محدودة (FSM) مزودة بمكدسين. ثانيًا، يمكن محاكاة المكدسين بواسطة أربعة عدادات. أخيرًا، يمكن محاكاة العدادات الأربعة بواسطة عدادين. تستخدم آلة العدادين مجموعة التعليمات { INC ( r, z ), JZDEC ( r, z _true , z _false ) }.

لم تكن آلة حاسبة فريدن EC-130 مزودة بمنطق جمع بالمعنى المتعارف عليه. كان منطقها تسلسليًا للغاية، حيث تُجرى العمليات الحسابية بالعد. داخليًا، كانت الأرقام العشرية تُحسب بنظام الأساس 1 - على سبيل المثال، كان الرقم 6 يُمثل بست نبضات متتالية ضمن الفترة الزمنية المخصصة له. تحمل كل فترة زمنية رقمًا واحدًا، بدءًا من الأقل أهمية. تُفعّل عمليات الحمل قلابًا، مما يؤدي إلى إضافة عدّة واحدة إلى الرقم في الفترة الزمنية التالية.

كانت عملية الجمع تتم بواسطة عداد تصاعدي، بينما كان الطرح يتم بواسطة عداد تنازلي، مع وجود مخطط مماثل للتعامل مع عمليات الاستلاف.

حدد نظام الفترات الزمنية ستة سجلات، كل منها يحتوي على 13 رقمًا عشريًا، ولكل سجل بت إشارة . وكانت عمليات الضرب والقسمة تتم أساسًا عن طريق الجمع والطرح المتكررين. أما نسخة الجذر التربيعي ، EC-132، فكانت تطرح الأعداد الفردية المتتالية، حيث يتطلب كل إنقاص عمليتي طرح متتاليتين. بعد الأولى، كان المطروح منه يزيد بمقدار واحد قبل عملية الطرح الثانية.

• نموذج الآلة المضادة
• حاسوب ذو مجموعة تعليمات واحدة
• آلة المؤشر
• آلة ما بعد التورينج
• آلة الوصول العشوائي
• آلة التسجيل
• وانغ بي-ماشين
• نظام جمع المتجهات

• بولوس، جورج ؛ بورغيس، جون ب .؛ جيفري، ريتشارد (2007) [1974]. الحوسبة والمنطق (الطبعة الخامسة  ). كامبريدج، إنجلترا: مطبعة جامعة كامبريدج . doi : 10.1017/CBO9780511804076 . ISBN 9780521877527.قام بورغيس بتنقيح نص بولوس-جيفري الأصلي بشكل موسع، ليصبح أكثر تقدماً من مجرد كتاب تمهيدي. وقد تم تطوير نموذج "آلة المعداد" بشكل موسع في الفصل الخامس " قابلية حساب المعداد " ؛ وهو أحد ثلاثة نماذج تمت معالجتها ومقارنتها بشكل شامل - آلة تورينج (التي لا تزال في شكلها الأصلي الرباعي لبولوس) والتكرار هما النموذجان الآخران.

• بوركس، آرثر ؛ غولدستين، هيرمان ؛ فون نيومان، جون (1946). مناقشة أولية للتصميم المنطقي لجهاز حاسوب إلكتروني .أُعيد طبعه في: بيل، جوردون ؛ نيويل، ألين، محرران (1971) [1946]. هياكل الحاسوب: قراءات وأمثلة . نيويورك: شركة ماكجرو هيل للنشر. ISBN 0-07-004357-4.
• كوك، ستيفن أ .؛ ريكهاو، روبرت أ. (1973). "آلات الوصول العشوائي المحدودة زمنيًا" (ملف PDF) . مجلة علوم الحاسوب والأنظمة . 7 (4): 354-375 . doi : 10.1016/S0022-0000(73)80029-7 .
• ديفيس، مارتن (1958). قابلية الحساب وعدم قابلية الحل . نيويورك: شركة ماكجرو هيل للنشر.
• إلغوت، كالفن؛ روبنسون، أبراهام (1964). "آلات البرامج المخزنة ذات الوصول العشوائي، مدخل إلى لغات البرمجة". مجلة رابطة آلات الحوسبة . 11 (4): 365-399 . doi : 10.1145/321239.321240 .
• فيشر، باتريك سي .؛ ماير، ألبرت ر .؛ روزنبرغ، أرنولد ل. (1968)، "آلات العد ولغات العد"، نظرية الأنظمة الرياضية ، 2 (3): 265-283 ، doi : 10.1007/bf01694011 ، MR 0235932 ، S2CID 13006433  يطور نظريات التسلسل الهرمي الزمني والمكاني لآلات العد، على غرار التسلسلات الهرمية لآلات تورينج.
• هارتمانيس، جوريس (1971). "التعقيد الحسابي لآلات البرامج المخزنة ذات الوصول العشوائي". نظرية الأنظمة الرياضية . 5 (3): 232-245 . doi : 10.1007/BF01694180 .
• هوبكروفت، جون ؛ أولمان، جيفري (1979). مقدمة في نظرية الأوتوماتا واللغات والحوسبة (الطبعة الأولى  ). ريدينغ، ماساتشوستس: أديسون-ويسلي. ISBN 0-201-02988-X.كتاب صعب يتمحور حول قضايا التفسير الآلي لـ "اللغات"، واكتمال NP، وما إلى ذلك.
• هوبكروفت، جون ؛ موتاني، راجيف ؛ أولمان، جيفري (2003) [1979]. مقدمة في نظرية الأوتوماتا واللغات والحوسبة (الطبعة الثانية  ). ريدينغ، ماساتشوستس: أديسون-ويسلي. ص  352. ISBN 0-201-44124-1.
• كلين، ستيفن (1952). مقدمة في ما وراء الرياضيات . أمستردام، هولندا: شركة نورث هولاند للنشر. ISBN 0-7204-2103-9.{{cite book}}عدم توافق رقم ISBN / التاريخ ( مساعدة )
• كنوت، دونالد (1973) [1968]. فن برمجة الحاسوب (  الطبعة الثانية). ريدينغ، ماساتشوستس: أديسون-ويسلي.انظر الصفحات 462-463 حيث يُعرّف "نوعًا جديدًا من الآلات المجردة أو "الآلات الآلية" التي تتعامل مع الهياكل المرتبطة".
• لامبيك، يواكيم (1961). "كيفية برمجة عداد لانهائي". النشرة الرياضية . 4 (3): 295-302 . doi : 10.4153/CMB-1961-032-6 .يقترح لامبيك في الملحق الثاني تعريفاً رسمياً لـ "البرنامج". ويشير إلى كتاب ميلزاك (1961) وكلين (1952) مقدمة في ما وراء الرياضيات .
• ميلزاك، ز. أ. (1961). "مقاربة حسابية غير رسمية للحوسبة والحساب". النشرة الرياضية الكندية . 4 (3): 279-293 . doi : 10.4153/CMB-1961-031-9 .لم يقدم ميلزاك أي مراجع ولكنه أقر "بفائدة المحادثات مع الدكاترة ر. هامينغ، د. ماكيلروي، و ف. فيسوتس من مختبرات بيل للهواتف ومع الدكتور هـ. وانغ من جامعة أكسفورد".
• مينسكي، مارفن (1961). "عدم قابلية حل مسألة "الوسم" لبوست بشكل متكرر ومواضيع أخرى في نظرية آلات تورينج". حوليات الرياضيات . 74 (3): 437-455 . doi : 10.2307/1970290 . JSTOR 1970290 . 
• مينسكي، مارفن (1967). الحوسبة: الآلات المحدودة واللامحدودة (  الطبعة الأولى). إنجلوود كليفس، نيوجيرسي: برنتيس هول، إنك.انظر تحديدًا الفصل 11: نماذج مشابهة للحواسيب الرقمية ، والفصل 14: أسس بسيطة جدًا للحوسبة . في الفصل الأول، يُعرّف "آلات البرمجة"، وفي الفصل الثاني، يناقش "آلات البرمجة الشاملة ذات سجلين" و"...ذات سجل واحد"، إلخ.
• شيباردسون، جيه سي ؛ ستورجيس، إتش إي (1963). "قابلية حساب الدوال التكرارية" . مجلة رابطة آلات الحوسبة . 10 (2): 217-255 . doi : 10.1145/321160.321170 .ورقة مرجعية قيّمة. في الملحق (أ)، يستشهد المؤلفون بأربعة مراجع أخرى فيما يتعلق بـ "الحد الأدنى من التعليمات المستخدمة في 4.1: مقارنة مع أنظمة مماثلة".
  • كافينجست، هاينز (1959). "Eine Abstrakte Programmgesteuerte Rechenmaschine". Zeitschrift für mathatische Logik und Grundlagen der Mathematik . 5 ( 14– 24): 366– 379. دوى : 10.1002/malq.19590051413 .
  • إرشوف، ا ف ب (1958). "على خوارزميات المشغل" . دوكلادي أكاديمي ناوك SSSR (بالروسية). 122 (6): 967- 970.الترجمة الإنجليزية، Automat. Express 1 (1959)، 20-23.
  • بيتر روزا (1958). "المخططات البيانية والوظائف المتكررة" . ديالكتيك (في المانيا). 12 ( 3– 4): 373– 393. دوى : 10.1111/j.1746-8361.1958.tb01470.x .
  • هيرميس، هانز (1954). "Die Universalität Programmgesteuerter Rechenmaschinen". الرياضيات-فيزياء. نصف فصل . 4 . غوتنغن: 42-53 .
• شونهاج، أرنولد (ديسمبر 1973). محاكاة في الوقت الحقيقي لآلات تورينج متعددة الأبعاد بواسطة آلات تعديل التخزين (مذكرة فنية). كامبريدج، ماساتشوستس: مشروع MIT MAC. hdl : 1721.1/148866 .
• شونهاج، أرنولد (1980). "آلات تعديل التخزين". مجلة SIAM للحوسبة 9 ( 3). جمعية الرياضيات الصناعية والتطبيقية: 366-379 . doi : 10.1137/0209036 .حيث يوضح شونهاج تكافؤ SMM الخاص به مع "آلة الوصول العشوائي" (RAM) اللاحقة، إلخ.
• شرويبل، ريتش (1972). "آلة ذات عدادين لا تستطيع حساب 2^ ^ن " (ملف PDF) . معهد ماساتشوستس للتكنولوجيا، مختبر الذكاء الاصطناعي، مذكرة الذكاء الاصطناعي رقم 257.يشير المؤلف إلى مينسكي 1967 ويلاحظ أن " فرانسيس ياو أثبتت بشكل مستقل عدم قابلية الحساب باستخدام طريقة مماثلة في أبريل 1971".
• فان إمده بواس، بيتر (1989). نماذج ومحاكاة الآلات (ملف PDF) (تقرير فني). الحوسبة ونظرية التعقيد. معهد المنطق واللغة والحوسبة، جامعة أمستردام . تاريخ الاسترجاع: 27 يوليو 2025 .
• فان إمده بواس، بيتر (1990). "نماذج ومحاكاة الآلات". في فان ليوين، يان (محرر). دليل علوم الحاسوب النظرية. المجلد أ: الخوارزميات والتعقيد (  الطبعة الأولى). مطبعة معهد ماساتشوستس للتكنولوجيا/إلسيفير. الصفحات 3-66 . ISBN  9780444880710.يُقدّم فان إمدي بواس تحليله لـ SMMs في الصفحات  من 32 إلى 35. يُوضّح هذا التحليل ما ورد في دراسة شونهاج عام 1980، إذ يتبعها عن كثب مع توسيع طفيف لها. وقد يكون من الضروري الرجوع إلى كلا المرجعين لفهمٍ فعّال.
• وانغ، هاو (1957). "صيغة معدلة لنظرية تورينغ لآلات الحوسبة". مجلة ACM . 4 : 63-92 . doi : 10.1145/320856.320867 .تم تقديمها في اجتماع الجمعية، 23-25 ​​يونيو 1954.

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

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