نظریه محاسبات

نظریهٔ رایانش یا نظریهٔ محاسبات (به انگلیسی: Theory of computation) زمینهٔ وسیعی است که امکان و کارایی حل مسائل گوناگون به وسیلهٔ مدل‌های محاسباتی، با استفاده از الگوریتم‌ها را مورد مطالعه قرار می‌دهد.

این نظریه را به دو شاخهٔ عمده به‌صورت زیر تقسیم می‌کنند:

• نظریهٔ محاسبه‌پذیری یا قابلیت محاسبه
• نظریهٔ پیچیدگی

هر دو شاخهٔ فوق با مدل‌های صوری محاسبات سر وکار دارد.

تاریخچه

در علم رایانه نظری و ریاضیات نظریهٔ رایانش شاخه‌ای است که با توجه به مشکلات می‌توان به آن به عنوان یک مدل محاسبه با استفاده از یک الگوریتم پرداخت.

این نظریه را به دو شاخهٔ عمده به صورت زیر تقسیم می‌کنند:

• نظریهٔ محاسبه‌پذیری یا قابلیت محاسبه
• نظریهٔ پیچیدگی

هر دو شاخهٔ یادشده در بالا با مدل‌های صوری محاسبات سروکار دارد.

به منظور انجام یک مطالعه دقیق از محاسبات دانشمندان رایانه با انتزاع ریاضی رایانه به عنوان یک مدل محاسبه کار می‌کنند.

مدل‌های بسیاری در این زمینه وجود دارد ولی معمولاً مدل مورد بررسی ماشین تورینگ است.

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

ظرفیت حافظه به‌طور بالقوه بی‌نهایت یک ویژگی غیرمیسر است؛ در حالی که تصمیم‌های ماشین تورینگ نیاز به تنها مقدار محدودی از حافظه دارد.

بنابرین، هر مشکل که می‌تواند حل شود. تصمیم یک ماشین تورینگ را می‌توان با یک رایانه که دارای یک مقدار محدود از حافظه است، حل کرد.

شاخه‌ها

نظریهٔ ماشین‌ها

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

نظریهٔ زبان رسمی

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

نظریهٔ رایانش

معادلات نظریهٔ محاسبات در درجه اول با سؤال از میزان یک هم‌شکل قابل حل در یک رایانه است شروع می‌شود. یکی از نتایج مهم در نظریهٔ محاسبات این است که توقف، توسط یک ماشین تورینگ قابل حل نمی‌باشد. این مشکل یک نمونه از مشکلاتی است که تدوین و فرموله کردن آن با استفاده از یک ماشین تورینگ غیرممکن است. نظریه محاسبات مربوط به شاخه‌ای از منطق ریاضی به نام نظریهٔ بازگشت است که به عنوان مدل محاسبه تقلیل به مدل تورینگ است.

نظریهٔ پیچیدگی رایانشی

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

مدل‌های رایانش

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

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

• منطق ریاضی
• بنیان‌های ریاضیات
• پیچیدگی محاسباتی
• علوم نظری رایانه
• ماشین‌های تورینگ
• زبان‌های صوری
• استقراء ریاضی
• نظریه محاسبه‌پذیری

پانویس

• مایکل سیپسر، محمدحسن شیرعلی‌شهرضا، مقدمه‌ای بر نظریهٔ محاسبات، ناشر: دانشگاه یزد، ۱۳۸۶، ۴۳۲ ص
• https://web.archive.org/web/20080507073114/http://www.academist.ir/?p=631
• مقدمه‌ای بر زبان‌ها و نظریهٔ محاسبات (انگلیسی)

• Sudkamp, T. A. , An Introduction to the Theory of Computer Science, Languages and Machines, 3rd ed. , Pearson Education, Inc. , 2006. ISBN 0-321-32221-5 [۱]