主题
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 函数, 全函数

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 中被引用

阿克曼函数

请引用为

Weisstein, Eric W. "阿克曼函数。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/AckermannFunction.html

主题分类