مدل محاسبه

در نظریه رایانش پذیری و نظریه پیچیدگی محاسباتی، مدل محاسبه مدلی است که نحوه محاسبه خروجی یک تابع ریاضی را با توجه به ورودی توصیف می‌کند. به بیانی دیگر مدل محاسبه تعریف مجموعه‌ای از عملیات‌های قابل قبول مورد استفاده در محاسبات و نسبت هزینه‌هایشان است. برای اندازه‌گیری پیچیدگی یک الگوریتم در زمان اجرا یا حافظهٔ مصرف شده، با فرض مدل خاصی از محاسبات استفاده می‌شود، در تجزیه و تحلیل منابع محاسباتی مورد نیاز بحث کردن در مورد محدودیت‌های الگوریتم یا رایانهها ممکن است. یک مدل نحوه سازماندهی واحدهای محاسبات، حافظه‌ها و ارتباطات را توصیف می‌کند.

مثال‌ها

بعضی از مثال‌ها عبارت اند از ماشین تورینگ، ماشین حالات متناهی، توابع بازگشتی، حساب دیفرانسیل لامبادا، منطق ترکیبی و چکیده سیستم بازنویسی.

استفاده‌ها

در زمینه زمان تحلیل الگوریتم‌ها، مشخص کردن یک مدل محاسبه در رابطه با عملیات اولیه مجاز دارای هزینه واحد معمول است. یک مثالی که به‌طور معمول استفاده می‌شود ماشین دستیابی تصادفی است، که دارای ارزش واحد برای خواندن و نوشتن دستیابی به همهٔ خانه‌های حافظه است. از این منظر، با ماشین تورینگی که در بالا گفته شده‌است تفاوت دارد.

در مهندسی مدل-رانده، مدل محاسبه توضیح می‌دهد که چگونه رفتار کل سیستم نتیجهٔ رفتار هر جزء آن است.

یک نکته اصلی که اغلب چشم پوشی می‌شود این است که حدود پایین منتشر شده برای مشکل‌ها در بیشتر مواقع برای یک مدل محاسباتی بیشتر محدود می‌شوند تا مجموعه عملیاتی که کسی می‌تواند استفاده کند در پرداختن و از این رو ممکن است الگوریتم‌هایی سریع تر از آنچه به سادگی فکر می‌کردیم وجود داشته باشد.

دسته‌بندی مدل‌ها

مدل محاسباتی بسیاری وجود دارد که در مجموعه اعمال مجاز و هزینه محاسباتشان تفاوت می‌کنند. مدل‌های محاسباتی را می‌توان به سه دسته تقسیم کرد: مدل‌های متوالی، مدل‌های عملکردی و مدل‌های همزمان.

مدل‌های متوالی

مدل‌های متوالی عبارتند از:

• ماشین حالات متناهی
• ماشین‌های پست (ماشین‌های پست تورینگ و ماشین‌های برچسب).
• اتوماتون پشته‌ای
• ماشین ثبت
  • ماشین دسترسی تصادفی
• ماشین‌های تورینگ
• مدل‌های درخت تصمیم‌گیری

مدل‌های کاربردی

مدل‌های کاربردی عبارتند از:

• سیستم‌های بازنویسی انتزاعی
• منطق ترکیبی
• توابع بازگشتی عمومی
• حساب لامبدا

مدل‌های همزمان

مدل‌های همزمان عبارتند از:

• مدل بازیگر
• اتوماتای سلولی
• شبکه‌های تعاملی
• شبکه‌های پردازش کان
• دروازه منطقی و مدارهای دیجیتال
• شبکه پتری
• جریان داده همزمان

برخی از این مدل‌ها دارای انواع قطعی و غیر قطعی هستند.

جستارهای وابسته

• ماشین پشته‌ای (ماشین ۰ عملوندی)
• انباشتگر (ماشین ۱ عملوندی)
• ماشین ثبت (۲٬۳،... ماشین عملوند)
• ماشین دسترسی تصادفی
• دستگاه انتزاعی
• مدل سلول-کاوشگر
• مدل پرس و جو رابرتسون-وب
• وراثت چامسکی
• کامل بودن تورینگ

برای مطالعهٔ بیشتر

• Fernández, Maribel (2009). Models of Computation: An Introduction to Computability Theory. Undergraduate Topics in Computer Science. Springer. ISBN 978-1-84882-433-1.
• Savage, John E. (1998). Models Of Computation: Exploring the Power of Computing. Archived from the original on 12 October 2016. Retrieved 26 June 2015.