رياضيدان به نام‌هاي ويلهام اكرمن و گابريل سودن كه در دانشگاه ديويد هيلبرت در رشته مباني محاسبات مطالعه و تحقيق مي‌كردند، تابعي به نام آكرمان ارائه كردند. اين تابع يك تابع بازگشتي درجه اول مثل فاكتوريل نيست، ولي آنها اثبات كردند با يك كامپيوتر، پردازشگر سريع و حافظه‌اي بزرگ مي‌توان آن را محاسبه كرد.
اين تابع به صورت زير تعريف مي‌شود.
اگر تابع را بررسي كنيم، متوجه مي‌شويم كه پس از هر مرحله براي m دو حالت اتفاق مي‌افتد:
1ـ مقدارش كم مي‌شود.
2ـ مقدار m تا زماني ثابت مي‌ماند كه مقدار n آنقدر كاهش بيابد تا به صفر برسد و از آن پس مقدار m كم مي‌شود.
پس مطمئن هستيم كه m بالاخره بعد از چند مرحله كاهش مي‌يابد تا به صفر برسد و سپس مقدار n يك واحد افزايش پيدا مي‌كند. وقتي m به صفر برسد، تابع آكرمن به جواب رسيده است. اما نكته اين است كه به ازاي تمامي مقادير ورودي m ميزان رشد n يكسان نيست و براي بعضي از مقادير m ميزان رشد n بشدت زياد خواهد بود. مثلا براي مقدار 3 ورودي براي m در مرحله nام خروجي تابع برابر 3- (3+n)2 مي‌شود. براي مقادير كوچك‌تر از 3خروجي، تابع از اين مقدار نيز كمتر مي‌شود اما براي مقادير بزرگ‌تر مساوي با 4 خروجي، تابع بسيار بزرگ مي‌شود. مثلا براي ورودي m برابر 4 و n برابر 4 مقدار تابع عددي برابر 3ـ2265533 مي‌شود كه عددي بسيار بزرگ است. همان طور كه مشخص است به ازاي مقادير بزرگ‌تر مساوي 4 ، رشد n بسيار زياد است و نمي‌توان آن را حساب كرد.
تابع آكرمن تك متغير
اگر تابع آكرمن را به صورت (Ackerman (n,n تعريف كنيم به يك تابع تك‌متغير تبديل مي‌شود كه رشد مقادير آن بسيار زياد است و نسبت به توابع ديگر تك‌متغير داراي رشد سريع‌تري است.
تابع معكوس آكرمن
اين تابع به صورت زير تعريف مي‌شود:
كه نسبت به خود تابع آكرمن رشد سريع تري دارد.
حال چگونه برنامه‌اي بنويسيم كه تابع آكرمن را به ازاي 2 مقدار ورودي حساب بكند؟ براي حساب كردن اين تابع در اينجا از 3 روش استفاده و سرانجام آنها را با هم مقايسه مي‌كنيم.
روش اول
روش اول به صورت بازگشتي است. يعني آنقدر تابع را فراخواني مي‌كنيم كه مقدار n به صفر برسد. كد اين روش به صورت زير است:
unsigned int naive_ackermann(unsigned int m, unsigned int n) {
calls++;
if (m == 0)
return n + 1;
else if (n == 0)
return naive_ackermann(m - 1, 1);
else
return naive_ackermann(m - 1, naive_ackermann(m, n - 1));
}
اين تابع ابتدا بررسي مي‌كند كه اگر m برابر صفر بود، مقدار n+1 را به خروجي برمي‌گرداند. در غير اين صورت آنقدر به صورت بازگشتي اجرا مي‌شود تا مقدار n به صفر برسد و اگر برابر صفر شد، تابع خودش را ورودي m -1 و 1 فراخواني مي‌كند.
روش دوم
روش دوم به صورت تكراري است. يعني براي محاسبه مقدار تابع از يك حلقه استفاده مي‌كنيم. اين روش تقريبا شبيه روش قبلي است. كد اين روش به صورت زير است:
unsigned int iterative_ackermann (unsigned int m, unsigned int n) {
calls++;
while (m != 0) {
if (n == 0) {
n = 1; }
else {
n = iterative_ackermann(m, n-1);}
m--;
}
return n + 1;
}
اين حلقه تا زماني اجرا مي‌شود كه مقدار m برابر صفر شود، شرط بازگشت به خود تابع اين است كه آرگومان n آن برابر صفر نشود. اگر تابع را با m و n صفر فراخواني بكنيم تابع n+1 را برمي‌گرداند. (البته اين روش تا حدودي شبيه به روش بازگشتي است به خاطر اين كه وقتي n ورودي برابر صفر نشود تابع دوباره به خودش باز مي‌گردد.)
روش سوم
روش سوم با استفاده از فرمول است. در اين روش ورودي‌ها ***** مي‌شوند و سپس نتايج مشابه آنها به خروجي مي‌رود. ممكن است اين روش يك مقدار ابتدايي باشد اما از آنجا كه اگر تابع آكرمن از يك مقداري بزرگ‌تر باشد براي كامپيوتر‌هاي شخصي غيرقابل محاسبه مي‌شود، پس نيازي به انجام محاسبات براي همه نوع ورودي‌ها نيست و از نتايجي كه ديگران به دست آورده‌اند استفاده مي‌شود. كد اين روش به صورت زير است:
unsigned int formula_ackermann(unsigned int m, unsigned int n) {
calls++;
while(1) {
switch(m) {
case 0: return n + 1;
case 1: return n + 2;
case 2: return (n «« 1) + 3;
case 3: return (1 «« (n+3)) - 3;
default:
if (n == 0) {
n = 1; }
else {
n = formula_ackermann(m, n - 1); }
m--;
break; }
}
}
همان طور كه مشخص است اين تابع براي برخي ورودي‌هاي خاص مقدار ثابت را كه از يك فرمول به دست آمده برمي‌گرداند و اگر خارج از آن محدوده باشد و كامپيوتر بتواند آن را حساب بكند براي محاسبه آن از مقادير قبلي استفاده مي‌كند. اما با مقايسه 3 روش بالا، همان طور كه از توضيحات بر مي‌آيد قطعا روش سوم سريع‌ترين راه است، حالا از روش‌هاي دوم و اول كدام بهتر است؟ براي جواب به اين سوال روش‌هاي فوق را با مقادير ? و ? به عنوان ورودي آزمايش مي‌كنيم.
نتيجه از اين قرار است:
Naive: 65533 (2862984010 calls)
Iterative: 65533 (1431459240 calls)
Formula: 65533 (2 calls)
همان طور كه مي‌بينيد ميزان فراخواني در تابع تكراري نسبت به تابع بازگشتي كمتر است، آيا براي همه نوع مقادير نيز به همين منوال است؟ جواب اين سوال به عهده خواننده گذاشته شده است.
