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

'''阿克曼函数(Ackermann function)'''是由德国数学家威廉·阿克曼(Wilhelm Ackermann)创造的非原始递归函数。

==== 定义 ====
<math>A(m, n) = 
  \begin{cases}
     n+1 &, m=0 \\
     A(m-1, 1) &, m>0\ \text{and}\ n=0\\
     A(m-1, A(m, n-1)) &, m>0\ \text{and}\ n>0
  \end{cases}</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</math>
|-
! 2
| 3 || 5 || 7 || 9 || 11 || <math>2\cdot(n + 3)-3</math>
|-
! 3
| 5 || 13 || 29 || 61 || 125 || <math>2^{(n+3)} - 3</math>
|-
! 4
| 13 || 65533
| 2<sup>65536</sup>&nbsp;&minus;&nbsp;3
| ''A''(3,&nbsp;2<sup>65536</sup>&nbsp;&minus;&nbsp;3)
| ''A''(3,&nbsp;''A''(4,&nbsp;3))
| <math>\begin{matrix}\underbrace{{2^2}^{{\cdot}^{{\cdot}^{{\cdot}^2}}}} - 3 \end{matrix}</math>（n+3个2）
|-
! 5
| 65533 || ''A''(4,&nbsp;65533) || ''A''(4,&nbsp;''A''(5,&nbsp;1))
| ''A''(4,&nbsp;''A''(5,&nbsp;2)) || ''A''(4,&nbsp;''A''(5,&nbsp;3))
|-
! 6
| ''A''(5,&nbsp;1) || ''A''(5,&nbsp;''A''(5,&nbsp;1))
| ''A''(5,&nbsp;A(6,&nbsp;1))
| ''A''(5,&nbsp;''A''(6,&nbsp;2)) || ''A''(5,&nbsp;''A''(6,&nbsp;3))
|}

==== 小贴士 ====
阿克曼函数的FGH[[增长率]]约为<math>\omega</math>。
[[分类:记号]]
[[分类:入门]]