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

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

Definition

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

Scope

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

Sub-topics

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

Core questions

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

Key theories

معادل‌سازی تحت تز چرچ-تورینگ

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

واگرایی در کارایی

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

Clinical relevance

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

History

در دهه ۱۹۳۰، حساب لامبدای چرچ، توابع بازگشتی گودل و کلینی، و ماشین‌های تورینگ هر یک پیشنهاد شدند و سپس معادل بودن آن‌ها نشان داده شد. مدل‌های بعدی ابعاد جدیدی را اضافه کردند: پیچیدگی مدار، محاسبات موازی و سخت‌افزاری را رسمی کرد، و پیشنهاد فاینمن در سال ۱۹۸۲ برای شبیه‌سازی کوانتومی، مدل محاسبات کوانتومی را پایه‌گذاری کرد.

Key figures

• Alonzo Church
• Alan Turing
• Stephen Kleene
• Richard Feynman

Seminal works

• church1936
• sipser2013
• aroraBarak2009

Frequently asked questions

چرا باید مدل‌های زیادی را مطالعه کرد اگر آن‌ها توابع یکسانی را محاسبه می‌کنند؟

معادل‌سازی فقط برای آنچه اصولاً قابل محاسبه است، صادق است. مدل‌های مختلف بیان یا تحلیل چیزهای مختلف را آسان می‌کنند: حساب لامبدا برنامه‌نویسی تابعی را روشن می‌کند، مدارها موازی‌سازی و هزینه‌های سخت‌افزاری را آشکار می‌کنند، و مدل‌های کوانتومی پدیده‌های فیزیکی را به تصویر می‌کشند، بنابراین هر یک برای سؤالات مختلف لنز مناسبی هستند.

آیا همه مدل‌های محاسبات معادل هستند؟

همه مدل‌های کلاسیک معقول، کلاس یکسانی از توابع را محاسبه می‌کنند که از تز چرچ-تورینگ حمایت می‌کند. اما آن‌ها می‌توانند در کارایی بسیار متفاوت باشند، و مدل‌هایی که از منابع مختلفی مانند برهم‌نهی کوانتومی بهره می‌برند، ممکن است برخی مسائل را سریع‌تر حل کنند، حتی در حالی که توابع یکسانی را محاسبه می‌کنند.