تابع اکرمن

در سال ۱۹۲۰ ویلهلم اکرمن و گابریل سودن، دو ریاضیدان دانشجوی دانشگاه دیوید هیلبرت بر روی مبانی محاسبات مطالعه می‌کردند. سودن با تابع نه چندان معروفی که به نام خود ثبت کرد شناخته می‌شود.که این تابع از نوع بازگشتی چند ضابطه‌ای بوده. مدتی بعد و به طور مستقل در سال ۱۹۲۸ اکرمن تابع بازگشتی خود که چندضابطه‌ای بود را ارائه داد.
اکرمن ثابت کرد که ((A)) ((تابع اکرمن)) یک تابع بازگشتی است که یک رایانه یا پردازشگر با حافظه بی‌کران می‌تواند آن را محاسبه کند.اما یک تابع بازگشتی درجه اول مانند فاکتوریل یا تابع جمع نیست.

تعریف

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

$A(m, n) = \begin{cases} n+1 & \mbox{if } m = 0 \\ A(m-1, 1) & \mbox{if } m > 0 \mbox{ and } n = 0 \\ A(m-1, A(m, n-1)) & \mbox{if } m > 0 \mbox{ and } n > 0 \end{cases}$

ویژگی‌ها

ممکن است در نگاه اول نتوان به راحتی جواب تابع اکرمن را تشخیص داد. در هر مرحله دو رویداد ممکن است رخ دهد:

1. m کاهش میابد.
2. m ثابت میماند و n تا وقتی که به صفر برسد کاهش میابد و از آنجا m یک واحد کاهش میابد.
   

پس به هر حال m پس از طی مراحل محدودی به صفر میرسد و تابع اکرمن به جواب نهایی خواهد رسید. البته در هر مرحله که m یک واحد کاهش میابد n شاید تا چندین واحد افزایش یابد.
برای مقادیر کوچک m مانند 1 و 2 و 3 تابع اکرمن با افزایش n نسبتا کند رشد میکند. اما برای mهای بزرگ تر یا مساوی 4 سریع تر رشد میکند. به طوری که19728^A(4,2)=2*10 و رشد تابع(3,4)=A با هر مقیاس تعداد اندازه گیری غیر قابل اندازه گیری است. که بسیار بیشتر از تخمین تعداد کل اتم‌های جهان یعنی (80^10) است.

مقادیر A(m, n)

m\n	0	1	2	3	4	n
0	1	2	3	4	5	$n + 1$
1	2	3	4	5	6	$n + 2 = 2 + (n + 3) - 3$
2	3	5	7	9	11	$2n + 3 = 2\cdot(n + 3) - 3$
3	5	13	29	61	125	$2^{(n+3)} - 3$
4	13	65533	265536 − 3	${2^{2^{65536}}} - 3$	${2^{2^{2^{65536}}}} - 3$	$\begin{matrix}\underbrace{{2^2}^{{\cdot}^{{\cdot}^{{\cdot}^2}}}} - 3 \\n\mbox{ + 3}\end{matrix}$

---

مثال

$\begin{align} A(4, 3) & = A(3, A(4, 2)) \\ & = A(3, A(3, A(4, 1))) \\ & = A(3, A(3, A(3, A(4, 0)))) \\ & = A(3, A(3, A(3, A(3, 1)))) \\ & = A(3, A(3, A(3, A(2, A(3, 0))))) \\ & = A(3, A(3, A(3, A(2, A(2, 1))))) \\ & = A(3, A(3, A(3, A(2, A(1, A(2, 0)))))) \\ & = A(3, A(3, A(3, A(2, A(1, A(1, 1)))))) \\ & = A(3, A(3, A(3, A(2, A(1, A(0, A(1, 0))))))) \\ & = A(3, A(3, A(3, A(2, A(1, A(0, A(0, 1))))))) \\ & = A(3, A(3, A(3, A(2, A(1, A(0, 2)))))) \\ & = A(3, A(3, A(3, A(2, A(1, 3))))) \\ & = A(3, A(3, A(3, A(2, A(0, A(1, 2)))))) \\ & = A(3, A(3, A(3, A(2, A(0, A(0, A(1, 1))))))) \\ & = A(3, A(3, A(3, A(2, A(0, A(0, A(0, A(1, 0)))))))) \\ & = A(3, A(3, A(3, A(2, A(0, A(0, A(0, A(0, 1)))))))) \\ & = A(3, A(3, A(3, A(2, A(0, A(0, A(0, 2)))))) \\ & = A(3, A(3, A(3, A(2, A(0, A(0, 3))))) \\ & = A(3, A(3, A(3, A(2, A(0, 4))))) \\ & = A(3, A(3, A(3, A(2, 5)))) \\ & = ... \\ & = A(3, A(3, A(3, 13))) \\ & = ... \\ & = A(3, A(3, 65533)) \\ & = ... \\ & = A(3, 2^{65536} - 3) \\ & = ... \\ & = 2^{2^{ \overset{65536}{} }} - 3. \\ \end{align}$

بیان تک متغیره

تابع (f(n)=A(n,n را تعریف میکنیم که این تابع با افزایش m nو n به صورت توام و یکسان تغییر میکنند و میتوان آن را یک تابع بازگشتی تک پارامتری تصور کرد. که از هر تابع بازگشتی تک ضابطه مانند فاکتوریل یا جمع سریع تر رشد میکند.

معکوس تابع اکرمن

معکوس تابع اکرمن را به صورت زیر تعریف میکنیم:

$\lfloor x \rfloor$ تابع قدر مطلق میباشد:

$\alpha(m,n) = \min\{i \geq 1 : A(i,\lfloor m/n \rfloor) \geq \log_2 n\}$

تابع معکوس اکرمن رشد بسیار کمی دارد.تابع معکوس اکرمن را به صورت تک متغیره نیز میتوان تعریف کرد.

منابع

• مشارکت‌کنندگان ویکی‌پدیا، «Ackermann function»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۲۹ می ۲۰۱۱).