آلة مور

في نظرية الحوسبة ، تُعرَّف آلة مور بأنها آلة ذات حالات محدودة، حيث تُحدَّد قيم مخرجاتها الحالية بحالتها الراهنة فقط . وهذا يختلف عن آلة ميلي ، التي تُحدَّد قيم مخرجاتها بحالتها الراهنة وقيم مدخلاتها معًا. وكما هو الحال في آلات الحالات المحدودة الأخرى، تؤثر المدخلات في آلات مور عادةً على الحالة التالية. وبالتالي، قد تؤثر المدخلات بشكل غير مباشر على المخرجات اللاحقة، ولكن ليس على المخرجات الحالية أو المباشرة. سُميت آلة مور نسبةً إلى إدوارد ف. مور ، الذي طرح هذا المفهوم في بحثٍ نُشر عام ١٩٥٦ بعنوان " تجارب فكرية على الآلات التسلسلية". ^{[ ١ ]}

يمكن تعريف آلة مور بأنها مجموعة من ستة عناصر${\displaystyle (S,s_{0},\Sigma ,\Lambda ,\delta ,G)}$ويتكون مما يلي:

• مجموعة محدودة من الحالات${\displaystyle S}$
• حالة البداية (وتسمى أيضًا الحالة الابتدائية)${\displaystyle s_{0}}$وهو عنصر من${\displaystyle S}$
• مجموعة محدودة تسمى أبجدية الإدخال${\displaystyle \Sigma }$
• مجموعة محدودة تسمى أبجدية الإخراج${\displaystyle \Lambda }$
• دالة انتقالية${\displaystyle \delta :S\times \Sigma \rightarrow S}$ربط حالة ما وأبجدية الإدخال بالحالة التالية
• دالة إخراج${\displaystyle G:S\rightarrow \Lambda }$ربط كل حالة بالأبجدية الناتجة

يتحقق "التطور عبر الزمن" في هذا التجريد من خلال جعل آلة الحالة تستشير رمز الإدخال المتغير مع الزمن عند "نبضات المؤقت" المنفصلة.${\displaystyle t_{0},t_{1},t_{2},...}$والتفاعل وفقًا لتكوينها الداخلي في تلك اللحظات المثالية، أو جعل آلة الحالة تنتظر رمز الإدخال التالي (كما هو الحال في FIFO) والتفاعل كلما وصل.

يمكن اعتبار آلة مور نوعًا محدودًا من محولات الطاقة ذات الحالة المحدودة .

بما أن آلات مور وميلي كلاهما نوعان من الآلات ذات الحالة المحدودة، فإنهما يتمتعان بقدرة تعبيرية متساوية: يمكن استخدام أي من النوعين لتحليل لغة منتظمة .

الفرق بين آلات مور وآلات ميلي هو أن مخرج الانتقال في الأخيرة يتحدد من خلال مزيج من الحالة الحالية والمدخلات الحالية (${\displaystyle S\times \Sigma }$باعتبارها مجال${\displaystyle G}$)، بدلاً من الوضع الحالي فقط (${\displaystyle S}$باعتبارها مجال${\displaystyle G}$عند تمثيلها كمخطط حالة ،

• بالنسبة لآلة مور، يتم تصنيف كل عقدة (حالة) بقيمة إخراج؛
• بالنسبة لآلة ميلي، يتم تسمية كل قوس (انتقال) بقيمة الإخراج.

كل آلة مور${\displaystyle M}$وهي مكافئة لآلة ميلي بنفس الحالات والانتقالات ووظيفة الإخراج${\displaystyle G(s,\sigma )=G_{M}(\delta _{M}(s,\sigma ))}$، والذي يأخذ كل زوج من الحالة والمدخلات${\displaystyle (s,\sigma )}$وينتج${\displaystyle G_{M}(\delta _{M}(s,\sigma ))}$، أين${\displaystyle G_{M}}$يكون${\displaystyle M}$دالة الإخراج و${\displaystyle \delta _{M}}$يكون${\displaystyle M}$دالة الانتقال الخاصة بـ 's.

مع ذلك، لا يمكن تحويل كل آلة ميلي إلى آلة مور مكافئة. بعضها لا يمكن تحويله إلا إلى آلة مور مكافئة تقريبًا ، مع إزاحة المخرجات زمنيًا. ويعود ذلك إلى طريقة ربط تسميات الحالة بتسميات الانتقال لتشكيل أزواج المدخلات/المخرجات. لنفترض انتقالًا${\displaystyle s_{i}\rightarrow s_{j}}$من الولاية${\displaystyle s_{i}}$للتصريح${\displaystyle s_{j}}$المدخل الذي تسبب في الانتقال${\displaystyle s_{i}\rightarrow s_{j}}$يُصنّف الحافة${\displaystyle (s_{i},s_{j})}$. المخرج المقابل لهذا المدخل هو تصنيف الحالة${\displaystyle s_{i}}$[ ^{٢ ]} لاحظ أن هذه هي حالة المصدر للانتقال. لذا، بالنسبة لكل مُدخل، يكون الناتج مُحددًا مُسبقًا قبل استقبال المُدخل، ويعتمد فقط على الحالة الحالية. هذا هو التعريف الأصلي لإدوارد مور. ومن الأخطاء الشائعة استخدام مُصطلح الحالة ^.${\displaystyle s_{j}}$كناتج للانتقال${\displaystyle s_{i}\rightarrow s_{j}}$.

يتم تصنيفها حسب عدد المدخلات/المخرجات.

بسيط

تحتوي آلات مور البسيطة على مدخل واحد ومخرج واحد:

• كاشف الحواف باستخدام XOR
• آلة جمع ثنائية
• الأنظمة التسلسلية الموقوتة (شكل محدود من آلة مور حيث تتغير الحالة فقط عندما تتغير إشارة الساعة العالمية)

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

مثال عملي

تحتوي الشبكة التسلسلية على مدخل واحد ومخرج واحد. يصبح المخرج 1 ويبقى كذلك بعد ذلك عندما يكون هناك على الأقل مدخلان بقيمة 0 ومدخلان بقيمة 1.

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

الوضع الحالي	مدخل	الولاية التالية	الناتج
أ	0	د	0
	1	ب
ب	0	هـ	0
	1	ج
ج	0	F	0
	1	ج
د	0	جي	0
	1	هـ
هـ	0	ح	0
	1	F
F	0	أنا	0
	1	F
جي	0	جي	0
	1	ح
ح	0	ح	0
	1	أنا
أنا	0	أنا	1
	1	أنا

في ورقة مور البحثية لعام 1956 بعنوان " التجارب الفكرية على الآلات التسلسلية"، ^{[ 1 ]}${\displaystyle (n;m;p)}$الآلات (أو الأوتوماتا)${\displaystyle S}$تُعرَّف بأنها تمتلك${\displaystyle n}$الولايات،${\displaystyle m}$رموز الإدخال و${\displaystyle p}$رموز الإخراج. تم إثبات تسع نظريات حول بنية${\displaystyle S}$، وتجارب مع${\displaystyle S}$. لاحقاً، "${\displaystyle S}$أصبحت الآلات تُعرف باسم "آلات مور".

في نهاية الورقة، في قسم "مشاكل إضافية"، تم ذكر المهمة التالية:

تتمثل المشكلة الأخرى التي تلي ذلك مباشرة في تحسين الحدود الواردة في النظريتين 8 و 9.

تُصاغ نظرية مور رقم 8 على النحو التالي:

بافتراض قيمة عشوائية${\displaystyle (n;m;p)}$آلة${\displaystyle S}$إذا كان كل حالتين من حالاتها قابلتين للتمييز عن بعضهما البعض، فإنه يوجد اختبار بطول${\displaystyle {\tfrac {n(n-1)}{2}}}$الذي يحدد حالة${\displaystyle S}$في نهاية التجربة.

في عام 1957، أثبت AA Karatsuba النظريتين التاليتين، اللتين حلتا تمامًا مشكلة مور بشأن تحسين حدود طول التجربة لنظريته "8".

النظرية أ. إذا${\displaystyle S}$هو${\displaystyle (n;m;p)}$إذا كانت الآلة بحيث يمكن تمييز كل حالتين من حالاتها عن بعضهما البعض، فإنه يوجد تجربة متفرعة طولها على الأكثر${\displaystyle {\tfrac {(n-1)(n-2)}{2}}+1}$والتي من خلالها يمكن تحديد حالة${\displaystyle S}$في نهاية التجربة.

النظرية ب. يوجد${\displaystyle (n;m;p)}$آلة، كل حالتين منها قابلتان للتمييز عن بعضهما البعض، بحيث يكون طول أقصر التجارب التي تحدد حالة الآلة في نهاية التجربة مساوياً لـ${\displaystyle {\tfrac {(n-1)(n-2)}{2}}+1}$.

استُخدمت النظريتان أ و ب كأساس لعمل الطالب أ.أ. كاراتسوبا، في السنة الرابعة، بعنوان "حول مسألة من نظرية الأوتوماتا"، والذي تميز بشهادة تقدير في مسابقة أعمال الطلاب بكلية الميكانيكا والرياضيات بجامعة موسكو الحكومية عام 1958. قُدِّمت ورقة كاراتسوبا إلى مجلة " أوسبيخي مات. ناوك" في 17 ديسمبر 1958 ونُشرت هناك في يونيو 1960. ^{[ 3 ]}

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

• دائرة متزامنة
• آلة الدقيق
• آلة الحالة الخوارزمية
• النظام المستقل (الرياضيات)

• كونواي، جيه إتش (1971). الجبر المنتظم والآلات المحدودة . لندن: تشابمان وهول. ISBN 0-412-10620-5. Zbl 0231.94041 . 
• مور إي إف تجارب فكرية على الآلات التسلسلية. دراسات الأوتوماتا، حوليات دراسات الرياضيات ، 34، 129-153. مطبعة جامعة برينستون، برينستون، نيوجيرسي (1956).
• كاراتسوبا أ.أ. حل إحدى المسائل من نظرية الأوتوماتا المحدودة. أوسب. مات. ناوك، 15:3، 157-159 (1960).
• Karatsuba AA تجربة الإلكترون الآلي (الألماني). معلومات كيبرنتيك، 11، 611-612 (1975).
• قائمة أعمال كاراتسوبا البحثية .

آلة مور وميلي

• الوسائط المتعلقة بآلة مور على ويكيميديا ​​كومنز