FANDOM


阿克曼函數
基於 後繼函數
增長率 \(f_{\omega}(n)\)

阿克曼函數\(A(x,y)\)是一個遞迴函數,最初版本由威廉·阿克曼發明,後來Rosza Peter和Raphael M. Robinson將其簡化。通常現在所指的阿克曼函數就是Robinson的版本,定義如下:[1]

\[ A(x,y)= \begin{cases} y+1 & \text{如果}\ x=0, \\ A(x-1,1) & \text{如果}\ x>0、y=0, \\ A(x-1,A(x,y-1)) & \text{其他情況}。 \end{cases} \]

例如:

\[ \begin{array}{cclclcl} 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} \]

使用箭號表示法,可以寫成\(A(x,y)=2\uparrow^{x-2}(y+3)-3\)。

參考來源 编辑

  1. Ackermann Function

您使用了广告屏蔽软件!


Wikia通过广告运营为用户提供免费的服务。我们对用户通过嵌入广告屏蔽软件访问网站进行了使用调整。

如果您使用了广告屏蔽软件,将无法使用我们的服务。请您移除广告屏蔽软件,以确保页面正常加载。