打开/关闭搜索
打开/关闭菜单
223
68
64
2725
Googology Wiki
打开/关闭外观设置菜单
打开/关闭个人菜单
未登录
未登录用户的IP地址会在进行任意编辑后公开展示。

高德纳箭头：修订间差异

来自Googology Wiki
更多操作
←上一编辑
可视化wikitext
QWQ-bili​（留言 | 贡献）
监督员、​管理员
146次编辑
小无编辑摘要
Z​（留言 | 贡献）
监督员、​管理员
617次编辑
小无编辑摘要
 
（未显示5个用户的30个中间版本）
第1行： 第1行：
'''高德纳箭头'''（'''Knuth's up-arrow notation''', 亦称"上箭头记号"），一种满足'''右结合律'''的二元运算。其定义如下：
'''高德纳箭头（Knuth's arrow notation，亦称"上箭头记号"）'''，一种满足'''右结合律'''的二元运算。它涉及对运算的递归。<ref>Guy, R. K., & Selfridge, J. L. (1973). The Nesting and Roosting Habits of the Laddered Parenthesis. ''Amer. Math. Monthly'', '''80''', 868-876.</ref>


== 定义 ==
高德纳箭头由如下公式递归定义：
* <math>a \uparrow b = a^{b}</math>
* <math>a \uparrow b = a^{b}</math>
* <math>a \uparrow^{c} 1 = a</math>
* <math>a \uparrow^{c} 0 = 1</math>
* <math>a \uparrow^{c+1} b+1 = a \uparrow^{c} ( a \uparrow^{c+1} b)</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,c</math> 均为'''正整数，'''<math>b</math> 为'''自然数'''，<math>a \uparrow^{c} b = a\ \underbrace{ \uparrow\uparrow\cdots\uparrow }_{c}\ b</math>。


==== 性质 ====
在计算高德纳箭头时，如无括号，按照从右往左的顺序计算，即：


<math>a \uparrow^{m} b\uparrow^{n} c=a \uparrow^{m} (b\uparrow^{n} c)</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>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^c2=.. .=2\uparrow2=4</math>
* <math>a \uparrow^{c+1} 1 = a \uparrow^{c}a\uparrow^{c+1}0 =a\uparrow^{c} 1=...=a\uparrow1=a</math>
* <math>1 \uparrow^{c+1} b+1 = 1\uparrow^c(1\uparrow^{c+1} b)=1\uparrow^c(1\uparrow^c(\cdots\uparrow^c(1\uparrow^{c}1)))=1\uparrow^{c} 1=1</math>


===== 恒等律 =====
==== 增长率 ====
高德纳箭头的 [[增长层级#快速增长层级|FGH]] 增长率为 <math>\omega</math>，特别地，<math>a \uparrow^{c} b \approx f_{c+1}(b) </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} (b+1) = a \uparrow^{c} ( a \uparrow^{c+1} b)</math>
* <math>f_{c+1}(b+1)=f_{c}^{b+1}(b+1)=f_{c}(f_{c}^{b}(b+1))</math>


<math>a \uparrow^{c+1} 0 = a \uparrow^{c} 0 = 1</math>
==== 超运算 ====
高德纳箭头是目前已被广泛认可、基本采用的[[超运算|超运算记号]]。


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


高德纳箭头的[[FGH]]增长率为 '''ω'''，特别地，
== 历史 ==
高德纳箭头是由 Donald Ervin Knuth 在 1976 年发明的大数记号<ref>Knuth, D. E. (1976). 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. https://cse-robotics.engr.tamu.edu/dshell/cs625/finiteness.pdf</ref>，曾在 1977 年被 Martin Gardner 用于递归地定义[[葛立恒数]]。<ref>Gardner, M. (1977). 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>a \uparrow^{c} b \approx f_{c}(b) </math>，
而<math>\mathrm{Ronald\ Graham}</math>本人并未在论文中使用高德纳箭头或超运算来估计 [[葛立恒数#葛立恒问题|葛立恒问题]] 的上界，而是使用了类似 [[阿克曼函数]] 的递归函数 <math>F(m,n)</math>，和分别近似为 <math>2 \uparrow\uparrow n,2 \uparrow\uparrow\uparrow n</math> 的函数 <math>\rm TOWER(n),WOW(n)</math>。<ref>Graham, R. L., & Rothschild, B. L. (1971). Ramsey’s theorem for $n$-parameter sets[J]. ''Transactions of the American Mathematical Society'', 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. (1991). Ramsey theory: Vol. 20[M]. ''John Wiley & Sons''. https://people.dm.unipi.it/dinasso/ULTRABIBLIO/Graham_Rothschild_Spencer%20-%20Ramsey%20Theory%20(2nd%20edition).pdf</ref>


该推论可通过审视以下两组等式得到：
== 构造过程 ==
高德纳箭头本质上是一种高级运算“折叠”低级运算的记号。


<math>a \uparrow^{c+1} b+1 = a \uparrow^{c} ( a \uparrow^{c+1} b)</math>
现在让我们回到数学的起点，并考察各种级别的运算是如何逐渐地建立起来的。这将进一步地启发我们构造增长率更快的计数法。


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


===== 超运算 =====
为了使某数 n 变大，最简单的运算应该就是“数出 n 这个数后面的一个数”。我们将这种运算称为'''“后继”'''。后继是最基础的运算，表现为 n+1.


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


若定义后继运算的运算等级为<math>0</math>，那么 <math>n</math> 个高德纳箭头的运算等级为 <math>n+2</math>
我们经常需要表示一种“从 n 开始，取 m 次后继”这样的运算。写得次数太多了之后，我们就引入了一个新的运算符 +，将这样的运算称为'''“加法”'''，表示为 n+m.


==== 历史 ====
在 n+m 中，运算 + 折叠了对 n 的 m 次后继运算，即
<math>\ n+m=n+\underbrace{1+1+\cdots+1}_{\text{m个1}}.</math>


高德纳箭头是由 <math>\mathrm{Donald\ Ervin\ Knuth}</math> 在1976年发明的大数记号，曾被 <math> \mathrm{Ronald\ Graham} </math> 用于递归地定义[[葛立恒数]]。
==== 乘法 ====
==== 形式化定义 ====


<math>n \uparrow m = n^{m}</math>
还能不能更快些呢？假设我们已经通过某些操作得到了 n，那么要想最快地得到一些更大的数，我们就要将 n 加上自身，并将这个过程重复若干次。我们引入一个新的运算符 <math>\times</math>，将这样的运算称为'''“乘法”'''，表示为 <math>n\times 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\times m</math> 中，运算 <math>\times</math> 折叠了对 n 的 m 次 + 运算，即
<math>\ n\times m=\underbrace{n+n+\cdots+n}_{\text{m个n}}.</math>
 
==== 乘方 ====
 
对乘法重复若干次，我们就可以得到一个增长更快的运算。仿照之前的过程，我们进一步引入一个新的运算符 <math>\uparrow</math>，将这一运算称为'''“乘方”'''，表示为 <math>n\uparrow m</math> 或 <math>n^{m}</math>.
 
在 <math>n^{m}</math> ( <math>n\uparrow m</math> ) 中，运算 <math>\uparrow</math> 折叠了对 n 的 m 次 <math>\times</math> 运算，即


该定义可通过以下分析与推理得到：
<math>\ n^{m}=\underbrace{n\times n\times \cdots \times n}_{\text{m个n}}.</math>


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


后继是最基础的运算，表现为 <math>n+1</math>.
我们已经看到了上述各个运算的推广过程：最简单的运算是后继；将后继重复若干次可以得到一个增长更快的运算，称为加法；将加法重复若干次可以再次得到一个增长更快的运算，称为乘法；进一步地将乘法重复若干次，我们又可以得到一个增长速度更快的运算，称为乘方。这里面的每一个运算的增长速度都远远超过了此前的所有运算。


在<math>n+m</math>中，运算 <math>+</math> 折叠了对 <math>n</math> 的 <math>m</math> 次后继运算，即
现在如果我们想要得到一个增长速度超越乘方的运算，那么应该如何做呢？答案已经很简单了：我们只需要将乘方运算（单箭头运算 <math>\uparrow </math>）重复若干次，并将其定义为一个新的运算'''“幂塔”'''即可。我们将这一运算的运算符用双箭头 <math>\uparrow \uparrow</math> 来进行表示。


<math>n+m=n+\underbrace{1+1+\cdots+1}_{\text{m个1}}</math>.
在 <math>{}^m\!n</math> ( <math>n\uparrow \uparrow m</math> ) 中，运算 <math>\uparrow \uparrow</math> 折叠了对 n 的 m 次 <math>\uparrow</math> 运算，即


在<math>n\times m</math>中，运算 <math>\times</math> 折叠了对 <math>n</math> 的 <math>m</math> 次 <math>+</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\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^{k} m</math> 中，运算 <math>\uparrow^{k}</math> 折叠了对 n 的 m 次 <math>\uparrow^{k-1}</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 = \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>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\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 />
<references />{{默认排序:大数记号}}
[[分类:记号]]
[[分类:记号]]
[[分类:入门]]
[[分类:入门]]

2025年8月20日 (三) 16:27的最新版本

高德纳箭头（Knuth's arrow notation，亦称"上箭头记号"），一种满足右结合律的二元运算。它涉及对运算的递归。[1]

定义

高德纳箭头由如下公式递归定义：

  • a↑b=ab
  • a↑c0=1
  • a↑c+1(b+1)=a↑c(a↑c+1b)

其中，a,c 均为正整数，b 为自然数，a↑cb=a ↑↑⋯↑⏟c b。

在计算高德纳箭头时，如无括号，按照从右往左的顺序计算，即：

a↑mb↑nc=a↑m(b↑nc)

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

性质

高德纳箭头有如下性质：

展开

n↑km=n↑k−1n↑k−1⋯↑k−1n⏟m个n

恒等律

  • 2↑c+12=2↑c2=...=2↑2=4
  • a↑c+11=a↑ca↑c+10=a↑c1=...=a↑1=a
  • 1↑c+1b+1=1↑c(1↑c+1b)=1↑c(1↑c(⋯↑c(1↑c1)))=1↑c1=1

增长率

高德纳箭头的 FGH 增长率为 ω，特别地，a↑cb≈fc+1(b)。

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

  • a↑c+1(b+1)=a↑c(a↑c+1b)
  • fc+1(b+1)=fcb+1(b+1)=fc(fcb(b+1))

超运算

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

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

历史

高德纳箭头是由 Donald Ervin Knuth 在 1976 年发明的大数记号[2]，曾在 1977 年被 Martin Gardner 用于递归地定义葛立恒数。[3]

而Ronald Graham本人并未在论文中使用高德纳箭头或超运算来估计 葛立恒问题 的上界，而是使用了类似 阿克曼函数 的递归函数 F(m,n)，和分别近似为 2↑↑n,2↑↑↑n 的函数 TOWER(n),WOW(n)。[4][5]

构造过程

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

现在让我们回到数学的起点，并考察各种级别的运算是如何逐渐地建立起来的。这将进一步地启发我们构造增长率更快的计数法。

后继

为了使某数 n 变大，最简单的运算应该就是“数出 n 这个数后面的一个数”。我们将这种运算称为“后继”。后继是最基础的运算，表现为 n+1.

加法

我们经常需要表示一种“从 n 开始，取 m 次后继”这样的运算。写得次数太多了之后，我们就引入了一个新的运算符 +，将这样的运算称为“加法”，表示为 n+m.

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

 n+m=n+1+1+⋯+1⏟m个1.

乘法

还能不能更快些呢？假设我们已经通过某些操作得到了 n，那么要想最快地得到一些更大的数，我们就要将 n 加上自身，并将这个过程重复若干次。我们引入一个新的运算符 ×，将这样的运算称为“乘法”，表示为 n×m.

在 n×m 中，运算 × 折叠了对 n 的 m 次 + 运算，即 

 n×m=n+n+⋯+n⏟m个n.

乘方

对乘法重复若干次，我们就可以得到一个增长更快的运算。仿照之前的过程，我们进一步引入一个新的运算符 ↑，将这一运算称为“乘方”，表示为 n↑m 或 nm.

在 nm ( n↑m ) 中，运算 ↑ 折叠了对 n 的 m 次 × 运算，即 

 nm=n×n×⋯×n⏟m个n.

幂塔

我们已经看到了上述各个运算的推广过程：最简单的运算是后继；将后继重复若干次可以得到一个增长更快的运算，称为加法；将加法重复若干次可以再次得到一个增长更快的运算，称为乘法；进一步地将乘法重复若干次，我们又可以得到一个增长速度更快的运算，称为乘方。这里面的每一个运算的增长速度都远远超过了此前的所有运算。

现在如果我们想要得到一个增长速度超越乘方的运算，那么应该如何做呢？答案已经很简单了：我们只需要将乘方运算（单箭头运算 ↑）重复若干次，并将其定义为一个新的运算“幂塔”即可。我们将这一运算的运算符用双箭头 ↑↑ 来进行表示。

在 mn ( n↑↑m ) 中，运算 ↑↑ 折叠了对 n 的 m 次 ↑ 运算，即 

 n↑↑m=n↑n↑⋯↑n⏟m个n=nnn⋯⏟m个n. （注意是右结合）

高德纳箭头

仿照上述定义，以此类推。

最终，我们得到了高德纳箭头的展开定义：

在 n↑km 中，运算 ↑k 折叠了对 n 的 m 次 ↑k−1 运算，即 

 n↑km=n↑k−1n↑k−1⋯↑k−1n⏟m个n.

计算示例

3↑↑↑3 =3↑↑3↑↑3=3↑↑(3↑3↑3)=3↑↑(3↑27)=3↑↑7625597484987=333⋯⏟7625597484987


3↑↑↑↑4 =3↑↑↑3↑↑↑3↑↑↑3=3↑↑↑3↑↑↑333⋯⏟7625597484987=3↑↑↑( 3↑↑3↑↑⋯↑↑3⏟333⋯⏟7625597484987 )=3↑↑3↑↑⋯↑↑3⏟3↑↑3↑↑⋯↑↑3⏟333⋯⏟7625597484987

参考资料

  1. ↑ Guy, R. K., & Selfridge, J. L. (1973). The Nesting and Roosting Habits of the Laddered Parenthesis. Amer. Math. Monthly, 80, 868-876.
  2. ↑ Knuth, D. E. (1976). 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. https://cse-robotics.engr.tamu.edu/dshell/cs625/finiteness.pdf
  3. ↑ Gardner, M. (1977). Mathematical games[J]. Scientific American, 1977, 237(3): 28-38. https://raw.githubusercontent.com/AllenDowney/ModSimPy/master/papers/scientific_american_nov_77.pdf
  4. ↑ Graham, R. L., & Rothschild, B. L. (1971). Ramsey’s theorem for $n$-parameter sets[J]. Transactions of the American Mathematical Society, 159: 257-292. https://www.ams.org/journals/tran/1971-159-00/S0002-9947-1971-0284352-8/S0002-9947-1971-0284352-8.pdf
  5. ↑ Graham, R. L., & Rothschild, B. L., & Spencer, J. H. (1991). Ramsey theory: Vol. 20[M]. John Wiley & Sons. https://people.dm.unipi.it/dinasso/ULTRABIBLIO/Graham_Rothschild_Spencer%20-%20Ramsey%20Theory%20(2nd%20edition).pdf
检索自“http://wiki.googology.top/index.php?title=高德纳箭头&oldid=2149”