主題
Search

阿克曼函式

阿克曼函式是一個 良定義 全函式 的最簡單例子，它是 可計算的 但不是 原始遞迴的，這為 20 世紀初人們認為每個 可計算函式 也是 原始遞迴的 這一信念提供了反例 (Dötzel 1991)。它的增長速度比 指數函式 甚至多重指數函式還要快。

阿克曼函式 A(x,y) 對於整數 x 和 y 定義如下

A(x,y)={y+1 if x=0; A(x-1,1) if y=0; A(x-1,A(x,y-1)) otherwise.
(1)

整數 x 的特殊值包括

A(0,y)=y+1
(2)
A(1,y)=y+2
(3)
A(2,y)=2y+3
(4)
A(3,y)=2^(y+3)-3
(5)
A(4,y)=2^(2^(·^(·^(·^2))))_()_(y+3)-3.
(6)

後一種形式的表示式有時被稱為 冪塔。A(0,y) 可以從定義中直接得出。A(1,y) 可以推導如下

A(1,y)=A(0,A(1,y-1))
(7)
=A(1,y-1)+1
(8)
=A(0,A(1,y-2))+1
(9)
=A(1,y-2)+2
(10)
=...
(11)
=A(1,0)+y
(12)
=A(0,1)+y=y+2.
(13)

A(2,y) 有類似的推導

A(2,y)=A(1,A(2,y-1))
(14)
=A(2,y-1)+2
(15)
=A(1,A(2,y-2))+2
(16)
=A(2,y-2)+4
(17)
=...
(18)
=A(2,0)+2y
(19)
=A(1,1)+2y
(20)
=2y+3.
(21)

Buck (1963) 使用相同的基本 遞推關係 定義了一個相關函式（引數與 Buck 的約定相反）

F(x,y)=F(x-1,F(x,y-1)),
(22)

但邊界值略有不同

F(0,y)=y+1
(23)
F(1,0)=2
(24)
F(2,0)=0
(25)
F(x,0)=1 for x=3,4,....
(26)

Buck 的遞推給出

F(1,y)=2+y
(27)
F(2,y)=2y
(28)
F(3,y)=2^y
(29)
F(4,y)=2^(2^(·^(·^(·^2))))_()_(y).
(30)

取 F(4,n) 得到序列 1, 2, 4, 16, 65536, 2^(65536), ... (OEIS A014221)，而 F(n,n) 對於 n=0, 1, ... 則給出 1, 3, 4, 8, 65536, 2^(2^(·^(·^(·^2))))_()_(m), ... (OEIS A001695)。這裡，m=2^(2^(·^(·^(·^2))))_()_(65536)，這是一個非常巨大的數字！

另請參閱

阿克曼數, 可計算函式, Goodstein 序列, 冪塔, 原始遞迴函式, TAK 函式, 全函式

使用 探索

參考文獻

Buck, R. C. "Mathematical Induction and Recursive Definitions." Amer. Math. Monthly 70, 128-135, 1963.Dötzel, G. "A Function to End All Functions." Algorithm: Recreational Programming 2.4, 16-17, 1991.Kleene, S. C. 元數學導論。 Princeton, NJ: Van Nostrand, 1964.Péter, R. 計算機理論中的遞迴函式。 Budapest: Akad. Kiado, 1951.Reingold, E. H. and Shen, X. "More Nearly Optimal Algorithms for Unbounded Searching, Part I: The Finite Case." SIAM J. Comput. 20, 156-183, 1991.Rose, H. E. 子遞迴、函式和層次結構。 New York: Clarendon Press, 1988.Sloane, N. J. A. Sequences A001695/M2352 和 A014221 in "整數序列線上百科全書"。Smith, H. J. "阿克曼函式。" http://www.geocities.com/hjsmithh/Ackerman.html.Spencer, J. "Large Numbers and Unprovable Theorems." Amer. Math. Monthly 90, 669-675, 1983.Tarjan, R. E. 資料結構和網路演算法。 Philadelphia PA: SIAM, 1983.Vardi, I. Mathematica 中的計算娛樂。 Redwood City, CA: Addison-Wesley, pp. 11, 227, and 232, 1991.Wolfram, S. 一種新科學。 Champaign, IL: Wolfram Media, p. 906, 2002.

在 中被引用

阿克曼函式

請引用為

Weisstein, Eric W. "阿克曼函式。" 來自 Web 資源。 https://mathworld.tw/AckermannFunction.html

主題分類