آلة ميلي

آلة ميلي هي آلة ذات حالات محدودة في نظرية الحوسبة يتم تحديد مخرجاتها من قبل حالاتها الحالية ومدخلاتها. وهي تناقض في هذا جهاز مور، حيث يتم تحديد قيم مخرجات (Moore) وفقًا لحالته الحالية فقط. آلة ميلي هي محول قطعي محدود الحالة: حيث يكون هناك تحويلة واحدة لكل من الحالات والمدخلات في أغلب الأحيان.

التاريخ

سميت آلة ميلي باسم جورج ميلي ، الذي قدم الفكرة في ورقته البحثية المنشورة عام 1955 «طريقة لتركيب الدوائر المتسلسلة».

التعريف

يعرف جهاز ميلي من حيز سداسي (6-tuple) $(S,S_{0},\Sigma ,\Lambda ,T,G)$يتألف مما يلي:

• مجموعة محدودة من الحالات أو $S$
• حالة البدء (تسمى أيضًا الحالة الأولية) $S_{0}$وهو عنصر من $S$
• مجموعة منتهية تسمى أبجدية الإدخال $\Sigma$
• مجموعة منتهية تسمى أبجدية المخرجات $\Lambda$
• دالة الانتقال $T:S\times \Sigma \rightarrow S$ والتي تعين أزواجاً من الحالات والمدخلات إلى ما يُقابلها من الحالات المقابلة.
• وظيفة المخرجات $G:S\times \Sigma \rightarrow \Lambda$ والتي تعين أزواجاً من الحالات والمدخلات إلى ما يُقابلها من المخرجات.
• .

في بعض الصيغ، يتم دمج دالة الانتقال والإخراج في دالة واحدة $T:S\times \Sigma \rightarrow S\times \Lambda$

مقارنة بين آلات ميلي وآلات مور

1. تميل الآت ميلي لأن تكون ذات عدد أقل من الحالات:
   • مخرجات مختلفة على الأقواس ( n ² ) بدلاً من الحالات ( n ).
2. آلات مور أكثر أمانا:
   • تتغير المخرجات عند حافة التوقيت (دائمًا بعد دورة واحدة).
   • في أجهزة ميلي، يمكن أن يتسبب تغيير المدخلات في تغيير المخرجات بمجرد الانتهاء من الدارة المنطقية - وهي مشكلة كبيرة عندما يكون الجهازان مترابطين - قد تحدث ردود فعل غير متزامنة إذا لم يكن أحدهما دقيقًا.
3. تتفاعل آلات ميلي بشكل أسرع مع المدخلات:
   • تتفاعل في نفس الدورة - لا تحتاج إلى الانتظار لمدة لدورة توقيت.
   • في أجهزة مور، قد يكون من الضروري إجراء المزيد من الجهد المنطقي لفك تشفير الحالة إلى مخرجات - مما يعني المزيد من التأخير في البوابة بعد حافة التوقيت.

أمثلة

المبسط

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

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

المعقد

يمكن أن تحتوي آلات ميلي الأكثر تعقيدًا على مدخلات متعددة ومخرجات متعددة.

التطبيقات

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

آلات مور / ميلي، هي أنظمة أتمتة محدودة قطعية التي لها أيضا مخرجات مع نبضات المؤقت. بشكل مشابه لما تحتويه وحدات المعالجة المركزية الحديثة، وأجهزة الكمبيوتر، والهواتف المحمولة، والساعات الرقمية، والأجهزة / الآلات الإلكترونية الأساسية على نوع من أنواع الآلات المحدودة للتحكم فيها.

بعض الأمثلة على تطبيقات آلة ميلي:

• تصنيف الرقم
• آلات البيع
• إشارات المرور
• ماسح الباركود
• مضخات الغاز

انظر أيضًا

• دائرة التزامن

المراجع

• Mealy، George H. (1955). A Method for Synthesizing Sequential Circuits. Bell System Technical Journal. ص. 1045–1079.
• Holcombe، W.M.L. (1982). Algebraic automata theory. Cambridge Studies in Advanced Mathematics. مطبعة جامعة كامبريدج. ج. 1. ISBN:0-521-60492-3. Zbl:0489.68046. Holcombe، W.M.L. (1982). Algebraic automata theory. Cambridge Studies in Advanced Mathematics. مطبعة جامعة كامبريدج. ج. 1. ISBN:0-521-60492-3. Zbl:0489.68046. Holcombe، W.M.L. (1982). Algebraic automata theory. Cambridge Studies in Advanced Mathematics. مطبعة جامعة كامبريدج. ج. 1. ISBN:0-521-60492-3. Zbl:0489.68046.
• Roth، Charles H., Jr. (2004). Fundamentals of Logic Design. Thomson-Engineering. ص. 364–367. ISBN:0-534-37804-8.{{استشهاد بكتاب}}: صيانة الاستشهاد: أسماء متعددة: قائمة المؤلفين (link) Roth، Charles H., Jr. (2004). Fundamentals of Logic Design. Thomson-Engineering. ص. 364–367. ISBN:0-534-37804-8.{{استشهاد بكتاب}}: صيانة الاستشهاد: أسماء متعددة: قائمة المؤلفين (link) Roth، Charles H., Jr. (2004). Fundamentals of Logic Design. Thomson-Engineering. ص. 364–367. ISBN:0-534-37804-8.{{استشهاد بكتاب}}: صيانة الاستشهاد: أسماء متعددة: قائمة المؤلفين (link)
• Akhavi، Ali؛ Klimann، Ines؛ Lombardy، Sylvain؛ Mairesse، Jean؛ Picantin، Matthieu (2012). "On the finiteness problem for automaton (semi)groups". Int. J. Algebra Comput. ج. 22 ع. 6. arXiv:1105.4725. Bibcode:2011arXiv1105.4725A. Zbl:1280.20038.