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

{{NoteTA
|G1 = IT
|G2 = Math
}}
'''阿克曼函數'''是非[[原始递归函数]]的例子；它需要兩個[[自然數]]作為輸入值，輸出一個自然數。它的輸出值增長速度非常高。

==歷史==
1920年代後期，數學家[[大衛·希爾伯特]]的學生Gabriel Sudan和[[威廉·阿克曼]]，當時正研究計算的基礎。Sudan發明了一個遞歸卻非原始遞歸的{{le|Sudan函數|Sudan function}}。1928年，阿克曼又獨立想出了另一個遞歸卻非原始遞歸的函數。[http://groups.google.com/group/soc.culture.romanian/tree/browse_frm/thread/7f684f8bd7f3edb1/]

他最初的念頭是一個三個變數的函數A(''m'',''n'',''p'')，使用[[康威鏈式箭號表示法]]是''m''→''n''→''p''。阿克曼證明了它是[[遞歸函數]]。希爾伯特在''On the Infinite''猜想這個函數不是[[原始遞歸函數]]。阿克曼在''On Hilbert's Construction of the Real Numbers''證明了這點。

後來{{le|Rózsa Péter|Rózsa Péter}}和[[拉斐尔·米切尔·罗宾逊]]定義了一個類似的函數，但只用兩個變數。

==定義==
{|
|rowspan="3"|<math> A(m, n) = 
  \begin{cases}
     n+1 \\
     A(m-1, 1) \\
     A(m-1, A(m, n-1)) \\
  \end{cases}
</math>
|若m=0
|-
|若m>0且n=0
|-
|若m>0且n>0
|}

以下是阿克曼函數的[[虛擬碼]]：

  '''function''' ack(m, n)
      '''while''' m &ne; 0
          '''if''' n = 0
              n := 1
          '''else'''
              n := ack(m, n-1)
          m := m - 1
      '''return''' n+1

[[Haskell]] 语言能生成更精确的定义:

  ack 0 n = n + 1
  ack m 0 = ack (m - 1) 1
  ack m n = ack (m - 1) (ack m (n - 1))

递归是有界的，因为在每次应用递归時，要么 ''m'' 递减，要么 ''m'' 保持不变而 ''n'' 递减。每次 ''n'' 达到零，''m'' 递减，所以 ''m'' 最终可以达到零。（較技術性的表达：在每种情况下，有序对(''m'', ''n'')按[[字典次序]]递减，它保持了非负整数的[[良序关系]]）。但是，在 ''m'' 递减的时候， ''n'' 的增加没有上界，而且增加的幅度比較大。

這個函數亦可用[[康威鏈式箭號表示法]]來作一個非遞迴性的定義：
: 對於''m''>2，A(''m'', ''n'') = (2 → (''n''+3) → (''m'' - 2)) - 3。
即是
: 對於''n''>2，2 → ''n'' → ''m'' = A(''m''+2,''n''-3) + 3。

使用[[hyper運算符]]就是
: A(''m'', ''n'') = hyper(2, ''m'', ''n'' + 3) - 3。

使用[[高德納箭號表示法]]則為
: A(''m'', ''n'') = 2↑<sup>m-2</sup>(n+3) - 3。

==函数值表==

{| 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))
|}

==反函數==
由於函數''f''&nbsp;(''n'')&nbsp;=&nbsp;''A''(''n'',&nbsp;''n'')的增加速率非常快，因此其[[反函數]]''f''<sup>−1</sup>則會以非常慢的速度增加。阿克曼反函數常用'''α'''表示。因為A(4,&nbsp;4)的數量級約等於<math>2^{2^{10^{19729}}}</math>，因此對於一般可能出現的數值''n''，α(n)均小於5。

阿克曼反函數會出現在一些[[演算法]]的時間[[計算複雜性理論|複雜度]]分析中，例如[[并查集]]或是Chazelle針對[[最小生成树]]的演算法中。有時會使用一些阿克曼函數的變體，例如省略運算式中的-3等，但其增加的速率都相當快。

以下是一個两個輸入值的阿克曼反函數，其中<math>\lfloor x \rfloor</math>為[[高斯符号|下取整函數]]：
:<math>\alpha(m,n) = \min\{i \geq 1 : A(i,\lfloor m/n \rfloor) \geq \log_2 n\}.</math>
許多演算法的複雜度分析會用到此函數，可以以此得到一個較好的時間上限。在并查集的資料結構中，''m''表示其運算的次數，而''n''表示元素的個數。在最小生成树演算法中，''m''表示其邊的個數，而''n''表示其[[顶点 (图论)|頂點]]的個數。

有些定義方式會用上述的定義略作修改，例如log<sub>2</sub>&nbsp;''n''改為''n''，或是下取整函數改為上取整函數。

有些研究則是用上述的定義，但是令m為常數，因此只需要一個輸入值<ref>[http://cat.inist.fr/?aModele=afficheN&cpsidt=15618233 An inverse-Ackermann style lower bound for the online minimum spanning tree verification problem] November 2002</ref>。

==参见==
* [[迭代冪次]]
* {{le|Busy beaver|Busy beaver}}

==引用==
* Wilhelm Ackermann, ''Zum Hilbertschen Aufbau der reelen Zahlen'', Math. Annalen 99 (1928), pp. 118-133.
* von Heijenoort. [https://web.archive.org/web/20060505062957/http://www.andrew.cmu.edu/user/cebrown/notes/vonHeijenoort.html From Frege To Gödel], 1967. This is an invaluable reference in understanding the context of Ackermann's paper ''On Hilbert’s Construction of the Real Numbers'', containing his paper as well as Hilbert’s ''On The Infinite'' and Gödel’s two papers on the completeness and consistency of mathematics.<div id="van Heijenoort"></div>
* Raphael M. Robinson, ''Recursion and double recursion'', Bull. Amer. Math. Soc., Vol. 54, pp. 987-993.

==参考资料==
{{Reflist}}

==外部链接==
*[http://www.stetson.edu/~efriedma/periodictable/html/Ac.html Erich Friedman's page on Ackermann] at [[Stetson University]]
*Scott Aaronson, ''[http://www.scottaaronson.com/writings/bignumbers.html  Who can name the biggest number?]'' (1999)
*[http://www-users.cs.york.ac.uk/~susan/cyc/a/ackermnn.htm Some values of the Ackermann function].
*[http://www.xgc.com/benchmarks/benchmarks.htm Example use of the Ackermann function as a benchmark]{{dead link|date=2018年1月 |bot=InternetArchiveBot |fix-attempted=yes }}. Note the huge number of function calls used in computing low values.
*[https://web.archive.org/web/20080317104411/http://www.kosara.net/thoughts/ackermann42.html Decimal expansion of A(4,2)]
*[http://forum.wolframscience.com/showthread.php?s=&threadid=579 Hyper-operations] Posting on A New Kind of Science Forum discussing the arithmetic operators of the Ackermann function and their inverse operators with link to an extended article on the subject.
*[https://web.archive.org/web/20020815083542/http://home.earthlink.net/~mrob/pub/math/ln-2deep.html Robert Munafo's Versions of Ackermann's Function] describes several variations on the definition of ''A''.
*<div id="Hilbert">Zach, Richard,</div> [http://plato.stanford.edu/archives/fall2003/entries/hilbert-program/ "Hilbert's Program"], ''The Stanford Encyclopedia of Philosophy'' (Fall 2003 Edition), Edward N. Zalta (ed.)

{{大数}}

[[Category:函数|A]]
[[Category:計算理論|A]]