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

الموسوعة الحرة

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

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

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 ]

The various editions beginning with 1970 the authors use the Lambek (1961) model of an "infinite abacus". This series of Wikipedia articles is using their symbolism, e.g. " [ r ] +1 → r" "the contents of register identified as number 'r', plus 1, replaces the contents of [is put into] register number 'r' ".

They use Lambek's name "abacus" but follow Melzak's pebble-in-holes model, modified by them to a 'stones-in-boxes' model. Like the original abacus model of Lambek, their model retains the Minsky (1961) use of non-sequential instructions –unlike the "conventional" computer-like default sequential instruction execution, the next instruction Ia is contained within the instruction.

Observe, however, that B-B and B-B-J do not use a variable "X" in the mnemonics with a specifying parameter (as shown in the Lambek version) --i.e. "X+" and "X-" –but rather the instruction mnemonics specifies the registers themselves, e.g. "2+", or "3-":

Action:Description:
a1. 1+ (Ia) [ r1 ] + 1 → r1 then go to instruction Ia. Increment (add 1 to) contents of register #1
b1. 1- (Ia, Ib) If [ r1 ] ≤ 0 THEN go to Ib else [ r1 ] -1 → r1 and go to Ia. Jump to instruction Ib if contents of register r1 is zero ELSE decrement (subtract 1 from) contents of register #1

1963: Shepherdson and Sturgis' model

Shepherdson & Sturgis (1963) reference Minsky (1961) as it appeared for them in the form of an MIT Lincoln Laboratory report:

In Section 10 we show that theorems (including Minsky's results [21, their reference]) on the computation of partial recursive functions by one or two tapes can be obtained rather easily from one of our intermediate forms.

Their model is strongly influenced by the model and the spirit of Hao Wang (1957)[6] and his Wang B-machine (also see Post–Turing machine). They "sum up by saying":

...we have tried to carry a step further the 'rapprochement' between the practical and theoretical aspects of computation suggested and started by Wang.

Unlimited Register Machine URM:[7] This, their "most flexible machine... consists of a denumerable sequence of registers numbered 1, 2, 3, ..., each of which can store any natural number...Each particular program, however involves only a finite number of these registers" (p. 219). In other words, the number of registers is potentially infinite, and each register's "size" is infinite.

They offer the following instruction set and the following "Notes":[1]

URM model:Action:Description:
a. P(n) [ r ] + 1 → r Increment (add 1 to) contents of register r
b. D(n) [ r ] - 1 → r Decrement (subtract 1 from) contents of register r
c:O(n)0 → rZero (clear) register r
d.C(m,n)[ rj ] → rk, [ rj ] → rj,Copy contents of register rj to register rk
e.J[E1]Jump to "Exit 1"Unconditional jump to "Exit #1"
f:J(r) [E1]IF [ rj ] = 0 THEN jump to "Exit 1"[9] ELSE next instructionIF contents of register r = 0 then jump to instruction "Exit 1"[9] else next instruction

Notes.

  1. This set of instructions is chosen for ease of programming the computation of partial recursive functions rather than economy; it is shown in Section 4 that this set is equivalent to a smaller set.
  2. There are infinitely many instructions in this list since m, n [ contents of rj, etc.] range over all positive integers.
  3. In instructions a, b, c, d the contents of all registers except n are supposed to be left unchanged; in instructions e, f, the contents of all registers are unchanged (p. 219).

Indeed, they show how to reduce this set further, to the following (for an infinite number of registers each of infinite size):

Reduced URM:Action:Description:
a1. P(r) [ r ] + 1 → r Increment (add 1 to) contents of register r
b1. D(n) [ r ] - 1 → r Decrement (subtract 1 from) contents of register r
~f1:J(r) [E1]IF [ r ] ≠ 0 THEN jump to "Exit 1"If contents of register m ≠ 0 THEN jump to instruction "Exit 1" ELSE continue

Limited Register Machine LRM: Here they restrict the machine to a finite number of registers N, but they also allow more registers to "be brought in" or removed if empty (cf. p. 228). They show that the remove-register instruction need not require an empty register.

آلة التسجيل الأحادي (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.قام بورغيس بتنقيح نص بولوس-جيفري الأصلي بشكل موسع، ليصبح أكثر تقدماً من مجرد كتاب تمهيدي. وقد تم تطوير نموذج "آلة المعداد" بشكل موسع في الفصل الخامس " قابلية حساب المعداد " ؛ وهو أحد ثلاثة نماذج تمت معالجتها ومقارنتها بشكل شامل - آلة تورينج (التي لا تزال في شكلها الأصلي الرباعي لبولوس) والتكرار هما النموذجان الآخران.
  • Ershov, A. P. (1958). "Ob operatsionnykh algoritmakh" [On Operator Algorithms]. Doklady Akademii Nauk SSSR (in Russian). 122: 967–970., "On Operator Algorithms". Automatic Translation / Programming and Translation (Automat. Express). 1: 20–23. 1959.
  • Hermes, Hans (1954). "Die Universalität programmgesteuerter Rechenmaschinen". Mathematisch-Physikalische Semesterberichte (Göttingen) (in German). 4: 42–53.
  • Kaphengst, Heinz (1959). "Eine Abstrakte programmgesteuerte Rechenmaschine". Zeitschrift für mathematische Logik und Grundlagen der Mathematik (in German). 5: 366–379.
  • Knuth, Donald E. (1973) [1968]. The Art of Computer Programming (2nd ed.). Reading, Massachusetts: Addison-Wesley. pp. 462–463. Cf pages 462-463 where he defines "a new kind of abstract machine or 'automaton' which deals with linked structures."
  • Lambek, Joachim (September 1961). "How to Program an Infinite Abacus". Mathematical Bulletin. 4 (3): 295–302. In his Appendix II, Lambek proposes a "formal definition of 'program'. He references Melzak (1961) and Kleene (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 ، إذ يتبعها عن كثب مع توسيع طفيف لها. قد يكون من الضروري الرجوع إلى كلا المرجعين لفهمٍ فعّال.

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