高德纳箭头：修订间差异

←上一编辑下一编辑→

可视化wikitext

2025年6月29日 (日) 18:01的版本

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

$a ↑ b = a^{b}$
$a ↑^{c} 1 = a$
$a ↑^{c + 1} b + 1 = a ↑^{c} (a ↑^{c + 1} b)$

其中， $a, b, c$ 均为正整数， $a ↑^{c} b = a \underset{c}{\underset{⏟}{↑ ↑ \dots ↑}} b$ .

性质

高德纳箭头有如下性质：

右结合律

$a ↑^{c} b ↑^{c} c = a ↑^{c} (b ↑^{c} c) \neq (a ↑^{c} b) ↑^{c} c$

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

恒等律

$2 ↑^{c + 1} 2 = 2 ↑^{c} 2 = 4$

$1 ↑^{c + 1} b = 1 ↑^{c} b = 1$

$a ↑^{c + 1} 0 = a ↑^{c} 0 = 1$

增长率

高德纳箭头的FGH增长率为 ω，特别地，

$a ↑^{c} b \approx f_{c} (b)$ ，

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

$a ↑^{c + 1} b + 1 = a ↑^{c} (a ↑^{c + 1} b)$

$f_{c + 1} (b + 1) = f_{c} (f_{c + 1} (b))$

超运算

高德纳箭头是目前已被广泛认可、基本采用^[1]的超运算记号。

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

历史

高德纳箭头是由 $D o n a l d E r v i n K n u t h$ 在1976年发明的大数记号，曾被 $R o n a l d G r a h a m$ 用于递归地定义葛立恒数。

形式化定义

$n ↑ m = n^{m}$

$n ↑^{k} m = \underset{m个n}{\underset{⏟}{n ↑^{k - 1} n ↑^{k - 1} \dots ↑^{k - 1} n}}$

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

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

后继是最基础的运算，表现为 $n + 1$ .

在 $n + m$ 中，运算 $+$ 折叠了对 $n$ 的 $m$ 次后继运算，即

 $n + m = n + \underset{m个1}{\underset{⏟}{1 + 1 + \dots + 1}}$ .

在 $n \times m$ 中，运算 $\times$ 折叠了对 $n$ 的 $m$ 次 $+$ 运算，即

 $n \times m = \underset{m个n}{\underset{⏟}{n + n + \dots + n}}$ .

在 $n^{m}$ ( $n ↑ m$ ) 中，运算 $↑$ 折叠了对 $n$ 的 $m$ 次 $\times$ 运算，即

 $n^{m} = \underset{m个n}{\underset{⏟}{n \times n \times \dots \times n}}$ .

在 $^{m} n$ ( $n ↑ ↑ m$ ) 中，运算 $↑ ↑$ 折叠了对 $n$ 的 $m$ 次 $↑$ 运算，即

 $n ↑ ↑ m = \underset{m个n}{\underset{⏟}{n ↑ n ↑ \dots ↑ n}} = \underset{m个n}{\underset{⏟}{n^{n^{n^{\dots}}}}}$ . （注意是右结合）

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

在 $n ↑^{k} m$ 中，运算 $↑^{k}$ 折叠了对 $n$ 的 $m$ 次 $↑^{k - 1}$ 运算，即

 $n ↑^{k} m = \underset{m个n}{\underset{⏟}{n ↑^{k - 1} n ↑^{k - 1} \dots ↑^{k - 1} n}}$

参考资料

↑ 曹知秋. 大数理论[EB/OL]. 2024, [2025-05-16](1): 35-36. https://github.com/ZhiqiuCao/Googology

[1] 曹知秋. 大数理论[EB/OL]. 2024, [2025-05-16](1): 35-36. https://github.com/ZhiqiuCao/Googology

[1]

@@ 第22行： / 第22行： @@
 <math>1 \uparrow^{c+1} b = 1 \uparrow^{c} b = 1</math>
+<math>a \uparrow^{c+1} 0 = a \uparrow^{c} 0 = 1</math>
 ===== 增长率 =====
@@ 第48行： / 第50行： @@
 <math>n \uparrow m = n^{m}</math>
-<math>n \uparrow^{c} m = \underbrace{n \uparrow^{c-1} n \uparrow^{c-1} \cdots \uparrow^{c-1} n }_{\text{m个n}}</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>
 ==== 参考资料 ====