تابع اکرمن

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

مدتی بعد و به طور مستقل در سال ۱۹۲۸ اکرمن تابع بازگشتی خود که چندضابطه‌ای بود را ارائه داد.
اکرمن ثابت کرد که ((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 مانند ۱ و ۲ و ۳ تابع اکرمن با افزایش n نسبتاً کند رشد می‌کند. اما برای mهای بزرگ تر یا مساوی ۴ سریع تر رشد می‌کند. به طوری که19728^A(۴٬۲)=۲*۱۰ و رشد تابع(۳٬۴)=A با هر مقیاس تعداد اندازه‌گیری غیر قابل اندازه‌گیری است. که بسیار بیشتر از تخمین تعداد کل اتم‌های جهان یعنی (۸۰^۱۰) است.[۱]

مقادیر A(mn)
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
۴ ۱۳ ۶۵۵۳۳ 265536 − ۳ {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\}

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

پی‌نوشت‌ها[ویرایش]

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

منابع[ویرایش]

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