fbpx
维基百科

阿克曼函數

阿克曼函數是非原始递归函数的例子;它需要兩個自然數作為輸入值,輸出一個自然數。它的輸出值增長速度非常高。

歷史 编辑

1920年代後期,數學家大衛·希爾伯特的學生Gabriel Sudan和威廉·阿克曼,當時正研究計算的基礎。Sudan發明了一個遞歸卻非原始遞歸的苏丹函数。1928年,阿克曼又獨立想出了另一個遞歸卻非原始遞歸的函數。[1]

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

後來Rózsa Péter英语Rózsa Péter拉斐尔·米切尔·罗宾逊定義了一個類似的函數,但只用兩個變數。

定義 编辑

  若m=0
若m>0且n=0
若m>0且n>0

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

 function ack(m, n) while m ≠ 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 → nm = A(m+2,n-3) + 3。

使用hyper運算符就是

A(m, n) = hyper(2, m, n + 3) - 3。

使用高德納箭號表示法則為

A(m, n) = 2↑m-2(n+3) - 3。

函数值表 编辑

A(mn) 的值
m\n 0 1 2 3 4 n
0 1 2 3 4 5  
1 2 3 4 5 6  
2 3 5 7 9 11  
3 5 13 29 61 125  
4 13 65533 265536 − 3 A(3, 265536 − 3) A(3, A(4, 3))  (n+3个数字2)
5 65533 A(4, 65533) A(4, A(5, 1)) A(4, A(5, 2)) A(4, A(5, 3))
6 A(5, 1) A(5, A(5, 1)) A(5, A(6, 1)) A(5, A(6, 2)) A(5, A(6, 3))

反函數 编辑

由於函數f (n) = A(nn)的增加速率非常快,因此其反函數f−1則會以非常慢的速度增加。阿克曼反函數常用α表示。因為A(4, 4)的數量級約等於 ,因此對於一般可能出現的數值n,α(n)均小於5。

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

以下是一個两個輸入值的阿克曼反函數,其中 下取整函數

 

許多演算法的複雜度分析會用到此函數,可以以此得到一個較好的時間上限。在并查集的資料結構中,m表示其運算的次數,而n表示元素的個數。在最小生成树演算法中,m表示其邊的個數,而n表示其頂點的個數。

有些定義方式會用上述的定義略作修改,例如log2 n改為n,或是下取整函數改為上取整函數。

有些研究則是用上述的定義,但是令m為常數,因此只需要一個輸入值[2]

参见 编辑

引用 编辑

  • Wilhelm Ackermann, Zum Hilbertschen Aufbau der reelen Zahlen, Math. Annalen 99 (1928), pp. 118-133.
  • von Heijenoort. , 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.
  • Raphael M. Robinson, Recursion and double recursion, Bull. Amer. Math. Soc., Vol. 54, pp. 987-993.

参考资料 编辑

  1. ^ [1] (页面存档备份,存于互联网档案馆
  2. ^ An inverse-Ackermann style lower bound for the online minimum spanning tree verification problem (页面存档备份,存于互联网档案馆) November 2002

外部链接 编辑

  • at Stetson University
  • Scott Aaronson, Who can name the biggest number? (页面存档备份,存于互联网档案馆 (1999)
  • Some values of the Ackermann function (页面存档备份,存于互联网档案馆).
  • Example use of the Ackermann function as a benchmark (页面存档备份,存于互联网档案馆). Note the huge number of function calls used in computing low values.
  • 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.
  • describes several variations on the definition of A.
  • Zach, Richard,
    "Hilbert's Program" (页面存档备份,存于互联网档案馆), The Stanford Encyclopedia of Philosophy (Fall 2003 Edition), Edward N. Zalta (ed.)

阿克曼函數, 是非原始递归函数的例子, 它需要兩個自然數作為輸入值, 輸出一個自然數, 它的輸出值增長速度非常高, 目录, 歷史, 定義, 函数值表, 反函數, 参见, 引用, 参考资料, 外部链接歷史, 编辑1920年代後期, 數學家大衛, 希爾伯特的學生gabriel, sudan和威廉, 阿克曼, 當時正研究計算的基礎, sudan發明了一個遞歸卻非原始遞歸的苏丹函数, 1928年, 阿克曼又獨立想出了另一個遞歸卻非原始遞歸的函數, 他最初的念頭是一個三個變數的函數a, 使用康威鏈式箭號表示法是m, 阿克曼證. 阿克曼函數是非原始递归函数的例子 它需要兩個自然數作為輸入值 輸出一個自然數 它的輸出值增長速度非常高 目录 1 歷史 2 定義 3 函数值表 4 反函數 5 参见 6 引用 7 参考资料 8 外部链接歷史 编辑1920年代後期 數學家大衛 希爾伯特的學生Gabriel Sudan和威廉 阿克曼 當時正研究計算的基礎 Sudan發明了一個遞歸卻非原始遞歸的苏丹函数 1928年 阿克曼又獨立想出了另一個遞歸卻非原始遞歸的函數 1 他最初的念頭是一個三個變數的函數A m n p 使用康威鏈式箭號表示法是m n p 阿克曼證明了它是遞歸函數 希爾伯特在On the Infinite猜想這個函數不是原始遞歸函數 阿克曼在On Hilbert s Construction of the Real Numbers證明了這點 後來Rozsa Peter 英语 Rozsa Peter 和拉斐尔 米切尔 罗宾逊定義了一個類似的函數 但只用兩個變數 定義 编辑A m n n 1 A m 1 1 A m 1 A m n 1 displaystyle A m n begin cases n 1 A m 1 1 A m 1 A m n 1 end cases nbsp 若m 0若m gt 0且n 0若m gt 0且n gt 0以下是阿克曼函數的虛擬碼 function ack m n while m 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 gt 2 A m n 2 n 3 m 2 3 即是 對於n gt 2 2 n m A m 2 n 3 3 使用hyper運算符就是 A m n hyper 2 m n 3 3 使用高德納箭號表示法則為 A m n 2 m 2 n 3 3 函数值表 编辑A m n 的值 m n 0 1 2 3 4 n0 1 2 3 4 5 n 1 displaystyle n 1 nbsp 1 2 3 4 5 6 n 2 displaystyle n 2 nbsp 2 3 5 7 9 11 2 n 3 3 displaystyle 2 cdot n 3 3 nbsp 3 5 13 29 61 125 2 n 3 3 displaystyle 2 n 3 3 nbsp 4 13 65533 265536 3 A 3 265536 3 A 3 A 4 3 2 2 2 3 displaystyle begin matrix underbrace 2 2 cdot cdot cdot 2 3 end matrix nbsp n 3个数字2 5 65533 A 4 65533 A 4 A 5 1 A 4 A 5 2 A 4 A 5 3 6 A 5 1 A 5 A 5 1 A 5 A 6 1 A 5 A 6 2 A 5 A 6 3 反函數 编辑由於函數f n A n n 的增加速率非常快 因此其反函數f 1則會以非常慢的速度增加 阿克曼反函數常用a表示 因為A 4 4 的數量級約等於2 2 10 19729 displaystyle 2 2 10 19729 nbsp 因此對於一般可能出現的數值n a n 均小於5 阿克曼反函數會出現在一些演算法的時間複雜度分析中 例如并查集或是Chazelle針對最小生成树的演算法中 有時會使用一些阿克曼函數的變體 例如省略運算式中的 3等 但其增加的速率都相當快 以下是一個两個輸入值的阿克曼反函數 其中 x displaystyle lfloor x rfloor nbsp 為下取整函數 a m n min i 1 A i m n log 2 n displaystyle alpha m n min i geq 1 A i lfloor m n rfloor geq log 2 n nbsp 許多演算法的複雜度分析會用到此函數 可以以此得到一個較好的時間上限 在并查集的資料結構中 m表示其運算的次數 而n表示元素的個數 在最小生成树演算法中 m表示其邊的個數 而n表示其頂點的個數 有些定義方式會用上述的定義略作修改 例如log2 n改為n 或是下取整函數改為上取整函數 有些研究則是用上述的定義 但是令m為常數 因此只需要一個輸入值 2 参见 编辑迭代冪次 忙碌的海狸引用 编辑Wilhelm Ackermann Zum Hilbertschen Aufbau der reelen Zahlen Math Annalen 99 1928 pp 118 133 von Heijenoort From Frege To Godel 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 Godel s two papers on the completeness and consistency of mathematics Raphael M Robinson Recursion and double recursion Bull Amer Math Soc Vol 54 pp 987 993 参考资料 编辑 1 页面存档备份 存于互联网档案馆 An inverse Ackermann style lower bound for the online minimum spanning tree verification problem 页面存档备份 存于互联网档案馆 November 2002外部链接 编辑Erich Friedman s page on Ackermann at Stetson University Scott Aaronson Who can name the biggest number 页面存档备份 存于互联网档案馆 1999 Some values of the Ackermann function 页面存档备份 存于互联网档案馆 Example use of the Ackermann function as a benchmark 页面存档备份 存于互联网档案馆 Note the huge number of function calls used in computing low values Decimal expansion of A 4 2 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 Robert Munafo s Versions of Ackermann s Function describes several variations on the definition of A Zach Richard Hilbert s Program 页面存档备份 存于互联网档案馆 The Stanford Encyclopedia of Philosophy Fall 2003 Edition Edward N Zalta ed 取自 https zh wikipedia org w index php title 阿克曼函數 amp oldid 75162826, 维基百科,wiki,书籍,书籍,图书馆,

文章

,阅读,下载,免费,免费下载,mp3,视频,mp4,3gp, jpg,jpeg,gif,png,图片,音乐,歌曲,电影,书籍,游戏,游戏。