查看“︁阿克曼函数”︁的源代码

'''阿克曼函数(Ackermann function)'''是由德国数学家 Wilhelm Ackermann 创造的非原始递归函数，后来由 Rozsa Peter 和 Raphael M. Robinson 简化。阿克曼函数有多种不同的版本。

=== 一般定义 ===

==== 定义 ====
Robinson 的版本<ref>Weisstein, Eric W. "Ackermann Function." From ''MathWorld''--A Wolfram Resource. https://mathworld.wolfram.com/AckermannFunction.html</ref>是最常被使用的阿克曼函数：

<math>A(m,n)=\begin{cases}n+1&,m=0\\A(m-1,1)&,m\neq0\ \text{and}\  n=0\\A(m-1,A(m,n-1))&,m\neq0\ \text{and}\  n\neq0\end{cases}</math>

在这个定义下，<math>A(x,y)=2\uparrow^{x-2}(y+3)-3</math>，它的 [[增长层级#快速增长层级|FGH]] 增长率约为 <math>\omega</math>。

==== 示例 ====
<math>\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}</math>

==== 函数值表 ====
{| class="wikitable"
|+ ''A''(''m'',''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 = 2 + (n + 3) - 3</math>
|-
! 2
| 3 || 5 || 7 || 9 || 11 || <math>2n + 3 = 2\cdot(n + 3) - 3</math>
|-
! 3
| 5 || 13 || 29 || 61 || 125 || <math>2^{(n + 3)} - 3</math>
|- style="vertical-align:top"
! style="vertical-align:middle" | 4
| rowspan="1" style="border-bottom:0" | 13
| rowspan="1" style="border-bottom:0" | 65533
| rowspan="1" style="border-bottom:0" | 2<sup>65536</sup>&nbsp;–&nbsp;3
| rowspan="1" style="border-bottom:0" | <math>{2^{2^{65536}}} - 3</math>
| rowspan="1" style="border-bottom:0" | <math>{2^{2^{2^{65536}}}} - 3</math>
| rowspan="1" style="border-bottom:0" | <math>=2\uparrow\uparrow (n+3) - 3</math>
|- style="vertical-align:bottom"
! style="vertical-align:middle" | 5
| 65533 
| <math>2\uparrow\uparrow\uparrow 4 - 3</math>
| <math>2\uparrow\uparrow\uparrow 5 - 3</math>
| <math>2\uparrow\uparrow\uparrow 6 - 3</math>
| <math>2\uparrow\uparrow\uparrow 7 - 3</math>
| <math>2\uparrow\uparrow\uparrow (n+3) - 3</math>
|-
! 6
| <math>2\uparrow\uparrow\uparrow\uparrow 3 - 3</math>
| <math>2\uparrow\uparrow\uparrow\uparrow 4 - 3</math>
| <math>2\uparrow\uparrow\uparrow\uparrow 5 - 3</math>
| <math>2\uparrow\uparrow\uparrow\uparrow 6 - 3</math>
| <math>2\uparrow\uparrow\uparrow\uparrow 7 - 3</math>
| <math>2\uparrow\uparrow\uparrow\uparrow (n+3) - 3</math>
|-
! ''m''
| <math>(2\uparrow^{m-2} 3)-3</math>
| <math>(2\uparrow^{m-2} 4)-3</math>
| <math>(2\uparrow^{m-2} 5)-3</math>
| <math>(2\uparrow^{m-2} 6)-3</math>
| <math>(2\uparrow^{m-2} 7)-3</math>
| <math>(2\uparrow^{m-2}(n+3))-3</math>
|}

=== 其他定义 ===
（本节内容大部分来自 Googology Wiki。<ref>Ackermann Function | Googology Wiki, Cooperation, January 11, 2009. https://googology.fandom.com/wiki/Ackermann_function</ref>）

==== 原始定义 ====
<math>A(n,x,y)=\begin{cases}x+1&,n=0\\\underbrace{A(n-1,A(n-1,\cdots A(n-1,0,x)\cdots,x),x)}_{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>

==== Buck 的定义 ====
Buck 使用相同的基本递归定义一个相关函数：<ref>Buck, R. C. "Mathematical Induction and Recursive Definitions." Amer. Math. Monthly 70, 128-135, 1963. https://cse.buffalo.edu/~rapaport/Papers/Papers.by.Others/buck63-MathIndnRecDefs.pdf</ref><math>F(x,y)=F(x-1,F(x,y-1))</math>

但边界值略有不同：

<math>\begin{aligned}F(0,y)&=&y+1&\\F(1,0)&=&2&\\F(2,0)&=&0&\\F(x,0)&=&1&\text{for }x=3,4,\cdots\end{aligned}</math>

这个函数递归得到：

<math>\begin{aligned}F(1,y)&=&2+y\\F(2,y)&=&2y\\F(3,y)&=&2^y\\F(4,y)&=&2\uparrow\uparrow y\end{aligned}</math>

F(4,n) 给出了序列 1, 2, 4, 16, 65536, 2<sup>65536</sup>,... (OEIS [http://oeis.org/A014221 A014221])；

F(n,n) 给出了序列 1, 3, 4, 8, 65536, <math>2\uparrow\uparrow65536</math>,...(OEIS [http://oeis.org/A001695 A001695])。<ref>Sloane, N. J. A. Sequences A001695/M2352 and A014221 in "The On-Line Encyclopedia of Integer Sequences."</ref>

==== Goucher 的定义 ====
A.P.Goucher 在其博客文章中提出了阿克曼函数的以下定义：<ref>Goucher, Adam P. Fast-growing functions, part 1, December 15, 2012. http://cp4space.wordpress.com/2012/12/15/fast-growing-1</ref>

* <math>f_1(n)=n+2</math>
* <math>f_{m+1}(n)=f_m^n(2)</math>
* <math>A(n)=f_n(n)</math>

该文章描述了该函数的另一个变体，该变体与以下问题相关：

给定一排盒子，每个盒子中有若干硬币，我们可以选择一个盒子并按照以下规则之一进行操作：

# 从该盒子中移除一枚硬币，并在第 n+1 个盒子中添加两枚硬币。
#从该盒子中移除一枚硬币，并反转第 n+1 和 n+2 个盒子中的硬币数量。

我们可以选择一种策略，即挑选盒子并应用相应的规则。考虑以下情况：除最右侧的盒子外，所有盒子均为空。此时，给定一排 n 个盒子，每个盒子中各有一枚硬币，<math>f(n)</math> 表示最右侧盒子中可能出现的最大硬币数量。计算该函数的精确值可能颇具挑战，但显而易见的是 <math>f(1)=1</math>、<math>f(2)=3</math> 和 <math>f(3)=7</math>。而证明 <math>f(4)=28</math> 则稍显困难。

=== 其他内容 ===

==== 定义在 R<sup>*</sup> 上的阿克曼函数 ====
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>

==== 阿克曼函数和阿克曼数 ====
数列 <math>A_n=A(n+2,n,n)</math>（使用原始定义）被称为阿克曼数(Ackermann Numbers)，<ref>Ackermann Number | Googology Wiki. Cooperation. January 1, 2001. https://googology.fandom.com/wiki/Ackermann_number</ref>这里 <math>A_n=n\uparrow^nn</math>。

==== 非原始递归的函数 ====
阿克曼函数是一个良定义全函数的最简单例子，它是可计算的但不是原始递归的，这为 20 世纪初人们认为每个可计算函数也是原始递归的这一信念提供了反例。<ref>Dötzel, G. "A Function to End All Functions." Algorithm: Recreational Programming 2.4, 16-17, 1991.</ref><ref>Kleene, S. C. ''Introduction to Metamathematics.'' Princeton, NJ: Van Nostrand, 1964.</ref><ref>Péter, R. ''Rekursive Funktionen in der Komputer-Theorie.'' Budapest: Akad. Kiado, 1951.</ref>

==== 阿克曼函数的逆函数 ====
由 <math>\lambda_i(n)=\min\{j\in\mathbb{N}|A(i,j)\geqslant n\}</math> 定义的函数 <math>\lambda:\mathbb{N}^2\rightarrow\mathbb{N}\quad(i,n)\mapsto\lambda_i(n)</math>（亦记为 <math>\alpha(i,n)</math>）被称为阿克曼函数的逆函数(inverse-Ackermann function)，尽管它并非非双射映射 <math>A:\mathbb{N}^2\rightarrow\mathbb{N}</math> 本身的逆映射。<ref>Pettie, S. An Inverse-Ackermann Type Lower Bound For Online Minimum Spanning Tree Verification*. Combinatorica 26, 207–230 (2006). https://doi.org/10.1007%2Fs00493-006-0014-1</ref>由于 <math>A(m,n)</math> 的增长速度相对较快，逆阿克曼函数因此呈现出极为缓慢的增长特性。有趣的是，该函数已在时间复杂度理论领域得到实际应用。<ref>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.</ref><ref>Tarjan, R. E. ''Data Structures and Network Algorithms.'' Philadelphia PA: SIAM, 1983.</ref>

==== 阿克曼函数的对角化 ====
函数 <math>A(x)=A(x,x)</math>（基于 Robinson 定义）是阿克曼函数的对角化，这个函数也被叫做 Gag 或 Knackeredman。这个名字来自 Alistair Cockburn，由于阿克曼函数与[[高德纳箭头|上箭头表示法]]的关系，<math>A(x)=2\uparrow^{x-2}(x+3)-3</math>。<ref>Gag | Googology Wiki, Cooperation, January 11, 2009. https://googology.fandom.com/wiki/Gag</ref>

[[分类:记号]]
[[分类:入门]]