آلة الدقيق

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

سميت آلة ميلي نسبة إلى جورج إتش. ميلي ، الذي قدم المفهوم في ورقة بحثية عام 1955 بعنوان "طريقة لتوليف الدوائر التسلسلية". ^{[ 1 ]}

آلة ميلي هي عبارة عن مجموعة من 6 عناصر${\displaystyle (S,S_{0},\Sigma ,\Lambda ,T,G)}$ويتكون مما يلي:

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

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

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

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

يربط مخطط الحالة لآلة ميلي قيمة الإخراج بكل حافة انتقال، على عكس مخطط الحالة لآلة مور، الذي يربط قيمة الإخراج بكل حالة.

عندما تكون أبجدية الإدخال والإخراج من النوع Σ ، يمكن ربط آلة ميلي برسم بياني موجه حلزوني ( S × Σ، ( x , i ) → ( T ( x , i ), G ( x , i ))) . ^{[ 2 ]} يتكون هذا الرسم البياني من أزواج من الحالات والحروف، حيث تكون درجة خروج كل عقدة واحدًا، ويكون العقدة التالية للعقدة ( x , i ) هي الحالة التالية للآلة والحرف الذي تُخرجه الآلة عندما تكون في الحالة x وتقرأ الحرف i . يكون هذا الرسم البياني اتحادًا لدورات منفصلة إذا كانت الآلة قابلة للانعكاس الثنائي .

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

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

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

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

• دائرة متزامنة
• آلة مور
• آلة الحالة الخوارزمية
• ريتشاردز كونترولر

• ميلي، جورج هـ. (1955). طريقة لتوليف الدوائر التسلسلية . مجلة بيل سيستم التقنية. ص 1045-1079 . 
• هولكومب، دبليو إم إل (1982). نظرية الأوتوماتا الجبرية . دراسات كامبريدج في الرياضيات المتقدمة. المجلد  1. مطبعة جامعة كامبريدج . ISBN 0-521-60492-3. Zbl 0489.68046 . 
• روث، تشارلز هـ. الابن (2004). أساسيات تصميم المنطق . تومسون للهندسة. الصفحات 364-367 . ISBN  0-534-37804-8.
• أخافي، علي؛ كليمان، إينيس؛ لومباردي، سيلفان؛ مايريس، جان؛ بيكانتين، ماثيو (2012). "حول مسألة التناهي لمجموعات (شبه) الأوتوماتون". المجلة الدولية للجبر والحساب . 22 (6). arXiv : 1105.4725 . Bibcode : 2011arXiv1105.4725A . doi : 10.1142/ S021819671250052X . S2CID 47518684. Zbl 1280.20038 .  

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