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

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

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

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

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

تاریخچه

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

یکی از اهداف مهم این پیشگامان، بررسی مسائلی مانند برنامه هیلبرت و قضایای گودل بود که در منطق و مبانی ریاضی مطرح شده بود.

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

از دیگر نتایج قابل توجه اثبات تمیز ناپذیری منطق مرتبه اول بود که توسط چرچ ثابت شد.

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

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

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

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

منابع

• مایکل سیپسر، محمدحسن شیرعلی‌شهرضا، مقدمه‌ای بر نظریهٔ محاسبات، ناشر: دانشگاه یزد، ۱۳۸۶، ۴۳۲ ص
• 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 [۱]