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

نظرية الحسابية، والمعروفة أيضًا باسم نظرية الوظيفة العودية، هي فرع من المنطق الرياضي الذي يدرس خصائص الخوارزميات وأجهزة الحوسبة المرتبطة بها. وهي أساس علوم الكمبيوتر وترتبط ارتباطًا وثيقًا بالنظريات الأخرى في علوم الكمبيوتر النظرية مثل نظرية التعقيد ونظرية المعلومات الخوارزمية.

أساس نظرية الحسابية هو أطروحة تشيرش-تورينج، التي تنص على أن الوظيفة قابلة للحساب فقط إذا كان من الممكن حسابها بواسطة آلة تورينج. الدالة الحسابية هي أي خوارزمية أو صيغة أو قاعدة يمكن كتابتها وتقييمها على جهاز كمبيوتر. تعتمد جميع الخوارزميات المستخدمة في أجهزة الكمبيوتر على نظرية الحسابية.

تم تطوير النظرية من قبل عدد من الباحثين المختلفين، بدءاً بعمل آلان تورينج في ثلاثينيات القرن العشرين. وبحلول أواخر الخمسينيات من القرن العشرين، كانت النظرية قد تطورت جيدًا وتم تطبيقها في مجالات أخرى، مثل نظرية التشغيل الآلي، ولغات البرمجة، والذكاء الاصطناعي. مع تقدم تكنولوجيا الحوسبة، تقدمت أيضًا نظريات وتطبيقات نظرية الحوسبة.

تُستخدم نظرية الحسابية لتحليل تعقيد الخوارزميات وكيفية حلها، وكذلك لفهم القيود المفروضة على أجهزة الكمبيوتر. كما أنها تستخدم لإثبات صحة الخوارزميات. وأخيرا، يتم استخدامه لدراسة القيود المفروضة على التعبير وحساب الوظائف والمسندات.