阿克曼函数：修订间差异

2025年7月3日 (四) 17:01的版本

阿克曼函数(Ackermann function)是由德国数学家威廉·阿克曼(Wilhelm Ackermann)创造的非原始递归函数。

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

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

@@ 第10行： / 第10行： @@
 ==== 函数值表 ====
+{| 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))
+|}