阿克曼函数：修订间差异

2025年7月3日 (四) 19:58的版本

阿克曼函数(Ackermann function)是由德国数学家 Wilhelm Ackermann 创造的非原始递归函数，后来由 Rozsa Peter 和 Raphael M. Robinson 简化。阿克曼函数的确切定义因作者而异。

定义

Robinson 的版本^[1]是最常被使用的 Ackermann 函数：

$A (m, n) = {\begin{cases} n + 1 & , m = 0 \\ A (m - 1, 1) & , m \neq 0 \land n = 0 \\ A (m - 1, A (m, n - 1)) & , m \neq 0 \land n \neq 0 \end{cases}$

在这个定义下， $A (x, y) = 2 ↑^{x - 2} (y + 3) - 3$ ，它的 FGH 增长率约为 $ω$ 。

示例

$\begin{array}{lll} 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(m,n) 的值
m\n	0	1	2	3	4	n
0	1	2	3	4	5	$n + 1$
1	2	3	4	5	6	$n + 2$
2	3	5	7	9	11	$2 \cdot (n + 3) - 3$
3	5	13	29	61	125	$2^{(n + 3)} - 3$
4	13	65533	2⁶⁵⁵³⁶-3	A(3,2⁶⁵⁵³⁶-3)	A(3,A(4,3))	$\begin{matrix} \underset{⏟}{{2^{2}}^{\cdot^{\cdot^{\cdot^{2}}}}} - 3 \end{matrix}$ （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))

其他定义

原始定义

$A (n, x, y) = {\begin{cases} x + y & , n = 0 \\ \underset{y times}{\underset{⏟}{A (n - 1, A (\dots (A (n - 1, x)) \dots))}} & , n \neq 0 \end{cases}$

它可以用上箭头表示法表示为 $A (n, x, y) = x ↑^{n - 2} y$ ，但是在它被定义前上箭头表示法还未被发明。它是根据高阶原始递归（即函数上的原始递归）定义的。^[2]

Friedman 的定义

$A (x, y) = {\begin{cases} 2 & , y = 1 \\ 2 y & , x = 1 \land y > 1 \\ A (x - 1, A (x, y - 1)) & , x > 1 \land y > 1 \end{cases}$

在这个定义下， $A (x, y) = 2 ↑^{x - 1} y$ 。^[3]

其他内容

定义在 R^* 上的 Ackermann 函数

CompactStar 的定义：^[4]

$A (x, y) = {\begin{cases} x + y + 1 & , x < 1 \\ A (x - 1, y \cdot A (x - 1, 1) - y + 1) & , x ⩾ 1 \land y < 1 \\ A (x - 1, A (x, y - 1)) & , x ⩾ 1 \land y ⩾ 1 \end{cases}$

Ackermann 函数和 Ackermann 数

数列 $A_{n} = A (n + 2, n, n)$ （使用原始定义）被称为 Ackermann 数，^[5]这里 $A_{n} = n ↑^{n} n$ 。

↑ Weisstein, Eric W. "Ackermann Function." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/AckermannFunction.html
↑ Ackermann, Wilhelm (1928). "Zum Hilbertschen Aufbau der reellen Zahlen". Mathematische Annalen. 99: 118–133. https://doi.org/10.1007%2FBF01459088
↑ Harvey M. Friedman. THE ACKERMANN FUNCTION IN ELEMENTARY ALGEBRAIC GEOMETRY, October 21, 2000. https://cpb-us-w2.wpmucdn.com/u.osu.edu/dist/1/1952/files/2014/01/AckAlgGeom102100-1rrdkag.pdf
↑ CompactStar. Continuous Ackermann function, June15, 2023. https://nirvanasupermind.github.io/googology/continuous-ackermann-function.html
↑ Ackermann Number | Googology Wiki. Cooperation. January 1, 2001. https://googology.fandom.com/wiki/Ackermann_number

[1] Weisstein, Eric W. "Ackermann Function." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/AckermannFunction.html

[2] Ackermann, Wilhelm (1928). "Zum Hilbertschen Aufbau der reellen Zahlen". Mathematische Annalen. 99: 118–133. https://doi.org/10.1007%2FBF01459088

[3] Harvey M. Friedman. THE ACKERMANN FUNCTION IN ELEMENTARY ALGEBRAIC GEOMETRY, October 21, 2000. https://cpb-us-w2.wpmucdn.com/u.osu.edu/dist/1/1952/files/2014/01/AckAlgGeom102100-1rrdkag.pdf

[4] CompactStar. Continuous Ackermann function, June15, 2023. https://nirvanasupermind.github.io/googology/continuous-ackermann-function.html

[5] Ackermann Number | Googology Wiki. Cooperation. January 1, 2001. https://googology.fandom.com/wiki/Ackermann_number

[1]

[2]

[3]

[4]

[5]

@@ 第1行： / 第1行： @@
-'''阿克曼函数(Ackermann function)'''是由德国数学家威廉·阿克曼(Wilhelm Ackermann)创造的非原始递归函数。
+'''阿克曼函数(Ackermann function)'''是由德国数学家 Wilhelm Ackermann 创造的非原始递归函数，后来由 Rozsa Peter 和 Raphael M. Robinson 简化。阿克曼函数的确切定义因作者而异。
-==== 定义 ====
+=== 定义 ===
-<math>A(m, n) =
+Robinson 的版本<ref>Weisstein, Eric W. "Ackermann Function." From ''MathWorld''--A Wolfram Resource. https://mathworld.wolfram.com/AckermannFunction.html</ref>是最常被使用的 Ackermann 函数：
-  \begin{cases}
-     n+1 &, m=0 \\
+<math>A(m,n)=\begin{cases}n+1&,m=0\\A(m-1,1)&,m\neq0\land n=0\\A(m-1,A(m,n-1))&,m\neq0\land n\neq0\end{cases}</math>
-     A(m-1, 1) &, m>0\ \text{and}\ n=0\\
-     A(m-1, A(m, n-1)) &, m>0\ \text{and}\ n>0
+在这个定义下，<math>A(x,y)=2\uparrow^{x-2}(y+3)-3</math>，它的 [[快速增长层级|FGH]] 增长率约为 <math>\omega</math>。
-  \end{cases}</math>
 ==== 示例 ====
@@ 第26行： / 第25行： @@
 ==== 函数值表 ====
 {| class="wikitable"
-|+ ''A''(''m'',&nbsp;''n'') 的值
+|+ A(m,n) 的值
 |-
-! ''m''\''n''
+! m\n
 ! 0
 ! 1
@@ 第52行： / 第50行： @@
 ! 4
 | 13 || 65533
-| 2<sup>65536</sup>&nbsp;&minus;&nbsp;3
+| 2<sup>65536</sup>-3
-| ''A''(3,&nbsp;2<sup>65536</sup>&nbsp;&minus;&nbsp;3)
+| ''A''(3,2<sup>65536</sup>-3)
-| ''A''(3,&nbsp;''A''(4,&nbsp;3))
+| ''A''(3,''A''(4,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))
+| 65533 || ''A''(4,65533) || ''A''(4,''A''(5,1))
-| ''A''(4,&nbsp;''A''(5,&nbsp;2)) || ''A''(4,&nbsp;''A''(5,&nbsp;3))
+| ''A''(4,''A''(5,2)) || ''A''(4,''A''(5,3))
 |-
 ! 6
-| ''A''(5,&nbsp;1) || ''A''(5,&nbsp;''A''(5,&nbsp;1))
+| A(5,1) || ''A''(5,''A''(5,1))
-| ''A''(5,&nbsp;A(6,&nbsp;1))
+| ''A''(5,A(6,1))
-| ''A''(5,&nbsp;''A''(6,&nbsp;2)) || ''A''(5,&nbsp;''A''(6,&nbsp;3))
+| ''A''(5,''A''(6,2)) || ''A''(5,''A''(6,3))
 |}
-==== 小贴士 ====
+=== 其他定义 ===
-阿克曼函数的FGH[[增长率]]约为<math>\omega</math>。
+==== 原始定义 ====
+<math>A(n,x,y)=\begin{cases}x+y&,n=0\\\underbrace{A(n-1,A(\cdots(A(n-1,x))\cdots))}_{y\text{ times}}&,n\neq0\end{cases}</math>
+它可以用[[高德纳箭头|上箭头表示法]]表示为 <math>A(n,x,y)=x\uparrow^{n-2}y</math>，但是在它被定义前[[高德纳箭头|上箭头表示法]]还未被发明。它是根据高阶原始递归（即函数上的原始递归）定义的。<ref>Ackermann, Wilhelm (1928). "Zum Hilbertschen Aufbau der reellen Zahlen". Mathematische Annalen. 99: 118–133. https://doi.org/10.1007%2FBF01459088</ref>
+==== Friedman 的定义 ====
+<math>A(x,y)=\begin{cases}2&,y=1\\2y&,x=1\land y>1\\A(x-1,A(x,y-1))&,x>1\land y>1\end{cases}</math>
+在这个定义下，<math>A(x,y)=2\uparrow^{x-1}y</math>。<ref>Harvey M. Friedman. THE ACKERMANN FUNCTION IN ELEMENTARY ALGEBRAIC GEOMETRY, October 21, 2000. https://cpb-us-w2.wpmucdn.com/u.osu.edu/dist/1/1952/files/2014/01/AckAlgGeom102100-1rrdkag.pdf</ref>
+=== 其他内容 ===
+==== 定义在 R<sup>*</sup> 上的 Ackermann 函数 ====
+CompactStar 的定义：<ref>CompactStar. Continuous Ackermann function, June15, 2023. https://nirvanasupermind.github.io/googology/continuous-ackermann-function.html</ref>
+<math>A(x,y)=\begin{cases}x+y+1&,x<1\\A(x-1,y\cdot A(x-1,1)-y+1)&,x\geqslant1\land y<1\\A(x-1,A(x,y-1))&,x\geqslant1\land y\geqslant1\end{cases}</math>
+==== Ackermann 函数和 Ackermann 数 ====
+数列 <math>A_n=A(n+2,n,n)</math>（使用原始定义）被称为 Ackermann 数，<ref>Ackermann Number | Googology Wiki. Cooperation. January 1, 2001. https://googology.fandom.com/wiki/Ackermann_number</ref>这里 <math>A_n=n\uparrow^nn</math>。
 [[分类:记号]]
 [[分类:入门]]