آلة المؤشر

في علم الحاسوب النظري ، تُعرَّف آلة المؤشر بأنها آلة حسابية مجردة ذرية، وهيكل تخزينها عبارة عن رسم بياني . ويمكن أن تكون خوارزمية المؤشر خوارزميةً مقيدة بنموذج آلة المؤشر. ^{[ 1 ]}

تُسمى بعض أنواع آلات المؤشر الخاصة بآلة الربط، وآلة KU، وآلة SMM، وآلة LISP الذرية ، وآلة مؤشر الشجرة، وما إلى ذلك. ^{[ 2 ]}

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

يُدرج كلٌّ من غوريفيتش وبن عمرام عددًا من النماذج "الذرية" المتشابهة جدًا لـ"الآلات المجردة"؛ ^{[ 3 ] [ 2 ]} ويرى بن عمرام ضرورة التمييز بين "النماذج الذرية" ونماذج "المستوى العالي". وسيتم عرض النماذج الذرية التالية أدناه:

• آلات تعديل التخزين الخاصة بشركة Schönhage (SMM)، ^{[ 4 ]}
• آلات Kolmogorov-Uspenskii (KUM أو KU-Machines). ^{[ 5 ]}

كما يقدم بن عمرام الأصناف التالية، والتي لم يتم تناولها بمزيد من التفصيل في هذه المقالة:

• آلة ذرية نقية مكتوبة بلغة ليسب (APLM)
• آلة ذرية كاملة مكتوبة بلغة ليسب (AFLM)،
• آلات المؤشر الذري العامة،
• لغة جونز الأولى (نوعان).

يتبع العرض التقديمي التالي عرض فان إمدي بواس. ^{[ 6 ]}

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

يمكن بعد ذلك ترجمة كل كلمة من الرموز في الأبجدية إلى مسار عبر الآلة؛ على سبيل المثال، سيتم ترجمة 10011 إلى أخذ الحافة 1 من عقدة البداية، ثم الحافة 0 من العقدة الناتجة، ثم الحافة 0، ثم الحافة 1، ثم الحافة 1. وبالتالي، تحدد الكلمة عقدة، وهي العقدة النهائية للمسار، ولكن هذا التحديد سيتغير مع تغير الرسم البياني أثناء الحساب.

يمكن للجهاز تلقي تعليمات تُغير تخطيط الرسم البياني. التعليمات الأساسية هي:

(1) تعليمات w الجديدة ، التي تنشئ عقدة جديدة في نهاية المسار w ، مع توجيه جميع حوافها إلى العقدة قبل الأخيرة في w .

(2) تعليمة تعيين w إلى v التي تعيد توجيه حافة إلى عقدة مختلفة. هنا، w و v يمثلان كلمتين . تؤدي هذه التعليمة إلى تغيير وجهة الحافة الأخيرة في المسار w .

(3) إذا كانت v = w، فانتقل إلى التعليمة z  : تعليمة شرطية تقارن مسارين ممثلين بالكلمتين w و v لمعرفة ما إذا كانا ينتهيان عند نفس العقدة؛ إذا كان الأمر كذلك، فانتقل إلى التعليمة z، وإلا فتابع. تؤدي هذه التعليمة نفس وظيفة الأمر if في أي لغة برمجة إجرائية .

(4) قراءة وكتابة التعليمات للإدخال/الإخراج، والوصول إلى شريط إدخال للقراءة فقط وشريط إخراج للكتابة فقط، وكلاهما يحتوي على رموز الأبجدية.

لاحظ كنوت أن نموذج SMM يتطابق مع نوع من "الأتمتة الرابطة" التي تم شرحها بإيجاز في المجلد الأول من كتاب فن برمجة الحاسوب . ^{[ 4 ]}

يختلف KUM عن SMM في أنه يسمح فقط بالمؤشرات القابلة للعكس: فلكل مؤشر من العقدة x إلى العقدة y، يجب أن يكون هناك مؤشر معكوس من y إلى x، يحمل نفس الرمز. بعبارة أخرى، يكون مخطط التخزين غير موجه. ولأن المؤشرات الصادرة يجب أن تحمل رموزًا مختلفة من الأبجدية، فإن كلاً من مخططات KUM وSMM لها درجة صادرة ثابتة O(1). مع ذلك، فإن قابلية عكس مؤشرات KUM تحد من الدرجة الواردة إلى O(1) أيضًا. وهذا يُعالج بعض المخاوف المتعلقة بالواقعية الفيزيائية (على عكس الواقعية المعلوماتية البحتة).

هناك اختلافات أخرى طفيفة بين النماذج، مثل شكل البرنامج - جدول حالة بدلاً من قائمة التعليمات.

استخدام النموذج في نظرية التعقيد : يعرب فان إمدي بواس (1990) عن قلقه من أن هذا الشكل من النموذج المجرد هو:

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

كما أعرب غوريفيتش عن قلقه:

"من الناحية العملية، يوفر نموذج شونهاج مقياسًا جيدًا للتعقيد الزمني في ظل أحدث التقنيات (على الرغم من أنني أفضل شيئًا مشابهًا لأجهزة الكمبيوتر ذات الوصول العشوائي مثل أنجلوين وفاليانت)". ^{[ 7 ]}

يوضح شونهاج التكافؤات في الوقت الحقيقي لنوعين من آلات الوصول العشوائي مع SMM. ^{[ 4 ]}

الخوارزميات في نموذج SMM : يوضح شونهاج أن نموذج SMM يمكنه إجراء عملية ضرب الأعداد الصحيحة في وقت خطي. ^{[ 4 ]}

الاستخدامات المحتملة للنموذج : يتساءل غوريفيتش عما إذا كانت آلة KU المتوازية "تشبه إلى حد ما الدماغ البشري" ^{[ 8 ]}

الحوسبة المتوازية : جميع النماذج المذكورة أعلاه تسلسلية. وقد اقترح كوك وديموند نموذجًا متوازيًا (ذريًا) لآلة المؤشر؛ ^{[ 9 ]} كما تم استخدام نموذج عالي المستوى (غير ذري) لآلة المؤشر المتوازية ^{[ 10 ].}

آلة التسجيل — نموذج حسابي عام لآلة مجردة قائمة على التسجيل

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

آلة تورينج - نموذج حسابي عام لآلة مجردة تعتمد على الشريط

• آلة ما بعد تورينج - آلة بسيطة ذات شريط واحد، اتجاهين، رمز واحد { فارغ، علامة } تشبه آلة تورينج ولكن مع تنفيذ التعليمات التسلسلي الافتراضي بطريقة مشابهة لآلات عداد التعليمات الأساسية المكونة من 3 تعليمات.

توجد معظم المراجع وقائمة المصادر في مقالة " آلة التسجيل" . وفيما يلي ما يخص هذه المقالة تحديدًا:

• أمير بن عمرام (1995)، ما هي "آلة المؤشر"؟، أخبار SIGACT (مجموعة الاهتمام الخاصة التابعة لجمعية ACM حول الأوتوماتا ونظرية الحوسبة)، المجلد 26، 1995. حيث يصف بن عمرام الأنواع والأنواع الفرعية: (النوع 1أ) الآلات المجردة: النماذج الذرية بما في ذلك آلات كولموغوروف-أوسبنسكي (KUM)، وآلات تعديل التخزين لشونهاج (SMM)، و"أوتومات الربط" لكنوت، وAPLM وAFLM (آلة LISP النقية الذرية) و(آلة LISP الكاملة الذرية)، وآلات المؤشر الذرية العامة، ولغة جونز I؛ (النوع 1ب) الآلات المجردة: النماذج عالية المستوى، (النوع 2) خوارزميات المؤشر.
• يوري غوريفيتش (2000)، آلات الحالة المجردة المتسلسلة تلتقط الخوارزميات المتسلسلة ، معاملات ACM في المنطق الحسابي، المجلد 1، العدد 1، (يوليو 2000)، الصفحات 77-111. في جملة واحدة، يقارن غوريفيتش "آلات تعديل التخزين" لشونهاج [1980] بـ"آلات المؤشر" لكنوث. لمزيد من المعلومات، راجع نماذج مشابهة مثل "آلات الوصول العشوائي" التي يستشهد بها غوريفيتش.
  • جون إي. سافاج (1998)، نماذج الحوسبة: استكشاف قوة الحوسبة . أديسون ويسلي لونجمان.
• يوري غوريفيتش (1988)، حول آلات كولموغوروف والقضايا ذات الصلة ، عمود "المنطق في علوم الحاسوب"، نشرة الرابطة الأوروبية لعلوم الحاسوب النظرية، العدد 35، يونيو 1988، 71-82. قدم الوصف الموحد لآلات شونهاج وكولموغوروف-أوسبنسكي المستخدمة هنا.
• أرنولد شونهاج (1980)، آلات تعديل التخزين ، جمعية الرياضيات الصناعية والتطبيقية، مجلة SIAM للحوسبة، المجلد 9، العدد 3، أغسطس 1980. حيث يُظهر شونهاج تكافؤ آلة تعديل التخزين الخاصة به مع "آلة الوصول العشوائي" (RAM) اللاحقة، إلخ. ويشير إلى ورقة بحثية سابقة قدم فيها آلة تعديل التخزين:
  • أرنولد شونهاج (1970)، يونيفرسال تورينج Speicherung ، Automatentheorie und Formale Sprachen، Dörr، Hotz، eds. ببليوجر. معهد مانهايم، 1970، ص  69-383.
• بيتر فان إمدي بواس ، نماذج ومحاكاة الآلات ، الصفحات  3-66، المنشورة في:

يان فان ليوين (محرر). دليل علوم الحاسوب النظرية. المجلد أ: الخوارزميات والتعقيد ، مطبعة معهد ماساتشوستس للتكنولوجيا/إلسيفير، 1990. ISBN 0-444-88071-2(المجلد أ).

يُقدّم فان إمدي بواس تحليله لـ SMMs في الصفحات من 32 إلى 35. يُوضّح هذا التحليل ما ورد في دراسة شونهاج عام 1980، إذ يتبعه عن كثب مع توسيع طفيف له. قد يكون من الضروري الرجوع إلى كلا المرجعين لفهمٍ فعّال.