دالة أكرمان

في البداية، في نظرية الحوسبة، دالة أكرمان، والتي سميت من بعد الرياضي الألماني فيلهلم أكرمان،  وهي من أحدث الأمثلة المكتشفة على الدوال الحسابية التي ليست دالة عودية بدائية. جميع الدوال البدائية العودية كاملة وقابلة للحساب، ولكن دالة أكرمان توضح أنه ليست كل الدوال الكلية القابلة للحساب بدائية عودية.

انظر كذلك

وفي السياق ذاته، قيمة هذه الدالة تتزايد بدرجة كبيرة جدا حتى من اجل قيم متغيرات صغيرة، فمثلا A(4،2) عدد صحيح متكون من 19،729 رقم عشري.

علاوةً على ذلك، بعد نشر أكرمان لدالته (التي كانت لها ثلاث متغيرات صحيحة موجبة)، عدلها الكثير من المؤلفين من بعده لتتناسب مع أغراضهم المختلفة، قد تشير «دالة أكرمان» إلى أي من الاشكال المختلفة للدالة الاصلية. واحدة من هاته الدوال وهي نسخة مشتركة فيما بينهم. وهي دالة أكرمان - بيتر ذات المتغيرين، وهي معرفة كما يلي:

دالة عودية بدائية