المحاكاة (علوم الحاسوب)

في علم الحاسوب النظري ، المحاكاة هي علاقة بين أنظمة انتقال الحالة التي تربط الأنظمة التي تتصرف بنفس الطريقة بمعنى أن أحد الأنظمة يحاكي الآخر.

بشكل بديهي، يحاكي النظام نظامًا آخر إذا كان بإمكانه مطابقة جميع تحركاته.

يربط التعريف الأساسي الحالات داخل نظام انتقال واحد، ولكن يمكن تكييف هذا بسهولة لربط نظامي انتقال منفصلين عن طريق بناء نظام يتكون من الاتحاد المنفصل للمكونات المقابلة.

بالنظر إلى نظام انتقال الحالة المصنف (${\displaystyle S}$،${\displaystyle \Lambda }$، → ), حيث${\displaystyle S}$هي مجموعة من الحالات،${\displaystyle \Lambda }$هي مجموعة من التصنيفات و → هي مجموعة من الانتقالات المصنفة (أي مجموعة فرعية من${\displaystyle S\times \Lambda \times S}$), العلاقات${\displaystyle R\subseteq S\times S}$تكون المحاكاة إذا وفقط إذا كان لكل زوج من الحالات${\displaystyle (p,q)}$في${\displaystyle R}$وجميع العلامات λ في${\displaystyle \Lambda }$:

لو${\displaystyle p{\overset {\lambda }{\rightarrow }}p'}$ثم هناك${\displaystyle q{\overset {\lambda }{\rightarrow }}q'}$بحيث${\displaystyle (p',q')\in R}$

وبصورة مكافئة، من حيث التركيب العلائقي :

${\displaystyle R^{-1}\,;\,{\overset {\lambda }{\rightarrow }}\quad {\subseteq }\quad {\overset {\lambda }{\rightarrow }}\,;\,R^{-1}}$

بافتراض حالتين${\displaystyle p}$و${\displaystyle q}$في${\displaystyle S}$،${\displaystyle p}$يمكن محاكاتها بواسطة${\displaystyle q}$مكتوب${\displaystyle p\,\leq \,q}$، إذا وفقط إذا كانت هناك محاكاة${\displaystyle R}$بحيث${\displaystyle (p,q)\in R}$العلاقة${\displaystyle \leq }$يُطلق عليه اسم الترتيب المسبق للمحاكاة ، وهو اتحاد جميع عمليات المحاكاة:${\displaystyle (p,q)\in \,\leq \,}$متى بالضبط${\displaystyle (p,q)\in R}$لبعض عمليات المحاكاة${\displaystyle R}$.

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

ولايتان${\displaystyle p}$و${\displaystyle q}$يقال إنها متشابهة ، مكتوبة${\displaystyle p\leq \geq q}$، إذا وفقط إذا${\displaystyle p}$يمكن محاكاتها بواسطة${\displaystyle q}$و${\displaystyle q}$يمكن محاكاتها بواسطة${\displaystyle p}$وبالتالي، فإن التشابه هو المجموعة الجزئية المتناظرة القصوى من ترتيب المحاكاة، مما يعني أنه انعكاسي ومتناظر ومتعدٍ؛ ومن ثم فهو علاقة تكافؤ . مع ذلك، ليس بالضرورة أن يكون محاكاة، وفي الحالات التي لا يكون فيها محاكاة، يكون أعم من التشابه الثنائي (أي أنه مجموعة شاملة للتشابه الثنائي). ^{[ ملاحظة 3 ]} وللتأكد من ذلك، لنفترض تشابهًا يمثل محاكاة . بما أنه متناظر، فهو محاكاة ثنائية . يجب أن يكون إذن مجموعة جزئية من التشابه الثنائي، وهو اتحاد جميع المحاكاة الثنائية. ومع ذلك، من السهل ملاحظة أن التشابه دائمًا مجموعة شاملة للتشابه الثنائي. من هذا نستنتج أنه إذا كان التشابه محاكاة، فإنه يساوي التشابه الثنائي. وإذا كان يساوي التشابه الثنائي، فهو بطبيعة الحال محاكاة (لأن التشابه الثنائي محاكاة). لذلك، يكون التشابه محاكاة إذا وفقط إذا كان يساوي التشابه الثنائي. إذا لم يكن كذلك، فلا بد أن يكون مجموعته الشاملة الصارمة؛ ومن ثم علاقة تكافؤ أكثر خشونة بشكل صارم.

عند مقارنة نظامي انتقال مختلفين (S', Λ', →') و (S", Λ", →")، يمكن استخدام المفاهيم الأساسية للمحاكاة والتشابه من خلال تكوين التركيب المنفصل للآلتين، (S, Λ, →) مع S = S' ∐ S", Λ = Λ' ∪ Λ" و → = →' ∪ →", حيث ∐ هو عامل الاتحاد المنفصل بين المجموعات.

• نظام انتقال الحالة
• المحاكاة الثنائية
• عملية التوليد النقدي
• الدلالات التشغيلية

1. بارك، ديفيد (1981). "التزامن والأتمتة على المتتاليات اللانهائية" (ملف PDF) . في: ديوسن، بيتر (محرر). وقائع المؤتمر الخامس لـ GI، كارلسروه . سلسلة محاضرات في علوم الحاسوب . المجلد  104. سبرينغر-فيرلاغ . الصفحات 167-183 . doi : 10.1007/BFb0017309 . ISBN  978-3-540-10576-3.
2. فان جلابيك، آر جيه (2001). "طيف الزمن الخطي - طيف الزمن المتفرع 1: دلالات العمليات الملموسة والمتسلسلة". دليل جبر العمليات . إلسيفير. ص 3-99 .