تابع اکرمن (Ackermann)

تابع اکرمن به‌ازای هر دو عدد صحیح و نامنفی $m$ و $n$ به صورت زیر تعریف می‌شود:

$$A(m,n)=\cases{n+1 &$m=0$\\A(m-1,1) &$m\geq 1$, $n=0$\\A(m-1,A(m,n-1)) &$m\geq 1$, $n\geq 1$}$$

علت شهرت این تابع، رشد بسیار بالای آن‌ است. آهنگ افزایش این تابع بازگشتی آن‌قدر زیاد است که با توابع چندجمله‌ای، فاکتوریل یا نمایی قابل مقایسه نیست. برای آشنایی بیشتر با این تابع بازگشتی، چند جمله‌ی اول آن را در نظر می‌گیریم:

$$A(0,0 ) = 1\\ A(0,1 ) = 2\\ A(0,2 ) = 3\\ A(0,3 ) = 4\\ A(0,4 ) = 5\\ A(1,0 ) = 2\\ A(1,1 ) = 3 \\A(1,2 ) = 4\\ A(1,3 ) = 5 \\A(1,4 ) = 6 \\A(2,0 ) = 3 \\A(2,1 ) = 5\\ A(2,2 ) = 7 \\A(2,3 ) = 9 \\A(3,0 ) = 5 \\A(3,1 ) = 13\\ A(3,2 ) = 29 \\A(4,0 ) = 13$$

با توجه به مقادیر بالا ممکن است فکر کنید که آهنگ افزایش این تابع آن‌قدرها هم زیاد نیست. اما حقیقت چیز دیگری است.

در واقع $A(4,1)=65533$ و حاصل $A(4,2)$ هم عددی 19729 رقمی است!

محاسبه‌ی مقدار $A(4,3)$ نیز تاکنون با پیشرفته‌ترین کامپیوترها امکان‌پذیر نشده است و مقادیر دیگر $A(m,n)$ وقتی $m\geq 4$ به مراتب بزرگ‌تر است. تابع اکرمن مثالی است برای نشان دادن اینکه کامپیوترهای سریع امروزی هنوز هم توان محاسبه‌ی مقدار متناهی برخی از توابع ریاضی را ندارند.