نظریه محاسبه

از ویکی‌پدیا، دانشنامهٔ آزاد.

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

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

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

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

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

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

این نوشتار ناقص است. با گسترش آن به ویکی‌پدیا کمک کنید.