2 رياضيدان به نام‌هاي ويلهام اكرمن و گابريل سودن كه در دانشگاه ديويد هيلبرت در رشته مباني محاسبات مطالعه و تحقيق مي‌كردند، تابعي به نام آكرمان ارائه كردند. اين تابع يك تابع بازگشتي درجه اول مثل فاكتوريل نيست، ولي آنها اثبات كردند با يك كامپيوتر، پردازشگر سريع و حافظه‌اي بزرگ مي‌توان آن را محاسبه كرد.
اين تابع به صورت زير تعريف مي‌شود.
اگر تابع را بررسي كنيم، متوجه مي‌شويم كه پس از هر مرحله براي 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 تعريف كنيم به يك تابع تك‌متغير تبديل مي‌شود كه رشد مقادير آن بسيار زياد است و نسبت به توابع ديگر تك‌متغير داراي رشد سريع‌تري است. 
عضو شوید
عضویت سریع
آمار مطالب
آمار بازدید
آمار
وب سایت:
