آلة الحالة المحدودة المتصلة

لأي عدد صحيح موجب${\displaystyle N}$، بروتوكول ^{[ 1 ] : 3} مع${\displaystyle N}$العملية (العمليات) هي رباعية${\displaystyle \{(S_{i})_{i=1}^{N},\ (o_{i})_{i=1}^{N},\ (M_{i,j})_{i,j=1}^{N},\ ({\mathtt {succ}})_{i=1}^{N}\}}$مع:

• ${\displaystyle (S_{i})_{i=1}^{N}}$، سلسلة من${\displaystyle N}$المجموعات المنتهية المنفصلة. تُستخدم كل مجموعة لتمثيل عملية، وكل عنصر من عناصرها${\displaystyle S_{i}}$يمثل حالة محتملة لـ${\displaystyle i}$العملية رقم -th.
• ${\displaystyle (o_{i})_{i=1}^{N}}$(مع${\displaystyle o_{i}\in S_{i}}$)، وهو تسلسل يمثل الحالة الأولية لكل عملية.
• ${\displaystyle (M_{i,j})_{i,j=1}^{N}}$، سلسلة منتهية من${\displaystyle N^{2}}$مجموعات منتهية منفصلة بحيث كل مجموعة${\displaystyle M_{i,j}}$يمثل هذا الرسائل المحتملة التي يمكن إرسالها من العملية${\displaystyle i}$للمعالجة${\displaystyle j}$. لو${\displaystyle i=j}$، ثم${\displaystyle M_{i,j}}$فارغ.
• ${\displaystyle ({\mathtt {succ}})_{i=1}^{N}:S_{i}\times \bigcup _{j=1}^{N}\left(M_{j,i}^{[+]}\cup M_{i,j}^{[-]}\right)\mapsto S_{i}}$هي سلسلة من دوال الانتقال. كل دالة تُنمذج الانتقال الذي يمكن إجراؤه عن طريق إرسال أو استقبال أي رسالة. فيما يتعلق بالعملية${\displaystyle i}$، الرمز${\displaystyle [+]}$يُستخدم لتدوين رسالة يمكن استقبالها و${\displaystyle [-]}$رسالة يمكن إرسالها.

الدولة العالمية هي زوج${\displaystyle \langle S,C\rangle }$أين

• ${\displaystyle S=(s_{1},...,s_{N})}$هي مجموعة مرتبة من الحالات بحيث كل${\displaystyle s_{i}}$يمثل حالة من${\displaystyle i}$العملية رقم -th.
• ${\displaystyle C}$هو${\displaystyle N\times N}$مصفوفة بحيث كل${\displaystyle c_{i,j}\in C}$هو تسلسل فرعي من${\displaystyle M_{i,j}}$.

الحالة العالمية الأولية عبارة عن زوج${\displaystyle \langle O,\mathrm {E} \rangle }$أين

• ${\displaystyle O=(o_{1},...,o_{N})}$
• ${\displaystyle \mathrm {E} }$يُعرَّف بأنه${\displaystyle N\times N}$مصفوفة بحيث يكون لكل${\displaystyle i,j\in \{1,...,N\}}$،${\displaystyle E_{i,j}}$يساوي الكلمة الفارغة،${\displaystyle \epsilon }$.

هناك نوعان من الخطوات، خطوات يتم فيها استقبال الرسائل وخطوات يتم فيها إرسال الرسائل.

خطوة يتم فيها${\displaystyle j}$تستقبل العملية رسالة سبق إرسالها بواسطة${\displaystyle i}$العملية رقم -th هي زوج من الشكل $\left\langle (s_{1},\dots ,s_{j},\dots ,s_{n}),\left(\begin{array}{lll}c_{1,1}&\dots &c_{1,n}\\\dots &\dots &\dots \\\dots &m_{i,j}c_{i,j}&\dots \\\dots &\dots &\dots \\c_{n,1}&\dots &c_{n,n}\end{array}}\right)\right\rangle \vdash \left\langle (s_{1},\dots ,s'_{j},\dots ,s_{n}),\left(\begin{array}{lll}c_{1,1}&\dots &c_{1,n}\\\dots &\dots &\dots \\\dots &c_{i,j}&\dots \\\dots &\dots &\dots \\c_{n,1}&\dots &c_{n,n}\end{array}}\right)\right\rangle }$متى${\displaystyle {\mathtt {succ}}_{i}(s_{j},+m_{i,j})=s'_{j}}$، مع${\displaystyle m'_{i,j}\in M_{i,j}}$وبالمثل، فإن الزوج الذي يتم فيه إرسال رسالة بواسطة${\displaystyle i}$العملية رقم -th إلى${\displaystyle j}$الزوج رقم -th هو زوج من الشكل $\left\langle (s_{1},\dots ,s_{i},\dots ,s_{n}),\left(\begin{array}{lll}c_{1,1}&\dots &c_{1,n}\\\dots &\dots &\dots \\\dots &c_{i,j}&\dots \\\dots &\dots &\dots \\c_{n,1}&\dots &c_{n,n}\end{array}}\right)\right\rangle \vdash \left\langle (s_{1},\dots ,s'_{i},\dots ,s_{n}),\left(\begin{array}{lll}c_{1,1}&\dots &c_{1,n}\\\dots &\dots &\dots \\\dots &m_{i,j}c_{i,j}&\dots \\\dots &\dots &\dots \\c_{n,1}&\dots &c_{n,n}\end{array}}\right)\right\rangle }$متى ${\displaystyle {\mathtt {succ}}_{i}(s_{i},-m_{i,j})=s'_{i}}$

التسلسل هو سلسلة من الحالات العالمية بحيث تربط كل خطوة حالة بالحالة التالية، وتكون الحالة الأولى هي الحالة الابتدائية.

يقال إن الدولة العالمية${\displaystyle \langle S,C\rangle }$يمكن الوصول إليها إذا كان هناك مسار يمر عبر هذه الحالة.

لقد ثبت، منذ طرح هذا المفهوم، أنه عندما تتواصل آلتان محدودتا الحالة بنوع واحد فقط من الرسائل، يمكن تحديد حالة التقييد، وحالات التعطل، وحالة الاستقبال غير المحددة، بينما لا يكون الأمر كذلك عندما تتواصل الآلتان بنوعين أو أكثر من الرسائل. لاحقًا، ثبت أيضًا أنه عندما تتواصل آلة محدودة الحالة واحدة فقط بنوع واحد من الرسائل، بينما يكون تواصل شريكتها غير مقيد، فإنه لا يزال بإمكاننا تحديد حالة التقييد، وحالات التعطل، وحالة الاستقبال غير المحددة. ^{[ 2 ]}

وقد ثبت كذلك أنه عندما تكون علاقة أولوية الرسائل فارغة، يمكن تحديد التقييد، والتعطل، وحالة الاستقبال غير المحددة حتى في حالة وجود نوعين أو أكثر من الرسائل في الاتصال بين الآلات ذات الحالة المحدودة. ^{[ 4 ]}

يمكن حسم مسائل التقييد، والانسداد، وحالة الاستقبال غير المحددة في وقت متعدد الحدود (مما يعني أنه يمكن حل مشكلة معينة في وقت معقول، وليس غير محدود) لأن مسائل القرار المتعلقة بها هي مسائل كاملة غير حتمية في فضاء لوغاريتمي. ^{[ 2 ]}

نظام القناة هو في جوهره نسخة من آلة الحالة المحدودة المتصلة، حيث لا تُقسّم الآلة إلى عمليات منفصلة. وبالتالي، توجد حالة واحدة فقط، ولا يوجد أي قيد يحدد النظام الذي يمكنه القراءة/الكتابة على أي قناة.

بصورة رسمية، بالنظر إلى بروتوكول${\displaystyle \langle (S_{i})_{i=1}^{n},(o_{i})_{i=1}^{n},(M_{i,j})_{i,j=1}^{n},({\mathtt {succ}})_{i}\rangle }$، ونظام القنوات المرتبط به هو${\displaystyle \langle \prod (S_{i})_{i=1}^{n},(o_{i})_{i=1}^{n},\bigcup _{i,j=1}^{n}(M_{i,j}),\Delta \rangle }$، أين${\displaystyle \Delta }$هي مجموعة${\displaystyle ((s_{1},\dots ,s_{j},\dots ,s_{n}),?m_{i,j},(s_{1},\dots ,{\mathtt {succ}}_{j}(s_{j},+m_{i,j}),\dots ,s_{n})}$و من${\displaystyle ((s_{1},\dots ,s_{i},\dots ,s_{n}),!m_{i,j},(s_{1},\dots ,{\mathtt {succ}}_{i}(s_{i},-m_{i,j}),\dots ,s_{n})}$.