عدم التحديد في الحوسبة المتزامنة

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

جادل باتريك هايز [1973] بأن "التمييز الحاد المعتاد بين عمليتي الحساب والاستنتاج مُضلل". وقد طور روبرت كوالسكي أطروحة مفادها أن الحساب يمكن أن يندرج ضمن الاستنتاج، واستشهد مُؤيدًا بعبارة "الحساب هو استنتاج مُتحكم به"، والتي نسبها إلى هايز في بحثه عام 1988 حول التاريخ المبكر للغة برولوج. وخلافًا لكوالسكي وهايز، ادعى كارل هيويت أن الاستنتاج المنطقي غير قادر على إجراء حسابات متزامنة في الأنظمة المفتوحة .

جادل كلٌّ من هيويت [1985] وآغا [1991]، وغيرهما من الباحثين المنشورين، بأن النماذج الرياضية للتزامن لا تُحدِّد العمليات الحسابية المتزامنة بشكلٍ مُحدَّد، وذلك على النحو التالي: يستخدم نموذج الممثل التحكيم (غالبًا في صورة مُحكِّمين افتراضيين ) لتحديد الرسالة التالية في ترتيب وصول الممثل الذي يتلقى رسائل متعددة في وقتٍ واحد. يُؤدي هذا إلى عدم تحديد ترتيب الوصول. وبما أن ترتيبات الوصول غير مُحدَّدة، فلا يُمكن استنتاجها من المعلومات المُسبقة باستخدام المنطق الرياضي وحده. لذلك، لا يُمكن للمنطق الرياضي تنفيذ الحساب المتزامن في الأنظمة المفتوحة.

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

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

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

ماذا تقول النظرية الرياضية للممثلين في هذا الشأن؟ يُعرَّف النظام المغلق بأنه النظام الذي لا يتواصل مع العالم الخارجي. توفر نظرية نموذج الممثل الوسائل اللازمة لتوصيف جميع العمليات الحسابية الممكنة لنظام ممثل مغلق باستخدام نظرية التمثيل [هيويت 2007] على النحو التالي:

يتم إيجاد الدلالة الرياضية التي يرمز إليها بنظام مغلق S من خلال بناء تقريبات أفضل بشكل متزايد من سلوك أولي يسمى ⊥ _S باستخدام سلوك يقارب تقدم الدالة _S لبناء دلالة (معنى) لـ S على النحو التالي:

${\displaystyle \mathbf {Denote} _{\mathtt {S}}\equiv \lim _{i\to \infty }\mathbf {progression} _{{\mathtt {S}}^{i}}(\bot _{\mathtt {S}})}$

وبهذه الطريقة، يمكن وصف سلوك S رياضياً من حيث جميع سلوكياته الممكنة (بما في ذلك تلك التي تنطوي على عدم حتمية غير محدودة).

لذا يمكن للمنطق الرياضي أن يصف (بدلاً من أن ينفذ) جميع العمليات الحسابية الممكنة لنظام الممثل المغلق.

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

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

جادل كارل هيويت وجول آغا [1991] بأن هذه الأنظمة المتزامنة الشبيهة بـ Prolog لم تكن استنتاجية ولا منطقية: مثل نموذج الممثل، كانت الأنظمة المتزامنة الشبيهة بـ Prolog تعتمد على تمرير الرسائل وبالتالي كانت عرضة لنفس عدم التحديد.

أكد هيويت أن درسًا أساسيًا يُمكن استخلاصه من لغة برولوج وأنظمة البرمجة المتزامنة الشبيهة بها: أن النموذج الشامل للحساب المتزامن محدودٌ بوجود أي تكلفة إضافية إلزامية في آليات الاتصال الأساسية. هذه حجة ضد تضمين الاستدعاء الموجه بالأنماط باستخدام التوحيد واستخراج الرسائل من تدفقات هياكل البيانات كعناصر أساسية. لكن قارن بدراسة شابيرو للغات البرمجة المتزامنة الشبيهة ببرولوج للاطلاع على حجج تدعم تضمينها.

يُعدّ التحكيم أساس عدم التحديد في نموذج الممثل للحوسبة المتزامنة (انظر تاريخ نموذج الممثل ونظرية نموذج الممثل ). وقد يلعب دورًا أيضًا في نماذج أخرى للأنظمة المتزامنة، مثل حسابات العمليات .

• الحوسبة الكمومية
• خوارزمية عشوائية
• آلة تورينج غير الحتمية

• كارل هيويت: ما هي الحوسبة؟ نموذج الممثل مقابل نموذج تورينج في كون قابل للحوسبة: فهم الحوسبة واستكشاف الطبيعة كحوسبة. مُهدى إلى ذكرى آلان م. تورينج في الذكرى المئوية لميلاده. حرره هيكتور زينيل. دار النشر العالمية العلمية. ٢٠١٢
• كارل هيويت. PLANNER: لغة لإثبات النظريات في الروبوتات IJCAI 1969.
• كارل هيويت. التضمين الإجرائي للمعرفة في المخطط IJCAI 1971.
• كارل هيويت، بيتر بيشوب، وريتشارد ستايجر. نموذج الممثل المعياري العالمي للذكاء الاصطناعي، المؤتمر الدولي المشترك للذكاء الاصطناعي 1973.
• روبرت كوالسكي، منطق المسند كلغة برمجة، مذكرة رقم 70، قسم الذكاء الاصطناعي، جامعة إدنبرة . 1973.
• بات هايز. الحساب والاستنتاج : الأسس الرياضية لعلوم الحاسوب: وقائع الندوة والمدرسة الصيفية، شتربسكي بليسو، جبال تاترا العليا، تشيكوسلوفاكيا، 3-8 سبتمبر 1973.
• كارل هيويت وهنري بيكر قوانين الاتصال بين العمليات المتوازية IFIP-77، أغسطس 1977.
• كارل هيويت. النظر إلى هياكل التحكم كأنماط لتمرير الرسائل. مجلة الذكاء الاصطناعي . يونيو 1977.
• هنري بيكر. أنظمة الممثلين للحوسبة في الوقت الحقيقي. أطروحة دكتوراه في قسم الهندسة الكهربائية وعلوم الحاسوب بمعهد ماساتشوستس للتكنولوجيا. يناير 1978.
• بيل كورنفيلد وكارل هيويت. استعارة المجتمع العلمي. معاملات IEEE في الأنظمة والإنسان وعلم التحكم الآلي . يناير 1981.
• ويل كلينجر. أسس دلالات الفاعلين. أطروحة دكتوراه في الرياضيات من معهد ماساتشوستس للتكنولوجيا. يونيو 1981.
• كارل هيويت. تحدي الأنظمة المفتوحة ، مجلة بايت، أبريل 1985. أعيد طبعه في كتاب أسس الذكاء الاصطناعي - كتاب مرجعي، مطبعة جامعة كامبريدج، 1990.
• غول آغا. الممثلون: نموذج للحوسبة المتزامنة في الأنظمة الموزعة . أطروحة دكتوراه. مطبعة معهد ماساتشوستس للتكنولوجيا. 1986.
• روبرت كوالسكي. حدود المنطق. وقائع المؤتمر السنوي الرابع عشر لجمعية آلات الحوسبة لعام 1986 حول علوم الحاسوب.
• إيهود شابيرو (محرر). برولوج المتزامن . مطبعة معهد ماساتشوستس للتكنولوجيا . 1987.
• روبرت كوالسكي. السنوات الأولى لبرمجة المنطق. اتصالات جمعية آلات الحوسبة . يناير 1988.
• إيهود شابيرو. عائلة لغات البرمجة المنطقية المتزامنة. مجلة ACM Computing Surveys . سبتمبر 1989.
• كارل هيويت وجول آغا. لغات جملة هورن المحمية: هل هي استنتاجية ومنطقية؟ المؤتمر الدولي لأنظمة حاسوب الجيل الخامس، أومشا 1988، طوكيو. موجود أيضًا في الذكاء الاصطناعي في معهد ماساتشوستس للتكنولوجيا ، المجلد 2، مطبعة معهد ماساتشوستس للتكنولوجيا، 1991.
• كارل هيويت. *كارل هيويت. الزوال المتكرر لبرمجة المنطق وسبب عودتها للحياة. ما الخطأ الذي حدث ولماذا: دروس من أبحاث وتطبيقات الذكاء الاصطناعي. تقرير فني SS-06-08. مطبعة AAAI. مارس 2006.

• هيويت، ماير، وشيبرسكي: نموذج الممثل (كل ما أردت معرفته، ولكنك كنت تخشى السؤال عنه) قناة مايكروسوفت 9. 9 أبريل 2012.