نظرية الحوسبة

نظرية الحوسبة أو النظرية الحسابية أو النظرية الاحتسابية (بالإنجليزية: Theory of Computation)‏ في علم الحاسوب يدرس إمكانية حل المسائل المطروحة بكفاءة بوساطة حاسوب ويدرس ما يمكن للحاسوب أن يقوم باحتسابة حاليا وإمكانية تطوره في المستقبل. لذلك يمكن تقسيمها إلى : نظرية الحاسوبية ونظرية نظرية التعقيد الحسابي. و كلاهما يتعاملان مع النماذج الرياضية للتحسيب. لإنجاز دراسة منهجية للتحسيب، يشكل علماء الحاسوب نماذج رياضية مجردة من الحواسيب تدعى نموذج التحسيب model of computation. توجد عدة أنماط من هذه النماذج قيد الاستعمال، لكن أهمها وأكثرها شيوعا هو آلة تورنغ. يمكن أن نتصور آلة تورنغ على أنها حاسوب منزلي مع سعة ذاكرة محدودة، ولايمكن الوصول إلا إلى قطاعات صغيرة متفرقة من هذه الذاكرة. تعتبر آلات تورنغ سهلة التصور والتصميم ومن الممكن تحليلها ودراستها للبرهنة عن النتائج المتوقعة بالتالي تمثل نموذجا معقولا لعملية التحسيب. شرط محدودية الذاكرة ضروري جدا لأن هذا ما يجعل آلة تورنغ واقعية، ويجعل تنبؤات آلة تورنغ مقبولة فأي مسألة يمكن حلها بوساطة آلة تورنغ يمكن حلها أيضا بوساطة أي حاسوب شخصي ذو ذاكرة كافية. في علم الحاسوب النظري والرياضيات، نظرية الحوسبة هي الفرع الذي يختص بفعالية حل المشاكل من خلال نموذج حوسبي باستخدام خوارزمية ما. ينقسم هذا المجال إلى ثلاثة أقسام رئيسية هي: نظرية التشغيل الذاتي واللغات، والنظرية الحاسوبية، ونظرية التعقيد الحسابي اللواتي يربطهن السؤال التالي: «ما هي الإمكانات والقيود الأساسية لأجهزة الحاسوب؟». من أجل إجراء دراسة دقيقة للحوسبة، يعمل علماء الحاسوب مع تجريد رياضي للحواسيب يسمى بنموذج الحوسبة. تُستخدم العديد من النماذج لكن أكثرها شيوعًا هي آلة تورنغ. يدرس علماء الحاسوب آلة تورنغ لأنها سهلة التشكيل، ويمكن تحليلها واستخدامها لإثبات النتائج، ولأنها تمثل ما يعتبره كثيرون أقوى نموذج حسابي «منطقي» ممكن. يبدو أن احتمالية وجود سعة ذاكرة لانهائية هي ميزة غير قابلة للتحقيق، لكن أي مشكلة يُقرر حلها عن طريق آلة تورنغ ستتطلب دائمًا كمية ذاكرة محدودة فقط. لذلك من حيث المبدأ، فإن أي مشكلة يمكن (تَقرّر) حلها عن طريق آلة تورنغ بالتالي يمكن حلها من خلال حاسوب يمتلك كمية محدودة من الذاكرة. تاريخها يمكن أن نعتبر أن نظرية الحوسبة هي إنشاء نماذج من جميع الأنواع في مجال علوم الحاسب. ولذلك يُستخدم فيها الرياضيات والمنطق. أصبحت في العقد الأخير قسمًا أكاديميًا مستقلًا وفُصلت عن الرياضيات. كان من ضمن الرائدين في نظرية الحوسبة رامون لول، ألونزو تشرتش، وكورت غودل، وآلان تورنغ، وستيفن كلين، وروزنا بيتر، وجون فون نيومان وكلود شانون.