تابع آکرمان

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

مدتی بعد و به‌طور مستقل در سال ۱۹۲۸ آکرمان تابع بازگشتی خود که چندضابطه‌ای بود را ارائه داد.
آکرمان ثابت کرد که ((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}}

ویژگی‌ها

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

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

پس به هر حال m پس از طی مراحل محدودی به صفر می‌رسد و تابع آکرمان به جواب نهایی خواهد رسید. البته در هر مرحله که m یک واحد کاهش میابد n شاید تا چندین واحد افزایش یابد.
برای مقادیر کوچک m مانند ۱ و ۲ و ۳ تابع آکرمان با افزایش n نسبتاً کند رشد می‌کند. اما برای mهای بزرگ تر یا مساوی ۴ سریع تر رشد می‌کند. به طوری که19728^A(۴٬۲)=۲*۱۰ و رشد تابع(۳٬۴)=A با هر مقیاس تعداد اندازه‌گیری غیرقابل اندازه‌گیری است. که بسیار بیشتر از تخمین تعداد کل اتم‌های جهان یعنی (۸۰^۱۰) است.

مقادیر A(m, n)
m\n	۰	۱	۲	۳	۴	n
۰	1	2	3	4	5	$n+1$
۱	2	3	4	5	6	$n+2=2+(n+3)-3$
۲	3	5	7	9	11	$2n+3=2\cdot (n+3)-3$
۳	5	13	29	61	125	$2^{(n+3)}-3$
۴	۱۳	۶۵۵۳۳	2 − ۳	${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{aligned}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{aligned}}

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

تابع (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\}

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

پی‌نوشت‌ها

↑ داده ساختارها و اگوریتم‌ها نوشته دکتر محمد قدسی چاپ اول سال 1388 انتشارات فاطمی ص391

منابع

[1] داده ساختارها و اگوریتم‌ها نوشته دکتر محمد قدسی چاپ اول سال 1388 انتشارات فاطمی ص391