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



قابل محاسبه بودن Reus, B. (2016). Limits of Computation: From a Programming Perspective. Springer 
پیدا کردن محدودیت‌های محاسبات نیازمند تعریفی دقیق از چیستی محاسبات است. منشا چیزی که امروز به عنوان نظریه_محاسبات می‌شناسیم به آلن_تورینگ ریاضی‌دان بریتانیایی برمی گردد که تعریفی از فعل محاسبه کردن ارائه داد. او که دستگاه محاسباتی که امروز به نام ماشین_تورینگ شناخته می‌شود را معرفی کرد، نشان داد که طبق تعریف او قطعاً حداقل یک تابع وجود دارد که نمی‌تواند در روش محاسبات پیشنهاد شده محاسبه شود. برای پیدا کردن محدودیت‌های محاسبات قدم اول پیدا کردن مسائلی است که حتی نمیتوان آن‌ها را در زمان و حافظه نامحدود محاسبه کرد.

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

مهم‌ترین کلاس‌های پیچیدگی بر اساس زمان 
 P: مساله‌هایی که حل آن‌ها در زمان چند جمله‌ای امکان‌پذیر است.
 NP: مجموعه‌ای از مساله‌های تصمیم هستند که در زمان چند جمله‌ای می‌توان به آن‌ها پاسخ بله داد.

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

محدودیت‌های فیزیکی محاسبات  
به‌طور معمول وقتی در مورد محدودیت‌های محاسبات پرسیده می‌شود ذهن افراد به سمت محدودیت‌های دستگاهی که برای انجام محاسبه استفاده می‌شود، می‌رود. محدودیت‌هایی که می‌تواند در این زمینه وجود داشته باشد می‌توانند از انواع مختلفی باشند: 
 محدودیت‌های ساخت قطعات: محدودیت‌هایی در قرار دادن در قرار دادن مواد روی سیلیکون در مقیاس بسیار کوچک با استفاده از تکنولوژی حاضر لیتوگرافی در نانوتکنولوژی وجود دارد که البته پیش‌بینی می‌شود در آینده پیشرفت‌هایی در این زمینه انجام گیرد.  
 محدودیت‌های اتصال: سیم‌های فلزی می‌توانند سریع یا با ظرفیت باشند اما نمی‌توانند هم زمان هر دو باهم باشند.
 محدودیت‌های ترانزیستورها: ترانزیستورها به دلیل ضخامت دی الکتریک خود دارای محدودیت هستند، چرا که در حال حاضر ضخامت دی الکتریک به مقیاس اتم رسیده‌است و از حدی کمتر نمی‌شود. این باعث محدودیت در ساخت پردازنده‌های قوی تر می‌شود. 
 محدودیت‌های طراحی: با توجه به افزایش پیچیدگی مدارهای مجتمع برای رسییدن به سرعت بیشتر و توان مصرفی کمتر استفاده از طراحی به کمک کامپیوتر(CAD) غیرقابل اجتناب است و هر طراحی جدید نیاز به ابزار CAD جدید دارد. در نتیجه الگوریتم‌های هوشمندانه برای بهره وری بهتر مورد نیاز است و محدودیت‌های نرم‌افزارهای CAD تأثیر مستقیم بر محدودیت محاسبات خواهد داشت.

منابع 

محدودیت‌ها محاسبات
نظریه محاسبات