查看“︁高德纳箭头”︁的源代码

'''高德纳箭头(Knuth's arrow notation, 亦称"上箭头记号")'''，一种满足'''右结合律'''的二元运算。其定义如下：

* <math>a \uparrow b = a^{b}</math>
* <math>a \uparrow^{c} 1 = a</math>
* <math>a \uparrow^{c+1} b+1 = a \uparrow^{c} ( a \uparrow^{c+1} b)</math>

其中，<math>a,c</math>均为'''正整数，'''<math>b</math>为'''自然数'''，<math>a \uparrow^{c} b = a\ \underbrace{ \uparrow\uparrow\cdots\uparrow }_{c}\ b</math>. 

==== 性质 ====

高德纳箭头有如下性质：

===== 右结合律 =====

<math>a \uparrow^{c} b\uparrow^{c} c=a \uparrow^{c} (b\uparrow^{c} c) \neq (a \uparrow^{c} b)\uparrow^{c} c  </math>

若将高德纳箭头的右结合律更替为左结合律，其余定义不变，将得到[[下箭号表示法|下箭头记号]]。

===== 恒等律 =====

<math>2 \uparrow^{c+1} 2 = 2 \uparrow^{c} 2 = 4</math>

<math>1 \uparrow^{c+1} b = 1 \uparrow^{c} b = 1</math>

<math>a \uparrow^{c+1} 0 = a \uparrow^{c} 0 = 1</math>

===== 增长率 =====

高德纳箭头的[[FGH]]增长率为<math>\omega</math>，特别地，

<math>a \uparrow^{c} b \approx f_{c}(b) </math>，

该推论可通过审视以下两组等式得到：

<math>a \uparrow^{c+1} b+1 = a \uparrow^{c} ( a \uparrow^{c+1} b)</math>

<math>f_{c+1}(b+1)=f_{c}^{b+1}(b+1)</math>

===== 超运算 =====

高德纳箭头是目前已被广泛认可、基本采用<ref>曹知秋. 大数理论: Vol.1[EB/OL]. (2025-05-16) [2025-07-02]: 35-36.</ref>的超运算记号。

若定义后继运算的运算等级为<math>0</math>，那么 <math>n</math> 个高德纳箭头的运算等级为 <math>n+2</math>

==== 历史 ====

高德纳箭头是由 <math>\mathrm{Donald\ Ervin\ Knuth}</math> 在1976年发明的大数记号<ref>Donald E. Knuth, ''Mathematics and Computer Science: Coping with Finiteness'', Advances in Our Ability to Compute are Bringing Us Substantially Closer to Ultimate Limitations, Science 194, pp. 1235--1242, 1976.https://cse-robotics.engr.tamu.edu/dshell/cs625/finiteness.pdf</ref>，曾在1977年被 <math> \mathrm{Martin\ Gardner} </math> 用于递归地定义[[葛立恒数]]。<ref>GARDNER M. Mathematical games[J]. Scientific American, 1977, 237(3): 28-38.https://raw.githubusercontent.com/AllenDowney/ModSimPy/master/papers/scientific_american_nov_77.pdf</ref>

而<math>\mathrm{Ronald\ Graham}</math>本人并未在论文中使用高德纳箭头或超运算来估计 [[葛立恒数#葛立恒问题|Graham问题]] 的上界，而是使用了类似 [[ACKERMANN函数]] 的递归函数 <math>F(m,n)</math>，和分别近似为 <math>2 \uparrow\uparrow n,2 \uparrow\uparrow\uparrow n</math> 的函数<math>TOWER(n),WOW(n)</math>。<ref>GRAHAM R L, ROTHSCHILD B L. Ramsey’s theorem for ff-parameter sets[J]. Transactions of the American Mathematical Society, 1971, 159: 257-292. https://www.ams.org/journals/tran/1971-159-00/S0002-9947-1971-0284352-8/S0002-9947-1971-0284352-8.pdf
</ref><ref>GRAHAM R L, ROTHSCHILD B L, SPENCER J H. Ramsey theory: Vol. 20[M]. John
Wiley & Sons, 1991.
 https://people.dm.unipi.it/dinasso/ULTRABIBLIO/Graham_Rothschild_Spencer%20-%20Ramsey%20Theory%20(2nd%20edition).pdf</ref>
==== 形式化定义 ====

<math>n \uparrow m = n^{m}</math>

<math>n \uparrow^{k} m = \underbrace{n \uparrow^{k-1} n \uparrow^{k-1} \cdots \uparrow^{k-1} n }_{\text{m个n}}</math>

该定义可通过以下分析与推理得到：

高德纳箭头本质上是一种高级运算“折叠”低级运算的记号。

后继是最基础的运算，表现为 <math>n+1</math>.

在<math>n+m</math>中，运算 <math>+</math> 折叠了对 <math>n</math> 的 <math>m</math> 次后继运算，即 

 <math>\ n+m=n+\underbrace{1+1+\cdots+1}_{\text{m个1}}</math>.

在<math>n\times m</math>中，运算 <math>\times</math> 折叠了对 <math>n</math> 的 <math>m</math> 次 <math>+</math> 运算，即 

 <math>\ n\times m=\underbrace{n+n+\cdots+n}_{\text{m个n}}</math>.

在 <math>n^{m}</math> ( <math>n\uparrow m</math> ) 中，运算<math>\uparrow</math>折叠了对 <math>n</math> 的 <math>m</math> 次 <math>\times</math> 运算，即 

 <math>\ n^{m}=\underbrace{n\times n\times \cdots \times n}_{\text{m个n}}</math>.

在 <math>{}^m\!n</math> ( <math>n\uparrow \uparrow m</math> ) 中，运算<math>\uparrow \uparrow</math>折叠了对 <math>n</math> 的 <math>m</math> 次 <math>\uparrow</math> 运算，即

 <math>\ n\uparrow \uparrow m=\underbrace{n\uparrow n\uparrow \cdots \uparrow n}_{\text{m个n}}=\underbrace{n^{n^{n^{\cdots}}}}_{\text{m个n}}</math>. （注意是右结合）

以此类推。最终，我们得到了高德纳箭头的形式化定义：

在<math>n \uparrow^{k} m</math>中，运算<math>\uparrow^{k}</math>折叠了对 <math>n</math> 的 <math>m</math> 次 <math>\uparrow^{k-1}</math> 运算，即

 <math>\ n \uparrow^{k} m = \underbrace{n \uparrow^{k-1} n \uparrow^{k-1} \cdots \uparrow^{k-1} n }_{\text{m个n}}</math>
==== 计算示例 ====

<math>\begin{align} 3 \uparrow\uparrow\uparrow 3\  & = 3\uparrow\uparrow3\uparrow\uparrow 3 \\ & = 3\uparrow\uparrow (3\uparrow 3\uparrow 3) \\ & = 3\uparrow\uparrow(3\uparrow27) \\ & = 3\uparrow\uparrow 7625597484987 \\ & = \underbrace{3^{3^{3^{\cdots}}}}_{7625597484987} \end{align}</math>


<math>\begin{align} 3 \uparrow\uparrow\uparrow\uparrow 4\   & = 3\uparrow\uparrow\uparrow3\uparrow\uparrow\uparrow3\uparrow\uparrow\uparrow3 \\ & = 3\uparrow\uparrow\uparrow3\uparrow\uparrow\uparrow\underbrace{3^{3^{3^{\cdots}}}}_{7625597484987} \\ & = 3\uparrow\uparrow\uparrow(\ \underbrace{3\uparrow\uparrow3\uparrow\uparrow\cdots\uparrow\uparrow3}_{\underbrace{3^{3^{3^{\cdots}}}}_{7625597484987}}\ ) \\ & = \underbrace{3\uparrow\uparrow3\uparrow\uparrow\cdots\uparrow\uparrow3}_{\underbrace{3\uparrow\uparrow3\uparrow\uparrow\cdots\uparrow\uparrow3}_{\underbrace{3^{3^{3^{\cdots}}}}_{7625597484987}}}\end{align}</math>
==== 参考资料 ====
<references />
[[分类:记号]]
[[分类:入门]]