查看“︁阿克曼函数”︁的源代码

'''阿克曼函数(Ackermann function)'''是由德国数学家 Wilhelm Ackermann 创造的非原始递归函数，后来由 Rozsa Peter 和 Raphael M. Robinson 简化。阿克曼函数的确切定义因作者而异。

=== 定义 ===
Robinson 的版本<ref>Weisstein, Eric W. "Ackermann Function." From ''MathWorld''--A Wolfram Resource. https://mathworld.wolfram.com/AckermannFunction.html</ref>是最常被使用的 Ackermann 函数：

<math>A(m,n)=\begin{cases}n+1&,m=0\\A(m-1,1)&,m\neq0\land n=0\\A(m-1,A(m,n-1))&,m\neq0\land n\neq0\end{cases}</math>

在这个定义下，<math>A(x,y)=2\uparrow^{x-2}(y+3)-3</math>，它的 [[快速增长层级|FGH]] 增长率约为 <math>\omega</math>。

==== 示例 ====
<math>\begin{array}{lll}
A(2,2) &=& A(1,A(2,1))\\ &=& A(1,A(1,A(2,0)))&&\\
       &=& A(1,A(1,A(1,1)))\\ &=& A(1,A(1,A(0,A(1,0))))\\ &=&  A(1,A(1,A(0,A(0,1))))\\ &=& A(1,A(1,A(0,2)))\\&=& A(1, A(1, 3))\\
&=& A(1, A(0, A(1, 2)))\\ &=& A(1, A(0, A(0, A(1, 1))))\\
&=& A(1, A(0, A(0, A(0, A(1, 0)))))\\ &=& A(1, A(0, A(0, A(0, A(0, 1)))))\\
&=& A(1, A(0, A(0, A(0, 2))))\\
&=& A(1, A(0, A(0, 3)))\\ &=& A(1, A(0, 4))\\ &=& A(1, 5)\\ &=& A(0, A(1, 4))\\
&=& A(0, A(0, A(1, 3)))\\ &=& A(0, A(0, A(0, A(1, 2))))\\
&=& A(0, A(0, A(0, A(0, A(1, 1)))))\\
&=& A(0, A(0, A(0, A(0, A(0, A(1, 0))))))\\
&=& A(0, A(0, A(0, A(0, A(0, A(0, 1))))))\\
&=& A(0, A(0, A(0, A(0, A(0, 2)))))\\ &=& A(0, A(0, A(0, A(0, 3))))\\
&=& A(0, A(0, A(0, 4)))\\ &=& A(0, A(0, 5))\\ &=& A(0, 6)\\ &=& 7
\end{array}</math>

==== 函数值表 ====
{| class="wikitable"
|+ ''A''(''m'',&nbsp;''n'')的值
|-
! m\n
! 0
! 1
! 2
! 3
! 4
! ''n''
|-
! 0
| 1 || 2 || 3 || 4 || 5 || <math>n + 1</math>
|-
! 1
| 2 || 3 || 4 || 5 || 6 || <math>n + 2 = 2 + (n + 3) - 3</math>
|-
! 2
| 3 || 5 || 7 || 9 || 11 || <math>2n + 3 = 2\cdot(n + 3) - 3</math>
|-
! 3
| 5 || 13 || 29 || 61 || 125 || <math>2^{(n + 3)} - 3</math>
|- style="vertical-align:top"
! rowspan="3" style="vertical-align:middle" | 4
| rowspan="1" style="border-bottom:0" | 13
| rowspan="1" style="border-bottom:0" | 65533
| rowspan="1" style="border-bottom:0" | 2<sup>65536</sup>&nbsp;–&nbsp;3
| rowspan="1" style="border-bottom:0" | <math>{2^{2^{65536}}} - 3</math>
| rowspan="1" style="border-bottom:0" | <math>{2^{2^{2^{65536}}}} - 3</math>
| rowspan="2" style="border-bottom:0" | <math>\begin{matrix}\underbrace{{2^2}^{{\cdot}^{{\cdot}^{{\cdot}^2}}}}_{n+3} - 3\end{matrix}</math>
|- style="vertical-align:bottom"
| rowspan="2" style="border-top:0" | <math>={2^{2^{2}}}-3</math><br /><math>=2\uparrow\uparrow 3 - 3</math>
| rowspan="2" style="border-top:0" | <math>={2^{2^{2^{2}}}}-3</math><br /><math>=2\uparrow\uparrow 4 - 3</math>
| rowspan="2" style="border-top:0" | <math>={2^{2^{2^{2^{2}}}}}-3</math><br /><math>=2\uparrow\uparrow 5 - 3</math>
| rowspan="2" style="border-top:0" | <math>={2^{2^{2^{2^{2^{2}}}}}}-3</math><br /><math>=2\uparrow\uparrow 6 - 3</math>
| rowspan="2" style="border-top:0" | <math>={2^{2^{2^{2^{2^{2^{2}}}}}}}-3</math><br /><math>=2\uparrow\uparrow 7 - 3</math>
|-
| rowspan="1" style="border-top:0" | <math>=2\uparrow\uparrow (n+3) - 3</math>
|- style="vertical-align:bottom"
! style="vertical-align:middle" | 5
| 65533 <br /><math>=2\uparrow\uparrow(2\uparrow\uparrow 2) - 3</math><br /><math>=2\uparrow\uparrow\uparrow 3 - 3</math>
| <math>2\uparrow\uparrow\uparrow 4 - 3</math>
| <math>2\uparrow\uparrow\uparrow 5 - 3</math>
| <math>2\uparrow\uparrow\uparrow 6 - 3</math>
| <math>2\uparrow\uparrow\uparrow 7 - 3</math>
| <math>2\uparrow\uparrow\uparrow (n+3) - 3</math>
|-
! 6
| <math>2\uparrow\uparrow\uparrow\uparrow 3 - 3</math>
| <math>2\uparrow\uparrow\uparrow\uparrow 4 - 3</math>
| <math>2\uparrow\uparrow\uparrow\uparrow 5 - 3</math>
| <math>2\uparrow\uparrow\uparrow\uparrow 6 - 3</math>
| <math>2\uparrow\uparrow\uparrow\uparrow 7 - 3</math>
| <math>2\uparrow\uparrow\uparrow\uparrow (n+3) - 3</math>
|-
! ''m''
| <math>(2\uparrow^{m-2} 3)-3</math>
| <math>(2\uparrow^{m-2} 4)-3</math>
| <math>(2\uparrow^{m-2} 5)-3</math>
| <math>(2\uparrow^{m-2} 6)-3</math>
| <math>(2\uparrow^{m-2} 7)-3</math>
| <math>(2\uparrow^{m-2}(n+3))-3</math>
|}

=== 其他定义 ===

==== 原始定义 ====
<math>A(n,x,y)=\begin{cases}x+y&,n=0\\\underbrace{A(n-1,A(\cdots(A(n-1,x))\cdots))}_{y\text{ times}}&,n\neq0\end{cases}</math>

它可以用[[高德纳箭头|上箭头表示法]]表示为 <math>A(n,x,y)=x\uparrow^{n-2}y</math>，但是在它被定义前[[高德纳箭头|上箭头表示法]]还未被发明。它是根据高阶原始递归（即函数上的原始递归）定义的。<ref>Ackermann, Wilhelm (1928). "Zum Hilbertschen Aufbau der reellen Zahlen". Mathematische Annalen. 99: 118–133. https://doi.org/10.1007%2FBF01459088</ref>

==== Friedman 的定义 ====
<math>A(x,y)=\begin{cases}2&,y=1\\2y&,x=1\land y>1\\A(x-1,A(x,y-1))&,x>1\land y>1\end{cases}</math>

在这个定义下，<math>A(x,y)=2\uparrow^{x-1}y</math>。<ref>Harvey M. Friedman. THE ACKERMANN FUNCTION IN ELEMENTARY ALGEBRAIC GEOMETRY, October 21, 2000. https://cpb-us-w2.wpmucdn.com/u.osu.edu/dist/1/1952/files/2014/01/AckAlgGeom102100-1rrdkag.pdf</ref>

=== 其他内容 ===

==== 定义在 R<sup>*</sup> 上的 Ackermann 函数 ====
CompactStar 的定义：<ref>CompactStar. Continuous Ackermann function, June15, 2023. https://nirvanasupermind.github.io/googology/continuous-ackermann-function.html</ref>

<math>A(x,y)=\begin{cases}x+y+1&,x<1\\A(x-1,y\cdot A(x-1,1)-y+1)&,x\geqslant1\land y<1\\A(x-1,A(x,y-1))&,x\geqslant1\land y\geqslant1\end{cases}</math>

==== Ackermann 函数和 Ackermann 数 ====
数列 <math>A_n=A(n+2,n,n)</math>（使用原始定义）被称为 Ackermann 数，<ref>Ackermann Number | Googology Wiki. Cooperation. January 1, 2001. https://googology.fandom.com/wiki/Ackermann_number</ref>这里 <math>A_n=n\uparrow^nn</math>。
[[分类:记号]]
[[分类:入门]]