كتب official account forms

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

حسابات اللامدا

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

المنطق الإتحادي

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

دوال مايكرو المتغيرة

الحساب يتكون من الدالة المتكرره، تعني تعاقبها التعريفي، أي قيم(ه) مدخلة وتعاقب الدوال المتكررة تظهر في التعاقب التعريفي مع المدخلات والمخرجات. وهكذا، إذا كان التعاقب التعريفي لدلة متكررة د(س) فإن الدوال ر(س) وز(س) ستظهر، ثم قد تظهر بنود النموذج ر(5)=7 أو ز(3,2)=10. كل مدخل في هذا الترتيب يحتاج لأن يكون تطبيق للدالة الأساسية أو تابع للمدخلات بالأعلى عن طريق استخدام التكوين، التكرار الأولي أو دالة التكرار. على سبيل المثال إذا كانت د(س)=ز(س، ر(س))، إذاً ستظهر د(5)=3، ويجب أن تحدث بالأعلى بنود مثل ر(5)=6 وز(3,6)=3. تنتهي الحسابات فقط إذا كان البند الأخير يعطي قيمة الدالة المتكررة المطبقة على المدخلات.

خوارزمية ماركوف

هو نظام كتابة حرفي يستخدم قواعد شبيهة بالكتابة للعمل على سلسة من الرموز.

آلة التسجيل

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

أ"

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

آلة تورنغ

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

آلة تورنغ متعددة الشرائط

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

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

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

بعض النماذج الأخرى المقيدة للحساب تشمل:

آلة الوضع المتناهي القطعية

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

آلة الوضع المتناهي غير القطعية

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

مستودع معلومات الكومبيوتر الذاتي

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