نموذج الآلة المضادة

📅 آخر تحديث: ٢٧ يوليو ٢٠٢٦
✍️ نُشر في: ٢٧ يوليو ٢٠٢٦
الموسوعة الحرة

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

النماذج بمزيد من التفصيل

1954: نموذج هيرميس

لاحظ شيبردسون وستورجيس (1963) أن "برهان هذه العمومية [للحواسيب الرقمية مقارنةً بآلات تورينج]... يبدو أنه قد دُوِّن لأول مرة على يد هيرمس، الذي أوضح في [7 - رقم مرجعهم] كيف يمكن برمجة حاسوب مثالي لمحاكاة سلوك أي آلة تورينج" ، و: "يُعدّ نهج كافينجست مثيرًا للاهتمام لأنه يُقدّم برهانًا مباشرًا على عمومية الحواسيب الرقمية الحالية، على الأقل عندما تكون مثالية لدرجة تسمح بوجود عدد لا نهائي من سجلات التخزين، كل منها قادر على تخزين كلمات طويلة كيفما شاء" . [ 1 ]

التعليمات الحسابية الوحيدة هي

  1. عملية لاحقة
  2. اختبار تساوي عددين

أما باقي العمليات فهي عمليات نقل من المسجل إلى المُراكم أو من المُراكم إلى المسجل أو عمليات اختبار القفز.

كُتبت ورقة كافينجست باللغة الألمانية؛ وتستخدم ترجمة شيبردسون وستورجيس مصطلحات مثل "mill" و "orders".

تحتوي الآلة على "مُجمِّع" (مُجمِّع). يُشير كافينغست إلى مُجمِّعه برمز اللانهاية، لكننا سنستخدم الرمز "A" في الوصف التالي. كما تحتوي على "سجل أوامر" (بمعنى "تعليمات"، وليس بمعنى "تسلسل"). (هذا الاستخدام مأخوذ من وصف تقرير بيركس-غولدستين-فون نيومان (1946) لـ "...جهاز حاسوب إلكتروني"). سجل الأوامر/التعليمات هو السجل "0". وعلى الرغم من عدم وضوح ذلك من شرح شيبردسون وستورجيس، إلا أن النموذج يحتوي على "سجل امتداد" يُشير إليه كافينغست بـ "اللانهاية-الأولية"؛ سنستخدم الرمز "E".

يتم تخزين التعليمات في السجلات:

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

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

فعل:وصف
D1:C(r, A)[ r ] → A, [ r ] → rانسخ محتويات السجل r إلى المُراكم A
D2:سيارة)[ أ ] → ر، [ أ ] → أانسخ محتويات المُراكم A إلى السجل r
ج1:O(A)0 → أالمُراكم الصفري (المسح) أ
أ1:P(A)[ أ ] + 1 → أقم بزيادة (أضف 1 إلى) محتويات المُراكم A
F1:J(A) [E1]إذا كانت قيمة [A] تساوي 0، فانتقل إلى "المخرج 1".اقفز إذا كانت محتويات المُراكم A = 0
G1:على (أ)إذا كان [A] = [r]، فإن 0 → <A>، وإلا فإن 1 → Aامسح محتويات A إذا كانت محتويات A تساوي محتويات r، وإلا فعيّن A=1
G2:O'(A)1 → أ"ضبط" محتويات A = 1

قام شيبردسون وستورجيس (1963) بإزالة وحدة الطحن/المراكم A، واختصرا تعليمات كافينجست إلى عملية "نسخ" بين المسجلات، وعملية "زيادة" حسابية، وعملية "مقارنة" بين المسجلات. لاحظ عدم وجود عملية إنقاص . هذا النموذج، بصيغته الأصلية تقريبًا، موجود في مينسكي (1967) ؛ انظر المزيد في القسم أدناه.

فعل:وصف:
أ:P(A)[ أ ] + 1 → أقم بزيادة (أضف 1 إلى) محتويات المُراكم A
د.C(r j , r k )[ r j ] → rk , [ r j ] → r jانسخ محتويات السجل r j إلى السجل r k
و:J(r) [E1]إذا كانت قيمة [r] تساوي صفرًا، فانتقل إلى "الخروج 1"، وإلا فانتقل إلى التعليمات التالية.انتقل إذا كانت محتويات السجل r تساوي 0
ج:E(r j , r k )إذا كان [rj ] = [rk ] ، فإن 0 → E، وإلا فإن 1 → Eامسح محتويات السجل E إذا كانت محتويات rj تساوي محتويات rk ، وإلا فاجعل E = 1

1958: فئة إرشوف من خوارزميات المؤثرات

لاحظ شيبردسون وستورجيس (1963) أن نموذج إرسوف يسمح بتخزين البرنامج في المسجلات. ويؤكدان أن نموذج إرسوف هو كما يلي:

فعل:وصف:
د.C(r j ,r k )[ r j ] → rk , [ r j ] → r jانسخ محتويات السجل r j إلى السجل r k
د'.C' (r j ,r k )[ r j ] +1 → rk , [ r j ] → r jانسخ محتويات السجل r j المتزايدة إلى السجل r k
هـ.J[E1]انتقل إلى "المخرج 1"الانتقال الفوري إلى "المخرج رقم 1"
f*:J(r j , r k )[E1, E2]إذا كان [r j ] ≤ [rk ] ، فانتقل إلى "المخرج 1"، وإلا فانتقل إلى "المخرج 2".انتقل إلى المخرج E1 إذا كانت محتويات السجل r j أقل من أو تساوي محتويات السجل rk ، وإلا فانتقل إلى E=2

1958: "علاج" بيتر

لاحظ شيبردسون وستورجيس (1963) أن "علاج" بيتر (لم يحددا تفاصيل دقيقة هنا) يُعادل التعليمات الموضحة في الجدول التالي. وقد علّقا تحديدًا على هذه التعليمات، قائلين:

"من وجهة نظر إثبات قابلية حساب جميع الدوال الجزئية المتكررة بأسرع وقت ممكن ، فإن طريقة بيتر ربما تكون الأفضل؛ أما لإثبات قابلية حسابها بواسطة آلات تورينج، فمن الضروري إجراء تحليل إضافي لعملية النسخ على النحو الذي اتبعناه أعلاه." [ 2 ]
فعل:وصف:
ج:على)0 → [ n ]سجل الصفر (مسح) ن
د.C(m,n)[م] → ن، [م] → [م]انسخ محتويات السجل m إلى السجل n
د'.C'(m,n)[ m ] + 1 → [ n ], [ m ] → [ m ]انسخ محتويات السجل m المتزايدة إلى السجل n
هـ.J(m, n)[E1, E2]إذا كان [m]=[n] انتقل إلى E1، وإلا فانتقل إلى E2انتقل بشرط إلى E1 إذا كانت محتويات m تساوي محتويات n، وإلا فانتقل إلى E2.

1961: اختُزل نموذج مينسكي للدالة التكرارية الجزئية إلى "برنامج" مكون من تعليمتين فقط

أدى بحث مينسكي في مشاكل إميل بوست ( نظام العلامات ) ومشكلة هيلبرت العاشرة ( مشاكل هيلبرت ، المعادلة الديوفانتية ) إلى التعريف التالي لـ:

"أساس مثير للاهتمام لنظرية الدوال التكرارية التي تتضمن برامج لأبسط العمليات الحسابية فقط". [ 3 ]

تؤكد "نظريته Ia" أن أي دالة تكرارية جزئية يتم تمثيلها بواسطة "برنامج يعمل على عددين صحيحين S1 و S2 باستخدام التعليمات Ij من الأشكال: [ 4 ]

فعل:وصف:
أ. أضف (r، I j1 ) [ r ] + 1 → r; انتقل إلى التعليمات I j1 . قم بزيادة (أضف 1 إلى) محتويات السجل r وانتقل إلى التعليمات I j1 .
ب. SUB (r, I j1 ,I j2 )إذا كانت قيمة [r] ≤ 0، فانتقل إلى الآلة I j2، وإلا فإن قيمة [r] -1 → r وانتقل إلى الآلة I j1.إذا كانت محتويات السجل r تساوي صفرًا، فانتقل إلى التعليمات I j2 ؛ وإلا فقم بإنقاص (طرح 1 من) محتويات السجل r وانتقل إلى التعليمات I j1 .

تُشكّل النظرية الأولى سياقًا لنظرية ثانية تُسمى "النظرية الثانية أ" التي

"...يمثل أي دالة تكرارية جزئية بواسطة برنامج يعمل على عدد صحيح واحد S [موجود في سجل واحد r1] باستخدام التعليمات I j من الأشكال":
فعل:وصف:
أ. MULT (K j , I j1 ) [ r1 ]*K j → r1; انتقل إلى التعليمات I j1 . اضرب محتويات السجل r1 بالثابت K j
ب. DIV (K j , I j1 , I j2 )[ r1 ]/Kj = 0 ثم انتقل إلى التعليمات I j2 وإلا انتقل إلى I j1 . إذا لم ينتج عن قسمة محتويات السجل 1 على الثابت Kj باقي ، فسيتم تنفيذ الأمر Ij1، وإلا فسيتم تنفيذ الأمر Ij2 .

في هذا الشكل الثاني، تستخدم الآلة أرقام غودل لمعالجة "العدد الصحيح S". ويؤكد أن الآلة/النموذج الأول لا يحتاج إلى القيام بذلك إذا كان لديه 4 سجلات متاحة له.

1961: نموذج ميلزاك: تعليمات ثلاثية واحدة مع الجمع والطرح المناسب

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

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

النموذج المادي لملزاك هو عبارة عن ثقوب { X، Y، Z، إلخ. } في الأرض مع إمداد غير محدود من الحصى في حفرة خاصة S (هل هي حفرة تصريف أم مصدر أم كلاهما؟ لم يوضح ميلزاك ذلك).

تتألف آلة Q من عدد غير محدود من المواقع : S، A1، A2، ...، ومخزون غير محدود من العدادات موزعة بين هذه المواقع، وبرنامج، ومشغل مهمته الوحيدة تنفيذ التعليمات. في البداية، تكون جميع المواقع فارغة باستثناء عدد محدود منها، ويحتوي كل موقع من المواقع المتبقية على عدد محدود من العدادات . (ص 283، تم إضافة الخط الغامق)

التعليمات عبارة عن " عملية ثلاثية " واحدة يسميها "XYZ":

يشير "XYZ" إلى عملية
  1. احسب عدد الحصى في الحفرة Y ،
  2. أعدها إلى Y ،
  3. حاول إزالة نفس الرقم من الفتحة X. إذا لم يكن ذلك ممكنًا لأنه سيؤدي إلى إفراغ الفتحة X، فلا تفعل شيئًا وانتقل إلى التعليمات رقم I؛ وإلا،
  4. قم بإزالة الكمية Y من X و (iv) انقلها إلى، أي أضفها إلى، الكمية الموجودة في الحفرة Z.

من بين جميع العمليات الممكنة، هناك بعض العمليات غير المسموح بها، كما هو موضح في الجدول أدناه:

مسموحتعليماتثقب "X"ثقب "Y"ثقب "Z"معنى التعليمات
لاXXX
XXY([ X ] - [ X ])=0 → X[Y] + [X] → Y[ Z ] → Zجميع حصى X مأخوذة من X ومضافة إلى Y
XXS([ X ] - [ X ])=0 → X[ Y ] → Y[ Z ] → Zجميع حصى X مأخوذة من X وتوضع في المصرف/المصدر S
لاXYX
XYY[X] - [Y] → X[ Y ] + [ Y ] → Y[ Z ] → Zعدد الحصى التي أخذها Y من X ووضعها في Y، مما يضاعف عدد Y
XYS
لاXSX
لاXSY
لاXSS
XYZ[X] - [Y] → X[ Y ] → Y[Z] + [Y] → Zعدد الحصى التي أخذها Y من X وأضيفها إلى Z،
SYY[ X ] → X[ Y ] + [ Y ] → Y[ Z ] → Zعدد الحصى التي أخذها Y من S وأضيفها إلى Y، مما يضاعف عدد Y
SYZ[ X ] → X[ Y ] → Y[Z] + [Y] → [Z]عدد الحصى التي أخذها Y من S وأضيفها إلى Z

بعض الملاحظات حول نموذج ميلزاك :

  1. إذا كانت جميع الثقوب تبدأ بالصفر، فكيف نزيدها؟ من الواضح أن هذا غير ممكن؛ يجب أن يحتوي كل ثقب على حصاة واحدة.
  2. يحدث "القفز" الشرطي في كل حالة من النوع XYZ لأنه: إذا تعذر تنفيذه لأن X لا يحتوي على عدد كافٍ من العدادات/الحصى، فسيتم تنفيذ القفز؛ وإلا إذا كان من الممكن تنفيذه فسيتم ذلك وتستمر التعليمات إلى التالي في التسلسل.
  3. لا يمكن أن يتسبب كل من SXY و XXY في حدوث قفزة لأنه يمكن تنفيذهما دائمًا.
  4. يُضيف ميلزاك التوجيه غير المباشر إلى نموذجه (انظر آلة الوصول العشوائي ) ويُقدّم مثالين على استخدامه، لكنه لا يُسهب في شرحه. وهذه هي أول حالة موثقة لـ"التوجيه غير المباشر" تظهر في الأدبيات العلمية.
  5. تم استلام كلتا الورقتين - ورقة ز. ألكسندر ميلزاك ( الفائز في مسابقة ويليام لويل بوتنام الرياضية عام 1950) في 15 مايو 1961 وورقة يواكيم لامبيك التي تم استلامها بعد شهر في 15 يونيو 1961 - في نفس المجلد، واحدة تلو الأخرى.  
  6. هل ادعاء ميلزاك صحيح؟ – أن هذا النموذج "بسيط للغاية لدرجة أن طريقة عمله يمكن أن يفهمها طفل عادي في المدرسة بعد شرح لبضع دقائق" (ص 282)؟ على القارئ أن يقرر. 

1961: نموذج لامبيك "المعداد": تبسيط نموذج ميلزاك إلى X+ و X- مع الاختبار

النموذج الأصلي لـ "المعداد" من لامبيك (1962):

يشير لامبيك إلى ورقة ميلزاك البحثية. ويُجزّئ عملية ميلزاك الوحيدة ذات الثلاثة مُعاملات (أربعة في الواقع إذا احتسبنا عناوين التعليمات) إلى عملية زيادة ذات مُعاملين "X+" وعملية إنقاص ذات ثلاثة مُعاملات "X-". كما يُقدّم تعريفًا رسميًا وغير رسمي لـ "البرنامج". هذا الشكل مُطابق تقريبًا لنموذج مينسكي (1961)، وقد اعتمده بولوس، وبرجس ، وجيفري (2007 ، ص 45، في كتاب "قابلية الحوسبة باستخدام المعداد") . 

فعل:وصف:
أ. X+ (r, I a ) [ r ] + 1 → r; انتقل إلى التعليمات I a . قم بزيادة (أضف 1 إلى) محتويات السجل r
ب. X- (r, I a , I b ) إذا كانت قيمة [r] ≤ 0، فانتقل إلى الدالة Ib، وإلا فإن [r] - 1 → r وانتقل إلى الدالة Ia .اختبر أولاً ما إذا كان القيمة صفرًا، ثم أنقص (اطرح 1 من) محتويات السجل r

نموذج المعداد لبولوس وبرجس وجيفري : [ 5 ]

في الطبعات المختلفة التي بدأت عام 1970، استخدم المؤلفون نموذج لامبيك (1961) لـ "المعداد اللانهائي". تستخدم سلسلة مقالات ويكيبيديا هذه رموزهم، على سبيل المثال "[ r ] +1 → r" "يتم استبدال محتويات السجل المحدد بالرقم 'r'، بالإضافة إلى 1، بمحتويات السجل رقم 'r'".

يستخدمون اسم لامبيك "المعداد" لكنهم يتبعون نموذج ميلزاك "الحصاة في الثقوب"، مع تعديلهم له ليصبح نموذج "الأحجار في الصناديق". ومثل نموذج المعداد الأصلي للامبيك، يحتفظ نموذجهم باستخدام مينسكي (1961) للتعليمات غير المتسلسلة - على عكس التنفيذ التسلسلي الافتراضي "التقليدي" للتعليمات الشبيهة بالحاسوب، فإن التعليمات التالية I a مضمنة داخل التعليمات. 

لاحظ، مع ذلك، أن BB و BBJ لا تستخدمان متغيرًا "X" في الاختصارات مع معلمة تحديد (كما هو موضح في إصدار Lambek) --أي "X+" و "X-" -- ولكن بدلاً من ذلك تحدد اختصارات التعليمات السجلات نفسها، على سبيل المثال "2+" أو "3-": 

فعل:وصف:
أ1. 1+ (I a ) [ r1 ] + 1 → r1 ثم انتقل إلى التعليمات I a . قم بزيادة (أضف 1 إلى) محتويات السجل رقم 1
ب1. 1- (I a , I b ) إذا كان [ r1 ] ≤ 0 فانتقل إلى I b وإلا [ r1 ] -1 → r1 وانتقل إلى I a . انتقل إلى التعليمة I b إذا كانت محتويات المسجل r1 تساوي صفرًا، وإلا فقم بإنقاص (طرح 1 من) محتويات المسجل رقم 1

1963: نموذج شيبردسون وستورجيس

يشير شيبردسون وستورجيس (1963) إلى مينسكي (1961) كما ظهر لهما في شكل تقرير من مختبر لينكولن التابع لمعهد ماساتشوستس للتكنولوجيا :

في القسم 10 نوضح أن النظريات (بما في ذلك نتائج مينسكي [21، مرجعهم]) حول حساب الدوال التكرارية الجزئية بواسطة شريط واحد أو شريطين يمكن الحصول عليها بسهولة من أحد أشكالنا الوسيطة.

يتأثر نموذجهم بشدة بنموذج وروح هاو وانغ (1957) [ 6 ] وآلة وانغ بي الخاصة به (انظر أيضًا آلة ما بعد تورينغ ). ويمكن تلخيص ذلك بقولهم:

...لقد حاولنا المضي خطوة أخرى في "التقارب" بين الجوانب العملية والنظرية للحوسبة التي اقترحها وبدأها وانغ.

آلة التسجيل غير المحدودة (URM) : [ 7 ] هذه الآلة، "الأكثر مرونة لديهم... تتكون من سلسلة قابلة للعد من المسجلات المرقمة من 1 إلى 3، ...، حيث يمكن لكل منها تخزين أي عدد طبيعي ... ومع ذلك، فإن كل برنامج معين لا يتضمن سوى عدد محدود من هذه المسجلات" (ص  219). بعبارة أخرى، عدد المسجلات غير محدود نظريًا، و"حجم" كل مسجل غير محدود أيضًا.

يقدمون مجموعة التعليمات التالية والملاحظات التالية: [ 1 ]

نموذج إدارة الموارد البشرية:فعل:وصف:
أ. P(n) [ r ] + 1 → r قم بزيادة (أضف 1 إلى) محتويات السجل r
ب. D(n) [ r ] - 1 → r قم بإنقاص (طرح 1 من) محتويات السجل r
ج:على)0 → rسجل r الصفري (المسح)
د.C(m,n)[ r j ] → rk , [ r j ] → r j ,انسخ محتويات السجل r j إلى السجل r k
هـ.J[E1]انتقل إلى "المخرج 1"الانتقال الفوري إلى "المخرج رقم 1"
و:J(r) [E1]إذا كان [rj ] = 0، فانتقل إلى "الخروج 1" [ 9 ] ، وإلا فانتقل إلى التعليمات التالية.إذا كانت محتويات السجل r تساوي 0، فانتقل إلى التعليمة "Exit 1" [ 9 ] ، وإلا فانتقل إلى التعليمة التالية.

ملحوظات.

  1. تم اختيار هذه المجموعة من التعليمات لسهولة برمجة حساب الدوال التكرارية الجزئية بدلاً من الاقتصاد؛ وقد تم توضيح ذلك في القسم 4 أن هذه المجموعة تعادل مجموعة أصغر.
  2. يوجد عدد لا نهائي من التعليمات في هذه القائمة لأن m و n [محتويات r j وما إلى ذلك] تتراوح على جميع الأعداد الصحيحة الموجبة.
  3. في التعليمات أ، ب، ج، د، من المفترض أن تبقى محتويات جميع السجلات باستثناء ن دون تغيير؛ في التعليمات هـ، و، تبقى محتويات جميع السجلات دون تغيير (ص  219).

في الواقع، توضح هذه الأمثلة كيفية تقليص هذه المجموعة أكثر، إلى ما يلي (لعدد لا نهائي من السجلات، كل منها بحجم لا نهائي):

تقليل نسبة التهم الموجهة ضد الأقليات:فعل:وصف:
أ1. P(r) [ r ] + 1 → r قم بزيادة (أضف 1 إلى) محتويات السجل r
ب1. D(n) [ r ] - 1 → r قم بإنقاص (طرح 1 من) محتويات السجل r
~f1:J(r) [E1]إذا كانت قيمة [r] لا تساوي صفرًا، فانتقل إلى "المخرج 1".إذا كانت محتويات السجل m لا تساوي صفرًا، فانتقل إلى تعليمة "الخروج 1"، وإلا فتابع.

آلة التسجيل المحدودة (LRM) : في هذه الآلة، يتم تقييدها بعدد محدود من المسجلات (N)، ولكن يُسمح أيضًا بإضافة أو إزالة المزيد من المسجلات إذا كانت فارغة (انظر الصفحة  228). ويُبين هذا أن تعليمة إزالة المسجل لا تتطلب بالضرورة وجود مسجل فارغ.

آلة التسجيل الأحادي (SRM) : هنا، يُطبّقون نظام الوسوم الخاص بإميل بوست، مما يسمح بالكتابة حتى نهاية السلسلة فقط والمسح من البداية. يظهر ذلك في الشكل 1 على هيئة شريط برأس قراءة على اليسار ورأس كتابة على اليمين، ولا يمكن تحريك الشريط إلا إلى اليمين. "A" هي "الكلمة" (ص  229).

أ. P(i)؛ أضف ai إلى نهاية A
ب. د؛ احذف الحرف الأول من أ
f'. Ji[E1] ;إذا بدأت A بـ ai، انتقل إلى المخرج 1.

كما يقدمون نموذجًا على شكل "مجموعة من البطاقات" بالرموز { 0، 1 } (ص  232 والملحق ج ص  248):

  1. أضف البطاقة في أعلى الصفحة المطبوعة 1
  2. أضف البطاقة في أعلى الصفحة المطبوعة 0
  3. قم بإزالة البطاقة السفلية؛ إذا طُبع عليها الرقم 1، فانتقل إلى التعليمات m، وإلا فانتقل إلى التعليمات التالية.

1967: "قاعدة مينسكي العالمية البسيطة لحاسوب البرنامج"

في النهاية، يلاحظ مينسكي في المسألة 11.7-1 أنه يمكن تشكيل العديد من قواعد الحساب من مجموعة صغيرة:

"تشكل العديد من التوليفات الأخرى لأنواع العمليات [0]، [']، [-]، [O-]، [→]، و[RPT] أساسًا عالميًا. أوجد بعضًا من هذا الأساس. ما هي توليفات العمليات الثلاث التي لا تُشكل أساسًا عالميًا؟ ابتكر بعض العمليات الأخرى..." [ 10 ]

فيما يلي تعريفات للتعليمات المختلفة التي يتناولها:

فعل:وصف:
أ.[ 0 ]0 → rسجل r الصفري (المسح)
ب.[ ' ][ r ] + 1 → rقم بزيادة (أضف 1 إلى) محتويات السجل r (الفاصلة العليا ' تعني "الخلف").
ج.[ - ]إذا كانت قيمة [r] تساوي صفرًا، فانتقل إلى التعليمة z، وإلا فانتقل إلى التعليمة التالية.اختبر المسجل r وانتقل إلى التعليمة z إذا كانت محتوياته صفرًا؛ وإلا، فقم بإنقاص (طرح 1 من) محتويات المسجل r
د.[ O- ]إذا كان [r] ≠ 0، فإن [r] - 1 → r، وإلا فانتقل إلى التعليمة التالية.إذا لم يكن محتوى المسجل r صفرًا، فقم بإنقاص محتوى المسجل r وانتقل إلى التعليمة رقم z، وإلا إذا كان صفرًا، فانتقل إلى التعليمة التالية.
هـ.[ → ][ r j ] → rk , [ r j ] → r jانسخ محتويات السجل r j إلى السجل r k
و.[تقرير]RPT a:[m,n]. لا يمكن للتكرار أن يعمل ضمن نطاقه الخاص.استمر حتى يصبح محتوى السجل [r] = 0: كرر التعليمات من m إلى n. عندما يصبح [r] = 0، انتقل إلى التعليمات التالية.
ز.[H]وقف
ح.goto(z)انتقل إلى التعليمات zالانتقال غير المشروط إلى التعليمات z
أنا.[ ≠ ]إذا كان [rj ] ≠ [rk ] ، فانتقل إلى التعليمة رقم z، وإلا فانتقل إلى التعليمة التالية.القفزة الشرطية: إذا كانت محتويات المسجل rj لا تساوي محتويات المسجل rk ، فانتقل إلى التعليمة z، وإلا فانتقل إلى التعليمة التالية.
ج.[RPT]*RPT a:[m,n]. يمكن أن تعمل خاصية التكرار ضمن نطاقها الخاص.* ملاحظة: يجب أن يكون RPT في سجل لانهائي

يبدأ مينسكي (1967) بنموذج يتكون من العمليات الثلاث بالإضافة إلى التوقف:

{ [ 0 ], [ ' ], [ - ], [ H ] }

يلاحظ أنه يمكننا الاستغناء عن [0] إذا سمحنا بسجل معين، مثلاً w، يكون "فارغًا" بالفعل. [ 11 ] ثم يضغط القيم الثلاث {[0]، [']، [-]} إلى قيمتين {[']، [-]}. [ 12 ]

لكنه يُقرّ بأن النموذج يصبح أسهل إذا أضاف بعض التعليمات [الزائفة] [O-] (المُدمجة من [0] و[-]) و"go(n)". يبني "go(n)" من السجل w المُهيأ مسبقًا إلى 0، بحيث يكون [O-] ( w , (n)) قفزة غير مشروطة.

في القسم 11.5 "تكافؤ آلات البرمجة مع الدوال العامة المتكررة"، يقدم روتينين فرعيين جديدين:

و. [ → ]
ج. [ ≠ ]
انتقل ما لم يكن الناتج مساويًا للقيمة المطلوبة: إذا كان [rj ] ≠ [rk ] ، فانتقل إلى التعليمة رقم z، وإلا فانتقل إلى التعليمة التالية.

ثم يشرح كيفية استبدال مجموعة "الخلف-السابق" {[0], ['], [-]} بمجموعة "الخلف-المساواة" {[0], ['], [≠]}. بعد ذلك، يُعرّف "التكرار" [RPT] ويُبيّن أنه يُمكننا تعريف أي دالة تكرارية أولية باستخدام مجموعة "الخلف-التكرار" {[0], ['], [RPT]} (حيث لا يشمل نطاق [RPT] نفسه. إذا شمله، نحصل على ما يُسمى عامل mu (انظر أيضًا دوال mu التكرارية ) (ص  213)).

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

1980: نموذج Schönhage ذو المعلمة 0 RAM0

قام شونهاج (1980) [ 13 ] بتطوير نموذجه الحسابي في سياق نموذج "جديد" أطلق عليه اسم نموذج تعديل آلة التخزين (SMM)، وهو نوع من آلات المؤشر . وصف تطويره نموذج ذاكرة الوصول العشوائي (RAM ) بمجموعة تعليمات مميزة لا تتطلب أي معاملات على الإطلاق، باستثناء ربما "القفزة الشرطية" (وحتى ذلك يمكن تحقيقه بدون معامل):

"...يستحق إصدار RAM0 اهتمامًا خاصًا لبساطته الشديدة؛ تتكون مجموعة التعليمات الخاصة به من عدد قليل من الرموز المكونة من حرف واحد فقط، دون أي عنونة (صريحة)" (ص 494)

إن الطريقة التي اتبعها شونهاج في ذلك مثيرة للاهتمام. فهو (أ) يجزئ السجل التقليدي "address:datum" إلى جزأين: "address" و"datum"، و(ب) يولد "address" في سجل محدد n يمكن لتعليمات آلة الحالة المحدودة (أي " رمز الآلة ") الوصول إليه ، و(ج) يوفر سجل "مجمع" z حيث ستتم جميع العمليات الحسابية.

يحتوي نموذج RAM0 الخاص به على عمليتين حسابيتين فقط : "Z" لضبط محتويات المسجل z إلى الصفر، و"A" لإضافة واحد إلى محتويات المسجل z . ويتم الوصول إلى مسجل العنوان n فقط عبر تعليمة نسخ من A إلى N تُسمى "ضبط العنوان n ". ولتخزين قيمة في المُراكم z في مسجل معين، يستخدم الجهاز محتويات n لتحديد عنوان المسجل، ويستخدم المسجل z لتوفير القيمة المراد إرسالها إليه. 

الخصائص المميزة: تتمثل إحدى الخصائص المميزة لذاكرة Schönhage RAM0 في طريقة "تحميل" البيانات في المسجل z : حيث يقوم المسجل z أولاً بتزويد عنوان المسجل، ثم يستقبل البيانات منه - وهو شكل من أشكال "التحميل" غير المباشر. أما الخاصية المميزة الثانية فتتمثل في مواصفات عملية المقارنة (COMPARE). فهي عبارة عن "قفزة" إذا كان المسجل z يساوي صفرًا (وليس، على سبيل المثال، "مقارنة محتويات z بمحتويات المسجل الذي يشير إليه n "). على ما يبدو، إذا فشل الاختبار، تتجاوز الآلة التعليمات التالية التي يجب أن تكون دائمًا على شكل "goto λ" حيث "λ" هو عنوان القفزة. تختلف هذه التعليمات - "مقارنة محتويات z بالصفر " - عن نموذج Schönhage RAM1 اللاحق (أو أي نماذج لاحقة أخرى معروفة) الذي يستخدم التعليمات الأكثر شيوعًا "مقارنة محتويات المسجل z بمحتويات المسجل a للتأكد من التساوي".  

لأغراض مرجعية في المقام الأول - هذا نموذج ذاكرة وصول عشوائي (RAM)، وليس نموذج آلة عداد - فيما يلي مجموعة تعليمات Schönhage RAM0:  

تعليماتفعل:وصف:
1Z0 → zمسح سجل المُراكم z
2أ[ z ] + 1 → zقم بزيادة محتويات سجل المُراكم z
3شمال[ z ] → n, [ z ] → z"تعيين العنوان n": انسخ محتويات المُراكم z إلى سجل العنوان n
4ل[ [ z ] ] → zانسخ بشكل غير مباشر محتويات السجل الذي يشير إليه المُراكم z إلى المُراكم z
5S[ z ] → [ n ]قم بتخزين محتويات المُراكم z بشكل غير مباشر في السجل الذي تشير إليه محتويات سجل العنوان n
6جإذا كانت قيمة [ z ] تساوي 0، فتجاوز التعليمات التالية (والتي يجب أن تكون تعليمات goto I λ ).إذا كانت قيمة المُراكم z تساوي صفرًا، فتجاوز التعليمات التالية، وإلا فتابع.
7انتقل إلى I λتعليمة الانتقال غير المشروطة (goto) I λتعليمة الانتقال غير المشروطة (goto) I λ

مرة أخرى، مجموعة التعليمات المذكورة أعلاه مخصصة لجهاز الوصول العشوائي ، وجهاز ذاكرة الوصول العشوائي - جهاز عداد مع عنونة غير مباشرة؛ تسمح التعليمات "N" بالتخزين غير المباشر للمراكم، وتسمح التعليمات "L" بالتحميل غير المباشر للمراكم. 

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

مراجع

  1. 1 2 Shepherdson & Sturgis 1963 ، ص. 219.
  2. ↑ Shepherdson & Sturgis 1963 ، ص 246.
  3. ↑ مينسكي 1961 ، ص 437.
  4. ↑ انظر مينسكي 1961 ، ص 449
  5. ↑ Boolos, Burgess & Jeffrey 2007 , ص. 45, Abacus Computability.
  6. ↑ وانغ 1957 .
  7. ↑ انظر أيضًا كاتلاند 1980 ، ص 9
  8. ↑ كاتلاند 1980 ، ص 11.
  9. 1 2 فهم: "انتقل إلى "رقم التعليمات E1" [ 8 ]
  10. ↑ مينسكي 1967 ، ص 214.
  11. ↑ مينسكي 1967 ، ص 206.
  12. ↑ مينسكي 1967 ، ص 255 وما بعدها.
  13. ↑ شونهاج 1980 .

فهرس

  • بولوس، جورج ؛ بورغيس، جون ب .؛ جيفري، ريتشارد (2007) [1974]. الحوسبة والمنطق (  الطبعة الخامسة). كامبريدج، إنجلترا: مطبعة جامعة كامبريدج . ISBN 978-0-521-87752-7.قام بورغيس بتنقيح نص بولوس-جيفري الأصلي بشكل موسع، ليصبح أكثر تقدماً من مجرد كتاب تمهيدي. وقد تم تطوير نموذج "آلة المعداد" بشكل موسع في الفصل الخامس " قابلية حساب المعداد " ؛ وهو أحد ثلاثة نماذج تمت معالجتها ومقارنتها بشكل شامل - آلة تورينج (التي لا تزال في شكلها الأصلي الرباعي لبولوس) والتكرار هما النموذجان الآخران.
  • إرشوف، ا ف ب (1958). "Ob Operatsionnykh algoritmakh" [ في خوارزميات المشغل ] . دوكلادي أكاديمي ناوك SSSR (بالروسية). 122 : 967 – 970.، "حول خوارزميات المشغل". الترجمة الآلية / البرمجة والترجمة (الترجمة الآلية السريعة) . 1 : 20-23 . 1959.
  • هيرميس، هانز (1954). "Die Universalität Programmgesteuerter Rechenmaschinen". الرياضيات-الفيزياء Semesterberichte (غوتنغن) (في المانيا). 4 : 42 - 53.
  • كافينجست، هاينز (1959). "Eine Abstrakte Programmgesteuerte Rechenmaschine". Zeitschrift für mathematische Logik und Grundlagen der Mathematik (باللغة الألمانية). 5 : 366 - 379.
  • كنوت، دونالد إي. (1973) [1968]. فن برمجة الحاسوب (  الطبعة الثانية). ريدينغ، ماساتشوستس: أديسون-ويسلي. الصفحات 462-463 . انظر الصفحات 462-463 حيث يُعرّف "نوعًا جديدًا من الآلات المجردة أو "الآلات الآلية" التي تتعامل مع الهياكل المرتبطة".
  • لامبيك، يواكيم (سبتمبر 1961). "كيفية برمجة عداد لانهائي". النشرة الرياضية . 4 (3): 295-302 .يقترح لامبيك في الملحق الثاني تعريفًا رسميًا لـ "البرنامج". ويشير إلى ميلزاك (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: أسس بسيطة جدًا للحوسبة . في الفصل الأول، يُعرّف "آلات البرمجة"، وفي الفصل الثاني، يناقش "آلات البرمجة الشاملة ذات سجلين" و"...ذات سجل واحد"، إلخ.
  • بيتر روزا (1958). “المخططات البيانية والوظائف المتكررة”. ديالكتيك (في المانيا). 12 : 373.
  • شونهاج، أرنولد (1980). "آلات تعديل التخزين". مجلة SIAM للحوسبة 9 ( 3). جمعية الرياضيات الصناعية والتطبيقية: 366-379 . doi : 10.1137/0209036 .حيث يوضح شونهاج تكافؤ SMM الخاص به مع "آلة الوصول العشوائي" (RAM) اللاحقة، إلخ.
  • شرويبل، ريتش (مايو 1972). آلة ذات عدادين لا تستطيع حساب 2N ( مذكرة الذكاء الاصطناعي). AIM-257. معهد ماساتشوستس للتكنولوجيا، مختبر الذكاء الاصطناعي. hdl : 1721.1/6202 .يشير المؤلف إلى مينسكي (1967) ويلاحظ أن " فرانسيس ياو أثبتت بشكل مستقل عدم قابلية الحساب باستخدام طريقة مماثلة في أبريل 1971".
  • فان إمده بواس، بيتر (1990). "نماذج ومحاكاة الآلات". في فان ليوين، يان (محرر). دليل علوم الحاسوب النظرية. المجلد أ: الخوارزميات والتعقيد (  الطبعة الأولى). مطبعة معهد ماساتشوستس للتكنولوجيا/إلسيفير. الصفحات 3-66 . ISBN  9780444880710.يُقدّم فان إمدي بواس تحليله لـ SMMs في الصفحات من 32 إلى 35. يُوضّح هذا التحليل ما ورد في دراسة شونهاج عام 1980 ، إذ يتبعها عن كثب مع توسيع طفيف لها. قد يكون من الضروري الرجوع إلى كلا المرجعين لفهمٍ فعّال.

للمزيد من القراءة